[数据结构与算法] Codeforces Round #784 (Div. 4) AK题解

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Codeforces Round #784 (Div. 4) AK题解 -> 正文阅读

[数据结构与算法]Codeforces Round #784 (Div. 4) AK题解

小小纪念一下第一次ak cf div4 （虽然很简单，但据说CF此前只出现过一次 div4 灰常稀有）
链接：Round #784 (Div. 4)

A Division?

题目给出了不同分数对应等第 if语句判断输出即可

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
void solve()
{
    int n;
    cin >> n;
    if(n >= 1900)cout << "Division 1"<<endl;
    else if(1600<=n && n<=1899)cout << "Division 2"<<endl;
    else if(1400<=n && n<=1599)cout << "Division 3"<<endl;
    else if(n <=1399)cout << "Division 4"<<endl;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

B Triple

给定长度为 $n$ 的数组 $a i$ 询问数组是否存在某一数字出现的次数大于等于3,由于数字很小 $a i < n$ 所以我们用vis数组标记次数即可下标即代表值。若不存在ai的大小限制我们可以使用map记录效果相同

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
int vis[N];
void solve()
{
    int n;
    cin >> n;
    int ans = -1;
    for(int i=1;i<=n;i++)vis[i] = 0;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin >> x;
        vis[x] ++;
        if(vis[x] >= 3)ans = x;
    }
    cout << ans << endl;
    return ;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

C Odd/Even Increments

题意：

给定长度为 $n$ 的数组可以对偶数下标的或奇数下标的数全部加1并不限操作次数询问是否能使数组中所有数奇偶一至。

思路：

因为每次操作必须对全部偶数或奇数下标的数进行，所有对于下标奇偶相同的数来说每次变化是同步变化的，如果初始不同那么就不可能通过操作来使之相同。例如：1 2 2下标为1 3的数初始奇偶不同，对偶数下标操作对1 3下标无影响，对奇数下标操作也只能同时变化奇偶。于是判断一下是否初始数组奇数下标数/偶数下标数奇偶是否相同即可。

CODE：

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 110;
int a[N];
void solve()
{
    int n;
    cin >> n;
    bool F = true;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        if((i&1)&&a[i]%2!=a[1]%2)F = false;
        else if(i%2==0 && a[i]%2!=a[2]%2)F = false ;
    }
    if(F) cout << "YES" << endl;
    else cout << "NO" << endl;
    return ;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

D Colorful Stamp

题意：

给定长度为 $n$ 的字符串只存在 $^{'} R^{'}$ 红色 $^{'} B^{'}$ 蓝色 $^{'} W^{'}$ 白色三种字符，现在给你长度为 $n$ 的全部字符为 $W$ 的字符串。你有不限次数的操作，选定下标为 $i, i + 1$ 的字符使之改变为 $R B$ 或者 $B R$ 可以对同一字符重复操作，下标选定范围： $1 \leq i < n$ 。询问是否能进行若干次操作使字符串改变成给定的字符串

思路：

首先我们可以从题中得到：对于被 $W$ 隔开的子串可以单独拿出来判断，因为 $W$ 不能被染色改变，所有其互不存在影响 例如：WRRBWBBRW两个被隔开的子串RRB和BBR互不影响。接下来分情况讨论：

1.对于长度为1的字符串并且唯一字符为 $R$ 或 $B$ 是一定不可能得到的，所以可以据此推出单独的子串（被 $W$ 隔开的子串）如果其颜色为纯色且不为纯色的白色那么该子串是一定无法得到的 例如WBBW,WRR。

2.对于颜色非纯色的子串（即单独的子串中既包含 $B$ 又包含 $R$ ）我们先给出结论一定可以进行若干次操作得到，证明：对于相邻字符不存在相同字符的子串（即蓝色相邻的一定是红色，反之亦然）来说我们可以通过基本操作（ $B R$ , $R B$ ）来得到 $W W W$ -> $W R B$ -> $B R B$ 。
而相邻字符相等的子串来说也可以通过如下操作来得到 $W W W$ -> $W R B$ -> $R R B$ ， $R B B$ ， $B B R$ ， $B R R$ 也是如此。所以所有的子串我们都可以构造出来。
代码就很简单了，对于单独的子串计算R,B的数量若是一种颜色为0一种不为0说明该子串为非白色的纯色子串直接输出NO即可

CODE

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
char a[N];
void solve()
{
    int n;
    cin >> n;
    cin >> (a + 1);
    int sum1=0,sum2=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i] == 'R')sum1 ++;
        else if(a[i] == 'B')sum2 ++;
        
        if(a[i]=='W' || i==n)
        {
            if((sum1&&!sum2)||(!sum1&&sum2))
            {
                cout << "NO" << endl;
                return ;
            }
            sum1 = 0;
            sum2 = 0;
        }
        
    }
    cout << "YES" <<endl;
    return ;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

E 2-Letter Strings

题意：

给定 $n$ 个长度为2的字符串，询问有多少个字符串对 $(i, j) i < j$ 满足i字符串与j字符串有且仅有一个字符不同。

思路：

因为字符串长度只有两位我们用 $s 1$ $s 2$ 代表这两个字符，用 $c n t 1 ， c n t 2$ 数组分别记录第一个字符为 $s 1$ 的字符串第二个字符为 $s 2$ 的字符串的数量。
那么对于 $i$ 字符串： $c h 1, c h 2$ 的贡献就是加上第一个字符与 $c h 2$ 相同和第二个字符与 $c h 2$ 相同的字符串数量，最后去掉恰好为 $c h 1 c h 2$ 的字符串数量.因为计算第一个字符相同和第二个字符相同时恰好相等的字符串数量各被计算了一次，于是最后减去的要乘2。恰好为 $c h 1 c h 2$ 的字符串数量我们可以用map统计。于是 $ans = cnt1[ch1-'a'] + cnt2[ch2-'a'] - 2 * map[{ch1,ch2}];$ ，每次遍历过i后记得将i字符串的计数从cnt1中从cnt2中删除防止重复计算出现 $(i, j) i > = j 的情况$ 。例子：

