Codeforces Round #752 (Div. 2)题解(A-D)

好久没写博客了,之前发现因为let’s encrypt证书过期的问题停止了几天(也许是两个月)服务,现在换证书以后恢复了。不过反正这小破站也就我一人看爬虫都比我活跃,能不能访问完全无所谓。
网站备好案到现在也有两年了,目前友情链接数量还是0,反正也是佛系站长。

A.Era

题意

给一个数组,你可以在任意位置插入一个数任意次,使得操作后的数组满足a_i \leqslant i,问最少的操作次数。

题解

满足那个条件就要尽可能把数向后移,我们很容易看出来我们可以不断的去插入1,然后维护一个插入次数的变量,看需要向后移动几位。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        int n;
        cin>>n;
        ll pl=0;
        int num[n+1];
        for(int i=1;i<=n;i++){
            cin>>num[i];
            if(num[i]>i+pl){
                pl+=num[i]-(i+pl);
            }

        }
        cout<<pl<<endl;
    }
    return 0;
}

B.XOR Specia-LIS-t

题意

给出一个数组,我们可以将这个数组分成k个非空子数组,这个k个子数组里面的最长上升子序列长度分别为h_i,求是否有所有h_i XOR的值为0的分法。

题解

分奇偶讨论,如果偶数,直接分成全部都是长度为1的子数组,偶数个1的XOR一定是0。
如果是奇数,我们只需要查找是否存在非递增处。如果存在,这个非递增处长度为2,h为1。其他地方直接为长度为1的子数组,依然是偶数个1。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        ll n;
        cin>>n;
        ll num[n+1];
        bool f=0;
        for(int i=0;i<n;i++){
            cin>>num[i];
            if(i>0&&num[i-1]>=num[i]) f=1;
        }
        if(n%2==0||(n%2==1&&f==1)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;

    }
    return 0;
}

C.Di-visible Confusion

题意

给出一个数组,在一次操作中,只要一个数满足a_i mod (i+1) !=0,这个数就可以删去,剩下的数接着做下一次操作,问有限次操作能不能把数组里面的数删完?

题解

贪心,优先删后面的,找了一遍发现都删不了就NO。因为数据范围摆在那,构造不出来卡T的数据。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        ll n;
        cin>>n;
        vector<ll> num(n);
        for(int i=0;i<n;i++){
            cin>>num[i];
        }
        bool f=1;
        while(!num.empty()){
            if(num.back()%(num.size()+1)!=0){
                num.pop_back();
                continue;
            }
            bool fl=0;
            for(int i=num.size()-2;i>=0;i--){
                if(num[i]%(i+2)!=0){
                    num.erase(num.begin()+i);
                    fl=1;
                    break;
                }
            }
            if(fl==0){
                f=0;
                break;
            }

        }

        if(f==1) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

D.Moderate Modular Mode

题意

给出两个数x,y,找出一个数n,使得n  mod  x = y  mod  n

题解

(准确来说这题是我猜出来的结果,证明非常可能出现不严谨之处)
分三种情况,如果x=y,直接输出x,这个不解释。
如果x>y,令n>x>y,条件可直接简化为n  mod  x = y,我们可以推导出n-ax=y。即n=y+ax,a为任意正整数。
如果x<y,如果二者存在倍数关系,直接就是小的那个,否则,模数一定在(x,y)之内。因为都是偶数,所以他们模的中间值就可以使得它们的模相等。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        ll x,y;
        cin>>x>>y;
        ll n;
        if(x==y){
            cout<<x<<endl;
            continue;
        }
        if(x>y){
            cout<<x+y<<endl;
        }
        else{
            if((x+y)%x==0){
                cout<<x<<endl;
            }
            else{
                cout<<y-(y%x)/2<<endl;
            }
        }
    }
    return 0;
}
知识共享许可协议
Text is available under CC BY-NC-SA 4.0 unless otherwise stated.

除非特殊声明,本站所有内容均以 CC BY-NC-SA 4.0协议授权。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