AT ABC320C 题解

· · 题解

ABC320C

思路:

首先我们可以枚举 0 到 9 每个数字对答案的贡献。

注意到高桥同一时间只能停一个转盘，就会有三个转盘的先停哪个的优先级问题，注意到转盘数量只有三个，可以枚举所有优先级排列顺序，设三个转盘编号分别为 1,2,3，其排列顺序有 123,132,213,231,312,321 六种（123 表示当两个转盘该数字位置相同时优先考虑停止第一个转盘，另一个只得去转盘选下一个位置）直接枚举一遍。

因为重复次数最多为 3 次，所以可以把字符串拓展 3 倍就可以保证三个转盘和上一个重复后一定有后面的位置可以选择。

实现时使用容器 pos_{i,j} 存储第 i 个转盘 j 这个数在其串里的每一个位置，然后枚举 6 种情况跳指针，三个转盘的位置取 \max 即可，注意判断无解情况。

理论最差复杂度为 O(\omega n)，其中 \omega = 6 \times 10 = 60。但实际远远跑不满，1ms 跑得飞。

Code:

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
il void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
#define M 600
char s[4][M];
vector<int> pos[4][20];
signed main(){
    int n;cin>>n;
    for(int i=1;i<=3;i++){
        cin>>(s[i]+1);
        for(int j=1;j<=n;j++)
            s[i][j+n]=s[i][j+2*n]=s[i][j];
    }
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3*n;j++)
            pos[i][s[i][j]-'0'].emplace_back(j);
    int ans=1145141919;
    for(int d=0;d<=9;d++){
        if(pos[1][d].size()==0||pos[2][d].size()==0||pos[3][d].size()==0)continue;
        int tm1=pos[1][d][0],tm2,tm3;
        int pos2=0,pos3=0;
        while(pos[2][d][pos2]==tm1) pos2++;
        tm2=pos[2][d][pos2];
        while(pos[3][d][pos3]==tm1||pos[3][d][pos3]==tm2) pos3++;
        tm3=pos[3][d][pos3];
        ans=min(ans,max({tm1,tm2,tm3})-1);

        tm1=pos[1][d][0];//从上面复制粘贴下来改下顺序
        pos2=0,pos3=0;
        while(pos[3][d][pos2]==tm1) pos2++;
        tm2=pos[3][d][pos2];
        while(pos[2][d][pos3]==tm1||pos[2][d][pos3]==tm2) pos3++;
        tm3=pos[2][d][pos3];
        ans=min(ans,max({tm1,tm2,tm3})-1);

        tm1=pos[2][d][0];
        pos2=0,pos3=0;
        while(pos[1][d][pos2]==tm1) pos2++;
        tm2=pos[1][d][pos2];
        while(pos[3][d][pos3]==tm1||pos[3][d][pos3]==tm2) pos3++;
        tm3=pos[3][d][pos3];
        ans=min(ans,max({tm1,tm2,tm3})-1);

        tm1=pos[2][d][0];
        pos2=0,pos3=0;
        while(pos[3][d][pos2]==tm1) pos2++;
        tm2=pos[3][d][pos2];
        while(pos[1][d][pos3]==tm1||pos[1][d][pos3]==tm2) pos3++;
        tm3=pos[1][d][pos3];
        ans=min(ans,max({tm1,tm2,tm3})-1);

        tm1=pos[3][d][0];
        pos2=0,pos3=0;
        while(pos[1][d][pos2]==tm1) pos2++;
        tm2=pos[1][d][pos2];
        while(pos[2][d][pos3]==tm1||pos[2][d][pos3]==tm2) pos3++;
        tm3=pos[2][d][pos3];
        ans=min(ans,max({tm1,tm2,tm3})-1);

        tm1=pos[3][d][0];
        pos2=0,pos3=0;
        while(pos[2][d][pos2]==tm1) pos2++;
        tm2=pos[2][d][pos2];
        while(pos[1][d][pos3]==tm1||pos[1][d][pos3]==tm2) pos3++;
        tm3=pos[1][d][pos3];
        ans=min(ans,max({tm1,tm2,tm3})-1);
    }
    if(ans==1145141919)ans=-1;
    write(ans);
}