2025CCPC:四川&2022河南

Problem I. 本质不同后缀

输出n个字符串的后缀串集大小.第一次尝试直接用set存储后缀串,果然还是过不了啊,直接MIE. 在紫皮书上看到过这样的处理方式:通过滚动哈希优化,将字符串转换为哈希值存储.

操作:对每个字符串,逆序遍历计算后缀哈希值

const ull base=31;
set<ull>note;
void solve(){
    int n;cin>>n;
    REP1(i,1,n)
    {
        string s;cin>>s;
        ull cur=base;
        REP2(i,s.size()-1,0)
        {
            cur=base*(cur+s[i]);//计算哈希值
            note.insert(cur);
        }
    }
    cout<<note.size()<<'\n';
}

Problem H. 胡图图

这题应该算签到题了…结果没考虑到原点附近的轴上点的特殊处理. 先画图模拟一下就没这么多事了

void solve(){
    ll x=0,y=0,X,Y;
    cin>>x>>y>>X>>Y;
    X=abs(X-x);Y=abs(Y-y);//变换参考系
    ll sp1=(X+1)/2,sp2=(Y+1)/2;
    if(X==0&&Y==0){cout<<"0\n";return;}
    if((X==0&&Y<=2)||(Y==0&&X<=2))cout<<2<<'\n';//特判
    else cout<<max(sp1,sp2)<<'\n';
}

Problem F. 逆序对

wa四发,差点触发战败cg. 对长度为n的01序列,将序列中未确定字符替换为0或1来最大化逆序对.一开始想的很麻烦,什么前半补1后半补0,贪心,动态规划…就是没去试着暴力+优化.

最后想到之前写的一道很像的题https://codeforces.com/contest/2194/problem/B,只有第一次会遍历计算,后面单点修改再次计算的复杂度为O(1).

最后通过的思路:先计算全部替换为0时的情况,之后从前往后遍历,每次遇到替换位置时,改为1(填充01比例固定时,前1后0总是最优的)并维护变化(d=-pre1+suf0). 

int a[N],b[N],suf[N];
void solve(){
    int n;cin>>n;
    suf[n+1]=0;
    REP1(i,1,n)
    {
        suf[i]=0;
        char x;cin>>x;
        if(x=='1')a[i]=1;
        else if(x=='0')a[i]=0;
        else {a[i]=-1;}
    }
    //b[]记录填充后的序列
    REP1(i,1,n){
        if(a[i]==-1)b[i]=0;
        else b[i]=a[i];
    }
    //后缀0计数数组
    REP2(i,n,1)suf[i]=(b[i]==0?suf[i+1]+1:suf[i+1]);
    ll res=0;
    REP1(i,1,n){
        if(b[i]==1){
            res+=suf[i];
        }
    }
    //记录变化,线性时间复杂度
    ll pre1=0,d=0,note=0;
    REP1(i,1,n){
        if(a[i]==1){
            pre1++;
        }
        else if(a[i]==-1){
            //0->1
            d+=-pre1+suf[i+1];
            note=max(note,d);
            pre1++;
        }
    }
    cout<<res+note<<'\n';
}

Problem J. Mex Tree

对k:0-n,找到点集满足mex=k的最大子树的点的数量

参考:https://zhuanlan.zhihu.com/p/570781133

差不多忘了怎么建树了,dfs也陌生到感觉有点神奇…

Problem E. Serval 的俳句

尝试分割成三段恰好满足条件的区间.每段的处理方式相同,只是目标长度和起点的差异,封装成函数方便书写.

int n;
char s[N];
int pt(int& p,int len)
{
    unordered_map<int,int>cc;
    while(p<=n)
    {
        int c=s[p];
        cc[c]++;
        if(cc[c]>=len)
        {
            p++;
            return c;
        }
        p++;
    }
    return 0;
}
void solve(){
   	cin>>n;
    REP1(i,1,n)cin>>s[i];
    int st=1;
    int c1=pt(st,5);
    int c2=pt(st,7);
    int c3=pt(st,5);
    if(c1&&c2&&c3)
    {
        REP1(i,1,5)cout<<char(c1);
        REP1(i,1,7)cout<<char(c2);
        REP1(i,1,5)cout<<char(c3);
    }else cout<<"none\n";
}

Problem H. 旋转水管

dfs,最后记得重置vis.

