admin管理员组

文章数量:814298

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

A. Era (模拟)

比赛链接:

题目大意

给出长度为 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(位运算+数论)

比赛链接:

题目大意

现在给出一个长度为 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(思维)

比赛链接:

题目大意

给出一个长度为 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] a[i]% x ! = 0 x!=0 x!=0

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

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(思维+数学)

比赛链接:

题目大意

给出两个偶数 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集:

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

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

本文标签: Codeforces Round 752 (Div 2)部分题解(AD)