P3879 [TJOI2010] 阅读理解 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
trie树板子题,稍微有一丢丢不一样,套用字典树模板稍加修改就能过
手搓字典树代码:
char ch[1010][26], cnt[1010], idx;
void insert(string s)//插入
{
int p = 0;
for (int i = 1; s[i]; i++)
{
int j = s[i] - 'a';
if (!ch[p][j])
{
ch[p][j] = ++idx;
}
p = ch[p][j];
}
cnt[p]++;
}
int query(string s)//查询
{
int p = 0;
for (int i = 1; s[i]; i++)
{
int j = s[i] - 'a';
if (!ch[p][j])
{
return 0;
}
p = ch[p][j];
}
return cnt[p];
}
题解代码:
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
using namespace std;
typedef long long ll;
char s[50010];
char ch[500010][26], idx;
char w[500010][1010];
int n, m;
inline int read()
{
int k = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch>'9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
k = k * 10 + ch - '0';
ch = getchar();
}
return k * f;
}
void insert(int x)
{
scanf("%s", s + 1);
int l = strlen(s + 1);
int p = 0;
for (int i = 1; i<=l; i++)
{
int j = s[i] - 'a';
if (!ch[p][j])
{
ch[p][j] = idx++;
}
p = ch[p][j];
}
w[p][x] = 1;
}
void check()
{
scanf("%s", s + 1);
int l = strlen(s + 1);
int p = 0;
int flag = 1;
for (int i = 1; i<=l; i++)
{
int j = s[i] - 'a';
if (!ch[p][j])
{
flag = 0;
break;
}
p = ch[p][j];
}
if (flag)
{
for (int i = 1; i <= n; i++)
{
if (w[p][i])
{
cout << i << " ";
}
}
cout << endl;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
n = read();
for (int i = 1; i <= n; i++)
{
int x = read();
for (int j = 1; j <= x; j++)
{
insert(i);
}
}
m = read();
for (int i = 1; i <= m; i++)
{
check();
}
return 0;
}
位运算:
左移:
1<<n=2^n,n<<1=2n
右移:
n>>1=n/2
取出n在二进制下的第k位:(n>>k)&1
取出n在二进制下的第0~k-1位(后k位):n&((1<<k)-1)
把n在二进制下的第k位取反:n xor(1<<k)
对n在二进制下的第k位赋值1:n|(1<<k)
对n在二进制下的第k位赋值0:n&(~(1<<k))
来两道位运算的题目练练手(算法竞赛进阶指南)
P1226 【模板】快速幂 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:
解决这道题有两种方法:
1.分治思想:n为偶数时把2^n分成a^(n/2),n为奇数时分为a^(n/2)*a
2.倍增思想:稍微有一点难理解(
从头开始。若当前 p 为偶数,咱们不着急,只需把 x 自乘,然后 p/=2 (即考虑下一层,下几层会帮我们乘上 (x2)p/2的)。
若当前 p 为奇数,说明 p=x∗(x2)(p−1)/2 中前面那个 x 的存在,ans∗=x。然后继续考虑下一层(下几层会帮我们乘上(x2)(p−1)/2的)
)
代码1(分治):
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{
int k = 0, f = 1; char ch = getchar();
while (ch < '0' || ch>'9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
k = k * 10 + ch - '0';
ch = getchar();
}
return k * f;
}
int solve(ll a, ll b, ll p)
{
if (b == 0)
return 1;
ll ans = solve(a, b / 2, p) % p;
if (b % 2 == 0)
{
return ans * ans % p;
}
else
{
return ans * ans % p * a % p;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll a, b, p;
cin >> a >> b >> p;
cout << a << "^" << b << " mod " << p << "=" << solve(a, b, p) << endl;
return 0;
}
代码2(倍增):
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{
int k = 0, f = 1; char ch = getchar();
while (ch < '0' || ch>'9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
k = k * 10 + ch - '0';
ch = getchar();
}
return k * f;
}
void solve(ll x, ll y, ll p)
{
ll ans = 1 % p;
for (; y; y >>= 1)
{
if (y & 1)
{
ans = ans * x % p;
}
x = x * x % p;
}
cout << x << "^" << y << " mod " << p << "=" << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll a, b, p;
cin >> a >> b >> p;
solve(a, b, p);
return 0;
}
P10446 64位整数乘法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
代码:
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{
int k = 0, f = 1; char ch = getchar();
while (ch < '0' || ch>'9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
k = k * 10 + ch - '0';
ch = getchar();
}
return k * f;
}
void solve(ll x, ll y, ll z)
{
ll ans = 0;
for (; y; y >>= 1)
{
if (y & 1)
ans = (ans + x) % 5;
x = (x * 2) % z;
}
cout << ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll a, b, p;
cin >> a >> b >> p;
solve(a, b, p);
return 0;
}