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 构造字符矩阵
Codeforces Round 937 (Div. 4) B
代码

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 最大为 1 0 5 10^5 105 ,可以直接打表能够作为除数的十进制数。
代码

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 ≠ c a +1 \neq c a+1=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 的范围很小 ( ≤ 16 ) (≤ 16) (16),可以用邻接矩阵维护每两首歌是否能相邻。考虑维护 dp[state][i] 表示当前选中歌曲为 state (集合) 且最后一首歌为 i 的情况能否组成一个清单,其中 state 使用二进制表示表示每首歌是否选中,不难发现仅选择一首歌的情况是一定满足要求的,对于每个 state ,枚举选中的歌 i(作为最后一首)与未选中的歌 j ,通过邻接矩阵查询 i 、j 是否能够相邻,若能相邻,更新 d p [ s t a t e ∣ ( 1 < < j ) ] [ j ] dp[state | (1 << j)][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';
}

相关推荐

  1. Codeforces Round 935 (Div. 3)

    2024-03-31 23:06:02       8 阅读

最近更新

  1. leetcode705-Design HashSet

    2024-03-31 23:06:02       8 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-03-31 23:06:02       8 阅读
  3. vue3、vue2中nextTick源码解析

    2024-03-31 23:06:02       9 阅读
  4. 高级IO——React服务器简单实现

    2024-03-31 23:06:02       8 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-03-31 23:06:02       7 阅读
  6. go第三方库go.uber.org介绍

    2024-03-31 23:06:02       8 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-03-31 23:06:02       10 阅读

热门阅读

  1. c语言:把百分制转化为等级制度(switch语句)

    2024-03-31 23:06:02       6 阅读
  2. 搭建语音打电话机器人需要哪些技术和资源

    2024-03-31 23:06:02       5 阅读
  3. 座次问题(蓝桥杯)

    2024-03-31 23:06:02       4 阅读
  4. css页面搭建案例

    2024-03-31 23:06:02       5 阅读
  5. 输入 wo xiang he ni jao peng you.,倒着打。

    2024-03-31 23:06:02       4 阅读
  6. NC20128 不重复数字

    2024-03-31 23:06:02       3 阅读
  7. ES6:Map()与WeakMap()

    2024-03-31 23:06:02       3 阅读