Random Mushup

最近事情比较多(比较懒),所以把三场比赛一起补了,过程可能会简略些。

这场比赛比较迷,两题都是直接枚举过,主要是数学,并查集和dp,图论题没做出来。可能以后还会再补吧

  • 组合数学
  • 贪心,二分
  • 扩展欧几里得
  • 2-sat并查集处理
  • dp

A. Kyoya and Colored Balls

 

组合数学

每次先确定每种颜色最后一个球的位置,之后该种颜色其他的球就可以在剩下的位置上随便摆放,接着再确定下一种颜色最后一个球的位置,注意,每种颜色最后一个球的位置是确定的,当你已经摆完了所有的4号球后,3号球最后一个只能放在四号球前有空位的最近的地方,所以在求组合数时不能把最后一个球算在内。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
#define ll long long
const int maxn = 1000;
const int mod = 1000000007;
int k;
int a[maxn];
int sum;
ll ans = 1;
int C[maxn][maxn];
void init() {
for (int i = 0; i < maxn; i++) {
C[i][i] = 1;
C[i][0] = 1;
}
for (int i = 1; i < maxn; i++) {
for (int j = 1; j < i; j++) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
}
}
int main() {
init();
cin.sync_with_stdio(false);
cin >> k;
for (int i = 0; i < k; i++) {
cin >> a[i];
sum += a[i];
}
for (int i = k - 1; i >= 0; i--) {
ans = ans * C[sum - 1][a[i] - 1] % mod;
sum -= a[i];
}
cout << ans;
return 0;
}

 

C. Match Points

 

二分+贪心

看似直接配对就好了,但实际上如果把一个数与第一个符合条件的数就配对,会导致结果变小,类似于以下数据。

1
2
3
4
/*
4 3
1 4 5 7
*/

1和4配对导致之后数都无法配对。

所以把数据排序后二分,前一半的数只能和后一半的数配对,就不会出现数都配对的挤在前面的情况了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
int n, z;
int a[maxn];
int ans;
int main() {
cin.sync_with_stdio(false);
cin >> n >> z;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
int l, r;
l = 0; r = n / 2 ;
for (; l < n / 2; l++) {
while (r < n&&a[r] - a[l] < z) {
r++;
}
if (r == n) {
cout << ans;
return 0;
}
r++;
ans++;
}
cout << ans;
return 0;
}

 

E. Proper Nutrition

 

暴力/拓展欧几里得

神奇的题目,按常理来说应该用拓展欧几里得,但是直接暴力搜就过了,而且时间和用欧几里得是一样的。。可能是我优化地不够,但是爆搜时间真的很快。

先上扩展欧几里得版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
#define ll long long
const int maxn = 1e7 + 5;
int n, a, b;
int exgcd(int a, int b, ll& x, ll& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int t = exgcd(b, a%b, x, y);
ll tmp = x;
x = y;
y = tmp - (a / b)*y;
return t;
}
int main() {
cin.sync_with_stdio(false);
cin >> n >> a >> b;
ll x, y;
int m = exgcd(a, b, x, y);
if (n%m != 0) {
cout << "NO";
}
else {
x *= (n / m);
y *= (n / m);
while (x < 0) {
x += b;
y -= a;
}
while (y<0)
{
x -= b;
y += a;
}
if (x < 0 || y < 0)cout << "NO";
else {
cout << "YES" << endl;
cout << x << ' ' << y;
}
}
return 0;
}

然后是爆搜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<algorithm>
#include<cstring>
#include <functional>
#include<string>
#include<vector>
using namespace std;
#define ll long long
const int maxn = 1e7 + 5;
int n;
int a, b;
int x, y;
int main() {
cin >> n;
cin >> a >> b;
for (int i = 0; i*a <= n; i++) {
if ((n - i*a) % b == 0) {
cout << "YES" << endl;
cout << i << ' ' << (n - i*a) / b;
return 0;
}
}
cout << "NO" << endl;
return 0;
}

 

F. The Door Problem

 

2-sat模板题

并查集

当初刚学并查集的时候做到过类似题目,但是当时并不知道这是一类问题,也就没记,现在又做到了,以后不能再忘了!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
int n, m;
int a[maxn];
vector<int>g[maxn];
int par[maxn], rk[maxn];
void init(int n) {
for (int i = 0; i < n; i++) {
par[i] = i;
rk[i] = 0;
}
}
int find(int x) {
if (par[x] == x) {
return x;
}
else {
return par[x] = find(par[x]);
}
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y)return;
if (rk[x] < rk[y]) {
par[x] = y;
}
else {
par[y] = x;
if (rk[x] == rk[y])rk[x]++;
}
}
bool same(int x, int y) {
return find(x) == find(y);
}
int main() {
cin.sync_with_stdio(false);
cin >> n >> m;
init(2 * m);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 0; i < m; i++) {
int t;
cin >> t;
for (int j = 0; j < t; j++) {
int u;
cin >> u;
g[u].push_back(i);
}
}
//cout << g[1][0];
for (int i = 1; i <= n; i++) {
int x = g[i][0], y = g[i][1];
if (a[i]) {
unite(x, y);
unite(x + m, y + m);
}
else {
unite(x + m, y);
unite(x, y + m);
}
}
for (int i = 0; i < m; i++) {
if (same(i, i + m)) {
cout << "NO" << endl;
return 0;
}
}
cout << "YES" << endl;
return 0;
}

 

