原题大战，还是 \(4\) 道计数...
放个头图：
一蓝一紫两黑，简单且原题 0.o？
出模拟赛搬原题演都不演了，他真的我哭死。那这总结不写也罢
T1
\(n\leq 10^3\)。
简单来说，要选出子序列满足相同颜色连续的方案数。
签到题，但写了 \(\text{1h}\) 的我是 sb。
直接大力状压，设 \(dp_{i,s,c}\) 表示考虑了前 \(i\) 个，选了的颜色集合是 \(s\)，且上一个结尾颜色段为 \(c\) 的方案数，转移随便搞就好了。但是这唐题空间只给 \(\text{16MiB}\)，还得把 \(i\) 那维给滚了。
Code
#include <bits/stdc++.h>
#define il inline
#define rint register int
#define ll long long
using namespace std;
const int N = 1e3 + 10, INF = 2147483647, mod = 998244353;
char *p1, *p2, buf[N];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
#define gc() getchar()
il int rd() {
int x = 0, f = 1;
char ch = gc();
while (!isdigit(ch)) {
if (ch == '-')f = -1;
ch = gc();
}
while (isdigit(ch))x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc();
return x * f;
}
int n;
char s[N];
ll f[1 << 10], dp[1 << 10][11];
void Main () {
ll ans = 0;
int all = 1 << 10;
n = rd();
scanf("%s", s + 1);
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; ++i) {
int k = s[i] - 'A';
memset(f, 0, sizeof(f));
f[1 << k] = 1;
for (int j = all - 1; j >= 0; --j) {
if (!((j >> k) & 1)) {
for (int t = 0; t < 10; ++t)
if ((j >> t) & 1) (f[j] += dp[j][t]) %= mod;
(dp[j | (1 << k)][k] += f[j]) %= mod;
} else {
(f[j] += dp[j][k]) %= mod;
(dp[j][k] += f[j]) %= mod;
}
(ans += f[j]) %= mod;
}
}
printf("%lld\n", ans);
}
signed main() {
// freopen("counta.in", "r", stdin);
// freopen("counta.out", "w", stdout);
int T = rd();
while (T --) Main();
return 0;
}
T2
我们定义一个数组 \(b\) 是好的当且仅当所有的 \(b_i \ge i\)。
现在给你 \(q\) 次操作，每次操作有两个数 \(p\) 和 \(x\)，问把 \(a_p\) 赋值成 \(x\) 后 \(a\) 数组好的子串（连续的子序列）的个数。
数据范围：
- \(1 \le n \le 2 \times 10^5\)，\(1 \le q \le 2 \times 10^5\)。
- \(1 \le a_i \le n\)，\(1 \le p_j,x_j \le n\)。
典题，考虑对每个右端点记录最左端点 \(l_i\)，则 \(l_i=\max(l_{i-1},i-a_i+1)\)，那么显然这玩意具有单调性。然后给原系列 \(a\) 拍到线段树上，那么 \(l\) 就是个前缀取 \(\max\) 的形式，考虑每次修改会带来的影响，维护个区间最大值，线段树二分即可。
Code
#include <bits/stdc++.h>
#define lc k << 1
#define rc k << 1 | 1
#define il inline
#define rint register int
#define ll long long
using namespace std;
const int N = 2e5 + 10, INF = 2147483647;
char *p1, *p2, buf[N];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
#define gc() getchar()
il int rd() {
int x = 0, f = 1;
char ch = gc();
while (!isdigit(ch)) {
if (ch == '-')f = -1;
ch = gc();
}
while (isdigit(ch))x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc();
return x * f;
}
int n, m, a[N];
ll ans[N << 2], mx[N << 2];
ll calc (int k, int l, int r, int v) {
if (mx[k] <= v) return 1ll * (r - l + 1) * v;
if (l == r) return mx[k];
int mid = (l + r) >> 1;
if (mx[lc] >= v) return ans[k] - ans[lc] + calc(lc, l, mid, v);
return calc(rc, mid + 1, r, v) + 1ll * v * (mid - l + 1);
}
void pushup (int k, int l, int mid, int r) {
mx[k] = max(mx[lc], mx[rc]);
ans[k] = ans[lc] + calc(rc, mid + 1, r, mx[lc]);
}
void build (int k, int l, int r) {
if (l == r) return ans[k] = mx[k] = max(1, l - a[l] + 1), void();
int mid = (l + r) >> 1;
build(lc, l, mid), build(rc, mid + 1, r);
pushup(k, l, mid, r);
}
void update (int k, int l, int r, int v, int x) {
if (l == r) return ans[k] = mx[k] = max(1, l - x + 1), void();
int mid = (l + r) >> 1;
v <= mid ? update(lc, l, mid, v, x) : update(rc, mid + 1, r, v, x);
pushup(k, l, mid, r);
}
void Main() {
n = rd();
for (int i = 1; i <= n; ++i) a[i] = rd();
build(1, 1, n);
m = rd();
for (int i = 1; i <= m; ++i) {
int x, k;
ll ret = 0;
x = rd(), k = rd();
update(1, 1, n, x, k);
ret = 1ll * n * (n + 1) / 2 + n - ans[1];
printf("%lld\n", ret);
update(1, 1, n, x, a[x]);
}
}
signed main () {
// freopen("countb.in", "r", stdin);
// freopen("countb.out", "w", stdout);
int T = 1;
while (T--)Main();
return 0;
}
T3
T4
[ZJOI2019] 语言
有 \(n\) 个城市节点组成树。
在上古时代，这 \(n\) 个城市之间处于战争状态。在高度闭塞的环境中，每个城市都发展出了自己的语言。而在王国统一之后，语言不通给王国的发展带来了极大的阻碍。为了改善这种情况，国王下令设计了 \(m\) 种通用语，并进行了 \(m\) 次语言统一工作。在第 \(i\) 次统一工作中，一名大臣从城市 \(s_i\) 出发，沿着最短的路径走到了 \(t_i\)，教会了沿途所有城市（包括 \(s_i, t_i\)）使用第 \(i\) 个通用语。
一旦有了共通的语言，那么城市之间就可以开展贸易活动了。两个城市 \(u_i, v_i\) 之间可以开展贸易活动当且仅当存在一种通用语 \(L\) 满足 \(u_i\) 到 \(v_i\) 最短路上的所有城市（包括 \(u_i, v_i\)），都会使用 \(L\)。
为了衡量语言统一工作的效果，国王想让你计算有多少对城市 \((u, v)\)（\(u < v\)），他们之间可以开展贸易活动。
对于 \(100\%\) 的数据，有 \(1 \le x_i, y_i, s_i, t_i \le n\leq 10 ^ 5\)，\(1\leq m\leq 10 ^ 5\)，\(x_i\neq y_i\)。
啥都不会。