// B: 选数概率 #include<bits/stdc++.h> #pragma GCC optimize(2) #define int long long #define endl '\n' usingnamespace std; constint MAX = 2e5+5;
voidsolve(){ constint f1 = 2585, f2 = 2632, f3 = 1540, m = 10455; // p12=f1/m, p23=f2/m, p13=f3/m int s = 1; while (true) { s++; if (s * (s - 1) % m) continue; constint k = s * (s - 1) / m; for (int a = 1; a < s; a++) { for (int b = 1; b < s - a; b++) { int c = s - a - b; if (2 * a * b == f1 * k and2 * b * c == f2 * k and2 * a * c == f3 * k) { cout << a << ',' << b << ',' << c << endl; return; } } } } }
// C: 蚂蚁开会 #include<bits/stdc++.h> #pragma GCC optimize(2) #define int long long #define endl '\n' usingnamespace std; constint MAX = 2e5+5;
voidsolve(){ map<pair<int, int>, int> M; int n; cin >> n; for (int i = 0; i < n; i++) { int x, y, xx, yy; cin >> x >> y >> xx >> yy; constint g = __gcd(abs(xx - x), abs(yy - y)); constint a = (xx - x) / g, b = (yy - y) / g; int nx = x, ny = y; while (nx != xx or ny != yy) { M[{nx, ny}]++; nx += a; ny += b; } M[{nx, ny}]++; } int cnt = 0; for (constauto &p : M) if (p.second >= 2) cnt++; cout << cnt << endl; }
// D: 立定跳远 #include<bits/stdc++.h> #pragma GCC optimize(2) #define int long long #define endl '\n' usingnamespace std; constint MAX = 2e5+5;
int n, m; int a[MAX];
boolcheck(int x){ int cnt = 0, pre = 0; for (int i = 0; i < n; i++) { cnt += max<int>((a[i] - pre + x - 1) / x - 1, 0); pre = a[i]; } return cnt <= m + 1; }
voidsolve(){ cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; }
int l = 1, r = 1e8; while (l <= r) { int mid = (l + r) / 2; if (check(mid)) { r = mid - 1; } else { l = mid + 1; } } cout << l << endl; }
// E: 最小字符串 #include<bits/stdc++.h> #pragma GCC optimize(2) #define int long long #define endl '\n' usingnamespace std; constint MAX = 2e5+5;
voidsolve(){ int n, m; cin >> n >> m; string s, t; cin >> s >> t; sort(t.begin(), t.end());
int i = 0, j = 0; string res; while (i < n or j < m) { if (j == m or i < n and s[i] <= t[j]) { // s[i] < t[j] 是错误的 res += s[i++]; } else { res += t[j++]; } }
// 数星星 #include<bits/stdc++.h> #pragma GCC optimize(2) #define int long long #define endl '\n' usingnamespace std; constint MAX = 2e5+5; constint MOD = 1e9+7;
inlineintquick_pow(int b, int e){ int res = 1; while (e) { if (e & 1) res = res * b % MOD; b = b * b % MOD; e >>= 1; } return res; } inlineintinv(int x){ returnquick_pow(x, MOD - 2); }
int fac[MAX]; int inf[MAX]; voidload_C(int n){ fac[0] = 1; inf[0] = 1; for (int i = 1; i <= n; i++) { fac[i] = fac[i - 1] * i % MOD; inf[i] = inf[i - 1] * inv(i) % MOD; } } inlineintC(int n, int m){ if (m < 0or m > n) return0; return fac[n] * inf[m] % MOD * inf[n - m] % MOD; }
int deg[MAX];
voidsolve(){ int n; cin >> n; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; deg[u]++; deg[v]++; } int l, r; cin >> l >> r; l--, r--; int res = 0; for (int x = 1; x <= n; x++) { for (int i = l; i <= r; i++) { res += C(deg[x], i); } } cout << res << endl; }
// H: 套手镯 #include<bits/stdc++.h> #pragma GCC optimize(2) #define int long long #define endl '\n' usingnamespace std; constint MAX = 1e3+5;
int n, w, h; structCircle { int x, y, r; } c[MAX];
intwork(){ int res = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int cnt = 0; int sx = c[i].x - c[i].r, sy = c[j].y - c[j].r; int ex = sx + w, ey = sy + h; for (int k = 0; k < n; k++) { if (sx <= c[k].x - c[k].r and c[k].x + c[k].r <= ex and sy <= c[k].y - c[k].r and c[k].y + c[k].r <= ey) { cnt++; } } res = max(res, cnt); } } return res; }
voidsolve(){ cin >> n >> w >> h; for (int i = 0; i < n; i++) { cin >> c[i].x >> c[i].y >> c[i].r; }
int res = work(); swap(w, h); res = max(res, work());
首先我们可以将数据离散化处理。然后对于 x 轴使用双指针维护在区间 [l,r] 内 x 坐标合法索引,使用 vis 数组标记,注意这时候只保证区间 x 的最大最小值差(极差) 小于等于 w,但并未保证任何 y。对于上面的每个状态,再次使用双指针 [l′,r′] 维护在 y 坐标上的合法索引,只是此时忽略无 vis 标记的索引,因此此时区间维护的合法索引同时满足 x 和 y 的约束,此时得到的就是一种情况的计数,求它们的最大值即可。
// H: 套手镯 #include<bits/stdc++.h> // #pragma GCC optimize(2) #define int long long #define endl '\n' usingnamespace std; constint MAX = 2e3+5;
int n, w, h; structCircle { int x, y, r; } c[MAX];
pair<int, int> Mx[MAX]; // {value, index} int cntMx = 0; pair<int, int> My[MAX]; // {value, index} int cntMy = 0;
int res = 0; bool vis[MAX];
voidworkY(){ int cnt = 0; int r = 0, ri = My[r].second; for (int l = 0; l < cntMy; l++) { if (l == 0or My[l - 1].first < My[l].first) { while (r < cntMy and My[r].first <= My[l].first + h) { if (vis[ri] and My[r].first > c[ri].y and My[l].first <= c[ri].y - c[ri].r and c[ri].y + c[ri].r <= My[l].first + h) { cnt++; } r++, ri = My[r].second; } res = max(res, cnt); } int li = My[l].second; if (vis[li] and My[l].first < c[li].y and My[l].first <= c[li].y - c[li].r and c[li].y + c[li].r <= My[l].first + h) { cnt--; } } }
voidworkX(){ int r = 0, ri = Mx[r].second; for (int l = 0; l < cntMx; l++) { if (l == 0or Mx[l - 1].first < Mx[l].first) { while (r < cntMx and Mx[r].first <= Mx[l].first + w) { if (Mx[r].first > c[ri].x and Mx[l].first <= c[ri].x - c[ri].r and c[ri].x + c[ri].r <= Mx[l].first + w) { vis[ri] = true; } r++, ri = Mx[r].second; } workY(); } int li = Mx[l].second; if (Mx[l].first < c[li].x and Mx[l].first <= c[li].x - c[li].r and c[li].x + c[li].r <= Mx[l].first + w) { vis[li] = false; } } }
voidsolve(){ cin >> n >> w >> h; for (int i = 0; i < n; i++) { cin >> c[i].x >> c[i].y >> c[i].r; Mx[cntMx++] = {c[i].x - c[i].r, i}; Mx[cntMx++] = {c[i].x + c[i].r, i}; My[cntMy++] = {c[i].y - c[i].r, i}; My[cntMy++] = {c[i].y + c[i].r, i}; } sort(Mx, Mx + cntMx); sort(My, My + cntMy);
// I: 跳石头 #include<bits/stdc++.h> #pragma GCC optimize(2) #define int long long #define endl '\n' usingnamespace std; constint MAX = 4e4+5;
int c[MAX]; bitset<MAX> bits[MAX];
voidsolve(){ int n; cin >> n; for (int i = 1; i <= n; i++) cin >> c[i];
int res = 0; for (int i = n; i >= 1; i--) { bits[i][c[i]] = 1; if (i * 2 <= n) bits[i] |= bits[i * 2]; if (i + c[i] <= n) bits[i] |= bits[i + c[i]]; res = max<int>(res, bits[i].count()); } cout << res << endl; }
template <bool reverse = false> inline HashCode hash_sub(int l, int r) { if (reverse) { int s1 = mm2(g1[l + 1] - g1[r + 2] * p1[r - l + 1], M1); int s2 = mm2(g2[l + 1] - g2[r + 2] * p2[r - l + 1], M2); return s1 << 32 | s2; } int s1 = mm2(h1[r + 1] - h1[l] * p1[r - l + 1], M1); int s2 = mm2(h2[r + 1] - h2[l] * p2[r - l + 1], M2); return s1 << 32 | s2; }
intwork(constchar *s, int n){ int i = 0, j = n - 1; while (i < j and s[i] == s[j]) i++, j--;
int res = 0; hash_it(s, n); for (int k = i; k <= j; k++) { int l = 1, r = (j - k + 1) / 2; while (l <= r) { int m = (l + r) / 2; if (hash_sub(k, k + m - 1) == hash_sub<true>(j - m + 1, j)) { l = m + 1; } else { r = m - 1; } } res = max(res, i + r); }
return res; }
voidsolve(){ string s; cin >> s; constint n = s.size();
int res = work(s.c_str(), n); reverse(s.begin(), s.end()); res = max(res, work(s.c_str(), n));