duipai.cpp
//freopen("in.txt", "r", stdin); // 读入数据生成器造出来的数据 //freopen("std.txt", "w", stdout); // 输出答案 #include <bits/stdc++.h> using namespace std; int main() { while (1) // 一直循环，直到找到不一样的数据 { system("gen.exe"); system("tle.exe"); system("std.exe"); if (system("fc std.txt tle.txt")) // 当 fc 返回 1 时，说明这时数据不一样 break; // 不一样就跳出循环 } return 0; }
对拍脚本
g++ -o tle tle.cpp g++ -o std std.cpp g++ -o gen gen.cpp g++ -o duipai duipai.cpp duipai
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define int long long const int M = 3e5 + 5, mod = 998244353; int a[M]; struct dian { int l, r, lw, rw, sum; // lw表示左边连续的1的个数 // rw表示右边连续的1的个数 // sum表示区间每段连续1除2向上取整的和 } f[M << 2]; dian merge(dian x, dian y) { int c1 = x.lw, c2 = x.rw; int c3 = y.lw, c4 = y.rw; int flag1 = 0, flag2 = 0; if (c1 == x.r - x.l + 1) flag1 = 1; if (c3 == y.r - y.l + 1) flag2 = 1; int id = 0; dian ans; ans.l = x.l; ans.r = y.r; // 如果左子树全为1，右子树不为1，则将左边连续的1的个数加到右子树的左边 if (flag1 == 1 && flag2 == 0) { ans.lw = c1 + c3; ans.rw = c4; ans.sum = (c1 + c3 + 1) / 2 - (c3 + 1) / 2 + y.sum; return ans; } if (flag1 == 0 && flag2 == 1) { ans.lw = c1; ans.rw = c2 + c4; ans.sum = (c2 + c4 + 1) / 2 - (c2 + 1) / 2 + x.sum; return ans; } if (flag1 == 0 && flag2 == 0) { ans.lw = c1; ans.rw = c4; ans.sum = x.sum + y.sum - (c2 + 1) / 2 - (c3 + 1) / 2 + (c2 + c3 + 1) / 2; return ans; } ans.lw = c1 + c3; ans.rw = c2 + c4; ans.sum = (c1 + c3 + 1) / 2; return ans; } void pushup(int id) { f[id] = merge(f[id << 1], f[id << 1 | 1]); } void build(int id, int l, int r) { f[id].l = l, f[id].r = r; if (l == r) { f[id].lw = f[id].rw = a[l]; f[id].sum = a[l]; return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); pushup(id); } dian query(int id, int l, int r) { if (l <= f[id].l && f[id].r <= r) return f[id]; int mid = (f[id].l + f[id].r) >> 1; if (r <= mid) return query(id << 1, l, r); if (l > mid) return query(id << 1 | 1, l, r); dian x = query(id << 1, l, r); dian y = query(id << 1 | 1, l, r); return merge(x, y); } void solve() { int n, q; cin >> n >> q; string s; cin >> s; vector<int> sum(n + 2); for (int i = 1; i <= n; i++) { a[i] = s[i - 1] - '0'; sum[i] = sum[i - 1] + (a[i] == 0); } build(1, 1, n); while (q--) { int l, r; cin >> l >> r; dian ans = query(1, l, r); cout << ans.sum + (sum[r] - sum[l - 1]) << endl; } } signed main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int t = 1; // cin >> t; while (t--) solve(); return 0; }
https://www.luogu.com.cn/problem/P3370
#include <bits/stdc++.h> using namespace std; const int base1 = 29, base2 = 131, M = 2e5 + 5, mod1 = 1e9 + 7, mod2 = 1e9 + 9; int hash1[M], hash2[M], pow1[M], pow2[M]; string s; struct Hash { public: void init(string s) { // 下标从1开始 hash1[0] = hash2[0] = 0; pow1[0] = pow2[0] = 1; int n = s.size(); for (int i = 1; i <= n; ++i) { pow1[i] = pow1[i - 1] * base1 % mod1; pow2[i] = pow2[i - 1] * base2 % mod2; } for (int i = 1; i <= n; ++i) { hash1[i] = (hash1[i - 1] * base1 + s[i]) % mod1; hash2[i] = (hash2[i - 1] * base2 + s[i]) % mod2; } } pair<int, int> gethash(string s, int l, int r) { return {(hash1[r] - hash1[l - 1] * pow1[r - l + 1] % mod1 + mod1) % mod1, (hash2[r] - hash2[l - 1] * pow2[r - l + 1] % mod2 + mod2) % mod2}; } }; int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int t; cin >> t; set<pair<int, int>> f; while (t--) { cin >> s; s = " " + s; int n = s.size(); Hash h; h.init(s); f.insert(h.gethash(s, 1, n - 1)); } cout << f.size(); return 0; }
#include <bits/stdc++.h> using namespace std; #define int long long const int M = 1e5 + 5; int dp[M][22]; signed main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n, t; cin >> n >> t; for (int i = 1; i <= n; i++) cin >> dp[i][0]; for (int j = 1; j <= 22; j++) { for (int i = 1; i + (1 << j) - 1 <= n; i++) dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]); } while (t--) { int x, y; cin >> x >> y; int k = log2(y - x + 1); cout << max(dp[x][k], dp[y - (1 << k) + 1][k]) << "\n"; } return 0; }
https://www.luogu.com.cn/problem/P3383
#include <bits/stdc++.h> using namespace std; const int M = 1e8 + 10; int a[100000010], k = 0; bool f[100000010]; void fun(int n) { for (int i = 2; i <= n; i++) { if (f[i] == 0) a[++k] = i; for (int j = 1; j <= k && i * a[j] <= n; j ++) { f[i * a[j]] = 1; if (i % a[j] == 0) break; } } } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int t, n, x; cin >> n >> t; fun(n); while (t--) { cin >> x; cout << a[x] << "\n"; } return 0; }
