杂题合集
标题党去死
CF1714E Add Modulo 10
题意概述：
给出一个序列，可以给其中任意一个数加上当前它的个位数，问进行若干次操作后这个序列里的数能否全部相等。
解析：
思维题，不算难。
观察个位数，找规律：
- 个位数是 \(0\)：只能是 \(0\)。
- 个位数是 \(1\) ：\(1 → 2\)。
- 个位数是 \(2\) ：\(2 → 4 → 8 → 6 → 2\)。
- 个位数是 \(3\) ：\(3 → 6 → 2\)。
- 个位数是 \(4\)：\(4 → 8 → 6 → 2\)。
- 个位数是 \(5\)：\(5 → 0\)。
- 个位数是 \(6\)：\(6 → 2\)。
- 个位数是 \(7\)：\(7 → 4 → 8 → 6 →2\)。
- 个位数是 \(8\)：\(8 → 6 → 2\)。
- 个位数是 \(9\)：\(9 → 8 → 6 →2\)。
可见，除个位数为 \(0\) 和 \(5\) 外，所有的数都可将个位数变为 \(2\)。
对于个位数是 \(5\) 的数，就给它加上 \(5\)，此时只有其他数都与它相等，序列才合法。
对于其他数，都把它变成以 \(2\) 为个位数的数。注意到个位数从 \(2\) 再变到 \(2\)，相当于加了 \(20\)。
将变化后的数列sort一遍，判断相邻的两数之差是不是 \(20\) 的倍数就行了。
Code
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 2e5 + 10;
int t, n;
int num[MAXN];
inline int read(){
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
bool Check(){
sort(num + 1, num + 1 + n);
if(num[1] % 10 == 0){
if(num[n] == num[1]) return true;
else return false;
}
for(register int i = 2; i <= n; i++){
int cut = num[i] - num[i - 1];
if(cut % 20) return false;
}
return true;
}
int main(){
t = read();
while(t--){
n = read();
for(register int i = 1; i <= n; i++){
num[i] = read();
if(num[i] % 10 != 2){
switch(num[i] % 10){
case 1 : num[i] += 1; break;
case 3 : num[i] += 9; break;
case 4 : num[i] += 18; break;
case 5 : num[i] += 5; break;
case 6 : num[i] += 6; break;
case 7 : num[i] += 25; break;
case 8 : num[i] += 14; break;
case 9 : num[i] += 23; break;
}
}
}
if(Check()) puts("Yes");
else puts("No");
}
return 0;
}
CF1711B Party
题目概述：
给出一个 \(n\) 个点，\(m\) 条边的无向图，问删去多少的点使得删去的点权最小，且留下的点组成的图中有偶数条边。输出删去的点的点权和。
解析：
如果 \(m\) 为偶数，不用删点。
如果 \(m\) 为奇数，删点的同时删掉的边要为奇数条，大力分类讨论：
- 删一个点：显然要选择一个度数为奇数的点。
- 删两个点：再度大力分类讨论：
- 删去两个相连的，且度数都为偶数的点。
- 删去两个相连的，且度数都为奇数的点。
- 删去不相连的，度数一奇一偶的点：
但是我们可以只删去那个度数为奇数的点，这样做会更优，所以这种情况一定不会有最优解。
- 删三个点：先考虑删去一个度数为奇，两个度数为偶且两两不相连的点。但这样完全可以只删去那个度数为奇的点，所以删去三个点一定不会有最优解。
所以，最优解只有可能在三种情况中出现，即删掉一个度数为奇的点、删掉有相连的两个度数都为奇的点、删掉相连的两个度数都为偶数的点。
因为 \(n,m ≤ 1e5\)，删去一个点的直接枚举点，删去两个点的直接枚举边即可。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 10, MAXM = 1e5 + 10;
int t, n, m, ans;
int unhap[MAXN];
int from[MAXM], to[MAXM], deg[MAXN];
inline void Clear(){
ans = 2147483647;
memset(deg, 0, sizeof(deg));
}
inline int read(){
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
int main(){
t = read();
while(t--){
Clear();
n = read(), m = read();
for(register int i = 1; i <= n; i++)
unhap[i] = read();
for(register int i = 1; i <= m; i++){
int u, v;
u = read(), v = read();
deg[u]++, deg[v]++;
from[i] = u, to[i] = v;
}
if(!(m & 1)){
puts("0");
continue;
}
for(register int i = 1; i <= n; i++)
if(deg[i] & 1) ans = min(ans, unhap[i]);
for(register int i = 1; i <= m; i++){
int u = from[i], v = to[i];
if(!((deg[u] + deg[v]) & 1))
ans = min(ans, unhap[u] + unhap[v]);
}
printf("%d\n", ans);
}
return 0;
}