2025CCPC:四川&2022河南

Problem I. 本质不同后缀

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

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

const ull base=131;
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. 逆序对

对长度为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';
    
    
}

一些单题

Educational Codeforces Round 186

C. Production of Snowmen

https://codeforces.com/contest/2182/problem/C

题意:对三条传送带(循环数组),找到所有可能的起点组合(i,j,k),使得对所有对应位置都满足a[x]<b[x]<c[x];

暴力优化:

1.遍历检查所有组合:O(n^4)复杂度,超时;

2.事实上,三元组(i,j,k)等同于(i-j,0,k-j),移动中间数组时,符合条件的组合并没变. 固定b数组,分别遍历统计a,c数组符合条件的起始索引数.结果为cntacntc\n.

记得开long long.

int n,a[N],b[N],c[N];
int pt(int i,int f)
{
    int cnt=0;
    if(f==1){
        REP(p,0,n-1)if(a[(i+p)%n]<b[p])cnt++;
    }else{
        REP(p,0,n-1)if(c[(i+p)%n]>b[p])cnt++;
    }
    return cnt;
}
void solve()
{
    cin>>n;
    REP(i,0,n-1)cin>>a[i];
    REP(i,0,n-1)cin>>b[i];
    REP(i,0,n-1)cin>>c[i];
    ll r1=0,r2=0;
    REP(i,0,n-1)
    {
        if(pt(i,1)==n)r1++;
        if(pt(i,3)==n)r2++;
    }
    cout<<1ll*r1*r2*n<<'\n';
}

D. Christmas Tree Decoration

对n+1个盒子,每个人pi可以从面前的盒子或第0个盒子取装饰品,计算公平排列的数量.(如果出现pi和p0都为0,且当前没取完,则为不公平). 只要把p0中的装饰品分到小于最大数量的盒子中,看是否能保证数量差不大于1.

要达到公平,轮数差不能大于1.空缺由a[0]填补.考虑有x个最大值mx,y个mx-1,z个小于mx-1;

能填充到都为mx:n!

能填到下界为mx-1,多出来的可以自由分配给mx-1:排列组合

否则结果为0

ll n,a[N],fac[N],C[N][N];
void solve()
{
    cin>>n;
    REP(i,0,n)cin>>a[i];
    ll mx=*max_element(a+1,a+1+n);
    ll nd=0,nd2=0,mxcnt=0;
    REP(i,1,n){
        nd+=mx-a[i];
        if(a[i]<mx)nd2+=mx-1-a[i];
        if(a[i]==mx)mxcnt++;
    }
    if(a[0]>=nd)cout<<fac[n]<<'\n';
    else if(a[0]>=nd2){
        ll add=a[0]-nd2;
        cout<<fac[mxcnt+add]*fac[n-mxcnt-add]%M*C[n-mxcnt][a[0]-nd2]%M<<'\n';
    }else cout<<0<<'\n';
}
int main()
{
    fac[0]=1;
    REP(i,1,50)fac[i]=fac[i-1]*i%M;
    REP(i,0,51){C[i][i]=1ll;C[i][0]=1ll;}
    REP(i,1,51)
    {
        REP(j,1,i){C[i][j]=(C[i-1][j]+C[i-1][j-1])%M;}//cout<<C[i][j]<<' ';
        //cout<<'\n';
    }
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

自底而上的聚合标记

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

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];
    }
}

补题

2025CCPC:四川&2022河南

Problem I. 本质不同后缀

Problem H. 胡图图

Problem F. 逆序对

Problem J. Mex Tree

Problem E. Serval 的俳句

Problem H. 旋转水管

Problem J. Mex Tree

一些单题

Educational Codeforces Round 186

C. Production of Snowmen

D. Christmas Tree Decoration

自底而上的聚合标记

等价way1