void dfs(int x, int y, int in)//cur
{
    if (f||x < 0 || x>1 || y<1 || y>n)return;
    //cout << x << ' ' << y << ' ' << in << '\n';
    if (vis[x][y])return;
    vis[x][y]=1;

    if (x == 1 && y == ed) {
        if (((in == 3 || in == 4) && a[1][ed] == 'L') ||((in == 2) && a[1][ed] == 'I'))
        {
            f = true;
            return;
        }
    }
    if (a[x][y] == 'L')
    {
        if (in == 1||in==2) { dfs(x, y - 1, 3); dfs(x, y + 1, 4); }
        if (in == 3 || in == 4) { dfs(x - 1, y, 1); dfs(x + 1, y, 2); }
    }
    else
    {
        if (in == 1)dfs(x - 1, y, 1);
        else if (in == 2)dfs(x + 1, y, 2);
        else if (in == 3)dfs(x, y - 1, 3);
        else dfs(x, y + 1, 4);
    }
    vis[x][y]=0;//
}

Problem J. Mex Tree

k==0,打印与权值为0的点相接的最大子树的点数就行

k!=0,目标集必须包含所有[0,k-1]范围内的数.

证伪比证真容易,比起判断所有连接枝中是否有完整包含[0,k-1]集的, 将权0点作为树根,k作为子树根节点,判断k子树是否都大于k更易实现.

对整棵树从0根节点dfs,尝试更新res[]. 对点u,遍历树枝,统计u树点数sz[u]并记录树枝最小权mi[u], mi[u]>u,说明主树满足条件,大小为n-sz[u]. 最后更新mi[u]=u

int n;
int v[N],mi[N],sz[N],res[N];
vector<int> g[N];
void dfs(int u,int fa)
{
    sz[u]=1;
    mi[u]=inf;
    for(auto v:g[u])
    {
        if(v==fa)continue;
        dfs(v,u);
        sz[u]+=sz[v];
        mi[u]=min(mi[u],mi[v]);//记录u树枝最小点
    }
    if(mi[u]>u)res[u]=n-sz[u];//u子树
    mi[u]=min(mi[u],u);
}
void solve(){
    cin>>n;
    REP1(i,1,n)cin>>v[i];//1-n的权值
    REP1(i,2,n)//边(i,x)
    {
        int x;cin>>x;
        g[v[i]].push_back(v[x]);
        g[v[x]].push_back(v[i]);
    }
    dfs(0,0);
    for(auto v:g[0])res[0]=max(res[0],sz[v]);
    REP1(i,0,n-1)cout<<res[i]<<' ';
    cout<<n<<'\n';
    
    
}

一些单题

自底而上的聚合标记

有时候,把树当作特殊的图处理很方便.

https://codeforces.com/problemset/problem/1843/D

从所有叶子节点开始bfs向根节点汇总更新每个点下落到边界的情况数.

先将叶子节点更新标记并加入多源bfs的队列.

V way(n+1,0),vis(n+1,0),rem(n+1,0);
    queue<int>q;
    REP1(i,1,n)rem[i]=g[i].size();//总度
    REP1(i,2,n){
        if(rem[i]==1){
            way[i]=1;vis[i]=1;
            q.push(i);
        }
    }

反向dfs(关键),实时更新点的标记状态vis:

while(q.size()){
        int u=q.front();q.pop();
        for(int v:g[u]){
            if(vis[v])continue;
            way[v]+=way[u];
            rem[v]--;
            if(rem[v]==1&&v!=1){//只剩向上的出度
                q.push(v);
                vis[v]=1;
            }
        }
    }

对根单独处理:

if(!vis[1]){
        for(int v:g[1])way[1]+=way[v];
    }

示例代码则是直接用了dfs子树dp.真奇怪,如果形成一条链的话,不会栈溢出吗?因为担心这点,没有考虑用递归解决.

int dfs(int u,int f){
    int sum=0;
    if(g[u].size()==1&&u!=1){
        return way[u]=1;
    }
    for(auto v:g[u]){
        if(v==f)continue;
        sum+=dfs(v,u);
    }
    return way[u]=sum;
}

但毕竟递归是非常自然的想法,尝试其他的等效方法:

等价way1

BFS建序 + 逆序DP

根节点一次bfs建立树序

V ord,pa(n+1);
   queue<int>q;
   q.push(1);pa[1]=-1;
   while(!q.empty()){
       int u=q.front();q.pop();
       ord.push_back(u);
       for(auto v:g[u]){
           if(v==pa[u])continue;
           pa[v]=u;q.push(v);
       }
   }

从叶节点往上更新

REP2(i,ord.size()-1,0){
    int u=ord[i];
    if(g[u].size()==1&&u!=1)way[u]=1;
    for(int v:g[u]){
        if(pa[v]==u)way[u]+=way[v];
    }
}