减法和求余（数学）

思路没想到的原因

没有想到一种特殊情况。以后在写之前一定要再三思考有没有特殊情况（一般都有）。

思路

• 减法运算：所有数字之和减去两倍的最小值。

• 模运算：本质就是求最小值。

不要忘记特殊情况：当$n==1$时，直接输出$a[1]$。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=1e5+10;
int a[tt];

signed main(){
	freopen("divmod.in","r",stdin);
	freopen("divmod.out","w",stdout);
	int n,k;
	cin >>n>>k;
	int min_n=0x3f3f3f3f;
	int sum=0;
	for(int i=1;i<=n;i++){
		cin >>a[i];
		min_n=min(min_n,a[i]);
		sum+=a[i];
	}
	if(n==1&&k==1){
		cout <<a[1];
		return 0;
	} 
	if(k==1){//减法 
		cout <<sum-min_n*2;
	}else{//模运算 
		cout <<min_n;
	}
	return 0;
}

回文串（字符串&模拟）

思路

题目要求至多修改两个字符。具体步骤如下：

1. 先枚举整个字符串，使其变成回文串（使用最小代价）；
2. 如果能够继续修改（次数$<=1$），就从前往后枚举。若当前位置之前修改过，就只要把相对位置改成'a'，修改次数$+1$。
3. 若当前位置之前没有修改过，就把两个位置都改成'a'，修改次数$+2$。
4. 当字符串的长度是奇数时，其他位置都是最优的，尤其不要忘记特判中间的位置。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
	freopen("hw.in","r",stdin);
	freopen("hw.out","w",stdout);
	string s;
	cin >>s;
	int cnt=0;
	int sum_1=0,sum_2=0;
	for(int i=s.size()-1;i>=s.size()/2;i--){
		if(s[i]==s[s.size()-1-i]) continue;
		cnt++;
		if(cnt==1){
			sum_1=s.size()-1-i;
		}else if(cnt==2){
			sum_2=s.size()-1-i;
		}
	}
	if(cnt==1){
		char z=min(s[sum_1],s[s.size()-1-sum_1]);
		s[sum_1]='a';
		s[s.size()-1-sum_1]='a';
		if(z=='a'&&s.size()%2==1){
			s[s.size()/2]='a';
		}
	}else if(cnt==2){
		char z1=min(s[sum_1],s[s.size()-1-sum_1]);
		char z2=min(s[sum_2],s[s.size()-1-sum_2]);
		s[sum_1]=z1;
		s[s.size()-1-sum_1]=z1;
		s[sum_2]=z2;
		s[s.size()-1-sum_2]=z2;
	}else{
		for(int i=0;i<s.size();i++){
			if(s[i]!='a'){
				s[sum_1]='a';
				s[s.size()-1-sum_1]='a';
				break;
			}
		}
	}
	cout <<s;
	return 0;
}

涂色仪式（数学）

思路

其实本题只要判断两个连接节点的和是否为质数。是的话，答案$+1$。

本题需要用到质数筛对判断质数进行预处理，不然会超时。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=2e6+10;
int a[tt];
int flag[tt],prime[tt];

void is_primes(){
	int cnt=0;
	for(int i=2;i<=tt;i++){
		if(flag[tt]==0){
			prime[++cnt]=i;
		}
		for(int j=1;j<=cnt&&i*prime[j]<tt;j++){
			flag[i*prime[j]]=1; 
			if(i%prime[j]==0) break;
		}
	}
}

signed main(){
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	is_primes();
	int n;
	cin >>n;
	for(int i=1;i<=n;i++){
		cin >>a[i];
	}
	int sum=0;
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin >>u>>v;
		if(flag[a[u]+a[v]]==0){
			sum++;
		}
	}
	cout <<sum;
	return 0;
}

除法来咯（数学）

思路没想到的原因

只是输出了$n$，骗了$30$分。

思路

可以直接枚举商，范围是$1$到$5$。为什么呢？

因为当$a[i]≤1e6$时，只有除数为$1$这一种方案，相等的数的数量才是最多的。而$2e6$又有$2$这个选项……

以此类推，$5e6$就有$5$种除数的选择方案。

再加一个判断a[i]/(tt-10)<=j，如果不满足，说明这个商得不到。

然后a[i]/j>a[i]%j就是要求除数（a[i]/j）大于余数（a[i]%j）。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=1e6+10;
int a[tt];
int f[tt];

signed 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]/(tt-10)<=j));
		}
	}
	int max_n=0;
	for(int i=1;i<=5;i++){
		max_n=max(max_n,f[i]);
	}
	cout <<max_n;
	return 0;
}

谢谢