T0

div2存疑。
T2上黑题。(?)
NFLS又在培养宇航员了(bushi

T1

题意：给定p,q,k，设x=\frac{p}{q}，有一个序列a=\left\lfloor\ x\cdot i \right\rfloor，求序列内没有出现过的第k小的非负整数。

我真的是纸张。
想到二分答案，然后打爆了。
这题实际上二分的是最后的答案，而不是循环节内的答案，否则会让统计答案这件事非常头大。

T2

正解做法：

而如果一个T串可以由S串生成，那么T的每个字符都对应S的某一段，且mod3的值是相同的。
然后从后往前预处理上一字符与当前字符相同的位置，贪心去匹配。
但是实现的时候，因为C++负数%正数=负数，因此我们让W(y)=2，然后需要特判xyxyxyxy`交替的情况，答案为1。

#include
using namespace std;
const int N=1e5+5,mod=998244353;
typedef long long LL;
char str[N];
int n,same;
int s[N],ne[N][5];
LL res,f[N];
int main()
{
    freopen("abbreviate.in","r",stdin);
    freopen("abbreviate.out","w",stdout);
    scanf("%s",str+1);
    n=strlen(str+1);
    for(int i=1;i1&&str[i-1]==str[i])same=1;
        s[i]=(s[i-1]+(str[i]=='x'?1:2))%3;
    }
    if(!same)
    {
        puts("1");
        return 0;
    }
    ne[n+1][0]=ne[n+1][1]=ne[n+1][2]=n+1;
    for(int i=n;i;i--)
    {
        ne[i][0]=ne[i+1][0];
        ne[i][1]=ne[i+1][1];
        ne[i][2]=ne[i+1][2];
        ne[i][s[i]]=i;
    }
    f[0]=1;
    for(int i=0;i<=n;i++)
    {
        if(i&&s[i]==s[n])res=(res+f[i])%mod;
        f[ne[i+1][(s[i]+1)%3]]=(f[ne[i+1][(s[i]+1)%3]]+f[i])%mod;
        f[ne[i+1][(s[i]+2)%3]]=(f[ne[i+1][(s[i]+2)%3]]+f[i])%mod;
    }
    printf("%lld",res);
    return 0;
}

T3

题意：

给出一张有N个顶点的带权简单无向图，其中点的编号为1—N。保证点1不是一个割点（也就是说删掉点1之后，剩下的图仍然连通），且点1到其余N-1个点都有连边。
对每个K\in{1,2,3,4,…,N-1} ，你需要求出使得点1的度数恰好为K的最小生成树的花费。

考场上看错题然后爆炸了。
对于没有连接1的边，先做一遍最小生成树，在合并的过程中，记录删除删除此边后的代价，用1到其的权值与代价相减，排序后每次查询加上这个代价就可以了。

#include
using namespace std;
const int N=3e5+5;
typedef pairPII;
typedef long long LL;
int n,m,par[N],w[N],rev[N];
LL res=0;
vectoredge;
vectornew_edge;
int find(int x)
{
    if(~par[x])return par[x]=find(par[x]);
    else return x;
}
void unite(int a,int b,int c)
{
    a=find(a);
    b=find(b);
    if(a==b)return;
    if(w[a]<w[b])swap(a,b);
    par[a]=b;
    res+=(LL)(rev[a]=c);
}
int main()
{
    freopen("rootedmst.in","r",stdin);
    freopen("rootedmst.out","w",stdout);
    memset(par,-1,sizeof par);
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        int s=min(a,b),t=max(a,b);
        if(s==1)w[t]=c;
        else edge.push_back({c,{a,b}});
    }
    sort(edge.begin(),edge.end());
    for(auto item:edge)unite(item.second.first,item.second.second,item.first);
    for(int i=2;i<=n;i++)
    {
        if(~par[i])new_edge.emplace_back(w[i]-rev[i]);
        else res+=(LL)w[i];
    }
    sort(new_edge.begin(),new_edge.end());
    printf("%lld ",res);
    for(int i=0;i<n-2;i++)printf("%lld ",(res+=(LL)new_edge[i]));
    return 0;
}

T4

实在是不会了。

T5

后记：晚上研究了DP基础与莫队，然后觉得自己更是一纸张了。
(悲