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