A. Modulo Ruins the Legend
\[求s、d,使\sum a_i +sn+d\frac{n(n+1)}{2} \ (\bmod m)最小\\ 设sum = \sum a_i\ (\bmod m),t=gcd(n,\frac{n(n+1)}{2})\\ 原式=sum+kt\ (\bmod m)\\ 这时还不能求最小值,因为t和m没啥关系,可以添项\\ sum+kt\ (\bmod m) \Leftrightarrow sum+kt+pm\ (\bmod m)\\ 再做一步扩欧,设g=gcd(t,m)\\ 原式=sum+qg\ (\bmod m)\\ g\ |\ m,循环节的长度是m/g\\ 当q=\left \lceil \frac{m-sum}{g} \right \rceil时原式最小 \]LL exgcd(LL a, LL b, LL &x, LL &y) {
if (!b) {
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
void work() {
LL n, m;
cin >> n >> m;
LL sum = 0;
rep (i, 1, n) {
LL x;
cin >> x;
sum = (sum + x) % m;
}
LL x_s, y_d;
LL t = exgcd(n, n * (n + 1) / 2, x_s, y_d);
LL x_k, y_p;
LL g = exgcd(t, m, x_k, y_p);
LL q = (m - sum + g - 1) / g;
LL s = q * x_k % m * x_s % m, d = q * x_k % m * y_d % m;
cout << (q * g + sum) % m << endl;
cout << (s + m) % m << " " << (d + m) % m << endl;
}
C. No Bug No Game
\[状态表示:dp[i][j][0/1],表示从前i个物品中选,体积为j,是否完全选择的最大值\\ 状态转移:分别为第i个物品不选,完全选择第i个物品,不完全选择第i个物品。因为不完全选择至多一次,所以不完全只能从完全转移。\\ 初始状态:dp[i][j][0/1] = -inf,dp[0][0][0]=0\\ \]int n, k, s;
int p[N][11], dp[N][N][2]; // dp[i][j][0/1]:从前i个物品中选,体积为j,是否完全的最大值
void work() {
cin >> n >> k;
rep (i, 1, n) {
cin >> p[i][0];
s += p[i][0];
rep (j, 1, p[i][0]) cin >> p[i][j];
}
memset(dp, -0x3f, sizeof dp);
dp[0][0][0] = 0;
rep (i, 1, n) {
rep (j, 0, k) {
//不选第i个物品
dp[i][j][0] = dp[i - 1][j][0];
dp[i][j][1] = dp[i - 1][j][1];
//完全选择第i个物品
if (p[i][0] <= j) {
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - p[i][0]][0] + p[i][p[i][0]]); //完全更新完全
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - p[i][0]][1] + p[i][p[i][0]]); //完全更新不完全
}
//不完全选择第i个物品
rep (t, 1, p[i][0] - 1) {
if (t <= j) dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - t][0] + p[i][t]); //不完全更新完全
else break;
}
}
}
if (s <= k) cout << dp[n][s][0] << endl;
else cout << max(dp[n][k][0], dp[n][k][1]) << endl;
}
K. Master of Both
\[不论字母表怎么变,比较两个字符串的相应字母是不会变的,可以用字典树把所有字母对个数预处理出来,在字母表上求出对应的贡献即可 \]#define int long long
int n, q;
int son[N][30], cnt[N][30], idx = 1;
int mp[26][26], ex;
void insert(string s){
int cur = 0;
for (int i = 0; i < s.length(); i++) {
if (!son[cur][s[i] - 'a']) son[cur][s[i] - 'a'] = idx++;
rep (j, 0, 25) {
if (j == s[i] - 'a') continue;
mp[s[i] - 'a'][j] += cnt[cur][j];
}
cnt[cur][s[i] - 'a']++;
cur = son[cur][s[i] - 'a'];
}
rep (i, 0, 25) ex += cnt[cur][i];
}
void work() {
cin >> n >> q;
rep (i, 1, n) {
string s;
cin >> s;
insert(s);
}
rep (i, 1, q) {
string s;
cin >> s;
int res = ex;
rep (i, 0, 25) rep (j, i + 1, 25) res += mp[s[i] - 'a'][s[j] - 'a'];
cout << res << endl;
}
}
标签:cur,rep,int,题解,sum,2022icpc,铜牌,LL,dp
From: https://www.cnblogs.com/xhy666/p/16975726.html