A. Modulo Ruins the Legend
首先题目要求的是$(\sum (a_i + s + i \times d))% m $的最小值
等价于求\((\sum a_i + n\times s + \frac{n(n+1)}{2} \times d) \%m\)的最小值
令\(sum =(\sum a_i) \% m , a=n\%m,b=(\frac{n(n+1)}{2})%m\)
即求\((sum + as + bd)\%m\)的最小值
其中根据贝祖定理可得\(as+bd=k_1g_1\),其中\(g_1=\gcd(a,b)\)
所以可转化为求\((sum+k_1g_1)\%m\)的最小值
因为\(k_1g_1\equiv k_1g_1+tm(\mod m)\)
所以可转化为求\((sum+k_1g_1+tm)%m\)的最小值
其中根据贝祖定理可得\(k_1g_1+tm=k_2g_2\),其中\(g_2=\gcd(g1,m)\)
所以可以转化为求\((sum+k_2g_2)\%m\)的最小值
其中\(sum\)可以表示为\(sum = k g_2+x\)的形式
所以可以转化为求\((kg_2+x+k_2g_2)\%m=((k+k_2)g_2+x)\%m\)的最小值
因为\(g_2\)是\(m\)的因子,这一定存在\(k_2\)使得\((k+k_2)g_2\equiv 0(\mod m)\)
所以最小值就是\(res=x=sum\%g_2\),同时可以解出\(k_2=\frac{res+m-sum}{g_2}\)
所以构造一组可行的解的方法是:
先解出\(as+bd=g_1\),再解出\(k_1g_1+tm=g_2\),根据\(g_2,sum\)解出\(res,k_2\)
最小值就是\(res\),等差数列是\(s=k_1k_2s,d=k_1k_2d\),解出的\(s,d\)可能为负数,要取模为正数
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
#define int long long
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int z = x;
x = y;
y = z - y * (a / b);
return d;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
int sum = 0;
for (int i = 1, x; i <= n; i++)
cin >> x, sum = (sum + x) % m;
int a = n % m, b = (n * (n + 1) / 2) % m;
int s, d;
int g1 = exgcd(a, b, s, d);
int k1, t;
int g2 = exgcd(g1, m, k1, t);
int res = sum % g2, k2 = (res + m - sum) / g2;
s = (s * k1 % m * k2 % m + m) % m;
d = (d * k1 % m * k2 % m + m) % m;
cout << res << "\n" << s << " " << d << "\n";
return 0;
}
C. No Bug No Game
本题中相当于最多只有一种装备不全部取走,所以设状态为\(f[i][j][0/1]\)表示前\(i\)种物品,拿了\(j\)件,是否有一件没有全部取走的最大收益。转移时就类似于 01 背包,但注意如果前一种状态是不合法的则无法进行转移。因为本题的要求是除非全部都取走的情况,否则必须严格的取\(k\)件。
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
const int inf = 1e18;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m, sum = 0;
cin >> n >> m;
vector f(m + 1, vi(2, -inf));
f[0][0] = 0;
for (int i = 1, p; i <= n; i++) {
cin >> p, sum = min(sum + p, m);
vi w(p + 1);
for (int j = 1; j <= p; j++) cin >> w[j];
for (int j = m; j >= 0; j--) {
if (j - p >= 0) {
if (f[j - p][0] > -inf) f[j][0] = max(f[j][0], f[j - p][0] + w[p]);
if (f[j - p][1] > -inf) f[j][1] = max(f[j][1], f[j - p][1] + w[p]);
}
for (int k = 1; k < p; k++)
if (j - k >= 0 and f[j - k][0] > -inf) f[j][1] = max(f[j][1], f[j - k][0] + w[k]);
}
}
cout << max( f[sum][0] , f[sum][1] );
return 0;
}
D. Money Game
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
const int N = 5e7 + 5;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vector<double> ve(n);
for (int i = 0; i < n; ++i)cin >> ve[i];
double all = accumulate(ve.begin(), ve.end(), 0.0);
all /= (n + 1) * 1.0;
cout << fixed << setprecision(7) << all * 2.0 << ' ';
for (int i = 1; i < n; ++i) {
cout << fixed << setprecision(7) << all << ' ';
}
return 0;
}
F. Da Mi Lao Shi Ai Kan De
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
set<string> vis;
void solve() {
int n, f = 1;
cin >> n;
for (string s; n; n--) {
cin >> s;
if (vis.insert(s).second == false) continue;
if (s.find("bie") < s.size()) f = 0, cout << s << "\n";
}
if (f) cout << "Time to play Genshin Impact, Teacher Rice!\n";
}
i32 main() {
int TC;
for (cin >> TC; TC; TC--)
solve();
return 0;
}
K. Master of Both
我的处理方法是首先处理任意影响两个串字典序的大小的对,然后统计所有对出现的次数,在每次询问时,我们只需枚举所有逆序对,然后查看逆序对出现的次数就好了。
统计影响字典序大小对的方式就是按照顺序把串插入到字段树上,在插入过程中每个分叉口统计。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
#define int long long
using vi = vector<int>;
const int inf = 1e18;
int n;
int cnt[27][27];
struct Tire {
struct node {
vi nxt;
int val;
node() {
nxt = vi(27, -1);
val = 0;
}
};
vector<node> t;
Tire() : t(1, node()) {};
void insert(vi s) {
int pos = 0;
for (auto i: s) {
t[pos].val++;
for (int j = 0, v; j <= 26; j++) {
if (i == j) continue;
v = t[pos].nxt[j];
if (v == -1) continue;
cnt[j][i] += t[v].val;
}
if (t[pos].nxt[i] == -1)
t[pos].nxt[i] = t.size(), t.push_back(node());
pos = t[pos].nxt[i];
}
}
};
void solve() {
string s;
cin >> s;
vi vis(27);
int res = 0;
vis[0] = 1;
for (int i; auto c: s) {
i = c - 'a' + 1;
for (int j = 0; j <= 26; j++) {
if (vis[j] == 0) continue;
res += cnt[i][j];
}
vis[i] = 1;
}
cout << res << "\n";
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int TC;
cin >> n >> TC;
Tire tire;
for (string s; n; n--) {
cin >> s;
vi a;
for (auto c: s) a.push_back(c - 'a' + 1);
a.push_back(0);
tire.insert(a);
}
while (TC--) solve();
return 0;
}
标签:Contest,int,vi,sum,Regional,cin,Asia,long,using
From: https://www.cnblogs.com/PHarr/p/17879590.html