你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

Codeforces Round #752 (Div. 2)部分题解(A ~ D)

2021-11-2 20:52:24

A. Era (模拟)

比赛链接:https://codeforces.com/problemset/problem/1604/A

题目大意

给出长度为 n n n的数组 a a a,每次我们可以任意选择一个位置插入任意一个数字。

问:至少要插入多少个数字才能使得数组 a a a中所有的数都满足 a i < = i a_i<=i ai<=i ?

思路

忠告:不要吃烧烤味的薯片。吃完搞得我跟发烧一样,差点没给我送走了。
上一次刚说完自己CF的A题能WA三发,结果还真成现实了,呜呜呜

没想到什么妙招,干脆硬模拟。
假设现在的位置为 a n s ans ans,我们遍历到了 a [ p o s ] a[pos] a[pos],那么有:

  1. a [ p o s ] < = a n s a[pos]<=ans a[pos]<=ans:符合条件,不需要在 a [ p o s ] a[pos] a[pos]的前面插入数字;
  2. a [ p o s ] > a n s a[pos]>ans a[pos]>ans:不符合条件,至少需要在 a [ p o s ] a[pos] a[pos]的前面插入 a [ p o s ] − a n s a[pos]-ans a[pos]ans个数字才能使得 a [ p o s ] a[pos] a[pos]符合条件;

AC代码

#include<bits/stdc++.h>
using namespace std;

int a[150];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1; i<=n; i++)
            cin>>a[i];
        int pos=1;
        int cnt=0;
        int ans=1;
        while(pos<=n){
            if(a[pos]>ans){
                cnt+=a[pos]-ans;
                ans=a[pos];
            }
            ans++;
            pos++;
        }
        cout<<cnt<<endl;
    }
}

B - XOR Specia-LIS-t(位运算+数论)

比赛链接:https://codeforces.com/contest/1604/problem/B

题目大意

现在给出一个长度为 n n n的数组 a a a
我们规定,一个数组中最长递增子序列的长度为这个数组的 h h h值。例如数组2 5 3 1 4 h h h值为 3 3 3
我们可以把数组 a a a分成 k k k个子数组,而这些子数组的 h h h值按照子数组的顺序可以组成一个新的数组 H H H h 1 h_1 h1 h 2 h_2 h2 h 3 h_3 h3,…, h k h_k hk

问:我们是否可以把数组 a a a拆成 k k k个子数组,使得由子数组的 h h h值构成的数组 H H H的异或和为 0 0 0

思路

异或真的是一个很常见又很有意思的位运算。

异或的运算规则

1^1=0
0^1=1
1^0=1
0^0=0

异或的一些特点

1.奇数个奇数异或得奇数
2.偶数个奇数异或得偶数
3.偶数异或得偶数
4.奇数与偶数异或得奇数

首先,如果数组的长度为偶数,那么我们可以把数组 a a a拆成 n n n个子数组,每个子数组的 h h h值都会是1。
偶数个1的异或和就是0。

其次,如果数组的长度为奇数,那么我们就要找出一个递减的片段( a [ i ] > a [ i + 1 ] a[i]>a[i+1] a[i]>a[i+1]),将这两个数分到一起,其他的数还是一个数字为一组,这样就又是偶数个1了。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;

int a[maxn];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        if(n&1){
            string flag="NO";
            for(int i=2;i<=n;i++)
            if(a[i-1]>=a[i]){
                flag="YES";
                break;
            }
            cout<<flag<<endl;
        }
        else cout<<"YES"<<endl;

    }
}

C - Di-visible Confusion(思维)

比赛链接:https://codeforces.com/contest/1604/problem/C

题目大意

给出一个长度为 n n n的数组 a a a
如果数组 a a a中的 a [ i ] a[i] a[i]满足a[i]%(i+1)!=0,则你可以消除它。

问:是否存在某种消除的顺序使得整个数组都可以被消除。

思路

假设 a [ i ] a[i] a[i]之前的数字都可以被消除,那么消除 a [ i ] a[i] a[i]的条件就是 2 2 2 ~ ( i + 1 ) (i+1) (i+1)的范围内存在 x x x使得 a [ i ] a[i]%x!=0 a[i]

就找一下有没有数字没法被消除就好了。

AC代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+100;

int a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        string flag="YES";
        for(int i=1;i<=n;i++){
            int tmp=0;
            for(int j=1;j<=i;j++)
            if(a[i]%(j+1)){
                tmp=1;
                break;
            }
            if(tmp==0){
                flag="NO";
                break;
            }
        }
        cout<<flag<<endl;
    }
}

D - Moderate Modular Mode(思维+数学)

比赛链接:https://codeforces.com/contest/1604/problem/D

题目大意

给出两个偶数 x x x y y y,求出一个 n n n的值使得 n n n% x x x== y y y% n n n

思路

如果 x > y x>y x>y,则 n n n可以直接取 x + y x+y x+y做值。如果 y y y可以整除 x x x,则 n n n可以直接取 y y y做值。

但是,如果 y y y即不能整除 x x x,又比 x x x大的时候 n n n的值怎么取,博主一开始是没想到的。

「是时候呼叫超级飞侠了!」

在这里插入图片描述

这是Fire_Ming队长的解释,其中他对这一情况的取值为: ( y / x ∗ x + y ) / 2 (y/x*x+y)/2 (y/xx+y)/2
那我就不是很理解了,于是决定去折磨他一下。

在和lm队长进行了一番深♂入的探讨之后,我决定自己来思考这个值的合理性。
如何把n的范围确定在 x x x ~ y y y之间的解释,请见lm队长的博客,我就不过多说明了。

我们都知道, n n n % x x x == n − n n - n nn / x ∗ x x * x xx
n < y n<y n<y所以 n / x n/x n/x的值最大可以是 y / x y/x y/x,而n的最大值的范围可以在 ( y / x ∗ x , y ) (y/x*x,y) (y/xxy)内产生。
在这里插入图片描述
如上图所以,如果我们选择区间 ( y / x ∗ x , y ) (y/x*x,y) (y/xxy)内的一点作为 n n n的取值,则图中 a a a的值就是 n n n% x x x的值, b b b的值就是 y y y% n n n的值。
如果 a = = b a==b a==b x x x y y y又一定是偶数,那么 n n n的值就是这个区间的中点: ( y / x ∗ x + y ) / 2 (y/x*x+y)/2 (y/xx+y)/2

这种题往往都是在推出结论的那一刻是最舒服的,恨不得喊一句"还有谁",但是人还是谦虚一点比较好。

AC代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+100;

int a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        ll x,y;
        cin>>x>>y;
        if(y<x) cout<<x+y<<endl;
        else if(y%x==0) cout<<y<<endl;
        else cout<<(y/x*x+y)/2<<endl;
    }
}

后话

感谢阅读,希望能对你产生一点用处。

以下台词取自《银魂》第77集:

在这里插入图片描述

"阿银,我被叫做恋姐情结也没关系。"
"我很喜欢姐姐,也不想和她分开"
"可以的话,我是很希望能一直和她在一起。"
"不过呢,如果姐姐她有了喜欢的人,"
"就算是万年没钱的可疑男人"
"猩猩跟踪狂,蛋黄酱控或超级虐待狂也好"
"只要姐姐能幸福,我也做好哭着送她离开的觉悟。"
"但是,要我看姐姐哭着离开,我真的做不到。"
"我好希望姐姐能一直笑着。"

吾日三省吾身:日更否?刷题否?快乐否?
更新了,但不是日更;已刷;平静
路漫漫其修远兮,吾将上下而求索

在这里插入图片描述