Codeforces Round #818 (Div. 2)

出现了一些很严重的问题，，思路有了代码写不对，队内主代码手这样很危险啊。

A. Madoka and Strange Thoughts

给出数字n，求从1~n中满足lcm(a,b)/gcd(a,b)<=3的a，b对数。

思路：这个相除表示两数的最小公倍数最多是最大公因数的3倍，说明两数中较大数最多是较小数的三倍，这样直接计算即可。

AC Code：

#include 
 
typedef long long ll;
const int N=1e5+5;
ll t,n;
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n;
		ll ans=n;
		ans+=n/2*2+n/3*2;
		std::cout<'\n';
	}
	return 0;
}

B. Madoka and Underground Competitions

给出一个n*n的矩阵，规定一个点为‘X’，从上下左右四个方向上每隔k个格子最少有一个'X’，其他的格子上是‘.’ ，最小化‘X’的个数，输出构造的矩阵。

思路：我们最小化X的个数的方式是从规定位置开始斜着赋值，每一个赋X，然后再看每一行，在该行赋了X的位置向左向右每隔k个赋X，能保证这样满足要求时用的X最少。

AC Code：

#include 
 
typedef long long ll;
const int N=505;
int t,n,k,r,c;
char s[N][N];
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n>>k>>r>>c;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				s[i][j]='.';
			}
		}
		for(int i=0;i+r<=n;i++){
			int x=i+r,y=c-i;
			for(int j=y;j<=n;j+=k){
				if(j>=1) s[x][j]='X';
			}
			for(int j=y;j>=1;j-=k){
				if(j<=n) s[x][j]='X';
			}
		}
		for(int i=1;r-i>=1;i++){
			int x=r-i,y=c+i;
			for(int j=y;j<=n;j+=k){
				if(j>=1) s[x][j]='X';
			}
			for(int j=y;j>=1;j-=k){
				if(j<=n) s[x][j]='X';
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				std::cout<
			}
			std::cout<<'\n';
		}
	}
	return 0;
}

C. Madoka and Formal Statement

给出两个数组a和b，对a数组进行操作，当该数后一个数大于它时，可以将该数+1， 对于最后一个数，则是与第一个数比较，问是否可以经过若干次操作使得a数组等于b数组。

思路：首先显而易见的一点是，如果a数组中存在某个数大于b数组，那一定不满足条件；另外在目标数组中，前一个数最多比后一个数大1，因为两数相等之后，前一个数最多还能进行一次+1操作。

AC Code：

#include 
 
typedef long long ll;
const int N=505;
int t,n;
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n;
		std::vector<int>a(n),b(n);
		for(auto &x:a) std::cin>>x;
		for(auto &x:b) std::cin>>x;
		bool flag=true;
		for(int i=0;i
			if(a[i]>b[i]){
				flag=false;
				break;
			}
			if(a[i]b[(i+1)%n]+1){
				flag=false;
				break;
			}
		}
		std::cout<<(flag?"YES":"NO")<<'\n';
	}
	return 0;
}

os：跟着cup-pyy佬学习了一些新奇的写法，注意这样输入数组的值需要定义等大小的vector。

D. Madoka and The Corruption Scheme

M希望最后胜利的人的编号尽可能小，因为这样主办方给他的钱会多，而主办方则会不定向地修改比赛结果，使得花钱更少，即最后赢家的编号尽可能大，所以我们可以认为两者的目标是对立的。而现在对于这个比赛，M可以做的是修改一开始的顺序和决定每一局谁胜谁负，主办方可以修改k场比赛的结果。求最后的赢家编号，要对1e9+7取模。

思路：显而易见的是每个人如果想最后取得胜利，那他必须要赢n局比赛。现在可以分类讨论：如果k>=n，那主办方一定可以使编号最大的人胜利，因为使一个人胜利最多的修改次数是n次，这种情况下输出的答案就是最大的编号2^n；当k

AC Code：

#include 
 
#define int long long
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
int t,n,k;
int fact[N],infact[N];
 
int pmod(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return res;
}
 
void init(){
	fact[0]=infact[0]=1;
	for(int i=1;i<=N-3;i++){
		fact[i]=fact[i-1]*i%mod;
		infact[i]=infact[i-1]*pmod(i,mod-2)%mod;
	}
}
 
int C(int n,int x){
    return fact[n]*infact[n-x]%mod*infact[x]%mod;
}
 
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    init();
    std::cin>>n>>k;
    if(k>=n){
        std::cout<<pmod(2,n)%mod<<'\n';
        return 0;
    }
    int ans=0;
    for(int i=0;i<=k;i++){
        ans=(ans+C(n,i))%mod;
    }
    std::cout<'\n';
    return 0;
}

os：看题意搞了三天，终于搞出来了！！！！！

E是欧拉函数，数论嘛完全不会的，溜了溜了