字典树模板+位运算

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;
}