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]，那么有：
- 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]的前面插入 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/x∗x+y)/2。
那我就不是很理解了，于是决定去折磨他一下。
在和lm队长进行了一番深♂入的探讨之后，我决定自己来思考这个值的合理性。
如何把n的范围确定在
x
x
x ~
y
y
y之间的解释，请见lm队长的博客，我就不过多说明了。
我们都知道，
n
n
n %
x
x
x ==
n
−
n
n - n
n−n /
x
∗
x
x * x
x∗x。
而
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/x∗x，y)内产生。
如上图所以，如果我们选择区间
(
y
/
x
∗
x
，
y
)
(y/x*x，y)
(y/x∗x，y)内的一点作为
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/x∗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集：