ARC169
前言
学校晚饭后不让来机房，时间卡的很死。基本赶不上赛时 AtCoder，更不能谈 codeforces 了。这就导致到现在一场 ARC 没参加过。
于是今天 VP 了一下，A题很水十分钟碾过去了，B题先想到了一个假贪心，答题思路不变稍微改改改成 dp 就可以了。C 题写的比B还快，比较套路，一眼 dp。D 题卡住了，后来找性质写过去了。E 题一个点也不会。上网上搜题解，发现一个很神奇的是 MrcFrst，樱雪喵，Aigony 三位的文字题解描述一模一样，代码也差不多......搜来搜去都是这么做的，而且都讲的不大清楚。中间还有些变量名跟题解讲解对不上问题。后来搞 F 题也是一眼没思路。乱搞了一个小时后过不了样例，看完题解有了大致思路，写完之后过了，但我认为这个是个结论题，跟建不建造笛卡尔树有关系吗......反正我没建，不知道。
[ARC169A] Please Sign
传送门link
考虑贪心，由于会重复许多次，显然 \(depth\) 最大的答案对最终状态影响最大，所以只需要分别求出每层的权值总和即可。如果当前层结果为 1，就往上走。直到出现不等于零或者到了第一层仍然等于零即可。
复杂度 \(O(n)\)
int n;
int a[N], d[N];
int s[N];
int max_depth;
signed main()
{
cin >> n;
for (rint i = 1; i <= n; i++) cin >> a[i];
d[1] = 1;
s[1] = a[1];
for (rint i = 2; i <= n; i++)
{
int x;
cin >> x;
d[i] = d[x] + 1;
s[d[i]] += a[i];
max_depth = max(max_depth, d[i]);
}
for (rint i = max_depth; i >= 1; i--)
{
if (s[i] < 0)
{
cout << "-" << endl;
return 0;
}
if (s[i] > 0)
{
cout << "+" << endl;
return 0;
}
}
cout << 0 << endl;
return 0;
}
[ARC169B] Subsegments
传送门link
第一眼想到的是求和然后除以 \(x\)，最后判一下用不用 \(+1\)。但这个显然是假的，考虑 dp。设 \(f_{i}\) 为所有以 \(i\) 为结尾的连续子序列对答案的贡献值之和，则可得答案为 \(\sum^{n}_{i=1} f_{i}\)
若 \(\sum^{i}_{j=1} a_{j} \le s\)，那么所有以 \(i\) 为结尾的连续子序列都不用被分割，所以 \(f_{i} = i\)。
若 \(\sum^{i}_{j=1} a_{j} > s\)，那么以 \(i\) 为结尾的连续子序列需要被分割，则需要找到一个在 \(i\) 之前的下标 \(x\)，使得在 \(\sum^{i}_{j=x+1} a_{j} \le s\) 时，\(\sum^{i}_{j=x+1} a_{j}\) 最大
此时所有 \([t,i]~(1 \le t \le x)\) 的序列被分成了两部分，一部分为 \((x,i]\)，还有后面的 \([t,x]\)，而这段区间可能还需要分割，那么此时有子问题为求所有以 \(x\) 为结尾的连续子序列对答案的贡献值之和，即为 \(f_{x}\)
状态转移方程为 \(f_{i} = i + f_{x}\)。
求 \(x\) 可以用二分，因为前缀和一定是单调的。
复杂度为 \(O(n\log n)\)
int n, S;
int a[N], f[N];
int s[N];
int ans;
signed main()
{
cin >> n >> S;
for (rint i = 1; i <= n; i++)
{
cin >> a[i];
s[i] = s[i - 1] + a[i];
int x = lower_bound(s, s + i, s[i] - S) - s;
f[i]= f[x] + i;
}
for (rint i = 1; i <= n; i++) ans += f[i];
cout << ans << endl;
return 0;
}
[ARC169C] Not So Consecutive
传送门link
设 \(f_{i,j}\) 表示填了前 \(i\) 个位置，最后填了一个 \(j\) 的连续段
枚举连续段起点 \(k\)，满足 \([k,i]\) 里面没有已经被确定为其他数 \(\neq j\) 的数。记录 \(pos\) 存每个颜色最后出现的位置，每次到了一个被确定的位置就更新，然后对所有 \(pos\) 求最大值 \(maxx1\) 和次大值 \(maxx2\)，如果 \(a_{mx1}=j\)，那么那么 \(k\) 最远可以到 \(maxx2\)，否则可以到 \(maxx1\)。为了满足题目的限制，还需要对 \(i-j\) 取一个 \(max\)，最远可以取到的位置记为 \(l\).
转移方程为 \(f_{i,j}=\sum_{k=pos}^{i-1}\sum_{col\neq j} f_{k,col}\)
容斥一下 \(f_{i,j}=\sum_{k=pos}^{i-1}\sum_{col=1}^{n}f_{k,col}-\sum_{k=pos}^{i-1}f_{k,j}\)
前缀和优化掉，复杂度 \(O(n^2)\)
int n;
int a[N], pos[N];
int f[N][N];
int s[N][N], S[N];
signed main()
{
cin >> n;
for (rint i = 1; i <= n; i++) cin >> a[i];
f[0][0] = S[0] = 1;
for (rint i = 1; i <= n; i++)
{
if (a[i] != -1) pos[a[i]] = i;
int maxx1 = 0, maxx2 = 0;
for (rint j = 1; j <= n; j++)
{
if (pos[j] > maxx1)
{
maxx2 = maxx1;
maxx1 = pos[j];
}
else
{
maxx2 = max(maxx2, pos[j]);
}
}
for (rint j = 1; j <= n; j++)
{
int l, t = i - j;
if (a[maxx1] == j) l = max(t, maxx2);
else l = max(t, maxx1);
int d1 = l ? S[l - 1] : 0;
int d2 = l ? s[l - 1][j] : 0;
f[i][j] = (S[i - 1] - d1 + mod - (s[i - 1][j] - d2 + mod) + mod) % mod;
s[i][j] = (s[i - 1][j] + f[i][j]) % mod;
S[i] += f[i][j];
}
S[i] = (S[i] + S[i - 1]) % mod;
}
cout << (S[n] - S[n - 1] + mod) % mod << endl;
return 0;
}
[ARC169D] Add to Make a Permutation
传送门link
对于这种题显然地要去找性质。
操作本质就是选 \(m\) 个数加一，最后全部 \(mod\ n\)。记最后得到的未取模的序列为 \(b\)。那么 \(b\) 需要满足以下条件，显然有 \(b_i > a_i\) ，\(b_i\mod n\) 之后两两不相同。
但是我们需要观察更多的性质，即使一个很显然的性质也要写出来，有：
如果 \(sum=\sum_{i=1}^n (b_i-a_i)\)，那么一定 \(m|sum\)
如果 \(maxx=\max_{i=1}^n\{b_i-a_i\}\) ,那么一定 \(maxx\le \frac{sum}{m}\)
当操作数一定时，应尽量小才更有可能满足条件，又因为此时一定，所以每个位置加的量应该尽量均匀的去分配。把升序排序，那么操作完之后的序列也应是升序的，若有解，那么一定存在一种最优解形如 \(b=\{x,x+1,x+2,\dots,x+n-1\}\)
找最优解，即最小化 \(x\) 的值。显然有 \(x\) 下界 \(\max_{i=1}^n\{a_i-i+1\}\)
由于上面的第二个性质，\(x\) 每增加 \(1\)，不等式左边增加 \(1\)，右边增加 \(\frac{n}{m}\)，又因为 \(m\lt n\)，所以 \(\frac{n}{m}\gt 1\)，因此它也为 \(x\) 提供了一个下界。
最后满足以上第一个性质，发现 \(x\) 与 \(x+m\) 对这个条件而言是等价的，并且后者答案更劣。所以只需从 \(x\) 开始往上枚举 \(m\) 次到 \(x+m-1\) 即可。
复杂度 \(O(n)\)
int n, m;
int a[N];
int x, sum, maxx;
int lcm(int a, int b) {return a * b / gcd(a, b);}
signed main()
{
cin >> n >> m;
for (rint i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
for (rint i = 0; i < n; i++) x = max(x, a[i] - i);
for (rint i = 0; i < n; i++) sum += x + i - a[i];
bool flag = 0;
for (rint i = 0; i < m; i++)
{
if (!((sum + n * i) % m))
{
flag = 1;
x += i;
sum += n * i;
break;
}
}
if (!flag)
{
puts("-1");
return 0;
}
for (rint i = 0; i < n; i++)
{
maxx = max(maxx, x + i - a[i]);
}
while (maxx > sum / m)
{
maxx += m / gcd(n, m);
sum += lcm(n, m);
}
cout << sum / m << endl;
return 0;
}
[ARC169E] Avoid Boring Matches
传送门link
显然有 \(\texttt{R}\) 比 \(\texttt{B}\) 多一定无解。
怎样有解？换成 \(\texttt{BBBB...RRR}\) 的形式，一定有解。
考虑一个合法串“至少”应该是怎样，即找到一个“合法的最低标准”，那么我们考虑在构造合法解的同时让 \(\texttt{B}\) 的数量尽量少（刚好一半），并且位置尽量靠后。
所以，大体策略如下，从左到右考虑每个 \(\texttt{B}\)，将它和右边第一个未被配对的 \(\texttt{R}\) 配对。最终将所有剩下未配对的数两两配对。
设 \(t_i\) 表示长度为 \(2^i\)，且所有 \(\texttt{B}\) 尽可能靠右的合法解。
令 \(t_0=\texttt{R}\)
考虑从 \(t_{i-1}\) 转移 \(t_i\)，依次考虑 \(t_{i-1}\) 的每一位：如果为 \(\texttt{R}\) 说明没有匹配，就在 \(t_i\) 后面接上 \(\texttt{R}\)；如果为 \(\texttt{B}\)，那么我们要使得下一个 \(\texttt{B}\) 尽量靠后，就要在此处多放一个 R 直接与它配对，这样就可以多占一个位置，使得下一个 \(\texttt{B}\) 尽量靠后，即在 \(t_i\) 后面接上 \(\texttt{BR}\)。设 \(t_n\) 的第 \(j\) 个 \(\texttt{B}\) 的位置为 \(T_j\)，原序列位置为 \(S_j\)。那么若存在 \(S_j>T_j\)，则该序列不合法。证明大概是如果一个 \(S_j<T_j\)，匹配数不会变多。但如果 \(S_j >T_j\)，\(\texttt{BR}\) 的匹配数一定减少。
答案是令 \(S\) 满足上述条件的最小操作次数， \(\sum\limits_{j=1}^{2^n} \max(0,T_j-S_j)\)。
复杂度 \(\mathcal{O}(2^n)\)
int n;
string s, t[N];
int idx;
int pos[N];
int ans;
signed main()
{
cin >> n >> s;
t[0] = "R";
for (rint i = 1; i <= n; i++)
{
//从左到右预处理 t[i - 1] 的每一位
//转移到 t[i]
for (auto c : t[i - 1])
{
if (c == 'R') t[i] += "R";
else t[i] += "BR";
}
while ((int)t[i].size() < (1 << i)) t[i] += "B";
}
for (rint i = 0; i < (1 << n); i++)
{
if (t[n][i] == 'B')
{
pos[++idx] = i;
}
}
idx = 0;
for (rint i = 0; i < (1 << n); i++)
{
if (s[i] == 'B')
{
idx++;
if (i > pos[idx]) ans += i - pos[idx];
if (idx == (1 << (n - 1))) break;
}
}
if (idx < (1 << (n - 1)))
{
cout << -1 << endl;
return 0;
}
cout << ans << endl;
return 0;
}
[ARC169F] Large DP Table
传送门link
考虑算 \(X\) 带来的贡献，则 \(Y\) 类似。分析一下算 \(f(i,j)\) 的过程，其实就是把 \([1,i]\) 的后缀最大值拉出来。枚举 \(i\) ，考虑其中一个数 \(k\) 的贡献，发现这里就是找到第一个 \(B_t < A_k\)，然后答案加上 \((X_k-X_{fa_k})(j-t+1)\) 。换成枚举 \(k\) ，设 \(Q_k\)，则 \(k\) 的系数是 \((X_k-X_{fa_k})(Q_k-k)\)，令\(c_i=[B_i\geq A_k]\) ，则再乘上 \(1\) 构成的连续段的 \(\sum \tbinom{len+1}{2}\) 之和
复杂度 \(O(n)\)
int n;
int b[N], c[N], d[N], e[N];
int f[N], k[N], t[N], q[N];
int tl[N], s[N];
int ans;
void solve(int x)
{
f[x + 1] = 0;
rint j = 1;
for (rint i = 1; i < x + 2; tl[i] = t[j], t[1 + j++] = i, i++)
{
#define id t[j]
while (f[i] < f[id])
{
s[f[id]] = x < n;
q[f[id]] = ((k[id] - k[tl[id]] + mod) % mod * (i - id)) % mod;
j--;
}
#undef id
}
}
void update()
{
for (rint i = 1; i <= n; i++)
{
f[i] = b[i];
k[i] = d[i];
}
solve(n);
for (rint i = 1; i < n; i++)
{
f[i] = c[i + 1];
k[i] = i;
}
solve(n - 1);
q[c[1]] = 0;
int y = 0;
for (rint i = 1; i <= n * 2; i++)
{
if (s[i]) ans = (ans + y * q[i] % mod) % mod;
else y = (y + q[i]) % mod;
}
}
signed main()
{
cin >> n;
for (rint i = 1; i <= n; i++) cin >> b[i];
for (rint i = 1; i <= n; i++) cin >> c[i];
for (rint i = 1; i <= n; i++) cin >> d[i];
for (rint i = 1; i <= n; i++) cin >> e[i];
update();
for (rint i = 1; i <= n; i++)
{
swap(b[i], c[i]);
d[i] = e[i];
}
update();
cout << ans << endl;
return 0;
}