Codeforces Round 937 (Div. 4) (A~G)

比赛地址

A.Stair, Peak, or Neither?

题目大意
根据 a、b、c 的大小关系输出给定字符串
代码

void solve()
{
    ll a,b,c;
    cin>>a>>b>>c;
    if(a<b&&b<c) cout<<"STAIR"<<'\n';
    else if(a<b&&b>c) cout<<"PEAK"<<'\n';
    else cout<<"NONE"<<'\n';
}

B. Upscaling

题目大意
根据题目给出的 n 构造字符矩阵

代码

void solve()
{
    int n;
    cin>>n;
    for(int i=0;i<2*n;i++) {
        char ch=((i/2)%2)?'#':'.';
        for(int j=0;j<2*n;j++) {
            cout<<((j/2)%2?ch:(ch=='#'?'.':'#'));
        }
        cout<<'\n';
    }
}

C. Clock Conversion

题目大意
将 24 小时制时间改成 12 小时制
代码

void solve()
{
    int a,b;
    scanf("%d:%d",&a,&b);
    if(a<12) printf("%02d:%02d AM\n",a==0?12:a,b);
    else if(a==12) printf("%02d:%02d PM\n",a,b);
    else printf("%02d:%02d PM\n",a-12,b);
}

D. Product of Binary Decimals

题目大意
给定一个整数，问其是否能够被每位数字都是0或1的十进制数（如1，10，11，101等）整除。
思路
由于 n 最大为 $10^5$ ，可以直接打表能够作为除数的十进制数。
代码

const int _number[]={
    1,10,11,100,101,110,111,
    1000,1001,1010,1011,1100,1101,1110,1111,
    10000,10001,10010,10011,10100,10101,10110,10111,11000,11001,11010,11011,11100,11101,11110,11111,
    100000
};
void solve()
{
    int n;
    cin>>n;

    int temp=n;
    bool succ=true;
    while(temp) {
        succ=succ&&(temp%10==0||temp%10==1);
        temp/=10;
    }

    if(succ) {
        cout<<"YES"<<'\n';
        return;
    }

    for(int t=1;t<32;t++) {
        while(n%_number[t]==0) n/=_number[t];
    }

    cout<<(n==1?"Yes":"No")<<'\n';
}

E. Nearly Shortest Repeating Substring

题目大意
给定一个字符串 str，问是否存在字符串 k，使得 x 个 k 连接起来与 str 完全相同或者仅有一个字符不同（x值任意），求 k 的最小长度
思路
从小到大枚举划分的长度，对于每个枚举的长度：维护一个总和 sum，sum 为每个划分中相同下标的相同字符数量的最大值之和，判断 sum 是否不小于 n-1，若是，则当前枚举长度为最优解。
代码

void solve()
{
    int n;
    string line;
    cin>>n>>line;
    for(int len=1;len<=n;len++) {
        if(n%len) continue;
        int sum=0;
        for(int left=0;left<len;left++) {
            int mx=0;
            vector<int> cnt(26,0);
            for(int i=left;i<n;i+=len) {
                cnt[line[i]-'a']++;
                mx=max(mx,cnt[line[i]-'a']);
            }
            sum+=mx;
        }
        if(sum>=n-1) {
            cout<<len<<'\n';
            return;
        }
    }
}

F. 0, 1, 2, Tree!

题目大意
给定三个整数 a、b、c 分别表示树中有两个子节点的节点数量，有一个孩子的节点的数量与叶节点数量，问可以构造的数的最小高度。
思路
根据二叉树性质，若 $a+1\ne c$ 则无解。否则可用数组维护每层节点的最大数量：2 个孩子的节点放在上面一定是最优解，根据每层节点可以计算下一层节点的数量。
代码

void solve()
{
    int a,b,c;
    cin>>a>>b>>c;
    if(a!=c-1) {
        cout<<-1<<'\n';
        return;
    }

    vector<int> tr(1,1);
    int ptr=0;
    for(int i=1;i<=a+b;i++) {
        if(tr[ptr]==0) {
            ptr++;
        }
        if(ptr==int(tr.size()-1)) {
            tr.push_back(0);
        }
        tr[ptr]--;
        tr[ptr+1]+=(i<=a?2:1);
    }

    cout<<int(tr.size()-1)<<'\n';
}

G. Shuffling Songs

题目大意
每首歌由两部分组成：风格g 与 作者w，现在需要列一个清单，要求清单中相邻的两首歌曲要么 g 相同，要么 w 相同，问组成这样一个清单最少需要删除几首歌曲？
思路
状压dp
题目给出的 n 的范围很小 $(\le 16)$，可以用邻接矩阵维护每两首歌是否能相邻。考虑维护 dp[state][i] 表示当前选中歌曲为 state （集合） 且最后一首歌为 i 的情况能否组成一个清单，其中 state 使用二进制表示表示每首歌是否选中，不难发现仅选择一首歌的情况是一定满足要求的，对于每个 state ，枚举选中的歌 i（作为最后一首）与未选中的歌 j ，通过邻接矩阵查询 i 、j 是否能够相邻，若能相邻，更新 $dp[state|(1<<j)][j]$ 的值为 true，答案为所有值为true 的 state 的二进制中1数量的最大值。
代码

void solve()
{
    int n;
    cin>>n;
    vector<string> a(n),b(n);
    for(int i=0;i<n;i++) cin>>a[i]>>b[i];
    vector g(n,vector<bool>(n,false));
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            g[i][j]=g[j][i]=(a[i]==a[j]||b[i]==b[j]);
        }
    }

    vector dp((1<<n),vector<bool>(n,false));
    for(int i=0;i<n;i++) {
        dp[1<<i][i]=true;
    }

    int ans=0;
    for(int t=1;t<(1<<n);t++) {
        for(int i=0;i<n;i++) {
            if(dp[t][i]) {
                ans=max(ans,__builtin_popcount(t));
                for(int j=0;j<n;j++) {
                    if(!(t&(1<<j))&&(g[i][j])) {
                        dp[t|(1<<j)][j]=true;
                    }
                }
            }
        }
    }

    cout<<n-ans<<'\n';
}