n = 6
1.ac
2.ac
3.ak
4.ak
5.bc
6.bc
对于1.ac 第一个字符为a的字符串有1,2,3,4 共4个第二个字符为c的有1,2,5,6共4个
这两种都对1,2 ac进行了统计于是最后ans = 4 + 4 - 2 * 2

CODE

#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
ll s1[30],s2[30];
char ch1[N],ch2[N];
map<pair<char,char>,ll>mp;
void solve()
{
    int n;
    cin >> n;
    mp.clear();
    for(int i=1;i<=n;i++)
    {
        cin >> ch1[i] >> ch2[i];
        s1[ch1[i]-'a'] ++;
        s2[ch2[i]-'a'] ++;
        mp[{ch1[i],ch2[i]}] ++;
    }
    ll ans = 0;
    for(int i=1;i<=n;i++)
    {
        ll sum = s1[ch1[i]-'a'] + s2[ch2[i]-'a'] - 2 * mp[{ch1[i],ch2[i]}];
        ans += sum;
        s1[ch1[i]-'a'] --;
        s2[ch2[i]-'a'] --;
        mp[{ch1[i],ch2[i]}] --;
    }
    cout << ans << endl;
    return ;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

F Eating Candies

题意：

给定 $n$ 颗糖果重量为 $a i$ A只能从左往右吃，B只能从右往左吃，并且不能跳过不吃当前糖果去吃后面的。要求A和B吃到糖果重量一样，询问两人最多能吃到多少糖果。

思路：

只能向一个方向吃糖果，且要求重量相等我们想到了用前缀和。用map记录A的历史前缀和的下标即 $S 1 ? > S n$ ,接着从后往前求出B的前缀和对于每个 $S i$ 在map中进行查询若存在相等的，并且查询到的A的前缀和所在 $i d < i$ 那么就可以对答案进行更新。

例如:
6
2 1 4 2 4 1
map中记录的如下
2 3 7 9 13 14 从左往右的前缀和
1 2 3 4 5  6 前缀和对应的编号
从右先左求前缀和
 1  5 7 11 12 14
-1 -1 3 -1 -1 -1 map中记录的编号 只有7找到了对应的于是答案ans = 3 + n - 3 + 1

CODE

#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
int a[N];
map<ll,int>mp;
void solve()
{
    int n;
    cin >> n;
    mp.clear();
    ll sum1=0,sum2=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        sum1 += a[i];
        mp[sum1] = i;
    }
    int id;
    for(int i=n;i>=1;i--)
    {
        sum2 += a[i];
        if(mp.count(sum2))id = mp[sum2];
        else continue ;

        if(id < i)ans = id + n - i + 1;
        else break;
    }
    cout << ans << endl;
    return ;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

G Fall Down

模拟石头掉落的过程即可，因为列与列之间互不影响我们可以对每一列单独模拟

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 110;
char a[N][N];
void solve()
{
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++)scanf("%s",a[i] + 1);
    for(int i=1;i<=m;i++)//从列开始
    {
        for(int j=n,up=j;j>=1;up=j,j--)
        {
            if(a[j][i]=='o') continue ;

            int sum = 0;
            up = j;
            if(a[j][i]=='*')sum = 1;
            while(up - 1 >= 1 && a[up - 1][i]!='o')
            {
                up --;
                if(a[up][i]=='*')sum ++;
            }
            for(int k=0;k<sum;k++) a[j-k][i] = '*';
            for(int k=j-sum;k>=up;k--) a[k][i] = '.';
            j = up;
        }
    }
    for(int i=1;i<=n;i++)printf("%s\n",a[i] + 1);
    return ;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

H Maximal AND

题意：

很经典的cf位运算题，给定长度为 $n$ 的数组 $a$ 有 $k$ 次操作机会。可以使任意 $ai | 2^j(j<=30)$ 询问进行k次操作后将 $a 1 A N D a 2 A N D \dots A N D a n$ 后的最大值是多少。

思路：

因为二进制数 $A N D$ 操作不同数位之间没影响 ，最后得到的答案二进制位上如果是1要求所有的 $a i$ 二进制该数位上为1 于是我们贪心的从二进制的高位开始遍历数组，若 $a i$ 该位上为0那么计数 $s u m + +$ 将 $a 1 ? > a n$ 统计完后若小于等于 $k$ 说明该二进制数位可以通过若干操作使得全部 $a i$ 为1 答案加上该二进制数位代表的值，同时 $k ? s u m$

CODE

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
ll a[N],b[40],n,k;
void init()
{
    b[0] = 1;
    for(int i=1;i<=30;i++)b[i] = b[i-1] << 1;//预处理好二进制数位的值
}
void solve()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    ll ans = 0;
    for(int i=30;i>=0;i--)
    {
        int sum = 0;
        for(int j=1;j<=n;j++)
        {
            if(!(a[j]>>i&1)) sum ++;//位运算判断该位上二进制数位是否为1
        }
        if(k >= sum)
        {
            ans += b[i];
            k -= sum;
        }
    }
    printf("%lld\n",ans);
    return ;
}
int main()
{
    int T;
    init();
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}