codeforces - 1253 (div2)

A - Single Push

if  、 else 特判

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#pragma GCC optimize(2)
#define mm(i,v) memset(i,v,sizeof i);
#define mp(a, b) make_pair(a, b)
#define one first
#define two second
using namespace std;
typedef long long ll;
typedef pair<int, int > PII;
const int N = 1e5 + 5, mod = 1e9 + 9, INF = 0x3f3f3f3f;
int t, n, idx;
int a[N], b[N];
int main()
{
//
freopen("in.txt", "r", stdin);
//
freopen("out.txt", "w", stdout);
//
cin.tie(0);
//
cout.tie(0);
//
ios::sync_with_stdio(0);
cin >> t;
while (t--) {
cin >> n;
int flag = 1;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i) {
scanf("%d", &b[i]);
if (b[i] < a[i]) flag = 0;
}
if (!flag) {
puts("NO");
continue;
}
idx = 0;
flag = 1;
for (int i = 1; i <= n; ++i) {
if (a[i] == b[i] && flag == 1) {
continue;
} else if (a[i] != b[i] && flag == 1) {
idx = b[i] - a[i];
flag = 2;
continue;
} else if (flag == 2) {
if (b[i] != a[i]) {
if (b[i] - a[i] != idx) {
flag = -1;
break;
}
} else if (a[i] == b[i]) {
flag = 3;
continue;
}
} else if (flag == 3) {
if (a[i] != b[i]) {
flag = -1;
break;
}
}
}
if (flag == -1) puts("NO");
else puts("YES");
}
}

B - Silly Mistake

如果出现一个没有进入办公室的人走出来或者出现重复进入的情况就直接输出-1，别的情况就是每当进入办公室的人全部出去之后就把他们当作一个区间，剩下的重新进行开始的步骤。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#pragma GCC optimize(2)
#define mm(i,v) memset(i,v,sizeof i);
#define mp(a, b) make_pair(a, b)
#define one first
#define two second
using namespace std;
typedef long long ll;
typedef pair<int, int > PII;
const int N = 1e6 + 5, mod = 1e9 + 9, INF = 0x3f3f3f3f;
int n, ans, in, out, cnt, res;
int a[N];
map<int, PII> q;
queue <int> tq;
int main()
{
scanf("%d", &n);
int flag = 1;
PII t;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
//
if (flag == -1)
//
continue;
if (a[i] > 0) {
t = mp(0, 0);
if (q[a[i]] == t) {
t = mp(1, 1);
q[a[i]] = t;
in++;
//
} else if (q[a[i]] == mp(0, 1)) {
//
if (in != out)
//
flag = -1;
} else {
flag = -1;
}
} else if (a[i] < 0){
t = mp(1, 1);
if (q[-a[i]] == t) {
t = mp(0, 1);
q[-a[i]] = t;
out++;
} else {
flag = -1;
}
}
ans += a[i];
//
cout << ans << " " << in << " " << out << endl;
if (ans == 0 && in == out) {
tq.push(in << 1);
res += (in << 1);
cnt++;
q.clear();
in = 0;
out = 0;
}
}
if (res != n) flag = -1;
if (flag == -1)
cout << flag << endl;
else {
cout << cnt << endl;
while (tq.size()) {
int x = tq.front();
tq.pop();
cout << x << " ";
}
cout << endl;
}
}
/*
4
1 -1 2 3
*/

C - Sweets Eating

a数组记录糖果，把a数组sort一遍后用arr记录他的前缀和

推一下公式可以发现k[i] = arr[i] + k[i - m] ，注意要先预处理1到m的k

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#pragma GCC optimize(2)
#define mm(i,v) memset(i,v,sizeof i);
#define mp(a, b) make_pair(a, b)
#define one first
#define two second
using namespace std;
typedef long long ll;
typedef pair<int, int > PII;
const int N = 2e5 + 5, mod = 1e9 + 9, INF = 0x3f3f3f3f;
ll n, m;
ll a[N], arr[N], k[N];
int main()
{
//
freopen("in.txt", "r", stdin);
//
freopen("out.txt", "w", stdout);
//
cin.tie(0);
//
cout.tie(0);
//
ios::sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) arr[i] = arr[i - 1] + a[i];
for (int i = 1; i <= m; ++i) {
k[i] = arr[i];
cout << k[i] << " ";
}
for (int i = m + 1; i <= n; ++i) {
k[i] = k[i - m] + arr[i];
cout << k[i] << " ";
}
cout << endl;
}

D - Harmonious Graph

用并查集维护每个集合，维护的时候要注意每个集合的根节点要是该集合最大的结点。然后遍历一遍1到n，遍历的过程中不断更新 i 到 p[i] ，如果 i 和 p[i] 之间的点他们所在的集合的根节点不等于p[i] ，那么就把这两个点所在集合union起来，注意这个过程仍然要遵循把两个集合中最大的那个结点作为根节点的原则。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#pragma GCC optimize(2)
#define mm(i,v) memset(i,v,sizeof i);
#define mp(a, b) make_pair(a, b)
#define one first
#define two second
using namespace std;
typedef long long ll;
typedef pair<int, int > PII;
const int N = 2e5 + 5, mod = 1e9 + 9, INF = 0x3f3f3f3f;
int n, m;
int p[N];
int find(int x)
{
if (p[x] != x) return p[x] = find(p[x]);
return p[x];
}
void Union(int x, int y) {
}
int main()
{
//
freopen("in.txt", "r", stdin);
//
freopen("out.txt", "w", stdout);
//
cin.tie(0);
//
cout.tie(0);
//
ios::sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) p[i] = i;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
if (find(x) > find(y)) p[find(y)] = find(x);
else p[find(x)] = find(y);
}
int i, j;
int res = 0;
for (i = 1; i <= n; ++i) {
int Max = find(i);
while (i < Max) {
if (find(i) != Max) {
if(find(i) > Max) {
p[Max] = find(i);
Max = find(i);
}
else p[find(i)] = Max;
++res;
}
++i;
}
}
cout << res << endl;
}