G. The Brand New Function

 

枚举+剪枝

直接暴力枚举各个区间,set维护答案。

对每一个区间起始点,开始枚举区间结束点前设置一个check变量ck=0,若以后在枚举到某一个区间结束点时,ck与要压入set的答案相等,说明当前点再继续枚举下去的话,和a[i]=0的效果是一样的,那么这时就可以把区间起始点往右移动了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<set>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
int n;
int a[maxn];
set<int>ans;
int main() {
cin.sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
int tp = a[i];
int ck = 0;
ans.insert(a[i]);
for (int j = i + 1; j < n; j++) {
tp |= a[j];
ck |= a[j];
ans.insert(tp);
if (tp == ck) {
break;
}
}
}
cout << ans.size();
return 0;
}

 

H. Barcode

 

dp

因为前一天刚好在CCPC女生赛中做到String,也是道dp题,感觉差不多,所以自然想到了dp,但是不知道应该dp什么,最后还是看了眼题解。

dp[i] [j] [k]表示处理完第i列,当前列有j列连续,当前列颜色为0或1.

知道dp意义后,之后的都是自己想出来的了,虽然dp意义更重要,但也算是迈了第一步。0.o

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<set>
using namespace std;
#define ll long long
int n, m, x, y;
char mz[1005][1005];
int dp[1005][1005][2];
int num[1005];
int main() {
cin.sync_with_stdio(false);
cin >> n >> m >> x >> y;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> mz[i][j];
if (mz[i][j] == '#')num[j]++;
}
}
memset(dp, 0x3f, sizeof(dp));
dp[0][1][0] = num[0];
dp[0][1][1] = n - num[0];
for (int i = 1; i < m; i++) {
for (int j = x; j <= y; j++) {
dp[i][1][0] = min(dp[i][1][0], dp[i - 1][j][1] + num[i]);
dp[i][1][1] = min(dp[i][1][1], dp[i - 1][j][0] + n - num[i]);
}
for (int j = 2; j <= min(y, i + 1); j++) {
dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j - 1][0] + num[i]);
dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][1] + n - num[i]);
}
}
int ans = 0x3f3f3f3f;
for (int i = x; i <= y; i++) {
ans = min(ans, dp[m - 1][i][0]);
ans = min(ans, dp[m - 1][i][1]);
}
cout << ans;
return 0;
}

 

I. Producing Snow

 

优先队列

把当天和之前的V都存在优先队列里,这样方便删除已经V已经变成0的雪堆,而且借助size()不用一个个遍历加。

注意精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
int N;
int V[maxn], T[maxn];
priority_queue<ll, vector<ll>, greater<ll> >q;
int main() {
cin.sync_with_stdio(false);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> V[i];
}
ll pre = 0;
for (int i = 1; i <= N; i++) {
ll ans = 0;
int T;
cin >> T;
q.push(pre + V[i]);
while (!q.empty()) {
ll tp = q.top();
if (tp <= pre + T) {
ans += tp - pre;
q.pop();
}
else {
break;
}
}
ans += q.size()*T;
pre += T;
cout << ans << ' ';
}
return 0;
}

 

K. Ice Skating

 

并查集

若两个点的x或者y相同,则把他们放一堆,最后答案=堆数-1.

注意每个点可能不止和一个点合并,所以要检查它之前的所有点,我第一次是找到一个就break了,结果会变大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<algorithm>
#include<cstring>
#include <functional>
#include<string>
#include<vector>
using namespace std;
#define ll long long
int n;
int par[105], rk[105];
int x[105], y[105];
void init(int n) {
for (int i = 0; i < n; i++) {
par[i] = i;
rk[i] = 0;
}
}
int find(int x) {
if (par[x] == x) {
return x;
}
else {
return par[x] = find(par[x]);
}
}
void unit(int x, int y) {
x = find(x);
y = find(y);
if (x == y)return;
if (rk[x] < rk[y]) {
par[x] = y;
}
else {
par[y] = x;
if (rk[x] == rk[y])rk[x]++;
}
}
bool same(int x, int y) {
return find(x) == find(y);
}
int main() {
cin >> n;
init(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
for (int j = 0; j < i; j++) {
if (x[i] == x[j] || y[i] == y[j]) {
unit(i, j);
}
}
}
int ans = -1;
for (int i = 0; i < n; i++) {
if (par[i] == i)ans++;
}
cout << ans << endl;
return 0;
}