比赛成绩：0+0+0+0
### 不要问为什么，问就是没打
第一题：
ab 二分区间，在mid内，不在序列中的数是mid+1-mid/a*b
第二题：
### 建议看小粉兔题解
先把x变成1，y变成2，观察到操作时%3不变
令P（a）表示a串的和%3，令t为单个字符，先说结论，若P（t）P(a)且a中有连续的字符则可以由a变换为t；
证明：
若存在上述情况，则可以不断进行操作且使得P(a)不变，最终只剩下一个数
接下来考虑对于字符串S能不能变换得到
先贪心，对于S的每一个字符取a的最短前缀使它满足上面那个条件，进行分段，注意最后一段P()=0，若成功分段，则可变换，证明略（我不会）
所以剩下就是DP了，理解一下就好了
#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
string s;
long long len, a[100005], flag, dp[100005], ll[100005];
int main() {
freopen("abbreviate.in", "r", stdin);
freopen("abbreviate.out", "w", stdout);
cin >> s;
len = s.size();
s = " " + s;
for (int i = 1; i <= len; i++) {
if (s[i] == 'x')
a[len - i + 1] = 1;
else
a[len - i + 1] = 2;
}
for (int i = 2; i <= len; i++) {
if (a[i] == a[i - 1]) {
flag = 1;
break;
}
}
if (flag == 0) {
cout << "1";
return 0;
}
for (int i = 1; i <= len; i++) {
a[i] += a[i - 1];
a[i] %= 3;
}
for (int i = 1; i <= len; i++) {
if (a[i] == 0)
dp[i] = 0;
else
dp[i] = 1;
for (int j = 0; j <= 2; j++) {
if (j != a[i]) {
dp[i] = (dp[i] + dp[ll[j]]) % mod;
}
}
ll[a[i]] = i;
}
cout << dp[len];
return 0;
}
第三题：
可以先求出K=1时的情况，很简单，先把与1号点连接的边拿掉，跑最小生成数就行了
然后再找dis[1][i]的点连上就好了
考虑K+1时的情况，可以理解为选一条当前生成树上的边删掉，设权值为w1，找到子树中最小的边连上1号点，权值为w2，答案贡献就是w2-w1，容易想到每次找到最小的（w2-w1）断开就行了
于是就有了神奇的并查集代码
int find(int x) {
if (fa[x] == x)
return x;
else
return fa[x] = find(fa[x]);
}
sort(edge + 1, edge + cnt + 1, cmp);
for (int i = 1; i <= cnt; i++) {
fu = find(edge[i].u);
fv = find(edge[i].v);
fw = edge[i].w;
if (fu != fv) {
ans += fw;
if (val[fu] < val[fv])
swap(fu, fv);
dis[fu] = fw;
fa[fu] = fv;
}
}
很明显有贪心策略：离1号点进的点总能匹配到大的边（当然是对于经过前面操作后在一个子树内的点而言，能发现这个并茶集满足这个条件，因为先被改的点总会排在并查集的上层，所以当一个点在并查集的非子树部分不会影响它，这明显符合并查集性质）
所以就结束了
#include <bits/stdc++.h>
using namespace std;
long long n, m, val[300005], uu, vv, ww, cnt, fa[300005], fu, fv, fw, ans, dis[300005], ccnt, sum[600005];
struct sd {
long long u, v, w;
} edge[600005];
int cmp(sd A, sd B) { return A.w < B.w; }
int find(int x) {
if (fa[x] == x)
return x;
else
return fa[x] = find(fa[x]);
}
int main() {
freopen("rootedmst.in", "r", stdin);
freopen("rootedmst.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= m; i++) {
scanf("%lld%lld%lld", &uu, &vv, &ww);
if (uu > vv)
swap(uu, vv);
if (uu == 1) {
val[vv] = ww;
} else {
cnt++;
edge[cnt].u = uu;
edge[cnt].v = vv;
edge[cnt].w = ww;
}
}
sort(edge + 1, edge + cnt + 1, cmp);
for (int i = 1; i <= cnt; i++) {
fu = find(edge[i].u);
fv = find(edge[i].v);
fw = edge[i].w;
if (fu != fv) {
ans += fw;
if (val[fu] < val[fv])
swap(fu, fv);
dis[fu] = fw;
fa[fu] = fv;
}
}
for (int i = 2; i <= n; i++) {
if (find(i) == i) {
ans += val[i];
} else {
ccnt++;
sum[ccnt] = val[i] - dis[i];
}
}
cout << ans << " ";
sort(sum + 1, sum + ccnt + 1);
for (int i = 2; i <= n - 1; i++) {
printf("%lld ", ans + sum[i - 1]);
ans += sum[i - 1];
}
return 0;
}