voidcheck(int m, int d){ if (m < 1 || m > 12 || d < 1 || d > days[m]) return; res.insert(m * 100 + d); }
intmain(){ int ns[100]; for (int & n : ns) cin >> n; for (int a = 0; a < 100; a ++) { if (ns[a] != 2) continue; for (int b = a + 1; b < 100; b ++) { if (ns[b] != 0) continue; for (int c = b + 1; c < 100; c ++) { if (ns[c] != 2) continue; for (int d = c + 1; d < 100; d ++) { if (ns[d] != 3) continue;
#include<bits/stdc++.h> usingnamespace std; constint N = 60; int g[N][N], n, m, res = 0; bool st[N][N]; int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
voiddfs_1(int r, int c){ st[r][c] = true; //四向连通 for (int i = 0; i < 4; i ++) { int x = dx[i] + r, y = dy[i] + c; if (st[x][y] || g[x][y] == 0) continue; dfs_1(x, y); } }
voiddfs_0(int r, int c){ st[r][c] = true; //八向连通 for (int i = -1; i <= 1; i ++) for (int j = -1; j <= 1; j ++) { int x = r + i, y = c + j; if (x < 0 || x > n + 1 || y < 0 || y > m + 1 || st[x][y]) continue; if (g[x][y] == 0) dfs_0(x, y); elsedfs_1(x, y), res ++; } }
intmain(){ int T; cin >> T; while (T --) { memset(g, 0, sizeof g); memset(st, false, sizeof st); cin >> n >> m; res = 0; for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) { char c; cin >> c; g[i][j] = c - '0'; } dfs_0(0, 0);//从一个外海方格开始dfs cout << res << endl; } return0; }
设p[i]为前i个字符中字符的个数,
则对于下标为j的字符,
以其结尾且可以简写的子串数量即为p[j - k + 1]
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
// // Created by trudbot on 2023/4/9. //
#include<bits/stdc++.h> usingnamespace std; using ll = longlong; constint N = 5e5 + 10; ll p[N], res;
intmain(){ int k; cin >> k; string s; char a, b; cin >> s >> a >> b; for (int i = 1; i <= s.size(); i ++) p[i] = p[i - 1] + (s[i - 1] == a); for (int i = k; i <= s.size(); i ++) if (s[i - 1] == b) res += p[i - k + 1]; cout << res << endl; return0; }
intmain(){ int n, k; cin >> n >> k; r[0] = 1, l[n + 1] = n; priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> h; for (int i = 1; i <= n; i ++) cin >> v[i], l[i] = i - 1, r[i] = i + 1, h.push({v[i], i}); while (k --) { auto p = h.top(); h.pop(); if (p.first != v[p.second]) h.push({v[p.second], p.second}), k ++; elsedel(p.second); } int head = r[0]; while (head != n + 1) { cout << v[head]<< " "; head = r[head]; } return0; }
// // Created by trudbot on 2023/4/10. // #include<bits/stdc++.h> usingnamespace std; constint N = 1e5 + 10; using ll = longlong; vector<pair<int, int>> g[N]; ll dep[N], f[N][30], dist[N];
voiddfs(int u, int fa, ll d){ dep[u] = dep[fa] + 1, dist[u] = d, f[u][0] = fa; for (int i = 1; (1 << i) <= dep[u]; i ++) f[u][i] = f[f[u][i - 1]][i - 1]; for (auto &p : g[u]) { if (p.first == fa) continue; dfs(p.first, u, d + p.second); } }
intlca(int a, int b){ if (dep[a] < dep[b]) swap(a, b); for (int i = 20; i >= 0; i --) { if (dep[f[a][i]] >= dep[b]) a = f[a][i]; if (a == b) return a; } for (int i = 20; i >= 0; i --) { if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i]; } return f[a][0]; }
ll get(int a, int b){ return dist[a] + dist[b] - 2 * dist[lca(a, b)]; }
intmain(){ int n, k; cin >> n >> k; for (int i = 1; i < n; i ++) { int u, v, t; cin >> u >> v >> t; g[u].push_back({v, t}), g[v].push_back({u, t}); } vector<int> a(k); for (auto &x : a) cin >> x; dfs(1, 0, 0); ll sum = 0; for (int i = 1; i < k; i ++) sum += get(a[i - 1], a[i]); for (int i = 0; i < k; i ++) { ll ans = sum; if (i != 0) ans -= get(a[i], a[i - 1]); if (i != k - 1) ans -= get(a[i], a[i + 1]); if (i != 0 && i != k - 1) ans += get(a[i - 1], a[i + 1]); cout << ans << " "; } return0; }
#include<bits/stdc++.h> usingnamespace std; constint N = 1e5 + 10, M = 18; vector<pair<int, int>> g[N]; int dep[N], f[N][20], cnt[N], w[N];
voidinit(int u, int fa){ dep[u] = dep[fa] + 1, f[u][0] = fa; for (int i = 1; (1 << i) <= dep[u]; i ++) f[u][i] = f[f[u][i - 1]][i - 1]; for (auto &e : g[u]) { if (e.first != fa) init(e.first, u), w[e.first] = e.second; } }
intlca(int a, int b){ if (dep[a] < dep[b]) swap(a, b); for (int i = M; i >= 0; i --) { if (dep[f[a][i]] >= dep[b]) a = f[a][i]; if (a == b) return a; } for (int i = M; i >= 0; i --) { if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i]; } return f[a][0]; }
voidadd(int a, int b){ int LCA = lca(a, b); cnt[a] ++, cnt[b] ++, cnt[LCA] -= 2; }
voiddfs(int u, int fa){ for (auto &e : g[u]) { if (e.first != fa) dfs(e.first, u), cnt[u] += cnt[e.first]; } }
intmain(){ int n, m; cin >> n >> m; for (int i = 1; i < n; i ++) { int a, b; cin >> a >> b; g[a].push_back({b, i}), g[b].push_back({a, i}); } init(1, 0); for (int i = 0; i < m; i ++) { int a, b; cin >> a >> b; add(a, b); } dfs(1, 0); int res = -1; for (int i = 1; i <= n; i ++) if (cnt[i] == m && (w[i] > res)) res = w[i]; cout << res << endl; return0; }