A. Grade Allocation
不难发现，将所有人的分数全都加到第一个人身上，可以使得第一个人的分数达到最大值，同时平均分数不变。而单人的分数上限为 $m$，所以最终答案为 $min(sum, m)$.
# include <iostream>
# include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
int sum = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
sum += x;
}
cout << min(sum, m) << endl;
}
return 0;
}
B. String Modification
根据题意不难发现，当选择了 $k$ 之后，那么下标 $k$ ~ $n$ 的字符会顺次出现在交换后的字符串的开头，而当 $n - k + 1$ 为偶数时，说明 $1$ ~ $k - 1$ 这段字符被翻转了偶数次，即不改变顺序，依次出现在交换后的字符串的末尾；相反，如果 $n - k + 1$ 为奇数，说明 $1$ ~ $k - 1$ 这段字符被翻转了奇数次，所以会逆序出现在交换后的字符串的末尾。
因此，我们可以枚举 $k$ 的取值，然后用 $O(n)$ 的时间构造出交换后的字符串，用其更新答案即可。由于 $t$ 组测试数据中的 $n$ 之和不超过 $n$，所以该 $O(n^2)$ 时间复杂度可以胜任此题。
# include <iostream>
# include <cstring>
# include <algorithm>
using namespace std;
const int N = 5010;
int n, k;
char str[N], bk[N], res[N], temp[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
cin >> n >> str + 1;
temp[n + 1] = '\0';
memcpy(bk, str, sizeof str);
memcpy(res, str, sizeof str);
k = 1;
for (int i = 2; i <= n; i++) {
memcpy(str, bk, sizeof str);
int pos = 1;
for (int j = i; j <= n; j++)
temp[pos++] = str[j];
if ((n - i + 1) % 2)
for (int j = i - 1; j; j--)
temp[pos++] = str[j];
else
for (int j = 1; j < i; j++)
temp[pos++] = str[j];
if (strcmp(res + 1, temp + 1) > 0) {
memcpy(res, temp, sizeof res);
k = i;
}
}
cout << res + 1 << endl << k << endl;
}
return 0;
}
C. Primitive Primes
我们先来找找两个多项式相乘之后，新的多项式的系数有什么规律。
不妨先假设：$f(x) = a_0 + a_1 x + a_2 x^2, g(x) = b_0 + b_1 x + b_2 x^2 + b_3 x^3$.
依次写出相乘后新的多项式的系数：
- $x^0: a_0 \cdot b_0$
- $x^1: a_0 \cdot b_1 + a_1 \cdot b_0$
- $x^2: a_0 \cdot b_2 + a_1 \cdot b_1 + a_2 \cdot b_0$
- $x^3: a_0 \cdot b_3 + a_1 \cdot b_2 + a_2 \cdot b_1$
- $x^4: a_1 \cdot b_3 + a_2 \cdot b_2$
- $x^5: a_2 \cdot b_3$
为了使得上述系数表达式更加美观，我们可以增加一些项：
- $x^0: a_0 \cdot b_0$
- $x^1: a_0 \cdot b_1 + a_1 \cdot b_0$
- $x^2: a_0 \cdot b_2 + a_1 \cdot b_1 + a_2 \cdot b_0$
- $x^3: a_0 \cdot b_3 + a_1 \cdot b_2 + a_2 \cdot b_1 + a_3 \cdot b_0$
- $x^4: a_0 \cdot b_4 + a_1 \cdot b_3 + a_2 \cdot b_2 + a_3 \cdot b_1 + a_4 \cdot b_0$
- $x^5: a_0 \cdot b_5 + a_1 \cdot b_4 + a_2 \cdot b_3 + a_3 \cdot b_2 + a_4 \cdot b_1 + a_5 \cdot b_0$
可以发现，新增的项的值均为 $0$，而且这个形式更加整齐，易于用代码来实现。
显然，直接枚举相乘后的多项式的每一项再通过上式求和判断的代码的时间复杂度不能达到我们的要求。那么，现在问题就转化为，我们是否可以快速判断出 $f(x) \cdot g(x)$ 后的新多项式的某一项的系数一定满足题意？
由于 $gcd(a_0, a_1, …, a_{n - 1}) = gcd(b_0, b_1, …, b_{m - 1}) = 1$
那么就一定满足 $\forall i,j(0 \leq i < n \wedge 0 \leq j < m \wedge \varphi(a_i \cdot b_j) \leq 4)$，其中 $\varphi(x)$ 为 $x$ 的约数个数。
即：$a_i \cdot b_j$ 的约数只可能在 $1, a_i, b_j, a_i \cdot b_j$ 中。
那么，对于所有的 $a_i \cdot b_j$，只要 $(p \mid a_i) \vee (p \mid b_j)$ （其中 $\mid$ 表示整除）成立，则 $p \mid (a_i \cdot b_j)$ 一定成立。
而通过上述经过美化之后的系数的求法可以发现，$f(x)$ 中 $x$ 次方数较小的会与 $g(x)$ 中 $x$ 次方数较大的相乘，那么，如果在 $f(x), g(x)$ 中分别找到最小的 $i, j$，使得 $p \nmid a_i \wedge p \nmid b_j$，那么在 $f(x) \cdot g(x)$ 后的表达式中，$x^{i + j}$ 就会以如下形式计算：
$$
x^{i + j} = a_0 \cdot b_{i + j} + a_1 \cdot b_{i + j - 1} + … + a_i \cdot b_j + … + a_{i + j - 1} \cdot b_1 + a_{i + j} \cdot b_0
$$
不难发现，上式在对 $p$ 取模之后就只剩下了 $a_i \cdot b_j$ 项，而这一项恰好不能被 $p$ 整除，所以 $i + j$ 就为我们需要寻找的答案。
由于题目保证答案一定存在，所以我们只需要在 $f(x), g(x)$ 中分别找到满足上述条件的 $i, j$，而 $i + j$ 即为最终答案。时间复杂度为 $O(n)$.
# include <iostream>
# include <cstdio>
using namespace std;
const int N = 1e6 + 5;
int n, m, p;
int a[N], b[N];
int main()
{
scanf("%d %d %d", &n, &m, &p);
for (int i = 0; i < n; i++)
scanf("%d", a + i);
for (int i = 0; i < m; i++)
scanf("%d", b + i);
int i, j;
i = j = 0;
while (a[i] % p == 0)
i++;
while (b[j] % p == 0)
j++;
printf("%d\n", i + j);
return 0;
}
D. Nash Matrix
根据题意不难发现，如果几个点的终点相同且连通，那么，从这个终点开始做一遍 $BFS$，就能确定这些点的方向。
而对于所有输入为 $(-1, -1)$ 的点，它必定会走入某个循环上，而构造一个无限循环走向的最简单的方法就是：该点走向相邻的任意 $(-1, -1)$ 点，然后该点的所有相连通的 $(-1, -1)$ 点都要尽可能走到该点上，从而实现循环，即以该点为源点跑一遍上述 $BFS$。
比如样例$2$，坐标为 $(1, 1)$ 的点可以选择向右走，而剩余所有的输入为 $(-1, -1)$ 的点都要尽可能走到坐标 (1, 1)。就可以得到下述走法：
D L L
U X U
U L L
注：坐标为 $(1, 1), (3, 3)$ 的点的走向与代码中对四个方向的枚举顺序有关。
可以发现，一定存在一种循环可以由上述方式构造出来。
所以，在处理完上述的所有情况之后，无解就等价于该 $n \cdot n$ 的地图上仍有位置的走向不确定。否则，直接输出整张地图即可。时间复杂度 $O(n^2)$.
# include <iostream>
# include <cstdio>
# include <cstring>
# include <queue>
# include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3 + 5;
const int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
const char opt[4] = { 'U', 'D', 'L', 'R' }, ropt[4] = { 'D', 'U', 'R', 'L' };
int n;
PII F[N][N];
char str[N][N];
queue<PII> q;
bool check(int a, int b, int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= n && !str[x][y] && F[x][y] == F[a][b];
}
void bfs()
{
while (!q.empty()) {
int a = q.front().first, b = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int x = a + dx[i], y = b + dy[i];
if (check(a, b, x, y)) {
str[x][y] = ropt[i];
q.push({ x, y });
}
}
}
return;
}
void draw(int a, int b)
{
for (int i = 0; i < 4; i++) {
int x = a + dx[i], y = b + dy[i];
if (check(a, b, x, y)) {
str[a][b] = opt[i];
q.push({ a, b });
bfs();
break;
}
}
return;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
scanf("%d %d", &F[i][j].first, &F[i][j].second);
if (F[i][j] == make_pair(i, j)) {
str[i][j] = 'X';
q.push(F[i][j]);
}
}
bfs();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (F[i][j] == make_pair(-1, -1) && !str[i][j])
draw(i, j);
bool success = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
if (!str[i][j]) {
success = false;
break;
}
if (!success)
break;
}
if (success) {
printf("VALID\n");
for (int i = 1; i <= n; i++)
printf("%s\n", str[i] + 1);
}
else
printf("INVALID\n");
return 0;
}
E. Team Building
假设此题不需要选择观众，那么可以用简单的状压$dp$来做。
我们来考虑 $dp[i][j]$，其中 $j$ 是一个二进制数，那么它表示为：只考虑前 $i$ 个人的情况下，二进制数 $j$ 中为 $1$ 的位置已经选好了队员的集合。该集合的属性为俱乐部实力的最大值。
接下来我们考虑如何进行状态转移，假设当前枚举的状态为 $dp[i][j]$，其中 $j$ 的第 $k$ 位为 $1$，那么根据状态的定义，它就可以从只考虑前 $i - 1$ 个人的情况下，将 $j$ 的第 $k$ 位变为 $0$ 的队员选择的集合转移过来，即：
$$
dp[i][j] = max(dp[i][j], dp[i - 1][j \wedge (1 << k)] + score[i][k])
$$
当然，只有在 $dp[i - 1][j \wedge (1 << k)]$ 这个状态是合法的时候才能转移（下文的状态转移均在转移方程的前驱合法的条件下进行）。
接下来，我们加上选择观众这个条件。由于观众也可以增加俱乐部的实力，如果选择当前这个人作为观众，对于 $dp[i][j]$，就应该先从 $dp[i - 1][j] + audience[i]$ 转移，再进行上文的操作。
如果没有选择观众人数的限制的话，上文的分析即可解决问题。
现要求选择 $K$ 名观众，一个直观的贪心就是从不是队员的剩余人中选择增加的实力值最大的 $K$ 名。
我们可以先根据每个人作为观众所增加的实力排个序，当然，如果直接对于 $audience$ 这个数组排序，就会混乱 $score$ 中所存储的对应值，所以，我们单独存一下下标，将下标根据各自对应的 $audience$ 值排序。此时对于枚举到的第 $i$ 个人，其实用的是作为观众所增加的实力的第 $i$ 大的人进行上述操作，假设这个下标表示为 $id$，则上文的两个转移方程就就变为：
$$
dp[i][j] = dp[i - 1][j] + audience[id]
$$
$$
dp[i][j] = max(dp[i][j], dp[i - 1][j \wedge (1 << k)] + score[id][k])
$$
此时，根据枚举到的 $i$ 以及 $j$ 中 $1$ 的个数，就可以计算出在前 $i - 1$ 个人中，非参赛队员的人数 $c$，由于我们是根据 $audience$ 值从大到小枚举的每个人，所以应该优先从这 $c$ 个人里面选观众，即：
若 $c < K$，则当前枚举的人可以作为观众；否则，观众人数已满。用公式来表示如下：
$$
dp[i][j] = dp[i - 1][j] + (c < K \ ? \ audience[id] : 0)
$$
至此，我们就能解决此题，时间复杂度为 $O(n \cdot 2^p \cdot p)$.
最终答案即为 $dp[n][(1 << p) - 1]$.
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5, M = 7;
int n, p, k;
int a[N], s[N][M], idx[N];
LL dp[N][1 << M];
bool mycmp(int i, int j)
{
return a[i] > a[j];
}
int main()
{
scanf("%d %d %d", &n, &p, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
idx[i] = i;
}
for (int i = 1; i <= n; i++)
for (int j = 0; j < p; j++)
scanf("%d", s[i] + j);
sort(idx + 1, idx + n + 1, mycmp);
memset(dp, -1, sizeof dp);
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
int id = idx[i];
for (int j = 0; j < 1 << p; j++) {
int c = 0;
for (int k = 0; k < p; k++)
if (j >> k & 1)
c++;
c = i - 1 - c;
if (dp[i - 1][j] != -1)
dp[i][j] = dp[i - 1][j] + (c < k ? a[id] : 0);
for (int k = 0; k < p; k++)
if (j >> k & 1 && dp[i - 1][j ^ (1 << k)] != -1)
dp[i][j] = max(dp[i][j], dp[i - 1][j ^ (1 << k)] + s[id][k]);
}
}
printf("%lld\n", dp[n][(1 << p) - 1]);
return 0;
}
F. Battalion Strength
下文的 $a_i$ 即为题目中所述的 $p_i$（个人用喜欢用 $a$ 来分析hh）
对于任意的 $a_i, a_j (i < j)$，那么 $a_i \cdot a_j$ 不会作为乘积出现的情况数量如下：
$$
\sum_{k = 0}^{j - i + 1}C_{j - i + 1}^{k} = 2^{j - i + 1}
$$
即：至少存在一个 $k$，使得 $i \leq k \leq j$.
那么该期望值为：
$$
a_i \cdot a_j \cdot \frac{2^{n - (j - i + 1)}}{2^n} = a_i \cdot a_j \cdot \frac{1}{2^{j - i + 1}}
$$
将上式稍加更改：
$$
a_i \cdot 2^{i - 1} \cdot \frac{a_j}{2^j}
$$
那么，此题答案就可以两重循环计算：
$$
res = \sum_{i = 1}^{n}\sum_{j = i + 1}^{n}{a_i \cdot 2^{i - 1} \cdot \frac{a_j}{2^j}}
$$
显然，这个 $O(n^2)$ 的时间复杂度会 $TLE$.
不难发现，上式可以通过先求一个前缀或者后缀来优化，即：
$$
pre_i = \sum_{k = 1}^{i}{a_k \cdot 2^{k - 1}}
$$
$$
suf_j = \sum_{k = j}^{n}{\frac{a_k}{2^k}}
$$
此时，上述二重循环可以简化为：
$$
res = \sum_{j = 1}^{n}{pre_{j - 1} \cdot \frac{a_j}{2_j}} = \sum_{i = 1}^{n}{a_i \cdot 2^{i - 1} \cdot suf_{i + 1}}
$$
由于题目还要求了一个修改操作，再根据上文的分析可以大胆猜测一下，如果已经有了子区间的 $pre, suf$，是否可以得到当前整个区间的 $res?$ 即：是否可以用线段树来维护？
我们先来考虑线段树中需要维护哪些值：已知需要 $res, pre, suf$，由于上文的求值还涉及了 $n$，即区间大小，所以还需要维护一个 $cnt$：该区间内有值的点的个数。
根据题意可以发现此题是单点更新，所以只需要考虑如何用子区间的信息来更新当前区间的信息即可：
$$
cnt = l\_cnt + r\_cnt
$$
$$
res = l\_res + r\_res + \frac{l\_pre \cdot r\_suf}{2^{l\_cnt}}
$$
$$
pre = l\_pre + r\_pre \cdot 2^{l\_cnt}
$$
$$
suf = l\_suf + \frac{r\_suf}{2^{l\_cnt}}
$$
上述即为更新方式，现在来简单说明一下如何推得的这些公式：
- $cnt:$ 子区间的数量之和。
- $res:$ 首先，两段子区间各自内部的 $res$ 需要累加上，其次，对于跨区间的两个数，我们可以用以下方式计算：$\sum_{i = 1}^{r\_cnt}{l\_pre \cdot \frac{a_i}{2^i \cdot 2^{l\_cnt}}}$(即：考虑左半区间的 $pre$ 和右半区间的每个数 $a_i$ 对答案的贡献)；再利用右半区间的 $suf$ 值，这个公式就可以转化为：$\frac{l\_pre \cdot r\_suf}{2^{l\_cnt}}$.
- $pre:$ 左半区间的 $pre$ 可以直接加上，而右半区间的 $pre$ 需要乘上一个 $2^{l\_cnt}$ 才能转化为一整段区间。
- $suf:$ 左半区间的 $suf$ 可以直接加上，而右半区间的 $suf$ 需要除以一个 $2^{l\_cnt}$ 才能转化为一整段区间。
至此，可以由两段子区间更新当前区间，剩余的问题就是如何建立线段树，以及如何单点更新。
由于 $a_i, a_j$ 需要有序，所以我们可以将数组先排个序离散化，将离散化后的值建立线段树。而更新操作即为：先将原值所对应的位置更改为 $0$，同时将更新的值所对应的位置更改为更新的值。由此可以发现，虽然需要离散化，但是跟一般的离散化不同，这里不需要去重，只需要将用到的值排个序即可，然后对于某个值，用过了当前位置，就使其对应的位置 $+1$.（这里不太好理解，蒟蒻也不知道咋更好的表述，详情请看代码 $Orz$）
还有一点需要提的就是，本题需要取模，而更新的过程中频繁用到了 $2$ 的几次方以及其对应的逆元，所以我们需要事先预处理一遍，否则此题会因为大量的重复计算使时间复杂度多了一个 $log$ 而 $TLE$.
# include <iostream>
# include <cstdio>
# include <cstring>
# include <vector>
# include <unordered_map>
# include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 6e5 + 5, mod = 1e9 + 7;
int n;
int a[N], p[N];
LL X[N], Y[N];
PII q[N];
unordered_map<int, int> idx;
vector<int> nums;
struct segment_tree {
int l, r;
LL cnt, res, pre, suf;
}T[N << 2];
LL quickpow(LL a, LL b)
{
LL res = 1;
while (b) {
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void update(int p)
{
int lp = p << 1, rp = lp | 1;
LL x = X[T[lp].cnt], y = Y[T[lp].cnt];
T[p].cnt = T[lp].cnt + T[rp].cnt;
T[p].res = (T[lp].res + T[rp].res + T[lp].pre * T[rp].suf % mod * y % mod) % mod;
T[p].pre = (T[lp].pre + T[rp].pre * x % mod) % mod;
T[p].suf = (T[lp].suf + T[rp].suf * y % mod) % mod;
return;
}
void build(int p, int l, int r)
{
T[p].l = l, T[p].r = r;
if (l == r)
return;
int mid = l + r >> 1, lp = p << 1, rp = lp | 1;
build(lp, l, mid);
build(rp, mid + 1, r);
return;
}
void change(int p, int pos, int x)
{
if (T[p].l == T[p].r) {
if (x) {
T[p].cnt = 1;
T[p].res = 0;
T[p].pre = x;
T[p].suf = x * Y[1] % mod;
}
else
T[p].cnt = T[p].res = T[p].pre = T[p].suf = 0;
return;
}
int mid = T[p].l + T[p].r >> 1, lp = p << 1, rp = lp | 1;
if (pos <= mid)
change(lp, pos, x);
else
change(rp, pos, x);
update(p);
return;
}
int main()
{
for (int i = 0; i < N; i++) {
X[i] = quickpow(2, i);
Y[i] = quickpow(X[i], mod - 2);
}
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
nums.push_back(a[i]);
}
int Q;
scanf("%d", &Q);
for (int i = 1; i <= Q; i++) {
scanf("%d %d", &q[i].first, &q[i].second);
nums.push_back(q[i].second);
}
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
if (!idx[nums[i]])
idx[nums[i]] = i + 1; // 这个值对应的起始的离散化后的下标
build(1, 1, nums.size());
for (int i = 1; i <= n; i++)
change(1, p[i] = idx[a[i]]++, a[i]); // 更改当前的 p[i] 所存储的下标，同时更新 idx
printf("%lld\n", T[1].res);
for (int i = 1; i <= Q; i++) {
int pos = q[i].first, x = q[i].second;
change(1, p[pos], 0); // 原位置更改为 0
change(1, p[pos] = idx[x]++, x); // 更改当前的 p[i] 所存储的下标，同时更新 idx
printf("%lld\n", T[1].res);
}
return 0;
}
%%%