codeforces870+871

简介

第一次打机房号,各种罚时,划水划得厉害。最后rating涨了104,似乎不是太爆炸?

Problem A Search for Pretty Integers

题目大意

给出两个序列,序列中的数∈[1,9],要求找出一个最小的数使得这个数的数位上的数在两个序列中都出现过

解法

分类讨论,当两个序列中存在重复的数时答案为一位数,否则为两位数,具体处理非常简单

源码

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
#include <bits/stdc++.h>
using namespace std;
bool flag[11], bo = 0;
int ans = 10;
int main() {
int n, m, Mina = 10, Minb = 10;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
Mina = min(Mina, x);
flag[x] = 1;
}
for (int i = 1; i <= m; ++i) {
int x;
scanf("%d", &x);
if (flag[x]) {
bo = 1;
ans = min(x, ans);
}
Minb = min(Minb, x);
}
if (bo) cout << ans;
else cout << min(Mina, Minb) << max(Mina, Minb) << endl;
return 0;
}

Problem B Maximum of Maximums of Minimums

题目大意

给一组整数,把这个数组切成 k 段,要求这 k 段每段中所有数字的最小值的最大值最大,求出这个最大值。

解法

分三类讨论
k = 1的情况,直接输出最小值
k = 2的情况,可以发现,两段中必有一段含有数列的最小值,这一段的最小值是确定的。而这两段肯定分别包含一个端点,因此另一段的最小值不会小于端点值。可以发现,这个值一定能取到,只要让它长度为 11,其他的全部属于含有最小值的一段。因此,输出两个端点的最大值即可
k = 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
#include <bits/stdc++.h>
using namespace std;
int mi = 1e9, ma = -1e9, a[100010], b[100010], c[100010];
int main() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]), mi = min(a[i], mi), ma = max(ma, a[i]);
memset(b, 0x3f3f, sizeof b);
memset(c, 0x3f3f, sizeof c);
if (k == 1) {
printf("%d", mi);
return 0;
}
if (k >= 3) {
printf("%d", ma);
return 0;
}
int ans = -1e9;
for (int i = 1; i <= n; ++i) b[i] = min(b[i-1], a[i]);
for (int i = n; i >= 1; --i) c[i] = min(c[i+1], a[i]);
for (int i = 1; i < n; ++i) ans = max(ans, max(b[i], c[i+1]));
printf("%d", ans);
return 0;
}

Problem C Maximum splitting

题目大意

给出一个数,将这个数分成若干个合数的和,求最多能分成多少个合数

解法

因为最小的合数是4,将这个数按照在mod 4意义下分类讨论
0 : 直接分成若干个4,ans = n / 4;
1 : 提出一个9(模4余1意义下最小合数),剩下的分成若干个4,ans = (n - 9) / 4 + 1
2 : 提出一个6(模4余2意义下最小合数),剩下的分成若干个4,ans = (n - 6) / 4 + 1
3 : 提出一个15(模4余3意义下最小合数),剩下的分成若干个4,ans = (n - 15) / 4 + 2

源码

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
#include <bits/stdc++.h>
using namespace std;
int main() {
int q;
scanf("%d", &q);
for (int i = 1; i <= q; ++i) {
int n;
scanf("%d", &n);
if (n == 1 || n == 2 || n == 3 || n == 5 || n == 7 || n == 11) {
puts("-1");
continue;
}
int temp = n % 4;
switch (temp) {
case (0) : {
printf("%d\n", n / 4);
break;
}
case (1) : {
printf("%d\n", (n - 9) / 4 + 1);
break;
}
case (2) : {
printf("%d\n", (n - 2) / 4);
break;
}
case (3) : {
printf("%d\n", (n - 9) / 4 + 1);
break;
}
}
}
return 0;
}

Problem D Something with XOR Queries

题目大意

原有一个长度为n排列p和一个长度为n排列b,两个排列满足p[b[i]] = i,现在有2n次询问机会,每次询问传入i, j,返回p[i] ^ b[j]的值。由于即使已知所有数对的异或值,也可能有多种答案,输出方案数和其中一种方案

解法

因为p[i] ^ b[j] = (p[i] ^ b[0]) ^ (b[0] ^ p[0]) ^ (p[0] ^ b[j]),那么可以在2n次询问中得到所有数对的异或值。在此基础上枚举p[0],从而计算出p和b,判断是否满足排列和p[b[i]] = i的两个性质

