国庆模拟赛DAY$03$

A. 减法和求余

排序枚举。

这道题目我们发现减法和求余都是有规律的，减法是前$n-1$个数累减起来，再用$n$减去即可，而余数是直接输出$a_1$即可。

注意：

• 要开$long$ $long$。
• 若$n=1，k=1$，直接输出$a_1$即可。

（我就是都犯了这些毛病，所以只拿了$80$分，下一次一定要好好审题！！！！！！！！）

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010];
signed main(){
	freopen("divmod.in","r",stdin);
	freopen("divmod.out","w",stdout);
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);
	if(k==1){
		if(n==1){
			cout<<a[1];
			return 0;
		}
		int sum=a[1];
		for(int i=2;i<=n;i++){
			if(i==n){
				cout<<a[i]-sum;
				return 0;
			}
			sum-=a[i];
		}
	}
	else cout<<a[1];
	return 0;
}

B. 回文串

分类讨论字符串模拟。

这道题目我们可以看有几组要改的字母（设$cnt$为表示有几组要改的字母的变量），会分为以下几种情况：

• $cnt=2$，直接将这两组都分别改成两组中小的那一个字母，然后输出。
• $cnt=1$，会有以下几种情况：
  • 那一组有一个字母是$a$，将这一组都改成$a$，然后又会有两种情况：
    • 长度是奇数，将正中间的字母改成$a$。
    • 长度是奇数，输出。
  • 那一组两个字母都不是$a$，将这一组都改成$a$，输出。
• $cnt=0$​，会有以下几种情况：
  • 第一组有一个字母是$a$，将这一组都改成$a$，然后又会有两种情况：
    • 长度是奇数，将正中间的字母改成$a$。
    • 长度是奇数，输出。
  • 那一组两个字母是$a$，那么就遍历每一组，直到找到一个都不是$a$的一组，将这一组都改成$a$，输出。
  • 那一组两个字母都不是$a$，将这一组都改成$a$，输出。

根据这些来写即可。

注意：

• 不要漏了$cnt=1$与$cnt=0$的情况（我就是犯了这毛病，所以只拿了$90$分，下一次一定不能漏情况了）。

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("hw.in","r",stdin);
	freopen("hw.out","w",stdout);
	string s;
	cin>>s;
	int cnt=0;
	for(int i=0;i<=(s.size()-1)/2;i++) if(s[i]!=s[s.size()-i-1]) cnt++;
	if(cnt==2){
		int sum=0;
		for(int i=0;i<=(s.size()-1)/2;i++){
			if(s[i]!=s[s.size()-i-1]){
				if(s[i]>s[s.size()-i-1]) s[i]=s[s.size()-i-1];
				else s[s.size()-i-1]=s[i];
				sum++;
				if(sum==2) break;
			}
		}
	}
	else if(cnt==1){
		for(int i=0;i<=(s.size()-1)/2;i++){
			int sum=0;
			if(s[i]!=s[s.size()-i-1]){
				if(s[i]=='a') sum++;
				if(s[s.size()-i-1]=='a') sum++;
			    s[i]='a',s[s.size()-i-1]='a';
			    if(sum==1&&s.size()%2==1) s[s.size()/2]='a';
			}
		}
	}
	else{
		int sum=0;
		if(s[0]=='a') sum++;
		if(s[s.size()-1]=='a') sum++;
		s[0]='a',s[s.size()-1]='a';
		if(sum>=1&&s.size()%2==1) s[s.size()/2]='a';
		else if(sum==2){
			for(int i=0;i<=(s.size()-1)/2;i++){
				int sum=0;
				if(s[i]!='a'){
					s[i]='a',s[s.size()-i-1]='a';
					break;
				}
			}
		}
	}
	cout<<s;
	return 0;
}

C. 涂色仪式

数学。

被这道题目唬住了，本来以为很难，就去做其他的题去了，下一次一定不能这样了！！！

这道题目看起来是要用数据结构，实际上因为这是一个复杂的树状结构，所以一定有一个加起来会变成偶数，所以这道题目实际上就是让你求有几个数加起来是质数，那么我们用质数筛就可以了。

#include<bits/stdc++.h>
using namespace std;
int a[300010],st[2000010],idx;
void init(){
	for(int i=2;i<=2000010;i++) if(!st[i]) for(int j=i+i;j<=2000010;j+=i) st[j]=1;
}
int main(){
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	init();
	int n,cnt=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	n--;
	while(n--){
		int u,t;
		cin>>u>>t;
	    if(st[a[u]+a[t]]==0) cnt++;
	}
	cout<<cnt;
	return 0;
}

D. 除法来咯

数学。

这题是真想不到呀！！！！

对于这道题目我们可以枚举商，商的范围是$[1$~$5]$。

而被除数的上限是$1e6×$商，被除数的下限是$a_i$与$j$的除数与余数，所以我们由此可得一个条件，若$(a_ij)>(a_i$÷$1000000<=j)$，那么就不行。

最后求出最大值即可，

#include<bits/stdc++.h>
using namespace std;
int a[100010],f[10];
int main(){
	freopen("div.in","r",stdin);
	freopen("div.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		for(int j=1;j<=5;j++) f[j]+=((a[i]/j)>(a[i]%j)&&(a[i]/1000000<=j));
	}
	int ans=0;
	for(int i=1;i<=5;i++) ans=max(ans,f[i]);
	cout<<ans;
	return 0;
}