A. Era (模拟)

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

题目大意

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

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

思路

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

没想到什么妙招，干脆硬模拟。
假设现在的位置为$ans$，我们遍历到了$a[pos]$，那么有：

1. $a[pos]<=ans$：符合条件，不需要在$a[pos]$的前面插入数字；
2. $a[pos]>ans$：不符合条件，至少需要在$a[pos]$的前面插入$a[pos]-ans$个数字才能使得$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$的数组$a$。
我们规定，一个数组中最长递增子序列的长度为这个数组的$h$值。例如数组2 5 3 1 4的$h$值为$3$。
我们可以把数组$a$分成$k$个子数组，而这些子数组的$h$值按照子数组的顺序可以组成一个新的数组$H$：$h_1$，$h_2$，$h_3$，…，$h_k$。

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

思路

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

异或的运算规则

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

异或的一些特点

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

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

其次，如果数组的长度为奇数，那么我们就要找出一个递减的片段($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$的数组$a$。
如果数组$a$中的$a[i]$满足a[i]%(i+1)!=0，则你可以消除它。

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

思路

假设$a[i]$之前的数字都可以被消除，那么消除$a[i]$的条件就是在$2$ ~ $(i+1)$的范围内存在$x$使得$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$与$y$，求出一个$n$的值使得$n$%$x$==$y$%$n$。

思路

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

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

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

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

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

我们都知道，$n$ % $x$ == $n-n$ / $x\ast x$。
而$n<y$，所以$n/x$的值最大可以是$y/x$，而n的最大值的范围可以在$(y/x\ast x，y)$内产生。

如上图所以，如果我们选择区间$(y/x\ast x，y)$内的一点作为$n$的取值，则图中$a$的值就是$n$%$x$的值，$b$的值就是$y$%$n$的值。
如果$a==b$，$x$与$y$又一定是偶数，那么$n$的值就是这个区间的中点：$(y/x\ast x+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集：

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

---

吾日三省吾身：日更否？刷题否？快乐否？ 更新了，但不是日更；已刷；平静 路漫漫其修远兮，吾将上下而求索