$320$ $pits$ $(ﾉ*･ω･)ﾉ$

T1 减法和求余

错误原因：没有考虑 $n = 1$ 的情况，思维不严谨

solution

减法：要让值最大，使数组中最大值减去一个尽可能小的负数，所以 $ans = \sum_{k=1}^n a_k - 2 * a_1$

除法：可以证明为数组中最小值

code

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

const int N = 1e5 + 5;

int n , k , a[N];

signed main(){
	freopen("divmod.in" , "r" , stdin);
	freopen("divmod.out" , "w" , stdout);
	
	cin >> n >> k;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	sort(a + 1 , a + n + 1);
	if(k == 1){
		int sum = 0;
		for(int i = 1 ; i <= n ; i ++){
			sum += a[i];
		}
		if(n == 1) cout << a[1];
		else cout << sum - 2 * a[1];
	}else{
		cout << a[1];
	}
	return 0;
}

T2 回文串

错误原因：没有考虑到每一种情况

solution

从前向后去遍历字符串，如果发现 $s_i != s_{n - i - 1}$ 那么记录次数 $f$ ，将字符改为两个中较小的一个 , 同时记录字符所在的位置

1. 若 $f = 0$ 从前向后去遍历 , 遇到不为 $a$ 的改为 $a$
2. 若 $f = 1$ 将记录的位置改为 $a$ ，特判要改的在中间的情况

code

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

string s;
int f , k;

int main(){
	freopen("hw.in" , "r" , stdin);
	freopen("hw.out" , "w" , stdout);
	
	cin >> s;
	int n = s.size();
	for(int i = 0 ; i <= n / 2 ; i ++){
		if(s[i] != s[n - i - 1]){
			if(s[i] > s[n - i - 1]) s[i] = s[n - i - 1];
			else s[n - i - 1] = s[i];
			f ++ , k = i;
		}
		if(f == 2) break;
	}
	if(f == 0){
		for(int i = 0 ; i < n ; i ++){
			if(s[i] != 'a'){
				s[i] = s[n - i - 1] = 'a';
				break;
			}
		}
	}else if(f == 1){
		if(s[k] != 'a'){
			s[k] = s[n - k - 1] = 'a';
		}else if(n % 2 == 1) s[n / 2] = 'a';
	}
	cout << s;
	return 0;
}

T3 涂色仪式

solution

先用欧拉筛法，用 $dfs$ 从叶节点向上搜索，具体的把判断 $(check)$ 放在递归的后面

code

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

const int N = 3 * 1e5 + 5;
const int inf = 2 * 1e6;

int n , w[N] , vis[N] , color[N];
int p[N] , idx , ans;     // 每个节点的出度 
bool isp[inf];        // 质数为 false
vector<int> g[N];

void resolve(){
	for(int i = 2 ; i <= 2 * 1e6 ; i ++){
		if(!isp[i]) p[++ idx] = i;
		
		for(int j = 1 ; j <= idx ; j ++){
			if(i * p[j] > 2 * 1e6) break;
			isp[i * p[j]] = true;
			if(i % p[j] == 0) break;
		}
	}
}

bool check(int u , int v){
	if(!isp[w[u] + w[v]] && color[u] == 0 && color[v] == 0) return true;
	return false;
}

void dfs(int x){
	vis[x] = 1;
	for(int i = 0 ; i < g[x].size() ; i ++){
		int t = g[x][i];
		if(vis[t]) continue;
		vis[t] = 1;
		dfs(t);
		if(check(x , t)){
			color[t] = 1;
			ans ++;
		}
	}
}

signed main(){
	freopen("color.in" , "r" , stdin);
	freopen("color.out" , "w" , stdout);
	
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> w[i];
	}
	for(int i = 1 ; i < n ; i ++){
		int x , y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	resolve();
	dfs(1);
	cout << ans;
	return 0;
}

T4 除法来咯

错误原因：没有思考清楚

solution

枚举商，若存在一个数 $k$ 使得可以被除，则累加答案，注意：商最多为 $5$

code

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

const int N = 1e5 + 5;

int n , a[N] , ans , f[55];

signed main(){
	freopen("div.in" , "r" , stdin);
	freopen("div.out" , "w" , stdout);
	
	cin >> n;
	for(int i = 1 ; i <= n ; i ++) cin >> a[i];
	
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= 5 ; j ++){
			f[j] += ((a[i] / j) > (a[i] % j) && (a[i] / 1000000 <= j));
		}
	}
	for(int i = 1 ; i <= 5 ; i ++) ans = max(f[i] , ans);
	cout << ans;
	return 0;
}