Codeforces Round #600 (Div. 2) ---- 比赛传送门
昨晚成绩还好，AC A，B题，还能上分（到底有多菜）
补了C、D题，因为昨晚对C、D题已经有想法了，所以补起题来也快。（C题TLE了，D题想用并查集没好）
A
// http://codeforces.com/contest/1253/problem/A
/*
如果YES，则b[i] - a[i] 在一个区间里的差肯定是相同的且不小于0
*/
#include<iostream>
#include<cstdio>
using namespace std;
int a[100005], b[100005];
int tar[100005];
int T, n, l, r, k;
int main()
{
scanf("%d", &T);
while(T--){
bool flag = true;
int pla = -1, num = 0, x = -1; // pla 来存储第一个差不为 0 的位置 x 存第一个不为 0 的差值
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 0; i < n; i++){
scanf("%d", &b[i]);
tar[i] = b[i] - a[i];
if(tar[i] != 0) {
if(pla == -1) { pla = i; x = tar[i]; } // 找到第一个 不等的点
num++; // num 来记录有多少个不同点
}
}
if(pla == -1) printf("YES\n");
else {
for(int i = pla; i < n && num > 0; i++, num--){
if(tar[i] != x){ // 一个个校对
flag = false;
break;
}
}
if(x < 0) flag = false; // 特判第一个不等已经是 < 0 时
if(flag) printf("YES\n");
else printf("NO\n");
}
}
return 0;
}
B
// http://codeforces.com/contest/1253/problem/B
/*
因为分置的天数不需要最大或者最小，所以就直接处理最多天数的情况
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int num[1000006], c;
int in[1000006]; // 记录员工是否已上班已下班，0表示没上班，1表示还没下班，2表示已经下班
int ans[1000006], ans_count;
int n, a, tot, num_c, ans_c;
int main()
{
bool flag = true;
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a);
if(a > 0){
if(in[a] != 0) flag = false; // 如果已经上班了还上班，false
else { // 符合情况
in[a]++;
num[c++] = a; // 记录已经上班的员工
tot += a;
}
}
else {
if(in[-a] != 1) flag = false; // 已经下班了或者还没上班还下班，false
else { // 符合情况
in[-a]++;
tot += a;
}
}
num_c++;
if(tot == 0){ // tot == 0的时候既公司没人的时候
ans[ans_c++] = num_c;
num_c = 0;
for(int j = 0; j < c; j++){ // 初始化 用 memset 会超时
in[num[j]] = 0;
}
c = 0; // 初始化
}
}
if(n & 1) flag = false; // 特判 n 为奇数时
if(tot != 0) flag = false; // 特判最后一天 tot != 0 即公司的员工有人还没下班
if(flag){ // 符合情况 输出答案
printf("%d\n", ans_c);
for(int i = 0; i < ans_c; i++){
printf("%d%c", ans[i], i == ans_c - 1 ? '\n' : ' ');
}
}
else printf("-1\n"); // 不符合情况时输出 -1
return 0;
}
C
参考题解（官方）：
// http://codeforces.com/contest/1253/problem/C
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n, m;
int sweet[200005];
long long ans[200005];
// 前缀和 O(nlogn) ---- 主要用在了排序
int main(){
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &sweet[i]);
sort(sweet + 1, sweet + n + 1);
long long tot = 0;
for(int i = 1; i <= n; i++){
tot += sweet[i];
ans[i] = tot;
if(i > m){ // 当吃的比m大的时候，只是比 i - m 一天多了个 ans[i - m](可以在纸上写写)
ans[i] += ans[i - m]; // 前缀和
}
printf("%I64d%c", ans[i], i == n ? '\n' : ' ');
}
return 0;
}
/* O(n^2) TLE
int main()
{
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++){
scanf("%d", &sweet[i]);
}
sort(sweet, sweet + n);
double M = m;
for(int i = 1; i <= n; i++){
int day = ceil(i / M);
int eat = i;
int day_can = m;
int day_s = 1;
long long tot = 0;
while(eat > 0){ // 模拟操作
tot += sweet[eat - 1] * day_s;
// printf("tot:%I64d sweet:%d day_s:%d can:%d\n", tot, sweet[eat - 1], day_s, day_can);
day_can--;
if(day_can == 0){
day_s++;
day_can = m;
}
eat--;
}
// printf("\n");
ans[i] = tot;
// printf("day:%d\n", day);
}
for(int i = 0; i < n; i++){
printf("%d%c", sweet[i], i == n - 1 ? '\n' : ' ');
}
for(int i = 1; i <= n; i++){
printf("%I64d%c", ans[i], i == n ? '\n' : ' ');
}
return 0;
}
*/
D
参考题解的出处在代码里
// http://codeforces.com/contest/1253/problem/D
// 参考：Marca 的 #65186644 的 AC 代码
#include<iostream>
#include<cstdio>
using namespace std;
int n, m, a, b, x, y, ans;
int par[200005];
void init(int n){
for(int i = 1; i <= n; i++) par[i] = i;
}
int ff(int x){
if(par[x] == x) return x;
else return par[x] = ff(par[x]);
}
// 并查集解法
int main()
{
scanf("%d %d", &n, &m);
init(n);
for(int i = 0; i < m; i++){
scanf("%d %d", &a, &b);
x = ff(a);
y = ff(b);
// 把点大的都做树的根节点
if(x > y) swap(x, y);
par[x] = y;
}
for(int i = 1; i <= n; i++){
x = ff(i); // ff函数已包含路径压缩
while(i < x){
y = ff(i);
if(x != y){ // 不在一个区间里 合并
ans++; // 路径 ++
// 把点大的做树的根节点
if(y > x) swap(x, y);
par[y] = x;
}
i++;
}
}
printf("%d\n", ans);
return 0;
}
记录我这菜鸟的成长经历