源码

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
#include <bits/stdc++.h>
using namespace std;
int p[5010][5010], a[5010], b[5010], Ans[5010];
int ans = 0;
bool appear = 0, fff[5010];
int main() {
memset(Ans, 0, sizeof Ans);
int n;
scanf("%d", &n);
printf("? 0 0\n");
fflush(stdout);
scanf("%d", &p[0][0]);
for (int i = 1; i < n; ++i) {
printf("? %d 0\n", i);
fflush(stdout);
scanf("%d", &p[i][0]);
printf("? 0 %d\n", i);
fflush(stdout);
scanf("%d", &p[0][i]);
}
for (int i = 1; i < n; ++i)
for (int j = 1; j < n; ++j)
p[i][j] = ((p[i][0] ^ p[0][j]) ^ p[0][0]);
for (int i = 0; i < n; ++i) {
bool flag = 1;
a[0] = i;
for (int j = 0; j < n; ++j)
b[j] = (a[0] ^ p[0][j]);
for (int j = 1; j < n; ++j)
a[j] = (b[j] ^ p[j][j]);
memset(fff, 0, sizeof fff);
for (int j = 0; j < n; ++j)
if (b[j] >= n || fff[b[j]] || a[b[j]] != j) {
flag = 0;
break;
}
else fff[b[j]] = 1;
for (int j = 0; j < n; ++j)
if ((a[0] ^ b[j]) != p[0][j]) {
flag=0;
break;
}
for (int j = 0; j < n; ++j)
if ((a[j] ^ b[0]) != p[j][0]) {
flag=0;
break;
}
if (flag) {
ans ++;
if (!appear) {
for (int j = 0; j < n; ++j)
Ans[j] = a[j];
appear = 1;
}
}
}
printf("!\n");
printf("%d\n", ans);
for (int i = 0; i < n; ++i)
printf("%d ", Ans[i]);
return 0;
}

Problem E Points, Lines and Ready-made Titles

题目大意

平面上有一些点,你可以过每个点做一条平行于x轴的选或者平行于y轴的线的线(也可以不做)。求可能出现的不同图案个数。只要两条线重合,则认为它们是相同的,两个图案不同当且仅当它们中存在两条不同的直线,有和没有也算。

解法

考虑建图。离散化后,对每一个横坐标的值、纵坐标的值建成一个点,原来的一个点建成横坐标到纵坐标的一条边。对这个图计算出所有的连通块,不难发现,不同连通块之间没有任何干扰,因此可以分别考虑每个连通块,最后乘法原理解决
对每个连通块,枚举每个点选或不选,可以证明每一种方案都对应一个图案(就是用边数大于点数,证明选一个点时周围至少有一条没用过的边,否则与之前的连通性矛盾),但是如果这个块是一棵树,全选就不行。所以答案是2n或2n−1,n是连通图的点数。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const long long Yn = 1e9 + 7;
int x[2000010], y[2000010], f[2000010], t[2000010], fa[2000010], num[2000010];
long long p[2000010], s[2000010], ans = 1;
int tot = 0, cnt = 0;
map<int, int> mx, my, sx, sy;
int fly(int x) {return (fa[x] == x)?x:(fa[x]=fly(fa[x]));}
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d%d", &x[i], &y[i]), mx[x[i]] ++, my[y[i]] ++;
for (int i = 1; i <= n * 2; ++i) fa[i] = i;
for (map<int, int>::iterator it = mx.begin(); it != mx.end(); ++it) sx[it->first] = ++cnt;
for (map<int, int>::iterator it = my.begin(); it != my.end(); ++it) sy[it->first] = ++cnt;
for (int i = 1; i <= n; ++i) f[++tot] = sx[x[i]], t[tot] = sy[y[i]], fa[fly(f[tot])] = fly(t[tot]);
for (int i = 1; i <= tot; ++i) num[fly(f[i])] ++;
for (int i = 1; i <= cnt; ++i) s[fly(i)] ++;
for (int i = 0; i <= n * 2; ++i) p[i] = (i != 0)?p[i - 1] * 2 % Yn:1;
for (int i = 1; i <= cnt; ++i) if (fly(i) == i) if (s[i] - 1 == num[i]) (ans *= (p[s[i]] - 1)) %= Yn; else (ans *= p[s[i]]) %= Yn;
printf("%lld\n", (ans % Yn + Yn) % Yn);
return 0;
}

参考博客:GodCowC

文章目录
  1. 1. 简介
  • Problem A Search for Pretty Integers
    1. 1. 题目大意
    2. 2. 解法
    3. 3. 源码
  • Problem B Maximum of Maximums of Minimums
    1. 1. 题目大意
    2. 2. 解法
    3. 3. 源码
  • Problem C Maximum splitting
    1. 1. 题目大意
    2. 2. 解法
    3. 3. 源码
  • Problem D Something with XOR Queries
    1. 1. 题目大意
    2. 2. 解法
    3. 3. 源码
  • Problem E Points, Lines and Ready-made Titles
    1. 1. 题目大意
    2. 2. 解法
    3. 3. 源码
  • ,