#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
//https://codeforces.com/contest/1928/problem/D intcheck(int k){ int res = 0; rep(i, 1, n) { if (c[i] <= k) { res += c[i] * (c[i] - 1) / 2; } else { res += c[i] * (c[i] - 1) / 2; int avg = c[i] / k, mod = c[i] % k; res -= mod * (avg + 1) * avg / 2; res -= (k - mod) * avg * (avg - 1) / 2; } } res *= b; res -= (k - 1) * x; return res; } voidsolve(){ n = read(), b = read(), x = read(); rep(i, 1, n) c[i] = read();
int l = 1, r = 2e5 + 10; while (l < r) { int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3; if (check(lmid) <= check(rmid)) l = lmid + 1; else r = rmid - 1; }
int a[N]; int tmp[N]; int ans = 0;//逆序对数量 voidmerge(int l, int r){ if (l == r) return ; int mid = l + r >> 1; merge(l, mid); merge(mid + 1, r);
int i = l, j = mid + 1, k = l; while (i <= mid && j <= r) { if (a[i] <= a[j]) tmp[k++] = a[i++]; else { tmp[k++] = a[j++]; ans += mid - i + 1; } } while (i <= mid) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (i = l; i <= r; i++) a[i] = tmp[i]; }
动态规划
基本线性$dp$
最长上升子序列I $O(n ^ 2)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
int f[N]; int a[N]; voidsolve(){ int n = read(); for (int i = 1; i <= n; i++) a[i] = read(); a[0] = -INF; for (int i = 1; i <= n; i++) f[i] = 1; int res = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (a[i] > a[j]) f[i] = max(f[i], f[j] + 1); } res = max(res, f[i]); } cout << res << endl; }
int a[N]; int f[N];//长度为i的上升子序列末位的最小值,随着i的增加而增加 int n; intLIS(){ int len = 0; f[0] = -inf; for (int i = 1; i <= n; i++) { if (a[i] > f[len]) f[++len] = a[i]; else { int l = 1, r = len; while (l < r) { int mid = l + r >> 1; if (f[mid] > a[i]) r = mid; else l = mid + 1; } f[l] = a[i]; } } return len; }
最长公共子序列
朴素,$n <= 1e3, m <= 1e3。时间复杂度 O(n * m) $
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
int f[N][N];//f[i][j]:a中前i个字符, b中前j个字符的最长公共子序列的最大长度 char a[N], b[N]; voidsolve(){ int n = read(), m = read(); cin >> a + 1 >> b + 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { //省略a[i] != a[j]时 f[i][j] = f[i - 1][j - 1] //f[i - 1][j],f[i][j - 1], f[i - 1][j - 1] 之间有重叠,但是是求最大值因此无影响 f[i][j] = max(f[i - 1][j], f[i][j - 1]); if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1); } } cout << f[n][m] << endl; }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint inf = 1e18; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353;
voidprint128(__int128 x){ if (x < 0) putchar('-'), x = -x; if (x > 9) print128(x / 10); putchar(x % 10 + '0'); }
intSqrt(int x){ assert(x >= 0); int t = sqrt(x); while ((t + 1) * (t + 1) <= x) t++; while (t * t > x) t--; return t; }
int n; int a[N]; int f[N]; intLIS(){ int len = 0; f[0] = -inf; for (int i = 1; i <= n; i++) { if (a[i] > f[len]) f[++len] = a[i]; else { int l = 1, r = len; while (l < r) { int mid = l + r >> 1; if (f[mid] > a[i]) r = mid; else l = mid + 1; } f[l] = a[i]; } } return len; }
voidsolve(){ n = read(); map<int, int> mp; for (int i = 1; i <= n; i++) { int x = read(); mp[x] = i; } for (int i = 1; i <= n; i++) { a[i] = mp[read()]; }
int ans = LIS(); print(ans); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); // int T = 1; // T = read(); // while (T--) solve();
return0; }
背包
背包求组合种类
和顺序无关,先遍历物品再遍历背包
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution { public: intchange(int m, vector<int>& a){ int n = a.size(); vector<int> dp(m + 1, 0); dp[0] = 1; for (int i = 0; i < n; i++) { for (int j = a[i]; j <= m; j++)//背包物品可重复使用 dp[j] += dp[j - a[i]]; }
return dp[m]; } };
背包求排列种类
和顺序有关,先遍历背包再遍历物品
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { public: intcombinationSum4(vector<int>& a, int m){ int n = a.size(); vector<longlong> dp(m + 1, 0); dp[0] = 1; for (int j = 1; j <= m; j++) {//背包物品可重复使用 for (int i = 0; i < n; i++) { if (j >= a[i]) dp[j] += dp[j - a[i]]; } } return dp[m]; } };
#define int long long constint N = 42; constint INF = 1e18; int n, m; int w[N],v[N]; pair<int, int> a[1 << (N/2)];//体积、价值 voidsolve(){ cin >> n >> m; for (int i = 0; i < n; i++) cin >> v[i] >> w[i];
int n2 = n / 2; for (int i = 0;i < 1 << n2;i ++){//枚举组合 int ww = 0,vv = 0; for (int j = 0;j < n2;j ++){//枚举第几个 if (i >> j & 1){ ww += w[j]; vv += v[j]; } } a[i] = {vv, ww}; } sort(a, a + (1<<n2));//体积从小到大排序 int p = 1; for (int i = 1;i < 1 << n2;i ++){//让体积增大时,价值也跟着增大 if (a[p - 1].second < a[i].second) { a[p] = a[i]; p++; } } int res = 0; for (int i = 0;i < 1 << (n-n2);i++){ int ww = 0,vv = 0; for (int j = 0;j < n - n2;j++){ if (i >> j & 1 ){ ww += w[n2 + j]; vv += v[n2 + j]; } } if (vv <= m){ int t = (lower_bound(a, a + p,make_pair(m - vv,INF))-1)->second; res = max(res,ww + t); } } cout << res << endl; }
signedmain(){ int _ = 1; while (_--) solve(); return0; }
状态转移方程:dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]); #include<bits/stdc++.h> usingnamespace std; #define int long long
signedmain(){ int n; cin >> n; vector<int> s(n + 1, 0); for (int i = 1; i <= n; i++) { int x; cin >> x; s[i] = s[i - 1] + x; }
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0x3f3f3f3f)); for (int i = 1; i <= n; i++) dp[i][i] = 0; 时间复杂度(O(n^3)) for (int len = 1; len <= n; len++) {//从小区间向大区间合并 for (int i = 1; i + len - 1 <= n; i++) {//枚举左端点 int j = i + len - 1; for (int k = i; k < j; k++) {//枚举中间节点 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]); } } }
#define int long long int dp[20][20]; int a[10]; int cnt; intdfs(int pos, int pre, int lead, int limit){ if (pos == 0) return1; if (!limit && dp[pos][pre] != -1) return dp[pos][pre]; int up; if (limit) up = a[pos]; else up = 9; int ans = 0; for (int i = 0; i <= up; i++) { if (abs(i - pre) < 2) continue; if (lead && i == 0) ans += dfs(pos - 1, -2, 1, limit && i == up); else ans += dfs(pos - 1, i, 0, limit && i == up); } if (!limit) dp[pos][pre] = ans; return ans; }
voidsolve(){ for (int i = 0; i < 20; i++) { for (int j = 0; j < 20; j++) { dp[i][j] = -1; } } int x; cin >> x; x--; while (x) { cnt++; a[cnt] = x % 10; x /= 10; } int t1 = dfs(cnt, -2, 1, 1); cin >> x; cnt = 0; while (x) { cnt++; a[cnt] = x % 10; x /= 10; } int t2 = dfs(cnt,-2, 1, 1); cout << t2 - t1 << '\n'; }
signedmain(){ //freopen("in.txt", "r", stdin); ios::sync_with_stdio(false), cin.tie(0); // int T; cin >> T; // while (T--) solve();
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint inf = 1e18; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353;
voidprint128(__int128 x){ if (x < 0) putchar('-'), x = -x; if (x > 9) print128(x / 10); putchar(x % 10 + '0'); }
intSqrt(int x){ assert(x >= 0); int t = sqrt(x); while ((t + 1) * (t + 1) <= x) t++; while (t * t > x) t--; return t; }
int g[N]; int f[N]; structnode { int a, b, t; }arr[N];
voidsolve(){ int n = read(), m = read(), d = read(); int sum = 0; for (int i = 1; i <= m; i++) { int a = read(), b = read(), t = read(); arr[i] = {a, b, t}; sum += b; }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n' #define ld long double
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint inf = 1e18; constint N = 3e3 + 10; constint M = N << 1; constint mod = 998244353;
voidprint128(__int128 x){ if (x < 0) putchar('-'), x = -x; if (x > 9) print128(x / 10); putchar(x % 10 + '0'); }
intSqrt(int x){ assert(x >= 0); int t = sqrt(x); while ((t + 1) * (t + 1) <= x) t++; while (t * t > x) t--; return t; }
int a[N]; int w[3100][3100]; int dp[3100][400]; int p[3100][400]; voidsolve(){ int n = read(), m = read(); readn(a, n); for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { w[i][j] = w[i][j - 1] + a[j] - a[(i + j) / 2]; } } for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { dp[i][j] = inf; } }
dp[0][0] = 0; for (int i = 1; i <= m; i++) p[n + 1][i] = n; for (int j = 1; j <= m; j++) { for (int i = n; i >= j; i--) { for (int k = p[i][j - 1]; k <= p[i + 1][j]; k++) { if (dp[i][j] > dp[k][j - 1] + w[k + 1][i]) { dp[i][j] = dp[k][j - 1] + w[k + 1][i]; p[i][j] = k; } } } } print128(dp[n][m]); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); // int T = 1; // T = read(); // while (T--) solve();
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint inf = 1e18; constint N = 2e5 + 10; constint M = N << 1; constint mod = 998244353;
voidprint128(__int128 x){ if (x < 0) putchar('-'), x = -x; if (x > 9) print128(x / 10); putchar(x % 10 + '0'); }
intSqrt(int x){ assert(x >= 0); int t = sqrt(x); while ((t + 1) * (t + 1) <= x) t++; while (t * t > x) t--; return t; }
int n, m, k; int pre[N]; int last[N]; int f[N][6]; int g[N][6]; boolcheck(int x){ for (int i = 1; i <= k; i++) f[0][i] = g[0][i] = inf; for (int i = 1; i <= n; i++) { f[i][0] = 0; for (int j = 1; j <= k; j++) { if (i >= x) { int t = last[i - x]; f[i][j] = g[t][j - 1] + i - t - (pre[i] - pre[t]); } else { f[i][j] = inf; } g[i][j] = min(g[i - 1][j], f[i - 1][j]); } } int ans = inf; for (int i = 1; i <= n; i++) ans = min(ans, f[i][k]); return ans <= m; }
voidsolve(){ n = read(), m = read(), k = read(); string s; cin >> s; s = ' ' + s; for (int i = 1; i <= n; i++) { pre[i] += pre[i - 1]; if (s[i] == '1') pre[i]++; } for (int i = 1; i <= n; i++) { if (s[i] == '1') last[i] = last[i - 1]; else last[i] = i; }
int l = 1, r = n; while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } int ans = -1; if (check(l)) ans = l; print(ans); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); // int T = 1; // T = read(); // while (T--) solve();
#include<bits/stdc++.h> usingnamespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr); #define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++) #define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--) #define all(x) x.begin(),x.end() #define PII pair<int, int> #define x first #define y second
#define int long long #define endl '\n' constint inf = LONG_LONG_MAX; using i64 = longlong;
constint N = 1e6 + 10;
int nxt[N][26]; int n, k; intcal1(int l){ int r = min(nxt[l]['A' - 'A'] + 1, n + 1); r = min(nxt[r]['C' - 'A'] + 1, n + 1); r = min(nxt[r]['C' - 'A'] + 1, n + 1); r = min(nxt[r]['E' - 'A'] + 1, n + 1); r = min(nxt[r]['P' - 'A'] + 1, n + 1); r = nxt[r]['T' - 'A'];
return r; }
intcal2(int l){ int r = min(nxt[l]['W' - 'A'] + 1, n + 1); r = nxt[r]['A' - 'A'];
return r; }
voidsolve(){ cin >> n >> k; string s; cin >> s; s = ' ' + s; for (int j = 0; j < 26; j++) { nxt[n + 1][j] = n + 1; }
for (int i = n; i >= 1; i--) { for (int j = 0; j < 26; j++) { if (s[i] == 'A' + j) nxt[i][j] = i; else nxt[i][j] = nxt[i + 1][j]; } }
int ans = 0; for (int i = 1; i <= n; i++) { int rl = i + k - 1; if (rl > n) break; rl = max(rl, cal1(i)); int rr = cal2(i); if (rr >= rl) ans += rr - rl; }
cout << ans << '\n'; }
signedmain(){ IOS; // int T; cin >> T; // while (T--) solve(); return0; }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++) #define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--) #define all(x) x.begin(),x.end() #define PII pair<int, int> #define x first #define y second #define ll long long #define endl '\n'
using ull = unsignedlonglong;
/* next is main_solve */ char out[2][10] = {"No", "Yes"}; constint N = 1e6 + 10; int a[N]; int ans[N];
ull pre[N], suf[N]; ull base = 131; ull pw[N]; char s1[N], s2[N]; char ss[N]; charrev(char ch){ return ch == '0'? '1': '0'; } voidsolve(){ int n, k; cin >> n >> k; string s; cin >> s; s = ' ' + s; for (int i = 1; i <= k; i++) { s1[i] = '1'; s2[i] = '0'; } for (int i = k + 1; i <= n; i++) { s1[i] = rev(s1[i - k]); s2[i] = rev(s2[i - k]); }
ull h1 = 0, h2 = 0; for (int i = 1; i <= n; i++) { h1 = h1 * base + s1[i]; h2 = h2 * base + s2[i]; }
for (int i = 1; i <= n; i++) { ss[i] = s[n - i + 1]; }
for (int i = 1; i <= n; i++) { pre[i] = pre[i - 1] * base + s[i]; suf[i] = suf[i - 1] * base + ss[i]; }
int ans = -1; for (int i = 1; i <= n; i++) { ull t = (pre[n] - pre[i] * pw[n - i]) * pw[i] + (suf[n] - suf[n - i] * pw[i]); if (t == h1 || t == h2) { ans = i; break; } }
cout << ans << '\n'; }
signedmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); pw[0] = 1; for (int i = 1; i < N; i++) { pw[i] = pw[i - 1] * base; } int t; cin >> t; while (t--) solve(); return0; }
#include<bits/stdc++.h> usingnamespace std; #define int long long constint N = 1e5 + 10; int n; int s[N]; vector<int> e[N]; int dep[N], f[N][22]; voiddfs(int u, int fa){ dep[u] = dep[fa] + 1; f[u][0] = fa; for (int i = 1; i <= 20; i++) { f[u][i] = f[f[u][i - 1]][i - 1]; }
for (auto v : e[u]) { if (v == fa) continue; dfs(v, u); } } intlca(int x, int y){ if (dep[x] < dep[y]) swap(x, y);
for (int i = 20; i >= 0; i--) { if (dep[f[x][i]] >= dep[y]) x = f[x][i]; }
if (x == y) return x; for (int i = 20; i >= 0; i--) { if (f[x][i] != f[y][i]) { x = f[x][i]; y = f[y][i]; } } return f[x][0]; }
constint p = 131; constint mod = 1e9 + 7; int basep[N]; int pre[N], suf[N]; voiddfs1(int u, int fa){ pre[u] = (pre[fa] * p % mod + s[u]) % mod; suf[u] = (suf[fa] + s[u] * basep[dep[u] - 1] % mod) % mod; for (auto v: e[u]) { if (v == fa) continue; dfs1(v, u); } }
intqmi(int a, int b, int p){ int ans = 1; a %= p; while (b) { if (b & 1) ans = ans * a % p; b >>= 1; a = a * a % p; } return ans; }
intget(int x, int y){ int lc = lca(x, y); int h = (suf[x] - suf[lc] + mod) % mod; int t = (pre[y] - (pre[lc] * basep[dep[y] - dep[lc]] % mod) + mod) % mod; int len = dep[x] + dep[y] - 2 * dep[lc] + 1; h = h * qmi(basep[dep[x] - 1], mod - 2, mod) % mod; h = ((h * basep[len - 1] % mod) + (s[lc] * basep[dep[y] - dep[lc]] % mod) + t) % mod; return h; }
voidsolve(){ cin >> n; for (int i = 1; i <= n; i++) { char ch; cin >> ch; s[i] = ch - 'a' + 1; }
int root; for (int i = 1; i <= n; i++) { int father; cin >> father; if (!father) root = i; else { e[i].push_back(father); e[father].push_back(i); } }
dfs(root, 0);
basep[0] = 1ll; for (int i = 1; i < N; i++) { basep[i] = basep[i - 1] * p % mod; } dfs1(root, 0);
int q; cin >> q; while (q--) { int x, y; cin >> x >> y; int t1 = get(x, y); int t2 = get(y, x); if (t1 == t2) cout << "YES" << '\n'; else cout << "NO" << '\n'; } }
signedmain(){ ios::sync_with_stdio(false), cin.tie(0); // int T; cin >> T; // while (T--) solve(); return0; }
char a[N]; char s[N]; int d[N];//回文半径 intmanacher(){ int n = strlen(a + 1); // cin >> a + 1; //改造串, 使串为奇数串 int k = 0; //s[0]为哨兵 s[0] = '$', s[++k] = '#'; for (int i = 1; i <= n; i++) { s[++k] = a[i]; s[++k] = '#'; } n = k;
d[1] = 1; for (int i = 2, l, r = 1; i <= n; i++) { if (i <= r) d[i] = min(d[r - i + l], r - i + 1); while (s[i- d[i]] == s[i + d[i]]) d[i]++; if (i + d[i] - 1 > r) { l = i - d[i] + 1; r = i + d[i] - 1; } }
int res = 1; //原串的回文长度 = 新串的回文半径 - 1 for (int i = 1; i <= n; i++) res = max(res, d[i] - 1);
return res; }
$kmp$
Knuth–Morris–Pratt 算法:给定一个文本$ t $和一个字符串$ s$,我们尝试找到并展示$ s $在$ t $中的所有出现位置
为了简便起见,我们用$ n$ 表示字符串$ s$ 的长度,用 $m $表示文本$ t $的长度。
1 2 3 4 5 6 7 8 9 10
vector<int> find_occurrences(string text, string pattern){ string cur = pattern + '#' + text; int sz1 = text.size(), sz2 = pattern.size(); vector<int> v; vector<int> lps = prefix_function(cur); for (int i = sz2 + 1; i <= sz1 + sz2; i++) { if (lps[i] == sz2) v.push_back(i - 2 * sz2); } return v; }
#include<bits/stdc++.h> usingnamespace std; //#define int long long #define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++) #define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--) #define all(x) x.begin(),x.end() #define PII pair<int, int> #define x first #define y second #define ll long long #define endl '\n' using ull = unsignedlonglong; char out[2][10] = {"No", "Yes"}; constint N = 1e6 + 10; /* next is main_solve */
int n, trie[N][26], fail[N], cnt, in[N], vis[N], ans1[N]; int ans2[N]; vector <int> flag[N]; //点对应的字符串 voidadd(string x, int id){ //建trie树 int len = x.length (), now = 0; for (int i = 0; i < len; i++) { int c = x[i] - 'a'; if (!trie[now][c]) trie[now][c] = ++cnt; now = trie[now][c]; } flag[now].push_back (id); }
voidget_fail(){ //添加fail边 queue <int> q; for (int i = 0; i < 26; i++) if (trie[0][i]) q.push (trie[0][i]); while (!q.empty ()) { int u = q.front (); q.pop (); for (int i = 0; i < 26; i++) { if (trie[u][i]) { fail[trie[u][i]] = trie[fail[u]][i]; in[fail[trie[u][i]]]++; //fail边指向的点入度+1 q.push (trie[u][i]); } else trie[u][i] = trie[fail[u]][i]; } } }
voidquery(string x){ //查询答案 int len = x.length (), now = 0; for (int i = 0; i < len; i++) { int c = x[i] - 'a'; now = trie[now][c]; vis[now]++; //不需跳fail边 } }
voidtopu(){ //拓扑排序 queue <int> q; for (int i = 1; i <= cnt; i++) if (!in[i]) q.push (i); while (!q.empty ()) { int u = q.front (); q.pop (); for (auto it = flag[u].begin (); it != flag[u].end (); it++) ans1[*it] = vis[u]; int v = fail[u]; vis[v] += vis[u]; in[v]--; if (!in[v]) q.push (v); } }
voidsolve(){ int n; cin >> n; string a, c; cin >> a >> c; for (int i = 0; i <= a.size(); i++) { for (int j = 0; j < 26; j++) { trie[i][j] = 0; } fail[i] = in[i] = vis[i] = 0; flag[i].clear(); }
for (int i = 1; i <= n; i++) { ans1[i] = ans2[i] = 0; }
for (int i = 1; i <= n; i++) { string s1, s2; cin >> s1 >> s2; add(s1, i); if (s2.find(c) != string::npos) ans2[i] = 1; }
get_fail(); query(a); topu(); for (int i = 1; i <= n; i++) { if (ans1[i] > 0 && ans2[i] > 0) { cout << i << ' '; } } cout << '\n'; }
signedmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); int t; cin >> t; while (t--) solve(); return0; }
图论
链式前向星
1 2 3 4 5 6 7 8 9 10 11 12 13
int h[N], e[M], ne[M], tot, w[N];
voidadd(int a, int b, int c){ tot++; e[tot] = b; w[tot] = c; ne[tot] = h[a]; h[a] = tot; }
for (int i = h[u]; i; i = ne[i]) { int v = e[i];...... }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// 快读 // inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
voidprint128(__int128 x){ if (x < 0) putchar('-'), x = -x; if (x > 9) print128(x / 10); putchar(x % 10 + '0'); }
intSqrt(int x){ assert(x >= 0); int t = sqrt(x); while ((t + 1) * (t + 1) <= x) t++; while (t * t > x) t--; return t; }
char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint inf = 1e18; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353;
vector<pii> e[N];
int n, m; int dist[N]; int vis[N]; int tot[N]; boolspfa(){ for (int i = 1; i <= n; i++) { dist[i] = inf; }
queue<int> q; q.push(0); vis[0] = 1; dist[0] = 0; while (q.size()) { auto u = q.front(); q.pop(); vis[u] = 0; for (auto [v, w]: e[u]) { if (dist[v] <= dist[u] + w) continue;//最短路 dist[v] = dist[u] + w; if (!vis[v]) { tot[v]++; if (tot[v] == n + 1) returnfalse; // 注意添加了一个超级源点 q.push(v); vis[v] = 1; } } } returntrue; }
voidsolve(){ n = read(), m = read();
for (int i = 1; i <= m; i++) { int v = read(), u = read(), w = read(); e[u].push_back({v, w});// v <= u + w } for (int i = 1; i <= n; i++) { e[0].push_back({i, 0}); }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// 快读 // inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
voidprint128(__int128 x){ if (x < 0) putchar('-'), x = -x; if (x > 9) print128(x / 10); putchar(x % 10 + '0'); }
intSqrt(int x){ assert(x >= 0); int t = sqrt(x); while ((t + 1) * (t + 1) <= x) t++; while (t * t > x) t--; return t; }
char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint inf = 1e18; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353;
vector<pii> e[N];
voidaddEdge(int x, int y, int w){ e[x].push_back({y, w}); }
int dfn[N]; int low[N]; int scc[N]; int tot; int instk[N]; int sz[N]; stack<int> stk; int cnt;
int dp[N]; voidtarjan(int u){ dfn[u] = low[u] = ++tot; stk.push(u); instk[u] = 1; for (auto [v, w]: e[u]) { if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } elseif (instk[v]) { low[u] = min(low[u], dfn[v]); } } if (dfn[u] == low[u]) { int v; cnt++; do { v = stk.top(); stk.pop(); instk[v] = 0; scc[v] = cnt; sz[cnt]++; }while (v != u); } }
vector<pii> E[N];
int indeg[N];
voidsolve(){ int n = read(), m = read(); for (int i = 1; i <= m; i++) { int op = read(), x = read(), y = read(); if (op == 1) { addEdge(x, y, 0); addEdge(y, x, 0); } elseif (op == 2) { addEdge(x, y, 1); } elseif (op == 3) { addEdge(y, x, 0); } elseif (op == 4) { addEdge(y, x, 1); } else { addEdge(x, y, 0); } }
for (int i = 1; i <= n; i++) { if (!dfn[i]) tarjan(i); }
for (int u = 0; u <= n; u++) { for (auto [v, w]: e[u]) { if (scc[u] == scc[v] && w) { print(-1); return ; } elseif (scc[u] == scc[v]) continue; E[scc[u]].push_back({scc[v], w}); indeg[scc[v]]++; } }
queue<int> q; for (int i = 1; i <= cnt; i++) { dp[i] = -inf; if (!indeg[i]) { q.push(i); dp[i] = 1; } }
while (q.size()) { auto u = q.front(); q.pop();
for (auto [v, w]: E[u]) { dp[v] = max(dp[v], dp[u] + w); indeg[v]--; if (!indeg[v]) { q.push(v); } } }
int ans = 0; for (int i = 1; i <= cnt; i++) { ans += sz[i] * dp[i]; }
print(ans); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); // int T = 1; // T = read(); // while (T--) solve();
return0; }
$floyd$
全源最短路,插点法
时间复杂度$O(n^3)$
1 2 3 4 5 6 7 8 9
voidfloyd(){ for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } }
//并查集贪心 structedge{ int u, v, w; booloperator <(const edge &t) const{ return w < t.w; } }e[N]; int fa[N], ans, cnt;//ans为树的最小边权值和 boolkruskal(){ sort(e, e + m); for (int i = 1; i <= n; i++) fa[i] = i; for (int i = 0; i < m; i++) { int x = find(e[i].u); int y = find(e[i].v); if (x != y) { fa[x] = y; ans += e[i].w; cnt++; } } return cnt == n - 1; }
int n, m, q; structedge{ int u, v, w; booloperator <(const edge &t) const{ return w > t.w; } }E[N]; int f[M]; intfind(int x){ return x == f[x]? x : f[x] = find(f[x]); } vector<int> e[M]; int val[M]; voidkruskal(){ sort(E + 1, E + m + 1); for (int i = 1; i < 2 * n; i++) f[i] = i;//1 -- 2 * n - 1 int idx = n; for (int i = 1; i <= m; i++) { int u = E[i].u, v = E[i].v, w = E[i].w; u = find(u), v = find(v); if (u == v) continue; val[++idx] = w; e[idx].push_back(u); e[idx].push_back(v); f[u] = f[v] = idx; } }
int dep[N], fa[N][22]; int col[M], cols; voiddfs(int u, int father){ col[u] = cols; dep[u] = dep[father] + 1; fa[u][0] = father; for (int i = 1; i <= 20; i++) { fa[u][i] = fa[fa[u][i - 1]][i - 1]; } for (auto &v: e[u]) { dfs(v, u); } } intlca(int u, int v){ if (dep[u] < dep[v]) swap(u, v); for (int i = 20; i >= 0; i--) { if (dep[fa[u][i]] >= dep[v]) u = fa[u][i]; } if (u == v) return u; for (int i = 20; i >= 0; i--) { if (fa[u][i] != fa[v][i]) { u = fa[u][i], v = fa[v][i]; } } return fa[u][0]; } voidsolve(){ cin >> n >> m >> q; for (int i = 1; i <= m; i++) { cin >> E[i].u >> E[i].v >> E[i].w; } kruskal(); for (int i = 1; i < 2 * n; i++) { if (f[i] == i) { ++cols; dfs(i, 0); } } while (q--) { int x, y; cin >> x >> y; if (col[x] != col[y]) cout << -1 << endl; else { int l = lca(x, y); cout << val[l] << endl; } } }
int n, m, root; constint N = 5e5 + 10; int fa[N]; int ans[N]; intfind(int x){ return fa[x] == x? x: find(fa[x]); } vector<int> e[N]; vector<pair<int, int>> query[N]; int vis[N]; voidtarjan(int u){ vis[u] = 1; for (auto v: e[u]) { if (vis[v]) continue; tarjan(v); fa[v] = u; }
for (auto q: query[u]) { int v = q.first, i = q.second; if (vis[v]) ans[i] = find(v); } }
intmain(){ //freopen("in.txt", "r", stdin); cin >> n >> m >> root; for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); } for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; query[x].push_back({y, i}); query[y].push_back({x, i}); }
tarjan(root);
for (int i = 1; i <= m; i++) cout << ans[i] << endl;
#include<bits/stdc++.h> usingnamespace std; #define int long long
int n, m; constint N = 3e5 + 10; int s[N][51]; vector<int> e[N];
constint p = 998244353;
intqmi(int a, int b){ int ans = 1; a %= p; while (b) { if (b & 1) ans = ans * a % p; b >>= 1; a = a * a % p; }
return ans; }
int dep[N], fa[N][21]; voiddfs(int u, int father){ dep[u] = dep[father] + 1; for (int k = 1; k <= 50; k++) { int t = qmi(dep[u], k); s[u][k] = (s[father][k] + t % p) % p; }
fa[u][0] = father; for (int i = 1; i <= 20; i++) { fa[u][i] = fa[fa[u][i - 1]][i - 1]; } for (auto v: e[u]) { if (v == father) continue; dfs(v, u); } }
intlca(int x, int y){ if (dep[x] < dep[y]) swap(x, y);
for (int i = 20; i >= 0; i--) { if (dep[fa[x][i]] >= dep[y]) x = fa[x][i]; }
if (x == y) return x;
for (int i = 20; i >= 0; i--) { if (fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } } return fa[x][0]; } signedmain(){ //freopen("in.txt", "r", stdin); cin >> n; for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; e[x].push_back(y); e[y].push_back(x); }
dep[0] = -1; dfs(1, 0);
cin >> m; while (m--) { int x, y, k; cin >> x >> y >> k; int l = lca(x, y); int ans = (s[x][k] + s[y][k] - s[l][k] - s[fa[l][0]][k] + 2 * p) % p; cout << ans << endl; }
return0; }
树上边前缀和
$dist(x, y) = s[x] + s[y] - 2 * s[lca] $
1 2 3 4 5 6 7 8
int s[N]; voiddfs1(int u, int fa){ for (auto v: e[u]) { if (v == fa) continue; s[v] = s[u] + w[v]; dfs1(v, u); } }
#include<bits/stdc++.h> usingnamespace std; #define int long long int n, m; constint N = 5e4 + 10; vector<int> e[N]; int diff[N]; int dep[N], fa[N][21]; voiddfs(int u, int father){ dep[u] = dep[father] + 1; fa[u][0] = father; for (int i = 1; i <= 20; i++) { fa[u][i] = fa[fa[u][i - 1]][i - 1]; }
for (auto v: e[u]) { if (v == father) continue; dfs(v, u); } }
intlca(int x, int y){ if (dep[x] < dep[y]) swap(x, y);
for (int i = 20; i >= 0; i--) { if (dep[fa[x][i]] >= dep[y]) x = fa[x][i]; } if (x == y) return x;
for (int i = 20; i >= 0; i--) { if (fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } } return fa[x][0]; }
int a[N]; voiddfs1(int u, int father){ for (auto v: e[u]) { if (v == father) continue; dfs1(v, u); diff[u] += diff[v]; } a[u] += diff[u]; } signedmain(){ //freopen("in.txt", "r", stdin); cin >> n >> m; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); } dfs(1, 0);
for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; int l = lca(x, y); diff[x]++, diff[y]++, diff[l]--, diff[fa[l][0]]--; }
dfs1(1, 0); int mx = -1e18; for (int i = 1; i <= n; i++) { mx = max(mx, a[i]); } cout << mx << endl; return0; }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define PII pair<int, int> int n, m; constint N = 1e5 + 10; vector<int> e[N]; int diff[N]; int dep[N], f[N][22]; voiddfs(int u, int fa){ dep[u] = dep[fa] + 1; f[u][0] = fa; for (auto v: e[u]) { if (v == fa) continue; dfs(v, u); } } intlca(int x, int y){ if (dep[x] < dep[y]) swap(x, y); for (int i = 20; i >= 0; i--) { if (dep[f[x][i]] >= dep[y]) { x = f[x][i]; } } if (x == y) return ;
for (int i = 20; i >= 0; i--) { if (f[x][i] != f[y][i]) { x = f[x][i]; y = f[y][i]; } } return f[x][0]; }
voiddfs2(int u, int fa){ for (auto v: e[u]) { if (v == fa) continue; dfs2(v, u); diff[u] += diff[v]; } } voidsolve(){ int n, m; cin >> n >> m; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); }
dfs(1, 0); for (int i = 1; i <= 20; i++) { for (int j = 1; j <= n; j++) { f[j][i] = f[f[j][i - 1]][i - 1]; } }
for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; int lc = lca(x, y); diff[x]++, diff[y]++, diff[lc] -= 2; } dfs2(1, 0); }
#include<bits/stdc++.h> usingnamespace std; #define int long long constint N = 1e5 + 10; vector<int> e[N]; int deg[N]; signedmain(){ int n; cin >> n; //输入 for (int i = 1; i <= n; i++) { int v; cin >> v; while (v) { e[i].push_back(v); deg[v]++;//入度++ cin >> v; } }
queue<int> q; for (int i = 1; i <= n; i++) { if (!deg[i]) { q.push(i); } }
vector<int> ans;//ans为拓扑序 while (q.size()) { int u = q.front(); q.pop(); ans.push_back(u); for (auto v: e[u]) { deg[v]--; if (!deg[v]) q.push(v); } }
#include<bits/stdc++.h> usingnamespace std; int n, m; // n:点数 m:边数 int dfn[100001], low[100001], inde, res; // dfn:记录每个点的时间戳 // low:能不经过父亲到达最小的编号,inde:时间戳,res:答案数量 bool vis[100001], flag[100001]; // flag: 答案 vis:标记是否重复 vector<int> edge[100001]; // 存图用的
voidTarjan(int u, int father){ // u 当前点的编号,father 自己爸爸的编号 vis[u] = true; // 标记 low[u] = dfn[u] = ++inde; // 打上时间戳 int child = 0; // 每一个点儿子数量 for (auto v : edge[u]) { // 访问这个点的所有邻居 (C++11) if (!vis[v]) { child++; // 多了一个儿子 Tarjan(v, u); // 继续 low[u] = min(low[u], low[v]); // 更新能到的最小节点编号 if (father != u && low[v] >= dfn[u] && !flag[u]) { // 主要代码 // 如果不是自己,且不通过父亲返回的最小点符合割点的要求,并且没有被标记过 // 要求即为:删了父亲连不上去了,即为最多连到父亲 flag[u] = true; res++; // 记录答案 } } elseif (v != father) { // 如果这个点不是自己的父亲,更新能到的最小节点编号 low[u] = min(low[u], dfn[v]); } } // 主要代码,自己的话需要 2 个儿子才可以 if (father == u && child >= 2 && !flag[u]) { flag[u] = true; res++; // 记录答案 } }
intmain(){ cin >> n >> m; // 读入数据 for (int i = 1; i <= m; i++) { // 注意点是从 1 开始的 int x, y; cin >> x >> y; edge[x].push_back(y); edge[y].push_back(x); } // 使用 vector 存图 for (int i = 1; i <= n; i++) // 因为 Tarjan 图不一定连通 if (!vis[i]) { inde = 0; // 时间戳初始为 0 Tarjan(i, i); // 从第 i 个点开始,父亲为自己 } cout << res << endl; for (int i = 1; i <= n; i++) if (flag[i]) cout << i << " "; // 输出结果 return0; }
#include<bits/stdc++.h> usingnamespace std; constint N = 1e6 + 10; constint M = N << 1; vector<int> e[N], ne[N]; int dfn[N], low[N], tot; stack<int> stk; vector<int> dcc[N]; int cut[N], root, cnt, num, id[N]; voidtarjan(int x){ dfn[x] = low[x] = ++tot; stk.push(x); if (!e[x].size()) { dcc[++cnt].push_back(x); stk.pop(); return ; } int child = 0; for (auto y: e[x]) { if (!dfn[y]) { tarjan(y); low[x] = min(low[x], low[y]); if (low[y] >= dfn[x]) { child++; if (x != root || child > 1) { cut[x] = 1; } cnt++; while (true) { int z = stk.top(); stk.pop(); dcc[cnt].push_back(z); if (z == y) break; } } } else { low[x] = min(low[x], dfn[y]); } } }
voidsolve(){ int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; e[a].push_back(b); e[b].push_back(a); }
for (root = 1; root <= n; root++) { if (!dfn[root]) tarjan(root); }
num = cnt; for (int i = 1; i <= n; i++) { if (cut[i]) id[i] = ++num; }
for (int i = 1; i <= cnt; i++) { for (int j = 0; j < dcc[i].size(); j++) { int x = dcc[i][j]; if (cut[x]) { ne[i].push_back(id[x]); ne[id[x]].push_back(i); } } } }
#include<bits/stdc++.h> usingnamespace std; #define int long long
signedmain(){ //freopen("in.txt", "r", stdin); int n; cin >> n; vector<vector<int>> e(n + 1); for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); }
auto bfs = [&](int st) -> vector<int> { vector<int> dist(n + 1, -1ll); queue<int> q; q.push(st); dist[st] = 0; while (q.size()) { int u = q.front(); q.pop(); for (auto v: e[u]) { if (dist[v] != -1) continue; dist[v] = dist[u] + 1; q.push(v); } } return dist; };
int st = 1; vector<int> dist; auto func = [&]() -> void { dist = bfs(st); for (int i = 1; i <= n; i++) { if (dist[i] > dist[st]) st = i; } };
func(); func();
cout << dist[st] << endl;
return0; }
树形dp求树的直径
$我们定义 dp[u]:以 u 为根的子树中,从 u 出发的最长路径。那么容易得出转移方程: $$dp[u] = max(dp[u], dp[v] + w(u, v)) $
其中的$v$为的子节点, $w(u, v$)表示所经过边的权重
树形$ dp $可以在存在负权边的情况下求解出树的直径
对于树的直径,实际上是可以通过枚举从某个节点出发不同的两条路径相加的最大值求出。
因此,在 $DP$ 求解的过程中,我们只需要在更新 $dp[u]$ 之前,计算$ d = max(d, dp[u] + dp[v] + w(u, v)) $即可算出直径$ d $
constint N = 1e6 + 10; vector<int> e[N]; int f[N]; int d; voiddfs(int u, int fa){ for (auto v: e[u]) { if (v == fa) continue; dfs(v, u); d = max(d, f[u] + f[v] + 1); f[u] = max(f[u], f[v] + 1); } } voidsolve(){ int n; cin >> n; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); } dfs(1, 0);
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define pb push_back #define PII pair<int, int> #define x first #define y second #define endl '\n'
inlineintread(){ int c; cin >> c; return c; } inlinevoidreadn(int a[], int n){ for_each(a + 1, a + n + 1, [](int &x) { cin >> x; }); } inlinevoidwriten(int a[], int n){ for_each(a + 1, a + n + 1, [](int &x) { cout << x << ' '; }); cout << endl; } template <typename T, typename... Args> voidwrite(const T &first, const Args &...args){ cout << first; ((cout << ' ' << args), ...); cout << endl; } template <typename T, typename... Args> voidewrite(const T &first, const Args &...args){ cerr << '*'; cerr << first; ((cerr << ' ' << args), ...); cerr << endl; } char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353; structedge { int v, w; }; vector<edge> e[M];
voiddfs(int u, int fa, int dist[]){ for (auto [v, w]: e[u]) { if (v == fa) continue; dist[v] = dist[u] + w; dfs(v, u, dist); } }
int dist[N]; int distl[N]; int distr[N];
voidsolve(){ int n = read(); for (int i = 1; i < n; i++) { int u, v, c; u = read(), v = read(), c = read(); e[u].push_back({v, c}); e[v].push_back({u, c}); } for (int i = 1; i <= n; i++) { int d = read(); e[i].push_back({i + n, d}); e[i + n].push_back({i, d}); }
dfs(1, 0, dist); int l = max_element(dist + 1, dist + 1 + 2 * n) - dist; dfs(l, 0, distl); int r = max_element(distl + 1, distl + 1 + 2 * n) - distl; dfs(r, 0, distr);
for (int i = 1; i <= n; i++) { if (i + n == l) { write(distr[i]); } elseif (i + n == r) { write(distl[i]); } else { write(max(distl[i], distr[i])); } } }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); // int T = 1; // T = read(); // while (T--) solve();
#include<bits/stdc++.h> usingnamespace std; #define int long long using PII = pair<int, int>;
constint N = 1e5 + 10; int ans[N]; int a[N]; vector<PII> qs[N]; vector<int> e[N];
int sz[N], son[N], dep[N]; voiddfs(int u, int fa){ sz[u] = 1; dep[u] = dep[fa] + 1; for (auto v: e[u]) { if (v == fa) continue; dfs(v, u); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } }
priority_queue<PII> q[N]; int vis[N]; int Son; voidadd(int u, int fa){ vis[u] = 1; q[dep[u]].push({a[u], u}); for (auto v: e[u]) { if (v == fa || v == Son) continue; add(v, u); } }
voiddel(int u, int fa){ vis[u] = 0; for (auto v: e[u]) { if (v == fa) continue; del(v, u); } }
voiddfs2(int u, int fa, int op){ for (auto v: e[u]) { if (v == fa || v == son[u]) continue; dfs2(v, u, 0); } if (son[u]) { dfs2(son[u], u, 1); Son = son[u]; }
add(u, fa);
for (auto p: qs[u]) { int k = p.first, i = p.second; int d = dep[u] + k; while (q[d].size() && !vis[q[d].top().second]) { q[d].pop(); }
ans[i] = q[d].top().first; } if (!op) { del(u, fa); Son = 0; } } signedmain(){ int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); }
for (int i = 0; i < q; i++) { int x, k; cin >> x >> k; qs[x].push_back({k, i}); }
dfs(1, 0); dfs2(1, 0, 0);
for (int i = 0; i < q; i++) cout << ans[i] << '\n';
#include<bits/stdc++.h> usingnamespace std; #define int long long #define PII pair<int, int> constint N = 2e5 + 10; int a[N]; vector<int> e[N]; int ans; int cnt[N]; int sum[N]; vector<map<int, int>> mp(N); voiddfs(int u, int fa){ map<int, int> cc; int res = 0; for (auto v: e[u]) { if (v == fa) continue; dfs(v, u); if (mp[v].size() > cc.size()) { cc.swap(mp[v]); swap(res, sum[v]); } for (auto [k, t]: mp[v]) { res -= cc[k] * (cnt[k] - cc[k]); cc[k] += t; res += cc[k] * (cnt[k] - cc[k]); } mp[v].clear(); }
res -= cc[a[u]] * (cnt[a[u]] - cc[a[u]]); cc[a[u]]++; res += cc[a[u]] * (cnt[a[u]] - cc[a[u]]); mp[u].swap(cc); ans += res; sum[u] = res; } voidsolve(){ int n; cin >> n; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); }
for (int i = 1; i <= n; i++) { cin >> a[i]; cnt[a[i]]++; }
dfs(1, 0);
cout << ans; }
signedmain(){ ios::sync_with_stdio(false), cin.tie(0); // int t; cin >> t; // while (t--) solve();
#include<bits/stdc++.h> usingnamespace std; #define int long long #define PII pair<int, int> #define all x.begin(), x.end()
constint N = 1e6 + 10; vector<int> e[N]; set<int> s[N]; int dfn[N], dep[N], f[N][22]; int cnt; voiddfs(int u, int fa){ dfn[u] = ++cnt; dep[u] = dep[fa] + 1; f[u][0] = fa; for (auto v: e[u]) { if (v == fa) continue; dfs(v, u); } }
intlca(int x, int y){ if (dep[x] < dep[y]) swap(x, y); for (int i = 20; i >= 0; i--) { if (dep[f[x][i]] >= dep[y]) x = f[x][i]; } if (x == y) return x; for (int i = 20; i >= 0; i--) { if (f[x][i] != f[y][i]) { x = f[x][i]; y = f[y][i]; } } return f[x][0]; }
intsum(int x, int y){ int lc = lca(x, y); int ans = dep[x] + dep[y] - 2 * dep[lc]; return ans; }
int vis[N]; boolcmp(int x, int y){ return dfn[x] < dfn[y]; } int poi[N]; vector<PII> ee[N]; int top, stk[N]; voidbuild_VrTree(int m){ top = 1, stk[1] = 1; ee[1].clear(); for (int i = 1; i <= m; i++) { if (poi[i] == 1) continue; int lc = lca(poi[i], stk[top]); if (lc != stk[top]) { while (dfn[stk[top - 1]] > dfn[lc]) { ee[stk[top - 1]].push_back({stk[top], sum(stk[top - 1], stk[top])}); top--; } if (lc != stk[top - 1]) { ee[lc].clear(); ee[lc].push_back({stk[top], sum(lc, stk[top])}); stk[top] = lc; } else { ee[lc].push_back({stk[top], sum(lc, stk[top])}); top--; } } ee[poi[i]].clear(); stk[++top] = poi[i]; } for (int i = 1; i < top; i++) ee[stk[i]].push_back({stk[i + 1], sum(stk[i], stk[i + 1])}); }
int ans; int g[N], sz[N]; int dp[N]; int pre[N]; voiddfs2(int u){ g[u] = sz[u] = 0; for (auto [v, w]: ee[u]) { pre[v] = pre[u] + w; dfs2(v); g[u] += g[v]; sz[u] += sz[v]; } if (vis[u]) { g[u] += pre[u]; sz[u]++; } } int m; voiddfs3(int u){ for (auto [v, w]: ee[u]) { dp[v] = g[v] - sz[v] * pre[v] + dp[u] - (g[v] - sz[v] * pre[u]) + (m - sz[v]) * w; dfs3(v); } } voidsolve(){ int n; cin >> n; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); }
for (int i = 1; i <= n; i++) { int x; cin >> x; s[x].insert(i); }
dfs(1, 0); for (int i = 1; i <= 20; i++) { for (int j = 1; j <= n; j++) { f[j][i] = f[f[j][i - 1]][i - 1]; } }
for (int i = 1; i <= n; i++) { if (s[i].size() < 2) continue; m = 0; for (auto x: s[i]) { vis[x] = 1; poi[++m] = x; } sort(poi + 1, poi + 1 + m, cmp); build_VrTree(m); dfs2(1); dp[1] = g[1]; dfs3(1); int t = 0; for (int i = 1; i <= m; i++) { //cout << poi[i] << ' ' << dp[poi[i]] << '\n'; t += dp[poi[i]]; } //cout << '\n'; ans += t / 2; for (auto x: s[i]) { vis[x] = 0; } } cout << ans; }
signedmain(){ ios::sync_with_stdio(false), cin.tie(0); // int t; cin >> t; // while (t--) solve();
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ll long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define pb push_back #define PII pair<int, int> #define x first #define y second #define endl '\n'
for (int i = 1; i <= lgmx; i++) { int v = fa[u][i - 1]; fa[u][i] = fa[v][i - 1]; mi1[u][i] = min(mi1[u][i - 1], mi1[v][i - 1]); mi2[u][i] = min(mi2[u][i - 1], mi2[v][i - 1]); }
for (auto v: e[u]) { if (v == father) continue; dfs(v, u); } }
intlca(int u, int v){ if (dep[u] < dep[v]) swap(u, v); for (int k = dep[u] - dep[v], lg; k; k -= 1 << lg) { lg = __lg(k); u = fa[u][lg]; } if(u == v) return u;
for(int k = __lg(dep[u]); k >= 0; k--) { if (fa[u][k] != fa[v][k]) u = fa[u][k], v = fa[v][k]; } return fa[u][0]; }
intask1(int u, int v){ int ans = 1e18; for (int k = dep[u] - dep[v] + 1, lg; k; k -= 1 << lg) { lg = __lg(k); ans = min(ans, mi1[u][lg]); u = fa[u][lg]; } return ans; }
intask2(int u, int v){ int ans = 1e18; for (int k = dep[u] - dep[v] + 1, lg; k; k -= 1 << lg) { lg = __lg(k); ans = min(ans, mi2[u][lg]); u = fa[u][lg]; } return ans; }
voidsolve(){ int n, k; n = read(), k = read(); for (int i = 1; i < n; i++) { int u, v; u = read(), v = read(); e[u].push_back(v); e[v].push_back(u); }
queue<int> q; for (int i = 1; i <= k; i++) { int v; v = read(); q.push(v); vis[v] = 1; }
while (q.size()) { auto u = q.front(); q.pop(); for (auto v: e[u]) { if (vis[v]) continue; dp[v] = dp[u] + 1; vis[v] = 1; q.push(v); } }
dfs(1, 0); int Q; Q = read(); while (Q--) { int x, y; x = read(), y = read(); int lc = lca(x, y);
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define pb push_back #define PII pair<int, int> #define x first #define y second #define endl '\n'
inlineintread(){ int c; cin >> c; return c; } inlinevoidreadn(int a[], int n){ for_each(a + 1, a + n + 1, [](int &x) { cin >> x; }); } inlinevoidwriten(int a[], int n){ for_each(a + 1, a + n + 1, [](int &x) { cout << x << ' '; }); cout << endl; } template <typename T, typename... Args> voidwrite(const T &first, const Args &...args){ cout << first; ((cout << ' ' << args), ...); cout << endl; } template <typename T, typename... Args> voidewrite(const T &first, const Args &...args){ cerr << '*'; cerr << first; ((cerr << ' ' << args), ...); cerr << endl; } char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353;
structedge { int v, w, ne; }e[M]; int h[N], tot = 1; int mf[N], pre[N]; int n, m, s, t; voidadd(int u, int v, int w){ e[++tot] = {v, w, h[u]}; h[u] = tot; }
boolbfs(){ for (int i = 1; i <= n; i++) { mf[i] = 0; } queue<int> q; q.push(s); mf[s] = 1e18; while (q.size()) { auto u = q.front(); q.pop(); for (int i = h[u]; i; i = e[i].ne) { int v = e[i].v; if (!mf[v] && e[i].w) { mf[v] = min(mf[u], e[i].w); pre[v] = i; q.push(v); if (v == t) returntrue; } } } returnfalse; }
intEK(){ int flow = 0; while (bfs()) { int v = t; while (v != s) { int i = pre[v]; e[i].w -= mf[t]; e[i ^ 1].w += mf[t]; v = e[i ^ 1].v; } flow += mf[t]; } return flow; }
voidsolve(){ n = read(), m = read(), s = read(), t = read(); for (int i = 1; i <= m; i++) { int u, v, w; u = read(), v = read(), w = read(); add(u, v, w); add(v, u, 0); } int ans = EK(); write(ans); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); // int T; // T = read(); // while (T--) solve();
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define pb push_back #define PII pair<int, int> #define x first #define y second #define endl '\n'
inlineintread(){ int c; cin >> c; return c; } inlinevoidreadn(int a[], int n){ for_each(a + 1, a + n + 1, [](int &x) { cin >> x; }); } inlinevoidwriten(int a[], int n){ for_each(a + 1, a + n + 1, [](int &x) { cout << x << ' '; }); cout << endl; } template <typename T, typename... Args> voidwrite(const T &first, const Args &...args){ cout << first; ((cout << ' ' << args), ...); cout << endl; } template <typename T, typename... Args> voidewrite(const T &first, const Args &...args){ cerr << '*'; cerr << first; ((cerr << ' ' << args), ...); cerr << endl; } char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353;
structedge{ int v, w, ne; }e[M]; int h[N]; int tot = 1; int dep[N], cur[N]; int n, m, s, t; voidadd(int u, int v, int w){ e[++tot] = {v, w, h[u]}; h[u] = tot; }
boolbfs(){ for (int i = 1; i <= n; i++) dep[i] = 0; queue<int> q; q.push(s); dep[s] = 1; while (q.size()) { auto u = q.front(); q.pop(); for (int i = h[u]; i; i = e[i].ne) { int v = e[i].v; if (!dep[v] && e[i].w) { dep[v] = dep[u] + 1; q.push(v); if (v == t) returntrue; } } } returnfalse; }
intdfs(int u, int mf){ if (u == t) return mf; int sum = 0; for (int i = cur[u]; i; i = e[i].ne) { cur[u] = i; int v = e[i].v; if (dep[v] == dep[u] + 1 && e[i].w) { int f = dfs(v, min(mf, e[i].w)); e[i].w -= f; e[i ^ 1].w += f; sum += f; mf -= f; if (!mf) break; } } if (!sum) dep[u] = 0; return sum; }
intdinic(){ int flow = 0; while (bfs()) { for (int i = 0; i <= tot; i++) cur[i] = h[i]; flow += dfs(s, 1e18); } return flow; }
voidsolve(){ n = read(), m = read(), s = read(), t = read(); for (int i = 1; i <= m; i++) { int u, v, w; u = read(), v = read(), w = read(); add(u, v, w); add(v, u, 0); } int ans = dinic(); write(ans); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); // int T; // T = read(); // while (T--) solve();
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ld long double #define pii pair<int,int> #define all(x) x.begin(),x.end() #define endl '\n' #define MOD 998244353 #define INF 1e14 // #define lc (p<<1) // #define rc (p<<1|1)
constint N = 1201; constint M = 1.2e5 + 5; typedefstruct { int to; int c; int nxt; }edge; edge e[M << 1]; int h[N]; int cnt = 1; voidadd(int u, int v, int c){ e[++cnt].to = v; e[cnt].c = c; e[cnt].nxt = h[u]; h[u] = cnt; }
int n, m, S, T; int d[N], num[N], cur[N];
voidbfs(){ fill(num + 1, num + n + 1, 0); fill(d + 1, d + n + 1, -1); queue<int> q; q.push(T); d[T] = 0; num[0] = 1;
while (q.size()) { int u = q.front(); q.pop(); for (int ed = h[u];ed;ed = e[ed].nxt) { auto [v, c, nxt] = e[ed]; if (d[v] == -1 && !c) { d[v] = d[u] + 1; num[d[v]]++; q.push(v); } } } }
intdfs(int u, int mf){ if (u == T) return mf; int sum = 0; for (int ed = cur[u];ed;ed = e[ed].nxt) { cur[u] = ed;//当前弧优化 auto [v, c, nxt] = e[ed]; if (d[u] == d[v] + 1 && c) { int f = dfs(v, min(mf, c)); mf -= f; sum += f; e[ed].c -= f; e[ed ^ 1].c += f; if (!mf) return sum;//残量优化 } } //断层优化 if (--num[d[u]] == 0) d[S] = n + 1; ++d[u]; ++num[d[u]]; return sum; }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define pb push_back #define PII pair<int, int> #define x first #define y second #define endl '\n'
inlineintread(){ int c; cin >> c; return c; } inlinevoidreadn(int a[], int n){ for_each(a + 1, a + n + 1, [](int &x) { cin >> x; }); } inlinevoidwriten(int a[], int n){ for_each(a + 1, a + n + 1, [](int &x) { cout << x << ' '; }); cout << endl; } template <typename T, typename... Args> voidwrite(const T &first, const Args &...args){ cout << first; ((cout << ' ' << args), ...); cout << endl; } template <typename T, typename... Args> voidewrite(const T &first, const Args &...args){ cerr << '*'; cerr << first; ((cerr << ' ' << args), ...); cerr << endl; } char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353;
structedge{ int v, w, ne; }e[M]; int h[N]; int tot = 1; int dep[N], cur[N]; int n, m, s, t; voidadd(int u, int v, int w){ e[++tot] = {v, w, h[u]}; h[u] = tot; }
boolbfs(){ for (int i = 1; i <= n; i++) dep[i] = 0; queue<int> q; q.push(s); dep[s] = 1; while (q.size()) { auto u = q.front(); q.pop(); for (int i = h[u]; i; i = e[i].ne) { int v = e[i].v; if (!dep[v] && e[i].w) { dep[v] = dep[u] + 1; q.push(v); if (v == t) returntrue; } } } returnfalse; }
intdfs(int u, int mf){ if (u == t) return mf; int sum = 0; for (int i = cur[u]; i; i = e[i].ne) { cur[u] = i; int v = e[i].v; if (dep[v] == dep[u] + 1 && e[i].w) { int f = dfs(v, min(mf, e[i].w)); e[i].w -= f; e[i ^ 1].w += f; sum += f; mf -= f; if (!mf) break; } } if (!sum) dep[u] = 0; return sum; }
intdinic(){ int flow = 0; while (bfs()) { for (int i = 0; i <= tot; i++) cur[i] = h[i]; flow += dfs(s, 1e18); } return flow; }
int vis[N];
//求最小割划分 voidmicut(int u){ vis[u] = 1; for (int i = h[u]; i; i = e[i].ne) { int v = e[i].v; if (!vis[v] && e[i].w) micut(v); } }
voidsolve(){ n = read(), m = read(), s = 1, t = n; for (int i = 1; i <= m; i++) { int u, v, w; u = read(), v = read(), w = read(); add(u, v, w); add(v, u, 0); } int ans1 = 0, ans2 = 0; ans1 = dinic();
for (int i = 1; i <= tot; i++) { if (i % 2 == 0) { e[i].w = e[i].w > 0 ? 1e18 : 1; } else { e[i].w = 0; } } ans2 = dinic(); write(ans1, ans2); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); // int T; // T = read(); // while (T--) solve();
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ll long long #define ull unsigned long long #define all(x) x.begin(),x.end() #define PII pair<int, int> #define x first #define y second // #define endl '\n' inlineintread(){int c;cin>>c;return c;} inlinevoidreadn(int a[], int n){ for_each(a + 1, a + n + 1, [](int &x){cin>>x;}); } inlinevoidprintn(int a[], int n){ for_each(a + 1, a + n + 1, [](int &x){ cout<<x<<' '; }); cout<<endl; } template<typename T, typename... Args> voidwrite(const T& first, const Args&... args){ cout << first; ((cout << ' ' << args), ...); cout << endl; } char out[2][10] = {"No", "Yes"}; constint N = 1e6 + 10; /* next is main_solve */ int a[N]; vector<int> e[N]; int color[N]; intdfs(int x, int col, int fa){ color[x] = col; for (auto y : e[x]) { if (y == fa) continue; if (!color[y]) { if (dfs(y, 3 - col, x)) return1; } else { if (color[y] == col) { return1; } } } return0;//是二分图,即不存在奇数环 }
vector<int> sb[3];
voidsolve(){ int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { e[i].clear(); color[i] = 0; } for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); }
for (int i = 1; i <= 2; i++) sb[i].clear();
if (dfs(1, 1, 0)) { cout << "Alice" << endl; for (int i = 1; i <= n; i++) { cout << 1 << ' ' << 2 << endl; read(), read(); } } else { for (int i = 1; i <= n; i++) sb[color[i]].push_back(i); cout << "Bob" << endl; for (int i = 1; i <= n; i++) { int x = read(), y = read(); if (x > y) swap(x, y); if (sb[1].size() && sb[2].size()) { if (x == 1) { int v = sb[1].back(); sb[1].pop_back(); cout << v << ' ' << 1 << endl; } else { int v = sb[2].back(); sb[2].pop_back(); cout << v << ' ' << 2 << endl; } } else { if (sb[1].size()) { int v = sb[1].back(); sb[1].pop_back(); if (x == 2) cout << v << ' ' << y << endl; else cout << v << ' ' << x << endl; } else { int v = sb[2].back(); sb[2].pop_back(); if (x == 1) cout << v << ' ' << y << endl; else cout << v << ' ' << x << endl; } } } } }
signedmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); int t; cin >> t; while (t--) solve(); return0; }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
intSqrt(int x){ assert(x >= 0); int t = sqrt(x); while ((t + 1) * (t + 1) <= x) t++; while (t * t > x) t--; return t; }
char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint inf = 1e18; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353;
structedge{ int v, w, ne; }e[M]; int h[N]; int tot = 1; int dep[N], cur[N]; int n, m, s, t;
voidadd(int u, int v, int w){ e[++tot] = {v, w, h[u]}; h[u] = tot; }
boolbfs(){ for (int i = 0; i <= n + m + 1; i++) dep[i] = 0; queue<int> q; q.push(s); dep[s] = 1; while (q.size()) { auto u = q.front(); q.pop(); for (int i = h[u]; i; i = e[i].ne) { int v = e[i].v; if (!dep[v] && e[i].w) { dep[v] = dep[u] + 1; q.push(v); if (v == t) returntrue; } } } returnfalse; }
intdfs(int u, int mf){ if (u == t) return mf; int sum = 0; for (int i = cur[u]; i; i = e[i].ne) { cur[u] = i; int v = e[i].v; if (dep[v] == dep[u] + 1 && e[i].w) { int f = dfs(v, min(mf, e[i].w)); e[i].w -= f; e[i ^ 1].w += f; sum += f; mf -= f; if (!mf) break; } } if (!sum) dep[u] = 0; return sum; }
intdinic(){ int flow = 0; while (bfs()) { for (int i = 0; i <= tot; i++) cur[i] = h[i]; flow += dfs(s, 1e18); } return flow; }
voidsolve(){ n = read(), m = read(); int E = read(); for (int i = 1; i <= E; i++) { int x = read(), y = read(); add(x, y + n, 1); add(y + n, x, 0); } s = 0, t = n + m + 1; for (int i = 1; i <= n; i++) { add(s, i, 1); add(i, s, 0); } for (int i = 1; i <= m; i++) { add(i + n, t, 1); add(t, i + n, 0); } print(dinic()); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); // int T; // T = read(); // while (T--) solve();
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> usingnamespace std; #define LL long long #define N 510 #define INF 1e12 int n, m; int match[N]; // 右点匹配了哪个左点 int va[N], vb[N]; // 标记是否在交替路中 LL la[N], lb[N]; // 左顶标,右顶标 LL w[N][N], d[N]; // 维护更新的delta值
booldfs(int x){ va[x] = 1; // x在交替路中 for (int y = 1; y <= n; y++) { if (!vb[y]) { if (la[x] + lb[y] - w[x][y] == 0) { // 相等子图 vb[y] = 1; // y在交替路中 if (!match[y] || dfs(match[y])) { match[y] = x; // 配对 return1; } } else// 不是相等子图则记录最小的d[y] d[y] = min(d[y], la[x] + lb[y] - w[x][y]); } } return0; } LL KM(){ // 左顶标取i的出边的最大边权 for (int i = 1; i <= n; i++) la[i] = -INF; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) la[i] = max(la[i], w[i][j]); for (int i = 1; i <= n; i++) lb[i] = 0; for (int i = 1; i <= n; i++) { while (true) { // 直到左点i找到匹配 fill(va + 1, va + n + 1, 0); fill(vb + 1, vb + n + 1, 0); fill(d + 1, d + n + 1, INF); if (dfs(i)) break; LL delta = INF; for (int j = 1; j <= n; j++) if (!vb[j]) delta = min(delta, d[j]); for (int j = 1; j <= n; j++) { // 修改顶标 if (va[j]) la[j] -= delta; if (vb[j]) lb[j] += delta; } } } LL res = 0; for (int i = 1; i <= n; i++) res += w[match[i]][i]; return res; } intmain(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) w[i][j] = -INF; for (int i = 1; i <= m; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); w[x][y] = z; } printf("%lld\n", KM()); for (int i = 1; i <= n; i++) printf("%d ", match[i]); return0; }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define PII pair<int, int> #define all x.begin(), x.end() constint N = 1e6 + 10; int a[N]; int s[N]; voidsolve(){ int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { int x; cin >> x; s[i] = s[i - 1] + x; }
int ans = -1e18; deque<int> dq; dq.push_back(0); for (int i = 1; i <= n; i++) { while (dq.size() && i - dq.front() > m) dq.pop_front(); ans = max(ans, s[i] - s[dq.front()]); while (dq.size() && s[i] <= s[dq.back()]) dq.pop_back(); dq.push_back(i); } cout << ans << '\n'; }
signedmain(){ ios::sync_with_stdio(false), cin.tie(0); // int t; cin >> t; // while (t--) solve();
#include<bits/stdc++.h> usingnamespace std; #define int long long #define PII pair<int, int> #define all x.begin(), x.end() constint N = 1e6 + 10; int dp[N]; int h[N]; voidsolve(){ int n; cin >> n; for (int i = 1; i <= n; i++) cin >> h[i]; h[0] = 1e9; vector<int> arr; arr.push_back(0); for (int i = 1; i <= n; i++) { while (arr.size() && h[i] > h[arr.back()]) arr.pop_back(); dp[i] = dp[arr.back()] + (i - arr.back()) * h[i]; arr.push_back(i); }
for (int i = 1; i <= n; i++) cout << dp[i] + 1 << ' '; }
signedmain(){ ios::sync_with_stdio(false), cin.tie(0); // int t; cin >> t; // while (t--) solve();
return0; }
并查集
路径压缩
1 2 3 4 5 6 7 8
int fa[N]; intfind(int x){ return fa[x] == x? x: fa[x] = find(fa[x]); } voidmerge(int x, int y){ x = find(x), y = find(y); if (x != y) fa[x] = y; }
按秩合并
1 2 3 4 5 6 7 8 9 10 11 12 13
int fa[N], rnk[N]; intfind(int x){ while (fa[x] ^ x) x = fa[x]; return x; } voidmerge(int x, int y){ x = find(x), y = find(y); if (x != y) { if (rnk[x] > rnk[y]) swap(x, y); fa[x] = y; if (rnk[x] == rnk[y]) rnk[y]++; } }
启发式合并
1 2 3 4 5 6 7 8 9 10 11 12 13
int fa[N], sz[N]; intfind(int x){ while (fa[x] ^ x) x = fa[x]; return x; } voidmerge(int x, int y){ x = find(x), y = find(y); if (x != y) { if (sz[x] > sz[y]) swap(x, y); fa[x] = y; sz[y] += sz[x]; } }
#include<bits/stdc++.h> usingnamespace std; #define int long long constint N = 3e5 + 10; int cnt[N]; int tr[N][26]; int idx = 1; voidinsert(string s, int k){ int p = 1; for (auto ch: s) { int x = ch - 'a'; if (!tr[p][x]) tr[p][x] = ++idx; p = tr[p][x]; cnt[p] += k; } }
// int query(string str) { // int p = 1; // for (auto ch: str) { // int x = ch - 'a'; // if (tr[p][x]) p = tr[p][x]; // else return 0; // } // return cnt[p]; // } voidsolve(){ int n; cin >> n; int ans = 0; for (int i = 1; i <= n; i++) { string s; cin >> s; int p = 1; for (auto ch: s) { int x = ch - 'a'; if (tr[p][x]) p = tr[p][x]; elsebreak; ans += cnt[p]; } insert(s, 1); } cout << ans; }
signedmain(){ ios::sync_with_stdio(false), cin.tie(0); // int t; cin >> t; // while (t--) solve();
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ll long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define pb push_back #define PII pair<int, int> #define x first #define y second #define endl '\n'
/* next is main_solve */ int n, m; int a[N]; constint lgmx = 20; int mx[N][21]; voidst(){ for (int i = 1; i <= n; i++) { mx[i][0] = a[i]; }
for (int i = 1; i <= lgmx; i++) { for (int j = 1; j <= n; j++) { mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]); } } }
intask(int l, int r){ int ans = -1e18; for (int k = r - l + 1, lg; k; k -= 1 << lg) { lg = __lg(k); ans = max(ans, mx[l][lg]); l += 1 << lg; } return ans; }
voidsolve(){ n = read(), m = read(); readn(a, n);
st();
while (m--) { int l, r; l = read(), r = read(); cout << ask(l, r) << '\n'; } } voidcloud_fly(){ // int t; // cin >> t; // while (t--) solve(); }
using ll = longlong; constint N = 5e5 + 10; int n, m; ll a[N]; int len, tot, l[N], r[N], belong[N]; ll sum[N], b[N], add[N]; voidinit(){ len = (int)sqrt(n),tot = (n + len - 1) / len; for (int i = 1; i <= tot; i++) { l[i] = r[i - 1] + 1; r[i] = i * len; } r[tot] = n; for (int i = 1; i <= tot; i++) { for (int j = l[i]; j <= r[i]; j++) { belong[j] = i; sum[i] += a[j]; } b[i] = b[i - 1] + sum[i]; } }
voidmodify(int k, int x){//单点修改 a[k] += x; sum[belong[k]] += x; for (int i = belong[k]; i <= tot; i++) b[i] += x; }
voidupdate(int L, int R, int x){//区间修改 int p = belong[L], q = belong[R]; if (p == q) { for (int i = L; i <= R; i++)a[i] += x, sum[p] += x; for (int i = p; i <= tot; i++) b[i] = b[i - 1] + sum[i]; return ; } for (int i = L; i <= r[p]; i++) a[i] += x, sum[p] += x; for (int i = p + 1; i <= q - 1; i++) add[i] += x, sum[i] += (ll)(r[i] - l[i] + 1) * x; for (int i = l[q]; i <= R; i++) a[i] += x, sum[q] += x;
for (int i = p; i <= tot; i++) b[i] = b[i - 1] + sum[i]; }
ll query(int L, int R){//区间查询 int p = belong[L], q = belong[R]; ll ans = 0; if (p == q) { for (int i = L; i <= R; i++) ans += a[i] + add[p]; return ans; } ans = b[q - 1] - b[p + 1 - 1]; for (int i = L; i <= r[p]; i++) ans += a[i] + add[p]; for (int i = l[q]; i <= R; i++) ans += a[i] + add[q]; return ans; }
#include<bits/stdc++.h> usingnamespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr); #define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++) #define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--) #define all(x) x.begin(),x.end() #define PII pair<int, int> #define x first #define y second #define ll long long #define int long long #define endl '\n' using i64 = longlong;
constint N = 2e5 + 10;
int a[N]; int arr[N]; voidsolve(){ int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) { int p; cin >> p; arr[i] = a[p]; }
priority_queue<int> q1; priority_queue<int, vector<int>, greater<>> q2; int ans = 0, cnt = 0; for (int i = n; i >= 1; i--) { int x = arr[i]; if (q2.empty() || x >= q2.top()) q2.push(x); else q1.push(x); if (n - i + 1 < i) continue; while (q2.size() > i) q1.push(q2.top()), q2.pop(); while (q2.size() < i) q2.push(q1.top()), q1.pop(); int sum = i * q2.top(); if (sum >= ans) { ans = sum; cnt = i; } } cout << ans << ' ' << cnt << '\n'; }
signedmain(){ IOS; // freopen("1.in", "r", stdin); // freopen("1.out", "w", stdout); int T; cin >> T; while (T--) solve();
return0; }
树状数组
约瑟夫问题:树状数组解决
bit[i] 这个位置辖域是 [i - lowbit(i) + 1, i]
ans += 1ll<<i后,在树状数组上tr[ans]存储的是 ans-(1ll<<i)+1 到 ans 这长度为 (1ll<<i) 位置上的和
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define pb push_back #define PII pair<int, int> #define x first #define y second #define endl '\n'
inlineintread(){ int c; cin >> c; return c; } inlinevoidreadn(int a[], int n){ for_each(a + 1, a + n + 1, [](int &x) { cin >> x; }); } inlinevoidwriten(int a[], int n){ for_each(a + 1, a + n + 1, [](int &x) { cout << x << ' '; }); cout << endl; } template <typename T, typename... Args> voidwrite(const T &first, const Args &...args){ cout << first; ((cout << ' ' << args), ...); cout << endl; } template <typename T, typename... Args> voidewrite(const T &first, const Args &...args){ cerr << '*'; cerr << first; ((cerr << ' ' << args), ...); cerr << endl; } char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint N = 2e6 + 10; constint M = N << 1; constint mod = 1e9 + 7;
int a[N]; int tr[N]; int maxn; intlowbit(int x){ return x & -x; }
voidadd(int x, int k){ for (int i = x; i < N; i += lowbit(i)) { tr[i] += k; } }
intsum(int x){ int ans = 0; for (int i = x; i; i -= lowbit(i)) { ans += tr[i]; } return ans; }
intkth(int k){ int ans = 0, now = 0; for (int i = 20; i >= 0; i--) { ans += 1ll << i; if (ans > maxn || tr[ans] + now >= k) ans -= 1ll << i; else now += tr[ans]; } return ans + 1; }
voidsolve(){ int n, k; n = read(), k = read(); maxn = n; for (int i = 1; i <= n; i++) { add(i, 1); }
int now = 1; while (n > 1) { now = (now + k - 2) % n + 1; int ans = kth(now); add(ans, -1); cout << ans << ' '; n--; } }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); // int T; // T = read(); // while (T--) solve();
#include<bits/stdc++.h> usingnamespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr); #define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++) #define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--) #define all(x) x.begin(),x.end() #define PII pair<int, int> #define x first #define y second #define ll long long #define int long long #define endl '\n' constint inf = LONG_LONG_MAX; using i64 = longlong;
constint N = 1e6; #define lc p << 1 #define rc p << 1 | 1 structTree { int l, r, mx; }tr[N * 4];
voidpushup(int p){ tr[p].mx = max(tr[lc].mx, tr[rc].mx); } voidbuild(int p, int l, int r){ tr[p] = {l, r, 0ll}; if (l == r) return ; int mid = l + r >> 1; build(lc, l, mid); build(rc, mid + 1, r); pushup(p); }
intquery(int p, int ql, int qr){ if (ql <= tr[p].l && qr >= tr[p].r) return tr[p].mx; if (ql > tr[p].r || qr < tr[p].l) return0; returnmax(query(lc, ql, qr), query(rc, ql, qr)); }
voidmodify(int p, int x, int k){ if (tr[p].l == tr[p].r && tr[p].l == x) { tr[p].mx = k; return ; } if (x <= tr[lc].r) modify(lc, x, k); if (x >= tr[rc].l) modify(rc, x, k); pushup(p); }
int dp[N]; voidsolve(){ int n, d; cin >> n >> d; build(1, 0ll, 500000ll); for (int i = 1; i <= n; i++) { int x; cin >> x; int l = max(0ll, x - d), r = min(500000ll, x + d); int t = query(1, l, r); dp[x] = t + 1; modify(1, x, dp[x]); }
int ans = 0; for (int i = 1; i <= 5e5; i++) { ans = max(ans, dp[i]); } cout << ans << '\n'; }
signedmain(){ IOS; // int T; cin >> T; // while (T--) solve(); return0; }
#define int long long constint N = 1e5 + 10; int a[N]; #define lc p << 1 #define rc p << 1 | 1 structTree { int l, r; int lsum, rsum, sum, mx; }tr[N * 4];
tr[p].add = 0; tr[p].mul = 1; } voidupdate_add(int p, int ql, int qr, int k){ if (tr[p].l > qr || tr[p].r < ql) return ; if (ql <= tr[p].l && qr >= tr[p].r) { tr[p].add = (tr[p].add + k) % mod; tr[p].sum = (tr[p].sum + (tr[p].r - tr[p].l + 1) * k) % mod; return ; } pushdown(p); int mid = tr[p].l + tr[p].r >> 1; if (ql <= mid) update_add(lc, ql, qr, k); if (qr > mid) update_add(rc, ql, qr, k); pushup(p); }
voidupdate_mul(int p, int ql, int qr, int k){ if (tr[p].l > qr || tr[p].r < ql) return ; if (ql <= tr[p].l && qr >= tr[p].r) { tr[p].mul = tr[p].mul * k % mod; tr[p].add = tr[p].add * k % mod; tr[p].sum = tr[p].sum * k % mod; return ; }
pushdown(p); int mid = tr[p].l + tr[p].r >> 1; if (ql <= mid) update_mul(lc, ql, qr, k); if (qr > mid) update_mul(rc, ql, qr, k); pushup(p); }
intquery(int p, int ql, int qr){ if (tr[p].l > qr || tr[p].r < ql) return0; if (ql <= tr[p].l && qr >= tr[p].r) return tr[p].sum % mod; pushdown(p);
int ans = 0; int mid = tr[p].l + tr[p].r >> 1; if (ql <= mid) ans += query(lc, ql, qr); if (qr > mid) ans += query(rc, ql, qr); ans %= mod; return ans; }
voidsolve(){ cin >> n >> q >> mod; for (int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n);
while (q--) { int op; cin >> op; int l, r; cin >> l >> r; if (op == 1) { int k; cin >> k; update_mul(1, l, r, k); } elseif (op == 2) { int k; cin >> k; update_add(1, l, r, k); } else { cout << query(1, l, r) << '\n'; } } }
signedmain(){ IOS; // int T; cin >> T; // while (T--) solve(); return0; }
intquery(int p, int ql, int qr){ if (tr[p].l > qr || tr[p].r < ql) return0; if (ql <= tr[p].l && qr >= tr[p].r) return tr[p].mx; int ans = 0; int mid = tr[p].l + tr[p].r >> 1; if (ql <= mid) ans = max(ans, query(lc, ql, qr)); if (qr > mid) ans = max(ans, query(rc, ql, qr)); return ans; }
intread(){ int x; scanf("%lld", &x); return x; }
char op[4]; voidsolve(){ int n, m; n = read(), m = read(); for (int i = 1; i <= n; i++) a[i] = read(); build(1, 1, n);
while (m--) { scanf("%s", op); if (op[0] == 'A') { int l, r, v; l = read(), r = read(), v = read(); update(1, l, r, v); } elseif (op[0] == 'U') { int x, v; x = read(), v = read(); modify(1, x, v); } else { int l, r; l = read(), r = read(); cout << query(1, l, r) << '\n'; } } }
signedmain(){ //IOS; // int T; cin >> T; // while (T--) solve(); return0; }
#include<bits/stdc++.h> usingnamespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr); #define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++) #define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--) #define all(x) x.begin(),x.end() #define PII pair<int, int> #define x first #define y second #define ll long long #define int long long #define endl '\n' constint inf = LONG_LONG_MAX; using i64 = longlong;
constint N = 2e5 + 10; #define lc(x) tr[x].ch[0] #define rc(x) tr[x].ch[1] structTree { int ch[2]; int s; }tr[N * 22]; int root[N]; int a[N]; int idx;
voidbuild(int &p, int l, int r){ p = ++idx; if (l == r) return ; int mid = l + r >> 1; build(lc(p), l, mid); build(rc(p), mid + 1, r); }
voidinsert(int x, int &y, int l, int r, int v){ y = ++idx; tr[y] = tr[x]; tr[y].s++; if (l == r) return ; int mid = l + r >> 1; if (v <= mid) insert(lc(x), lc(y), l, mid, v); elseinsert(rc(x), rc(y), mid + 1, r, v); }
intquery(int x, int y, int l, int r, int k){ if (l == r) return l; int mid = l + r >> 1; int sum = tr[lc(y)].s - tr[lc(x)].s; if (sum >= k) returnquery(lc(x), lc(y), l, mid, k); elsereturnquery(rc(x), rc(y), mid + 1, r, k - sum); }
int arr[N]; voidsolve(){ int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; arr[i] = a[i]; } build(root[0], 1, n);
sort(arr + 1, arr + 1 + n); for (int i = 1; i <= n; i++) { a[i] = lower_bound(arr + 1, arr + 1 + n, a[i]) - arr; }
for (int i = 1; i <= n; i++) { insert(root[i - 1], root[i], 1, n, a[i]); }
while (m--) { int l, r, k; cin >> l >> r >> k; int t = query(root[l - 1], root[r], 1, n, k); cout << arr[t] << '\n'; } }
signedmain(){ IOS; // int T; cin >> T; // while (T--) solve(); return0; }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ll long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define pb push_back #define PII pair<int, int> #define x first #define y second #define endl '\n'
voidsolve(){ int n; cin >> n; for (int i = 1; i <= n; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; L[i] = {x1, x2, y1, 1}; L[n + i] = {x1, x2, y2, -1}; X[i] = x1; X[n + i] = x2; } n *= 2; sort(L + 1, L + 1 + n, cmp); sort(X + 1, X + 1 + n); int m = unique(X + 1, X + 1 + n) - X - 1; build(1, 1, m - 1);
int ans = 0; for (int i = 1; i < n; i++) { int ql = lower_bound(X + 1, X + 1 + m, L[i].x1) - X; int qr = lower_bound(X + 1, X + 1 + m, L[i].x2) - X; update(1, ql, qr - 1, L[i].tag); ans += 1ll * tr[1].len * (L[i + 1].y - L[i].y); } cout << ans << '\n'; }
#define int long long constint N = 5e3 + 10; int X[N * 2]; structline{ int x1, x2, y, tag; booloperator< (const line t) { if (y == t.y) return tag > t.tag; return y < t.y; } }L[N * 16];
structTree{ int l, r; int cnt, len; int lcover, rcover, sum; }tr[N * 8]; #define lc p << 1 #define rc p << 1 | 1
voidbuild(int p, int l, int r){ tr[p] = {l, r, 0, 0, 0, 0, 0}; if (l == r) return ; int mid = l + r >> 1; build(lc, l, mid); build(rc, mid + 1, r); }
voidupdate(int p, int ql, int qr, int k){ if (tr[p].r < ql || tr[p].l > qr) return ; if (tr[p].l >= ql && tr[p].r <= qr) { tr[p].cnt += k; pushup(p); return ; } update(lc, ql, qr, k); update(rc, ql, qr, k); pushup(p); }
voidsolve(){ int n; cin >> n; for (int i = 1; i <= n; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; X[i] = x1; X[n + i] = x2; L[i] = {x1, x2, y1, 1}; L[n + i] = {x1, x2, y2, -1}; } n *= 2; sort(X + 1, X + 1 + n); int m = unique(X + 1, X + 1 + n) - X - 1; sort(L + 1, L + 1 + n);
build(1, 1, m - 1); int ans = 0; int lst = 0; for (int i = 1; i < n; i++) { int l = lower_bound(X + 1, X + 1 + m, L[i].x1) - X; int r = lower_bound(X + 1, X + 1 + m, L[i].x2) - X; update(1, l, r - 1, L[i].tag); ans += abs(tr[1].len - lst); lst = tr[1].len; ans += tr[1].sum * (L[i + 1].y - L[i].y); } ans += L[n].x2 - L[n].x1; cout << ans << '\n'; }
constint N = 100010; int n, m; structnode { int s[2], p, v; int size, tag; // 懒标记 voidinit(int p1, int v1){ p = p1; v = v1; size = 1; } } tr[N]; int root, idx;
voidpushup(int x){ tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1; } voidpushdown(int x){ // 下传 if (tr[x].tag) { swap(tr[x].s[0], tr[x].s[1]); tr[tr[x].s[0]].tag ^= 1; tr[tr[x].s[1]].tag ^= 1; tr[x].tag = 0; } } voidrotate(int x){ int y = tr[x].p, z = tr[y].p; int k = tr[y].s[1] == x; tr[z].s[tr[z].s[1] == y] = x; tr[x].p = z; tr[y].s[k] = tr[x].s[k ^ 1]; tr[tr[x].s[k ^ 1]].p = y; tr[x].s[k ^ 1] = y; tr[y].p = x; pushup(y), pushup(x); } voidsplay(int x, int k){ while (tr[x].p != k) { int y = tr[x].p, z = tr[y].p; if (z != k) // 折转底,直转中 (tr[y].s[0] == x) ^ (tr[z].s[0] == y) ? rotate(x) : rotate(y); rotate(x); } if (k == 0) root = x; } voidinsert(int v){ int x = root, p = 0; while (x) p = x, x = tr[x].s[v > tr[x].v]; x = ++idx; tr[p].s[v > tr[p].v] = x; tr[x].init(p, v); splay(x, 0); } intget_k(int k){ // 返回第k个节点编号 int x = root; while (1) { pushdown(x); int y = tr[x].s[0]; if (tr[y].size + 1 < k) k -= tr[y].size + 1, x = tr[x].s[1]; elseif (tr[y].size >= k) x = y; else return x; } } voidoutput(int x){ // 中序遍历输出 pushdown(x); if (tr[x].s[0]) output(tr[x].s[0]); if (tr[x].v >= 1 && tr[x].v <= n) printf("%d ", tr[x].v); if (tr[x].s[1]) output(tr[x].s[1]); } intmain(){ insert(-1e6); insert(1e6); // 哨兵 scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) insert(i); while (m--) { // 把[l,r]夹挤到l-1和r+1之间 int l, r; scanf("%d%d", &l, &r); l = get_k(l), r = get_k(r + 2); splay(l, 0); splay(r, l); tr[tr[r].s[0]].tag ^= 1; } output(root); return0; }
#include<bits/stdc++.h> usingnamespace std; int ten[15051]; // 用于存储结果的十进制数
intmain(){ string eight; // 用于存储输入的八进制数 cin >> eight; int index = 0; // 从八进制数的最低位开始处理 for (int i = eight.size() - 1; i >= 0; i--){//i是外层已经枚举到的小数位数 int num = eight[i] - '0'; // 当前处理的八进制位的数字 int j = 0; //j是每一位计算时已到达的小数位数 // 对当前位进行处理,计算其在十进制中的值,并累加到结果中 while(j < index || num ){ int d = num * 10 + (j < index ? ten[j] :0 ); // 将当前位转换为十进制,并加上之前的结果 ten[j++] = d / 8; // 计算当前位的十进制值,并存储到结果数组中 num = d % 8; // 计算余数,用于下一轮处理 } index = j; // 更新当前处理的位置 } int len = 10000; while (!ten[len]) len--; for (int i = 0; i <= len; i++) cout << ten[i];
constint N = 1e7 + 10; int A[N], B[N]; constint p = 998244353; constint g = 3, gi = 332748118; intqmi(int a, int b){ a %= p; int res=1; while(b){ if(b & 1) res = res * a % p; b >>= 1; a = a * a % p; } return res; } voidchange(int A[], int n){ int k; //0 和 最后一个不用反转 for (int i = 1, j = n / 2; i < n - 1; i++) { if (i < j) swap(A[i], A[j]);// i < j 保证只交换一次
// i 做正常的加1, j 做左反转类型的加1, 始终保持i和j是反转的 k = n / 2; while (j >= k) { j -= k; k >>= 1; } if (j < k) j += k; } } voidntt(int A[], int n, int op){ change(A, n);//位逆序变换(蝴蝶变换) for (int m = 2; m <= n; m <<= 1) {//枚举块宽 int g1 = qmi(op == 1? g : gi, (p - 1) / m); for (int i = 0; i < n; i += m) {//枚举块数 int gk = 1; for (int j = 0; j < m / 2; j++) {//枚举半块 int x = A[i + j] % p, y = gk * A[i + j + m / 2] % p; A[i + j] = (x + y) % p; A[i + j + m / 2] = (x - y + 2 * p) % p; gk = gk * g1 % p; } } } } voidsolve(){ int n, m; cin >> n >> m; for (int i = 0; i <= n; i++) cin >> A[i]; for (int i = 0; i <= m; i++) cin >> B[i];
int sum = n + m; for (m = n + m + 1, n = 1; n <= m; n <<= 1) ;
ntt(A, n, 1), ntt(B, n, 1); for (int i = 0; i < n; i++) A[i] = A[i] * B[i] % p; ntt(A, n, -1);
int inv = qmi(n, p - 2); for (int i = 0; i <= sum; i++) { cout << (A[i] * inv) % p << " " ; } }
数论
试除法判定质数
1 2 3 4 5 6 7
boolis_prime(int x){ if(x < 2) returnfalse; for(int i = 2; i <= x / i; i++) { if (x % i == 0) returnfalse; } returntrue; }
最大公约数
欧几里德算法
1 2 3
intgcd(int a, int b){ return b? gcd(b, a % b) : a; }
int x, y; intexgcd(int a, int b, int &x, int &y){//返回gcd(a,b) 并求出解(引用带回) if (b == 0) { x = 1, y = 0; return a; } int x1, y1, d; d = exgcd(b, a % b, x1, y1); x = y1, y = x1 - a / b * y1; return d; }
//如果求不定方程:a * x + b * y = c的一组整数解 int d = exgcd(a, b, x, y); if (c % d == 0) { x = c / d * x; y = c / d * y; } else { puts("无解"); }
数论分块(整除分块)
$ ∑f[i] * (k / i) $
1 2 3 4 5 6 7 8 9 10 11
int res = n * k;
for (int l = 1, r; l <= n; l = r + 1) {
if (k / l == 0) break;
r = min(k / (k / l), n);
res -= (k / l) * (r - l + 1) * (l + r) / 2;
}
欧拉函数
1 2 3 4 5 6 7 8 9 10 11
intphi(int x){ int res = x; for (int i = 2; i <= x / i; i++) { if (x % i == 0) { while (x % i == 0) x /= i; res = res / i * (i - 1); } } if (x > 1) res = res / x * (x - 1); return res; }
筛法
埃式筛
1 2 3 4 5 6 7 8
int pr[N]; voidsieve(int n){ for (int i = 2; i <= n; i++) { for (int j = i; j <= n; j += i) { if (!pr[j]) pr[j] = i; } } }
线性筛求质数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
vector<int> minp, primes; voidsieve(int n){ minp.assign(n + 1, 0); primes.clear(); for (int i = 2; i <= n; i++) { if (minp[i] == 0) { minp[i] = i; primes.push_back(i); } for (auto p: primes) { if (i * p > n) break; minp[i * p] = p; if (p == minp[i]) break; } } }
int p[N], vis[N]; int mu[N]; int tot; voidsieve(int n){ mu[1] = 1; for (int i = 2; i <= n; i++) { if (!vis[i]) { p[++tot] = i; mu[i] = -1; } for (int j = 1; i * p[j] <= n; j++) { int m = i * p[j]; vis[m] = 1; if (i % p[j] == 0) { mu[m] = 0; break; } else { mu[m] = -mu[i]; } } } }
分解质因数
1 2 3 4 5 6 7 8 9 10 11 12 13
vector<int> breakdown(int n){ vector<int> result; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { while (n % i == 0) n /= i; result.push_back(i); } } if (n != 1) { result.push_back(n); } return result; }
约数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
voidget_divisors(int n) { vector<int> res; for (int i = 1; i <= n / i; i++) { if (n % i == 0) { res.push_back(i);
if (i != n / i) { res.push_back(n / i); } } } sort(res.begin(), res.end()); for (auto item : res) { cout << item << " "; } puts(""); }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
$gcd(a, p) = 1$, $a ^ {b} \ mod \ p = a ^ {b \ mod \ φ(p)} \ mod \ p$
$gcd(a, p) != 1$ ,
若 $b < φ(p)$ , $a ^ {b} \ mod \ p = a ^ {b} \ mod \ p$ ;
若 $b >= φ(p)$ , $a ^ {b} \ mod \ p = a ^ {b \ mod \ φ(p) + φ(p)} \ mod \ p$
除法取模($gcd(a, p) = 1$)
快速幂($p$是质数)
1 2 3 4 5 6 7 8 9 10 11 12 13 14
intqmi(int a, int b, int p){ a %= p; int res=1; while (b) { if(b & 1) res = res * a % p; b >>= 1; a = a * a % p; } return res; }
intinv(int x){ returnqmi(x, mod - 2, mod); }
exgcd($p$是一般数)
1 2 3 4 5 6 7 8 9 10
voidExgcd(ll a, ll b, ll &x, ll &y){ if (!b) x = 1, y = 0$ elseExgcd(b, a % b, y, x), y -= a / b * x; } intmain(){ ll x, y; Exgcd (a, p, x, y); x = (x % p + p) % p; printf ("%d\n", x); //x是a在mod p下的逆元 }
线性同余方程
${a * x ≡ b (mod\ m) \iff a x (mod\ m) \ m ≡ b}$
当 $b = 1$时,$ x $ 为 ${a}$ 的乘法逆元
1 2 3 4 5 6 7 8 9
voidsolve(){ int d = exgcd(a, m, x, y); if (b % d == 0) { res = 1ll * x * b / d % m; } else { puts("无解"); } }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
voidprint128(__int128_t x){ if (x < 0) putchar('-'), x = -x; if (x > 9) print128(x / 10); putchar(x % 10 + '0'); }
intSqrt(int x){ assert(x >= 0); int t = sqrt(x); while ((t + 1) * (t + 1) <= x) t++; while (t * t > x) t--; return t; }
char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint inf = 1e18; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353;
intexgcd(__int128_t a, int b, int &x, int &y){ if (!b) { x = 1; y = 0; return a; } int d, x1, y1; d = exgcd(b, a % b, x1, y1); x = y1, y = x1 - a / b * y1; return d; }
int n; __int128_tcrt(int m[], int r[]){ __int128_t M = 1; __int128_t ans = 0; for (int i = 1; i <= n; i++) M *= m[i]; for (int i = 1; i <= n; i++) { __int128_t c = M / m[i]; int x, y; exgcd(c, m[i], x, y); ans = (ans + r[i] * c * x % M) % M; } return (ans % M + M) % M; }
int a[N], b[N]; voidsolve(){ n = read(); for (int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; }
__int128_t x = crt(a, b); print128(x); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); // int T = 1; // T = read(); // while (T--) solve();
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
voidprint128(__int128_t x){ if (x < 0) putchar('-'), x = -x; if (x > 9) print128(x / 10); putchar(x % 10 + '0'); }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
intSqrt(int x){ assert(x >= 0); int t = sqrt(x); while ((t + 1) * (t + 1) <= x) t++; while (t * t > x) t--; return t; }
char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint inf = 1e18; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353;
intbsgs(int a, int b, int p){ a %= p; b %= p; if (b == 1) return0; int m = ceil(sqrt(p)); int t = b; unordered_map<int, int> ump; ump[b] = 0; for (int j = 1; j < m; j++) { t = t * a % p; ump[t] = j; }
int pw = 1; for (int i = 1; i <= m; i++) pw = pw * a % p; t = 1; for (int i = 1; i <= m; i++) { t = t * pw % p; if (ump.count(t)) { return i * m - ump[t]; } } return-1; }
voidsolve(){ int p = read(), b = read(), n = read(); int ans = bsgs(b, n, p); if (~ans) print(ans); elseprint("no solution"); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); // int T = 1; // T = read(); // while (T--) solve();
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
intSqrt(int x){ assert(x >= 0); int t = sqrt(x); while ((t + 1) * (t + 1) <= x) t++; while (t * t > x) t--; return t; }
char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint inf = 1e18; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353;
intgcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); }
intexbsgs(int a, int b, int p){ a %= p, b %= p; if (b == 1or p == 1) return0; int d, k = 0, A = 1; while (true) { d = gcd(a, p); if (d == 1) break; if (b % d) return-1; k++; b /= d; p /= d; A = A * (a / d) % p; if (A == b) return k; }
int m = ceil(sqrt(p)); int t = b; unordered_map<int, int> ump; ump[b] = 0; for (int j = 1; j < m; j++) { t = t * a % p; ump[t] = j; }
int pw = 1; for (int i = 1; i <= m; i++) pw = pw * a % p; t = A; for (int i = 1; i <= m; i++) { t = t * pw % p; if (ump.count(t)) { return i * m - ump[t] + k; } } return-1; }
voidsolve(int a, int b, int p){ int ans = exbsgs(a, b, p); if (~ans) print(ans); else print("No Solution"); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); // int T = 1; // T = read(); // while (T--) while (true) { int a = read(), p = read(), b = read(); if (a + b + p == 0) break; solve(a, b, p); }
return0; }
组合数学
排列组合
组合数
$dp$
$O(n^2)$
1 2 3 4 5 6 7 8 9 10 11
constint N = 1e3 + 10; constint mod = 998244353; int C[N][N]; voidinit(){ for (int i = 0; i < N; i++) C[i][0] = 1, C[i][1] = i; for (int i = 2; i < N; i++) { for (int j = 2; j <= i; j++) { C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } } }
constint N = 1e6 + 10; constint mod = 998244353; int fac[N], invfac[N]; intqmi(int a, int b, int p){ a %= p; int res = 1; while (b) { if(b & 1) res = res * a % p; b >>= 1; a = a * a % p; } return res; } intinv(int x){ returnqmi(x, mod - 2, mod); } voidinit(){ fac[0] = invfac[0] = 1; for (int i = 1; i < N; i++) { fac[i] = fac[i - 1] * i % mod; invfac[i] = invfac[i - 1] * inv(i) % mod; } } intC(int n, int r){ if (r > n) return0; return fac[n] * invfac[r] % mod * invfac[n - r] % mod; }
#include<bits/stdc++.h> usingnamespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr) #define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++) #define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--) #define all(x) x.begin(),x.end() #define PII pair<int, int> #define x first #define y second #define ll long long #define int long long #define endl '\n' using i64 = longlong;
constint N = 1e5 + 10; int mod = 998244353; int fac[N], invfac[N]; intqmi(int a, int b, int p){ a %= p; int res = 1; while (b) { if(b & 1) res = res * a % p; b >>= 1; a = a * a % p; } return res; } intinv(int x){ returnqmi(x, mod - 2, mod); } voidinit(){ fac[0] = invfac[0] = 1; for (int i = 1; i < N; i++) { fac[i] = fac[i - 1] * i % mod; invfac[i] = invfac[i - 1] * inv(i) % mod; } } intC(int n, int r){ if (r > n) return0; return fac[n] * invfac[r] % mod * invfac[n - r] % mod; }
intLucas(int n, int r){ if (r == 0) return1; returnC(n % mod, r % mod) * Lucas(n / mod, r / mod) % mod; } voidsolve(){ int n, m, p; cin >> n >> m >> p; mod = p; init(); cout << Lucas(n + m, n) << '\n'; }
signedmain(){ IOS; int T; cin >> T; while (T--) solve();
#include<bits/stdc++.h> usingnamespace std; #define int long long #define uint unsigned long long #define ld long double #define pii pair<int,int> #define complex complex<ld> #define rand mt19937_64 #define endl '\n' #define PI (ld)(3.141592653589793) #define INF (int)(1e8+1) #define MOD (int)(998244353) #define eps (ld)(1e-9) #define P (int)(998244353) #define G (int)(3) #define mpair(x,y) make_pair(x,y) #define all(x) x.begin(),x.end() #define lowbit(x) (x&-x)
intqpow(int base, int p){ int ans = 1; while (p) { if (p & 1) ans = ans * base % P; base = base * base % P; p >>= 1; } return ans; }
intinv(int x){ returnqpow(x, P - 2); }
voidNTT(vector<int>& A, const vector<int>& R, bool rev){ int n = A.size(); for (int i = 0;i < n;++i) if (i < R[i]) swap(A[i], A[R[i]]); for (int m = 2;m <= n;m <<= 1) { int g1 = qpow(rev ? inv(G) : G, (P - 1) / m); for (int i = 0;i < n;i += m) { int gk = 1; for (int j = 0;j < m / 2;++j) { int x = A[i + j], y = A[i + j + m / 2] * gk % P; A[i + j] = (x + y) % P; A[i + j + m / 2] = (x - y + P) % P; gk = gk * g1 % P; } } } if (!rev) return; int ni = inv(n); for (auto& v : A) (v *= ni) %= P; }
vector<int> polyadjust(const vector<int>& a){ int n = 0; for (int i = a.size();i >= 0;--i) if (a[i]) { n = i;break; } vector<int> ans; ans.assign(a.begin(), a.begin() + n); return ans; }
vector<int> polymul(const vector<int>& a, const vector<int>& b){ int n = 1; while (n < a.size() + b.size()) n <<= 1; vector<int> A(n), B(n), R(n); for (int i = 0;i < n;++i) R[i] = R[i / 2] / 2 + (i & 1 ? n / 2 : 0); for (int i = 0;i < a.size();++i) A[i] = a[i]; for (int i = 0;i < b.size();++i) B[i] = b[i]; NTT(A, R, 0);NTT(B, R, 0); for (int i = 0;i < n;++i) A[i] = A[i] * B[i] % P; NTT(A, R, 1); A.resize(a.size() + b.size() - 1); return A; }
vector<int> polyinv(const vector<int>& f){ int n = 1, ni, sz = f.size(); while (n < sz) n <<= 1; vector<int> ans{ inv(f[0]) }; for (int m = 2; m <= n;m <<= 1) { vector<int> R(m << 1), a(m << 1); ans.resize(m << 1, 0); for (int i = 0;i < m << 1;++i) R[i] = R[i / 2] / 2 + (i & 1 ? m : 0); for (int i = 0;i < min(m, sz);++i) a[i] = f[i]; NTT(ans, R, 0), NTT(a, R, 0); for (int i = 0; i < m << 1; ++i) ans[i] = ans[i] * (2ll - ans[i] * a[i] % P + P) % P; NTT(ans, R, 1); ans.resize(m); } ans.resize(sz); return ans; }
vector<int> polydiff(const vector<int>& f){ int n = f.size() - 1; vector<int> ans(n); for (int i = n;i;--i) ans[i - 1] = f[i] * i % P; return ans; }
vector<int> polyinte(const vector<int>& f){ int n = f.size() + 1; vector<int> ans(n); for (int i = 0;i < n - 1;++i) ans[i + 1] = f[i] * inv(i + 1) % P; return ans; }
vector<int> polyexp(const vector<int>& f){ int n = 1, ni, sz = f.size(); while (n < sz) n <<= 1; vector<int> ans{ 1 }; for (int m = 2; m <= n;m <<= 1) { vector<int> a(m << 1); ans.resize(m << 1, 0); for (int i = 0;i < min(m, sz);++i) a[i] = f[i]; vector<int> b = polyln(ans); for (int i = 0;i < m << 1;++i) b[i] = -b[i] + a[i]; (b[0] += 1) %= P; ans = polymul(ans, b); ans.resize(m); } ans.resize(sz); return ans; }
vector<int> polypow(const vector<int>& f, int p, int sz){ vector<int> ans = polyadjust(f); ans.resize((ans.size() - 1) * p + 1); ans = polyln(ans); for (auto& v : ans) (v *= p) %= P; ans = polyexp(ans); return ans; }
constint N = 2e5 + 1;
int n, m; int p[N<<1];
vector<int> alpha, bet;
voidinit(){ p[0] = 1; for (int i = 1;i < N<<1;++i) p[i] = p[i - 1] * i % MOD;
alpha.resize(N); bet.resize(N);
for (int i = 0;i < N;++i) { alpha[i] = (i & 1 ? -1 : 1) * inv(p[i]) % P; bet[i] = qpow(i, n) * inv(p[i]) % P; }
alpha = polymul(alpha, bet); }
voidsolve(){ cin >> n >> m; init(); //1 ok cout << qpow(m, n) << endl; //2 ok 组合数 if (n > m) cout << 0 << endl; else cout << p[m] * inv(p[m - n]) % MOD << endl; //3 ok 第二类斯特林数 + 排列 cout << alpha[m] * p[m] % MOD << endl; //4 ok 第二类斯特林数 累和 int res4 = 0; for (int i = 1;i <= m;++i) res4 = (res4 + alpha[i]) % MOD; cout << res4 << endl; //5 ok 瞪眼 if (n > m) cout << 0 << endl; else cout << 1 << endl; //6 ok 第二类斯特林数 cout << alpha[m] << endl; //7 ok 隔板法 cout << p[n + m - 1] * inv(p[m - 1]) % MOD * inv(p[n]) % MOD << endl; //8 ok C(m,n) if (n > m) cout << 0 << endl; else cout << p[m] * inv(p[n]) % MOD * inv(p[m - n]) % MOD << endl; //9 ok 隔板法 if (n < m) cout << 0 << endl; else cout << p[n - 1] * inv(p[n - m]) % MOD * inv(p[m - 1]) % MOD << endl; //10 vector<int> a(n + 1); for (int i = 1;i <= m;++i) for (int j = i;j <= n;j += i) a[j] += inv(j / i); vector<int> res = polyexp(a); cout << res[n] << endl; //11 ok 瞪眼 if (n > m) cout << 0 << endl; else cout << 1 << endl; //12 if (n < m) cout << 0 << endl; else cout << res[n-m] << endl; }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
intSqrt(int x){ assert(x >= 0); int t = sqrt(x); while ((t + 1) * (t + 1) <= x) t++; while (t * t > x) t--; return t; }
char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint inf = 1e18; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353;
int c[5]; int d[5];
int dp[N]; voidinit(){ dp[0] = 1; for (int i = 0; i < 4; i++) { for (int j = c[i]; j <= 1e5; j++) { dp[j] += dp[j - c[i]]; } } } voidsolve(){ for (int i = 0; i < 4; i++) d[i] = read(); int s = read();
int ans = dp[s]; for (int i = 1; i < 16; i++) { int t = 0, sgn = 1; for (int j = 0; j < 4; j++) { if (i >> j & 1) { t += c[j] * (d[j] + 1); sgn *= -1; } } if (s >= t) ans += sgn * dp[s - t]; } print(ans); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); for (int i = 0; i < 4; i++) c[i] = read(); init(); int T = 1; T = read(); while (T--) solve();
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
structmat { int row, col; int a[4][4]; mat() { row = col = 4; memset(a, 0, sizeof a); } mat operator* (mat b) { mat c; for (int i = 0; i < row; i++) { for (int j = 0; j < b.col; j++) { for (int k = 0; k < col; k++) { c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % mod) % mod; } }s } return c; } }; mat pow(mat p, int m){ mat ans; for (int i = 0; i <= 3; i++) ans.a[i][i] = 1; while (m) { if (m & 1) ans = ans * p; m >>= 1; p = p * p; } return ans; }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define pb push_back #define PII pair<int, int> #define x first #define y second #define endl '\n'
inlineintread(){ int c; cin >> c; return c; } inlinevoidreadn(int a[], int n){ for_each(a + 1, a + n + 1, [](int &x) { cin >> x; }); } inlinevoidwriten(int a[], int n){ for_each(a + 1, a + n + 1, [](int &x) { cout << x << ' '; }); cout << endl; } template <typename T, typename... Args> voidwrite(const T &first, const Args &...args){ cout << first; ((cout << ' ' << args), ...); cout << endl; } template <typename T, typename... Args> voidewrite(const T &first, const Args &...args){ cerr << '*'; cerr << first; ((cerr << ' ' << args), ...); cerr << endl; } char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint N = 1e6 + 10; constint M = N << 1; constint mod = 1e9 + 7;
int a[N]; int b[N]; int p[N]; int d[N]; int tot = 0;
int lgmx = 30; voidinsert(int x){ for (int i = lgmx; i >= 0; i--) { if ((x >> i) & 1) { if (!p[i]) { p[i] = x; break; } x ^= p[i]; } } }
voidrebuild(){ for (int i = 0; i <= lgmx; i++) { for (int j = i - 1; j >= 0; j--) { if ((p[i] >> j) & 1) { p[i] ^= p[j]; } } } for (int i = 0; i <= lgmx; i++) { if (p[i]) d[tot++] = p[i]; } } voidsolve(){ int n; n = read();
int xa = 0, xb = 0; for (int i = 1; i <= n; i++) { a[i] = read(); xa ^= a[i]; } for (int i = 1; i <= n; i++) { b[i] = read(); xb ^= b[i]; }
tot = 0; for (int i = 0; i <= lgmx; i++) { p[i] = d[i] = 0; }
for (int i = 1; i <= n; i++) { insert(a[i] ^ b[i]); } rebuild();
int ans = max(xa, xb); for (int i = tot - 1; i >= 0; i--) { int mx = max(xa ^ d[i], xb ^ d[i]); if (mx < ans) { xa ^= d[i]; xb ^= d[i]; ans = mx; } } write(ans); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); int T; T = read(); while (T--) solve();
return0; }
逆序对
线性判定排列逆序数的奇偶性
1 2 3 4 5 6 7 8 9 10 11 12 13
intparity(const vector<int> &a){ constint n = a.size(); vector<int> vis(n); int p = n % 2; for (int i = 0; i < n; i++) { if (vis[i]) continue; for (int j = i; !vis[j]; j = a[j]) { vis[j] = 1; } p ^= 1; } return p; }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
// inline int read() { // register int x = 0, t = 1; // register char ch = getchar(); // while (ch < '0'|| ch > '9'){ // if (ch == '-') // t = -1; // ch = getchar(); // } // while (ch >= '0' && ch <= '9'){ // x = (x << 1) + (x << 3) + (ch ^ 48); // ch = getchar(); // } // return x * t; // }
intSqrt(int x){ assert(x >= 0); int t = sqrt(x); while ((t + 1) * (t + 1) <= x) t++; while (t * t > x) t--; return t; }
char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint inf = 1e18; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353;
int a[N]; int tmp[N]; int ans = 0; voidmerge(int l, int r){ if (l == r) return ; int mid = l + r >> 1; merge(l, mid); merge(mid + 1, r);
int i = l, j = mid + 1, k = l; while (i <= mid && j <= r) { if (a[i] <= a[j]) tmp[k++] = a[i++]; else { tmp[k++] = a[j++]; ans += mid - i + 1; } } while (i <= mid) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (i = l; i <= r; i++) a[i] = tmp[i]; }
voidsolve(){ int n = read(); readn(a, n); merge(1, n); print(ans); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); // int T = 1; // T = read(); // while (T--) solve();
constdouble PI = acos(-1.0); structComplex{ double x, y; Complex(double _x = 0.0, double _y = 0.0) { x = _x, y = _y; } Complex operator +(const Complex &b) const{ returnComplex(x + b.x, y + b.y); } Complex operator -(const Complex &b) const{ returnComplex(x - b.x, y - b.y); } Complex operator *(const Complex &b) const{ returnComplex(x * b.x - y * b.y, x * b.y + y * b.x); } }; Complex A[N], B[N]; voidchange(Complex A[], int n){ int k; //0 和 最后一个不用反转 for (int i = 1, j = n / 2; i < n - 1; i++) { if (i < j) swap(A[i], A[j]);// i < j 保证只交换一次
// i 做正常的加1, j 做左反转类型的加1, 始终保持i和j是反转的 k = n / 2; while (j >= k) { j -= k; k >>= 1; } if (j < k) j += k; } } voidfft(Complex A[], int n, int op){ change(A, n);//位逆序变换(蝴蝶变换) for (int m = 2; m <= n; m <<= 1) {//枚举块宽 Complex w1({cos(2 * PI / m), sin(2 * PI / m) * op}); for (int i = 0; i < n; i += m) {//枚举块数 Complex wk({1, 0}); for (int j = 0; j < m / 2; j++) {//枚举半块 Complex x = A[i + j], y = A[i + j + m / 2] * wk; A[i + j] = x + y; A[i + j + m / 2] = x - y; wk = wk * w1; } } } } char a[N], b[N]; int ans[N]; voidsolve(){ scanf("%s%s", a, b); int n = strlen(a) - 1, m = strlen(b) - 1; for (int i = 0; i <= n; i++) A[i].x = a[n - i] - '0'; for (int i = 0; i <= m; i++) B[i].x = b[m - i] - '0'; for (m = n + m, n = 1; n <= m; n <<= 1) ; fft(A, n, 1), fft(B, n, 1); for (int i = 0; i < n; i++) A[i] = A[i] * B[i]; fft(A, n, -1); int k = 0; for (int i = 0, t = 0; i < n || t; i++) { t += A[i].x / n + 0.5; ans[k++] = t % 10; t /= 10; } while (k > 1 && !ans[k - 1]) k--; for (int i = k - 1; i >= 0; i--) printf("%d", ans[i]); }
constint N = 1e7 + 10; int A[N], B[N]; constint p = 998244353; constint g = 3, gi = 332748118; intqmi(int a, int b){ a %= p; int res=1; while(b){ if(b & 1) res = res * a % p; b >>= 1; a = a * a % p; } return res; } voidchange(int A[], int n){ int k; //0 和 最后一个不用反转 for (int i = 1, j = n / 2; i < n - 1; i++) { if (i < j) swap(A[i], A[j]);// i < j 保证只交换一次
// i 做正常的加1, j 做左反转类型的加1, 始终保持i和j是反转的 k = n / 2; while (j >= k) { j -= k; k >>= 1; } if (j < k) j += k; } } voidntt(int A[], int n, int op){ change(A, n);//位逆序变换(蝴蝶变换) for (int m = 2; m <= n; m <<= 1) {//枚举块宽 int g1 = qmi(op == 1? g : gi, (p - 1) / m); for (int i = 0; i < n; i += m) {//枚举块数 int gk = 1; for (int j = 0; j < m / 2; j++) {//枚举半块 int x = A[i + j] % p, y = gk * A[i + j + m / 2] % p; A[i + j] = (x + y) % p; A[i + j + m / 2] = (x - y + 2 * p) % p; gk = gk * g1 % p; } } } } voidsolve(){ int n, m; cin >> n >> m; for (int i = 0; i <= n; i++) cin >> A[i]; for (int i = 0; i <= m; i++) cin >> B[i];
int sum = n + m; for (m = n + m + 1, n = 1; n <= m; n <<= 1) ;
ntt(A, n, 1), ntt(B, n, 1); for (int i = 0; i < n; i++) A[i] = A[i] * B[i] % p; ntt(A, n, -1);
int inv = qmi(n, p - 2); for (int i = 0; i <= sum; i++) { cout << (A[i] * inv) % p << " " ; } }
#include<bits/stdc++.h> usingnamespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr); #define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++) #define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--) #define all(x) x.begin(),x.end() #define PII pair<int, int> #define x first #define y second #define ll long long #define int long long #define endl '\n' using i64 = longlong;
int a[2010][2010]; bitset<2010> f[2010][1010];//第j列 voidsolve(){ int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } }
int ans = 0; for (int i = 1; i <= n; i++) { bitset<2010> bi; for (int j = 1; j <= m; j++) { bi ^= f[j][a[i][j]]; f[j][a[i][j]][i] = 1; } ans += bi.count(); }
cout << ans << '\n'; } signedmain(){ IOS; // int T; cin >> T; // while (T--) solve(); return0; }
#include<bits/stdc++.h> usingnamespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr); #define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++) #define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--) #define all(x) x.begin(),x.end() #define PII pair<int, int> #define x first #define y second #define ll long long #define int long long #define endl '\n' using i64 = longlong;
constint N = 1e6 + 10; bitset<N> dp[110]; voidsolve(){ int n; cin >> n; dp[0].set(0); for (int i = 1; i <= n; i++) { int l, r; cin >> l >> r; for (int j = l; j <= r; j++) { dp[i] |= (dp[i - 1] << (j * j)); } }
cout << dp[n].count(); } signedmain(){ IOS; // int T; cin >> T; // while (T--) solve(); return0; }
#include<bits/stdc++.h> usingnamespace std; #define int long long #define ull unsigned long long #define all(x) x.begin(), x.end() #define vi vector #define pb push_back #define pii pair<int, int> #define x first #define y second #define endl '\n'
char out[2][10] = {"NO", "YES"}; constdouble eps = 1e-6; constint inf = 1e18; constint N = 1e6 + 10; constint M = N << 1; constint mod = 998244353;
voidprint128(__int128 x){ if (x < 0) putchar('-'), x = -x; if (x > 9) print128(x / 10); putchar(x % 10 + '0'); }
intSqrt(int x){ assert(x >= 0); int t = sqrt(x); while ((t + 1) * (t + 1) <= x) t++; while (t * t > x) t--; return t; } int n, k; int v[N], w[N]; double a[N]; boolcmp(double x, double y){ return x > y; } boolcheck(double mid){ for (int i = 1; i <= n; i++) a[i] = w[i] - mid * v[i]; sort(a + 1, a + 1 + n, cmp); double sum = 0; for (int i = 1; i <= k; i++) { sum += a[i]; } return sum > 0; }
voidsolve(){ n = read(), k = read(); for (int i = 1; i <= n; i++) { v[i] = read(); w[i] = read(); } double l = 0, r = 1e9; while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid; }
printf("%.2lf\n", l); }
signedmain(){ ios::sync_with_stdio(false), cin.tie(nullptr); int T = 1; T = read(); while (T--) solve();
return0; }
$Dinkelbach$
Dinkelbach 算法的大概思想是每次用上一轮的答案当做新的 L 来输入,不断地迭代,直至答案收敛。
#include<bits/stdc++.h> usingnamespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr); #define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++) #define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--) #define all(x) x.begin(),x.end() #define PII pair<int, int> #define x first #define y second #define ll long long #define int long long #define endl '\n' using i64 = longlong;
constint N = 1e5 + 10; structQ{ int l, r, id; }q[N]; int B; boolcmp(Q x, Q y){ if (x.l / B != y.l / B) return x.l < y.l; return x.r < y.r; }
int a[N]; int ans[N]; int sum; int cnt[N]; voidadd(int x){ sum -= cnt[x] * cnt[x]; cnt[x]++; sum += cnt[x] * cnt[x]; } voiddel(int x){ sum -= cnt[x] * cnt[x]; cnt[x]--; sum += cnt[x] * cnt[x]; } voidsolve(){ int n, m, k; cin >> n >> m >> k; for (int i = 1; i <= n; i++) cin >> a[i];
B = sqrt(n); for (int i = 0; i < m; i++) { int l, r; cin >> l >> r; q[i] = {l, r, i}; }
sort(q, q + m, cmp); for (int i = 0, l = 1, r = 0; i < m; i++) { while (l > q[i].l) add(a[--l]); while (r < q[i].r) add(a[++r]); while (l < q[i].l) del(a[l++]); while (r > q[i].r) del(a[r--]); ans[q[i].id] = sum; }
for (int i = 0; i < m; i++) cout << ans[i] << '\n'; } signedmain(){ IOS; // int T; cin >> T; // while (T--) solve(); return0; }
#include<bits/stdc++.h> usingnamespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr); #define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++) #define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--) #define all(x) x.begin(),x.end() #define PII pair<int, int> #define x first #define y second #define ll long long #define int long long #define endl '\n' constint inf = LONG_LONG_MAX; using i64 = longlong;
constint N = 1e6 + 10; int a[N]; int mq, mr; int B; structQ{ int l,r,id,tim; booloperator<(Q &b){ if(l / B != b.l / B) return l < b.l; if(r / B != b.r / B) return r < b.r; return tim < b.tim; } }q[N]; structR{ int p,c; }R[N]; int sum,cnt[N],ans[N]; voidadd(int x){ if (!cnt[x]) sum++; cnt[x]++; }
voiddel(int x){ cnt[x]--; if (!cnt[x]) sum--; }
voidsolve(){ int n, m; cin >> n >> m; B = pow(n, 0.66); for (int i = 1; i <= n; i++) { cin >> a[i]; }
for (int i = 1; i <= m; i++) { char ch; cin >> ch; int l, r; cin >> l >> r; if (ch == 'Q') { q[++mq] = {l, r, mq, mr}; } else { R[++mr] = {l, r}; } }
sort(q + 1, q + 1 + mq); for (int i = 1, l = 1, r = 0, x = 0; i <= mq; i++) { while(l > q[i].l) add(a[--l]); while(r < q[i].r) add(a[++r]); while(l < q[i].l) del(a[l++]); while(r > q[i].r) del(a[r--]);
while (x < q[i].tim) { int p = R[++x].p; if (l <= p && p <= r) { del(a[p]); add(R[x].c); } swap(a[p], R[x].c); } while (x > q[i].tim) { int p = R[x].p; if (l <= p && p <= r) { del(a[p]); add(R[x].c); } swap(a[p], R[x--].c); } ans[q[i].id] = sum; }
for (int i = 1; i <= mq; i++) { cout << ans[i] << '\n'; } }
signedmain(){ IOS; // int T; cin >> T; // while (T--) solve(); return0; }
#include<bits/stdc++.h> usingnamespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr); #define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++) #define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--) #define all(x) x.begin(),x.end() #define PII pair<int, int> #define x first #define y second #define ll long long #define int long long #define endl '\n' constint inf = LONG_LONG_MAX; using i64 = longlong;
constint N = 1e6 + 10; int a[N], b[N]; int block[N]; int res,last,ans[N],cnt[N],c[N]; int B; structQ{ int l,r,id; booloperator<(Q &b){ if(block[l] != block[b.l])return l < b.l; return r < b.r; } }q[N];
intcalc(int l, int r){ int mx = 0; for (int i = l; i <= r; i++) c[a[i]] = 0; for (int i = l; i <= r; i++) { c[a[i]]++; mx = max(mx, c[a[i]] * b[a[i]]); } return mx; }
voidadd(int x){ cnt[x]++; res = max(res, cnt[x] * b[x]); } voidsolve(){ int n, m; cin >> n >> m; B = sqrt(n); for (int i = 1; i <= n; i++) { cin >> a[i]; b[i] = a[i]; block[i] = (i - 1) / B + 1; } int num = block[n]; sort(b + 1, b + 1 + n); for (int i = 1; i <= n; i++) { a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b; }
for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; q[i] = {l, r, i}; } sort(q + 1, q + 1 + m);
for (int i = 1, x = 1; i <= num; i++) { for (int j = 1; j <= n; j++) cnt[j] = 0; res = last = 0; int R = min(i * B, n); int l = R + 1, r = R; for ( ; block[q[x].l] == i; x++) { if (block[q[x].l] == block[q[x].r]) { ans[q[x].id] = calc(q[x].l, q[x].r); continue; } while (r < q[x].r) add(a[++r]); last = res; while (l > q[x].l) add(a[--l]); ans[q[x].id] = res; while (l <= R) cnt[a[l++]]--; res = last; } }
for (int i = 1; i <= m; i++) { cout << ans[i] << '\n'; } }
signedmain(){ IOS; // int T; cin >> T; // while (T--) solve(); return0; }
#define LL long long constint N = 200005; int head[N], to[N], ne[N], idx; voidlink(int u, int v){ // 连边 to[++idx] = v; ne[idx] = head[u]; head[u] = idx; }
int fa[N], son[N], siz[N], dep[N], top[N]; int tim, in[N], out[N], a[N << 1]; voiddfs1(int u, int f){ // 树链剖分 fa[u] = f; siz[u] = 1; dep[u] = dep[f] + 1; for (int i = head[u]; i; i = ne[i]) { int v = to[i]; if (v == f) continue; dfs1(v, u); siz[u] += siz[v]; if (siz[son[u]] < siz[v]) son[u] = v; } } voiddfs2(int u, int t){ in[u] = ++tim; // 进u时刻 a[tim] = u; // 括号序 top[u] = t; if (son[u]) dfs2(son[u], t); for (int i = head[u]; i; i = ne[i]) { int v = to[i]; if (v == fa[u] || v == son[u]) continue; dfs2(v, v); } out[u] = ++tim; // 出u时刻 a[tim] = u; // 括号序 } intLCA(int u, int v){ while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); u = fa[top[u]]; } return dep[u] < dep[v] ? u : v; }
int n, m, k, B, tot, V[N], W[N], C[N]; int pos[N], newC[N], vis[N], cnt[N]; LL ans[N], sum; structQ { int l, r, t, id, lca; booloperator<(Q &b) { if (l / B != b.l / B) return l < b.l; if (r / B != b.r / B) return r < b.r; return t < b.t; } } q[N];
voidadd(int x){ vis[x] ^= 1; // 访问x点的次数 // 一次扩展 加上贡献,两次扩展 减去贡献 if (vis[x]) sum += 1ll * W[++cnt[C[x]]] * V[C[x]]; else sum -= 1ll * W[cnt[C[x]]--] * V[C[x]]; } intmain(){ scanf("%d%d%d", &n, &m, &k); // 点,糖果种类,操作 for (int i = 1; i <= m; ++i) scanf("%d", &V[i]); // 美味 for (int i = 1; i <= n; ++i) scanf("%d", &W[i]); // 新奇 for (int i = 1, u, v; i < n; ++i) // 连边 scanf("%d%d", &u, &v), link(u, v), link(v, u); // 预处理括号序和LCA dfs1(1, 0); dfs2(1, 1); for (int i = 1; i <= n; ++i) scanf("%d", &C[i]); // 糖果类型 // 预处理操作 for (int i = 1, t = 0, Type, x, y; i <= k; ++i) { scanf("%d%d%d", &Type, &x, &y); if (Type == 1) { // 区查 int lca = LCA(x, y); q[++tot].t = t; q[tot].id = tot; if (in[x] > in[y]) swap(x, y); // 先x后y if (lca == x) { // 直链情况 q[tot].l = in[x]; q[tot].r = in[y]; } else { // 折链情况 q[tot].l = out[x]; q[tot].r = in[y]; q[tot].lca = lca; // 以便补偿 } } else { // 点修 pos[++t] = x; // 位置 newC[t] = y; // 修改值 } } // 树上带修莫队 B = pow(2 * n, 0.66); sort(q + 1, q + tot + 1); for (int i = 1, l = 1, r = 0, t = 0; i <= tot; ++i) { while (l > q[i].l) add(a[--l]); while (r < q[i].r) add(a[++r]); while (l < q[i].l) add(a[l++]); while (r > q[i].r) add(a[r--]); while (t < q[i].t) { // 时间戳变大则替换 ++t; if (vis[pos[t]]) { add(pos[t]); swap(C[pos[t]], newC[t]); // 换成修改值 add(pos[t]); } else swap(C[pos[t]], newC[t]); } while (t > q[i].t) { // 时间戳变小则还原 if (vis[pos[t]]) { add(pos[t]); swap(C[pos[t]], newC[t]); // 还原修改值 add(pos[t]); } else swap(C[pos[t]], newC[t]); t--; } ans[q[i].id] = sum; if (q[i].lca) ans[q[i].id] += // 补上lca的 1ll * W[cnt[C[q[i].lca]] + 1] * V[C[q[i].lca]]; } for (int i = 1; i <= tot; ++i) printf("%lld\n", ans[i]); }