Codeforces Round 870 (Div. 2)AB

今天下午vp了两场div2，然后结果非常的惨淡，一共开了4道题，然后一道题目都没有做来了，这件很伤心的事情，但是正如高中的语文老师所说的，我应该值得庆幸，这是平常训练而不是考试，如果是考试的话自己就没了...

AProblem - A - Codeforces (Unofficial mirror by Menci)

一看题意感觉好难，没啥思路，而且脑子里面很混乱；

想了一会有了点思路，然后就开始写，我先用桶计数，设ans的初始值为150，人数最多为100人，

然后我开始枚举说谎的人数，当时我认为n-a[i]为说谎的人数，如果a[i]!=0&&n-a[i]>=i就为真的，然后ans取n-a[i]的最小值，如果ans最后为150，说明有矛盾。

然后就一直不对。赛后想了想，题目中说的是说谎的人至少为x，而不是正好是x，所以说谎的人数不一定为n-a[i]。

然后我把a[i]改为s[i]还是不对，仔细想下还是刚才那个原因：

下面是我的代码：

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<map>
#include<set>
#include <utility>
using namespace std;
typedef  long  long ll ;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;//106110956
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
void print(__int128 num) {
	if(num) {
		print(num/10);
		putchar(num%10+'0');
	}
}
int s[105];
int a[105];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		//memset(s,0,sizeof(s));
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++){
			int x;
			scanf("%d",&x);
			a[x]++;
		}
		if(a[0]==n){
			printf("0\n");
			continue;
		}
		int ans=150; 
		for(int i=0;i<=n;i++){
			if(a[i]!=0&&n-a[i]>=i){
				ans=min(ans,n-a[i]);
			}
		}
		if(ans==150){
			printf("-1\n");
		}else{
			printf("%d\n",ans);
		}
		
	}
 
	return 0;
}
 

正确思路：枚举说谎的人数i，然后枚举每个人给的说谎的人数a[j]，如果i<a[j]，就说明这个人说谎了，因为a[j]的意思是至少有a[j]人说谎；因为题目说如果有多种答案输出其中一种即可；

所以只要cnt==i，就break即可

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<map>
#include<set>
#include <utility>
using namespace std;
typedef  long  long ll ;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;//106110956
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
void print(__int128 num) {
	if(num) {
		print(num/10);
		putchar(num%10+'0');
	}
}
int a[105]; 
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		} 
		int flag=0;
		for(int i=0;i<=n;i++){
			int cnt=0;
			for(int j=1;j<=n;j++){
				if(a[j]>i)cnt++;
			}
			if(cnt==i){
				printf("%d\n",i);
				flag=1;
				break;
			}
		}
		if(flag==0)printf("-1\n");
	
	}
	return 0;
}
 

B：Problem - B - Codeforces (Unofficial mirror by Menci)

其实当时有一点思路了，然后自己就没思考清楚，就开始做题，导致错误；

这个毛病需要改一改了，带先理顺大概思路，才能写题！不然很吃亏！！！

 推理过程如下，如果一个数组a，a1==an,a2==an-1.....都相等的话，那么x为无限大，输出0，不然就x就是abs（a1-an）,abs(a2-an-1)......的最大公约数了注意此时（a1!=an,a2!=an-1），即gcd，

如果n为奇数，那么最中间的数是不需要考虑的！！

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<map>
#include<set>
#include <utility>
using namespace std;
typedef  long  long ll ;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;//106110956
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
void print(__int128 num) {
	if(num) {
		print(num/10);
		putchar(num%10+'0');
	}
}
ll a[100005];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		int flag=0;
		ll x;	
		for(int i=1,j=n;i<=j;i++,j--){
			if(a[i]==a[j]){
				continue;
			}else{
				if(flag==0){
					x=abs(a[i]-a[j]);
					flag=1;
				}else{
					x=__gcd(x,abs(a[i]-a[j]));
				}			
			}
		}
		if(flag==0){
			printf("0\n");
		}else{
			printf("%lld\n",x);
		} 
	}
	
	
	return 0;
}