题意：有个遥控器，有+1-1+2-2+5-5，6个键，不允许把音量调整至负数（当音量<5，则无法按-5），求最少按键使得a变成b。
题解：一开始以为音量<5按-5会变成0，这样要多一个特判。由于给的数字的缘故，并不会有穿过去然后反过来减掉更优的，比如+4不需要+5-1，直接+2+2。所以直接模拟。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void test_case() {
int a, b;
scanf("%d%d", &a, &b);
if(a > b)
swap(a, b);
printf("%d\n", (b - a) / 5 + ((b - a) % 5 + 1) / 2);
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t = 1;
scanf("%d", &t);
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}题意：有个n点m边无向图，每个点是冰箱，每条边是一种锁，要求安排一种方法使得每个点的锁不被另一个点的锁覆盖。
题解：原本m可以>n，这题就很复杂了，应该就把多出来的边换掉一最昂贵的边，意思是取出目前最贵的一组(u,v)，然后连边(x,u)，(x,v)，这样就消费掉1条边且只增加了2x，当x取最小值时，比每次取出最小的(x,y)增加的x+y要便宜。但是这样贪心是不是有漏洞就不得而知了。现在规定m<=n，很显然不被另一个锁覆盖的意思就是要连至少两条边，且两条边连去不同的点。这样有解的时候当n>2且m=n时，方法是连成一个环。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void test_case() {
int n, m;
scanf("%d%d", &n, &m);
bool suc = (m == n && n > 2);
int sum = 0;
for(int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
sum += x;
}
if(!suc) {
puts("-1");
return;
}
printf("%d\n", 2 * sum);
for(int i = 1; i <= n - 1; ++i)
printf("%d %d\n", i, i + 1);
printf("%d %d\n", n, 1);
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t = 1;
scanf("%d", &t);
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}题意：一个n个数的序列，分成n-2个连续的三元组，三元组之间的顺序可调，三元组内部的顺序也可调。要求复原其中一种。保证有解。
题解：一头一尾肯定只出现1次，然后次头次尾只出现2次（当n>=4），安排好这两个之后，就一路确定下去了。但是怎么实现呢？考虑用一个vector存一个数的左右最多4个邻居，然后每次固定下来的数把邻居给删掉（置为-1），要注意修改其中元素的写法是for(auto &i: vec)，又学了一招新的。vec是真的方便。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans[100005], cnt[100005];
vector<int> nei[100005];
void test_case() {
int n;
scanf("%d", &n);
memset(cnt, 0, sizeof(cnt[0]) * (n + 1));
for(int i = 1; i <= n; ++i)
nei[i].clear();
for(int i = 1; i <= n - 2; ++i) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
++cnt[x], ++cnt[y], ++cnt[z];
nei[x].push_back(y);
nei[x].push_back(z);
nei[y].push_back(x);
nei[y].push_back(z);
nei[z].push_back(x);
nei[z].push_back(y);
}
for(int i = 1; i <= n; ++i) {
sort(nei[i].begin(), nei[i].end());
nei[i].resize(unique(nei[i].begin(), nei[i].end()) - nei[i].begin());
}
int h1 = -1;
int ch1 = -1, ch2 = -1;
for(int i = 1; i <= n; ++i) {
if(cnt[i] == 1)
h1 = i;
if(cnt[i] == 2) {
if(ch1 == -1)
ch1 = i;
else
ch2 = i;
}
}
if(nei[h1][0] != ch1 && nei[h1][1] != ch1)
swap(ch1, ch2);
int nh1 = -1;
for(int i = 1; i <= n - 1; ++i) {
ans[i] = h1;
ans[i + 1] = ch1;
for(auto j : nei[h1]) {
if(j != -1 && j != ch1) {
nh1 = j;
break;
}
}
for(auto &j : nei[ch1]) {
if(j == h1)
j = -1;
}
for(auto &j : nei[nh1]) {
if(j == h1)
j = -1;
}
h1 = ch1;
ch1 = nh1;
}
for(int i = 1; i <= n; ++i)
printf("%d%c", ans[i], " \n"[i == n]);
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t = 1;
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}题意：有一个格子农场，上面有一些格子是R表示有食物，有k只鸡，保证食物一定比鸡多，求一种分法使得食物尽可能平均，且每只鸡分到的地是连通的。平均是指极差最小。
题解：一个格子农场必定可以被一条往返扫的线（或者一条螺旋形的线）覆盖，其中线的任意一段都是连通的。然后贪心，每次分够当前鸡需要的食物就截断。要注意每个格子都要分给某只鸡，所以剩下的格子要分给最后一只鸡（不要使用memset）。输入的时候要注意写法，不是扫进g+1而是g[i]+1。要平均分那肯定m1取K/k的下整，m2取m1+1，然后m2的数量恰好就是K%k剩下的数量。左右扫描线的写法偷学了大神的写法，就按照i的奇偶性判断j的方向，然后j越界的瞬间阻止其越界并增加i（之前有个蛇梯棋的期望dp但是当时是给每个点赋值一个编号，这个太蠢了）。给字符编码还有一种偷懒的直接用if(isalnum(i))来搞。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char id[67];
char g[105][105], h[105][105];
void test_case() {
int r, c, k;
scanf("%d%d%d", &r, &c, &k);
for(int i = 1; i <= r; ++i)
scanf("%s", g[i] + 1);
int K = 0;
for(int i = 1; i <= r; ++i) {
for(int j = 1; j <= c; ++j) {
if(g[i][j] == 'R')
++K;
}
}
int m1 = K / k;
int m2 = m1 + 1;
int cntm2 = K % k;
int cntm1 = k - cntm2;
for(int i = 1; i <= r; ++i) {
for(int j = 1; j <= c; ++j)
h[i][j] = id[k];
}
int i = 1, j = 1, cntid = 0;
while(cntm1--) {
++cntid;
int rest = m1;
while(rest) {
h[i][j] = id[cntid];
if(g[i][j] == 'R')
--rest;
if(i & 1) {
++j;
if(j > c) {
j = c;
++i;
}
} else {
--j;
if(j <= 0) {
j = 1;
++i;
}
}
}
}
while(cntm2--) {
++cntid;
int rest = m2;
while(rest) {
h[i][j] = id[cntid];
if(g[i][j] == 'R')
--rest;
if(i & 1) {
++j;
if(j > c) {
j = c;
++i;
}
} else {
--j;
if(j <= 0) {
j = 1;
++i;
}
}
}
}
for(int i = 1; i <= r; ++i) {
for(int j = 1; j <= c; ++j)
printf("%c", h[i][j]);
printf("\n");
}
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int top = 0;
for(char i = '0'; i <= '9'; ++i)
id[++top] = i;
for(char i = 'A'; i <= 'Z'; ++i)
id[++top] = i;
for(char i = 'a'; i <= 'z'; ++i)
id[++top] = i;
int t = 1;
scanf("%d", &t);
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}Codeforces Round #601 (Div. 2)
原文：https://www.cnblogs.com/KisekiPurin2019/p/11896551.html