0%

题目链接: https://vjudge.net/contest/418600

A 校门外的树

直接模拟染色的过程即可。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
for (c = getchar(); !isdigit(c); c = getchar());
for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 1e4 + 5;
int co[N];
int L, M;

int main() {
read(L);
read(M);
while (M--) {
int l, r;
read(l);
read(r);
for (int i = l; i <= r; i++) {
co[i]++;
}
}
int cnt = 0;
for (int i = 0; i <= L; i++) {
if (!co[i]) cnt++;
}
printf("%d\n", cnt);
return 0;
}

B 铺地毯

从后往前遍历地毯,找到的第一个即为答案。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
for (c = getchar(); !isdigit(c); c = getchar());
for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 1e7 + 5;

class carpet {
public:
int id, a, b, x, y;
carpet(int _id, int _a, int _b, int _x, int _y) {
id = _id;
a = _a;
b = _b;
x = _x;
y = _y;
}
};

vector<carpet> c;

int n;

int main() {
read(n);
for (int i = 1; i <= n; i++) {
int a, b, x, y;
read(a), read(b), read(x), read(y);
c.push_back(carpet(i, a, b, x, y));
}
int X, Y;
read(X), read(Y);
vector<carpet>::reverse_iterator it;
for (it = c.rbegin(); it != c.rend(); it++) {
carpet o = *it;
// printf("GET %d %d %d %d\n", o.a, o.b, o.x, o.y);
if (X >= o.a && X <= o.a + o.x && Y >= o.b && Y <= o.b + o.y) {
printf("%d\n", o.id);
return 0;
}
}
puts("-1");
return 0;
}

C 低买高卖

维护一个小根堆,每一个元素表示前 \(i-1\) 天中可以和当前第 \(i\) 天进行一次购买售出操作的股票。设 \(a[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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
for (c = getchar(); !isdigit(c); c = getchar());
for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 200000 + 5;
int a[N], n;

priority_queue<int, vector<int>, greater<int>> p;

int main() {
read(n);
for (int i = 1; i <= n; i++) read(a[i]);
p.push(a[1]);
int ans = 0;
for (int i = 2; i <= n; i++) {
int x = a[i];
if (x < p.top()) {
p.push(x);
} else {
ans += x - p.top();
p.pop();
p.push(x);
p.push(x);
}
}
printf("%d\n", ans);
return 0;
}

D IP地址转换

使用位运算模拟即可。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
for (c = getchar(); !isdigit(c); c = getchar());
for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

int main() {
char c = 0;
int a = 0;
while (c != '-') {
c = getchar();
if (c == '.') {
// printf("PRINT a = %d\n", a);
for (int i = 7; i >= 0; i--) {
int b = (a >> i) & 1;
printf("%d", b);
}
a = 0;
continue;
}
if (c == '\n') {
for (int i = 7; i >= 0; i--) {
int b = (a >> i) & 1;
printf("%d", b);
}
a = 0;
printf("\n");
continue;
}
a = a * 10 + c - '0';
}
return 0;
}

E 明明的随机数

sort()与unique()函数。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
for (c = getchar(); !isdigit(c); c = getchar());
for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 100 + 5;

int n, a[N];

int main() {
read(n);
for (int i = 1; i <= n; i++) {
read(a[i]);
}
sort(a + 1, a + n + 1);
int m = unique(a + 1, a + n + 1) - (a + 1);
printf("%d\n", m);
for (int i = 1; i <= m; i++) {
printf("%d ", a[i]);
}
puts("");
return 0;
}

F 拼数

观察了一下样例,发现这不就是字典序嘛,果断WA了。后来发现 \(432\) 字典序比 \(43\) 大,但是实际上却应该是 \(43432\) ,把字典序比较换成了 \(a+b\lt b+a\) 即可。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
for (c = getchar(); !isdigit(c); c = getchar());
for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

string s[2500];
int n;

bool cmp(string a, string b) {
return a + b > b + a;
}

int main() {
read(n);
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
sort(s + 1, s + n + 1, cmp);
for (int i = 1; i < n; i++) {
string a = s[i];
string b = s[i + 1];
}
for (int i = 1; i <= n; i++) {
cout << s[i];
}
puts("");
return 0;
}

G 今年暑假不AC

把线段按左端点排序,然后从右往左遍历排好的线段,贪心取不重叠的线段即可。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
for (c = getchar(); !isdigit(c); c = getchar());
for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

class segment {
public:
int l, r;
segment(int _l = 0, int _r = 0) {
l = _l, r = _r;
}
bool operator < (const segment o) const {
return l < o.l;
}
};

int n;
segment a[105];

void init() {
memset(a, 0, sizeof a);
}

int main() {
while (scanf("%d", &n)) {
if (n == 0) break;
init();
for (int i = 1; i <= n; i++) {
int l, r;
read(l), read(r);
a[i] = segment(l, r);
}
sort(a + 1, a + n + 1);
#ifdef DEBUG
for (int i = 1; i <= n; i++) {
printf("[%d, %d]\n", a[i].l, a[i].r);
}
#endif
int ans = 1;
segment x = a[n];
for (int i = n - 1; i >= 1; i--) {
if (a[i].r <= x.l) {
ans++;
x = a[i];
}
}
printf("%d\n", ans);
}
return 0;
}

H 排座椅

取桌子之间的间隙建立新网格,对行和列贪心取“串”起来最多的即可。(OOP大法好!)

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
81
82
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void r(_Tp &a, char c = 0) {
for (c = getchar(); !isdigit(c); c = getchar());
for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int _N_ = 1000 + 5;
const int _D_ = 2000 + 5;

int a[_N_], b[_N_];
int M, N, K, L, D;

class data {
public:
int id, cnt;
data() {
id = cnt = -1;
}
data(int _id, int _cnt) {
id = _id, cnt = _cnt;
}
bool operator < (const data o) const {
return cnt > o.cnt;
}
};

data A[_N_], B[_N_];

int main() {
r(M), r(N), r(K), r(L), r(D);
for (int i = 1; i <= D; i++) {
int x1, y1, x2, y2;
r(x1), r(y1), r(x2), r(y2);
if (y1 == y2) {
int x = min(x1, x2);
a[x]++;
}
if (x1 == x2) {
int y = min(y1, y2);
b[y]++;
}
}
int tot_A = 0, tot_B = 0;
for (int i = 1; i < M; i++) {
if (a[i]) {
A[++tot_A] = data(i, a[i]);
}
}
for (int i = 1; i < N; i++) {
if (b[i]) {
B[++tot_B] = data(i, b[i]);
}
}
sort(A + 1, A + tot_A + 1);
sort(B + 1, B + tot_B + 1);
vector<int> v, _v;
vector<int>::iterator it;
for (int i = 1; i <= K; i++) {
v.push_back(A[i].id);
}
sort(v.begin(), v.end());
for (it = v.begin(); it != v.end(); it++) {
int x = *it;
printf("%d ", x);
}
puts("");
for (int i = 1; i <= L; i++) {
_v.push_back(B[i].id);
}
sort(_v.begin(), _v.end());
for (it = _v.begin(); it != _v.end(); it++) {
int x = *it;
printf("%d ", x);
}
puts("");
return 0;
}

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void r(_Tp &a, char c = 0) {
for (c = getchar(); !isdigit(c); c = getchar());
for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

class date {
public:
int y, m, d;
date(string s) {
int _y = atoi(s.substr(0, 4).c_str());
int _m = atoi(s.substr(4, 2).c_str());
int _d = atoi(s.substr(6, 2).c_str());
y = _y, m = _m, d = _d;
}
bool operator == (const date A) const {
return A.y == y && A.m == m && A.d == d;
}
void print() {
printf("YEAR=%d MONTH=%d DAY=%d\n", y, m, d);
}
string sprint() {
char s[10];
sprintf(s, "%d%02d%02d\n", y, m, d);
string str = s;
return str;
}
void update() {
if (m == 1 ||
m == 3 ||
m == 5 ||
m == 7 ||
m == 8 ||
m == 10
) {
if (d == 31) {
d = 1;
m++;
} else {
d++;
}
} else if (m == 12) {
if (d == 31) {
d = 1;
m = 1;
y++;
} else {
d++;
}
} else if (m == 2) {
if ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0)) {
if (d == 29) {
d = 1;
m++;
} else {
d++;
}
} else {
if (d == 28) {
d = 1;
m++;
} else {
d++;
}
}
} else {
if (d == 30) {
d = 1;
m++;
} else {
d++;
}
}
}
};

string A, B;

bool good(string str) {
// printf("\t---COMPARING");
int len = 8;
for (int i = 0; i < len / 2 + 1; i++) {
int j = len - i - 1;
// printf(" j = %d %c <-> %c \n", j, str[i], str[j]);
if (str[i] != str[j]) return false;
}
return true;
}

int main() {
cin >> A >> B;
date a(A), b(B);
b.update();
int cnt = 0;
for (date t = a; !(t == b); t.update()) {
// printf("NOW AT DATE -> ");
// cout << t.sprint();
if (good(t.sprint())) cnt++;
}
printf("%d\n", cnt);
return 0;
}

J Claris and XOR

(这题真是要了老命)

贪心从高到低构造 \(1\) ,考虑当前是第 \(i\) 位,若 \(x\)\(y\) 在这一位的取法均为任意,则后面所有位一定都可以任意取,这时直接把答案的后面全取为 \(1\) 。如果两个数在这一位的取法受限,则贪心构造出答案 \(1\) 。如果贪心也不行则只能填上 \(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
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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
for (c = getchar(); !isdigit(c); c = getchar());
for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

ll a, b, c, d;
int T;

void print(ll x) {
for (int i = 63; i >= 0; i--) {
int p = x >> i & 1;
printf("%d", p);
}
}

int main() {
read(T);
while (T--) {
read(a), read(b), read(c), read(d);
ll ans = 0;
ll ta, tb, tc, td;
ta = a;
tb = b;
tc = c;
td = d;
for (int i = 62; i >= 0; i--) {
ll t = 1LL << (i + 1);
ll _t = 1LL << i;
// printf("i = %d \t_t =\n", i); print(_t); puts(""), puts("---");
int x0, x1, y0, y1;
x0 = x1 = y0 = y1 = 0;
if (ta <= _t - 1) x0 = 1;
if (tb >= _t) x1 = 1;
if (tc <= _t - 1) y0 = 1;
if (td >= _t) y1 = 1;
// printf("x0=%d x1=%d y0=%d y1=%d\n", x0, x1, y0, y1);
if (x0 && x1 && y0 && y1) {
ans += t - 1;
break;
}
if (x0 && y1) {
ans += _t;
tc -= _t;
td -= _t;
continue;
}
if (x1 && y0) {
ans += _t;
ta -= _t;
tb -= _t;
continue;
}
if ((!x0) && (!y0)) {
ta -= _t;
tb -= _t;
tc -= _t;
td -= _t;
}
// print(td), puts("");
// print(tc), puts("");
// print(tb), puts("");
// print(ta), puts("");
// puts("------------");
}
printf("%lld\n", ans);
}
return 0;
}

K Flip Game

注意到,翻片儿的顺序不会产生影响,则同一个地方最多翻一次即可,直接进行DFS记忆化搜索。

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void r(_Tp &a, char c = 0) {
for (c = getchar(); !isdigit(c); c = getchar());
for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

int a[5][5];
int G1, G2, st[100000];

void print(int x[][5]) {
puts("------\nPRINT\n------");
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
printf("%d", x[i][j]);
}
puts("");
}
puts("------\nEND PRINT\n------");
}

int trans(int x[][5]) {
int ret = 0;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
ret = (ret << 1) | x[i][j];
}
}
return ret;
}

int g1[5][5], g2[5][5];
bool vis[5][5];

void dfs(int x[][5], int cnt) {
int sta = trans(x);
if (st[sta] <= cnt) {
return;
}
st[sta] = cnt;
// printf("CURRENTLY AT -> cnt = %d\n", cnt);
// print(x);
if (sta == G1 || sta == G2) {
return;
}
int t[5][5];
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
t[i][j] = x[i][j];
}
}
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if (!vis[i][j]) {
t[i][j] ^= 1;
if (i - 1 >= 1) t[i - 1][j] ^= 1;
if (i + 1 <= 4) t[i + 1][j] ^= 1;
if (j - 1 >= 1) t[i][j - 1] ^= 1;
if (j + 1 <= 4) t[i][j + 1] ^= 1;

vis[i][j] = true;
dfs(t, cnt + 1);
vis[i][j] = false;

t[i][j] ^= 1;
if (i - 1 >= 1) t[i - 1][j] ^= 1;
if (i + 1 <= 4) t[i + 1][j] ^= 1;
if (j - 1 >= 1) t[i][j - 1] ^= 1;
if (j + 1 <= 4) t[i][j + 1] ^= 1;
}
}
}
}

int main() {
memset(st, 0x7f7f7f7f, sizeof st);
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
g1[i][j] = 0;
g2[i][j] = 1;
}
}
G1 = trans(g1);
G2 = trans(g2);
for (int i = 1; i <= 4; i++) {
string str;
cin >> str;
for (int j = 0; j < 4; j++) {
if (str[j] == 'b') {
a[i][j + 1] = 1;
} else {
a[i][j + 1] = 0;
}
}
}
// print(a);
// printf("G1 = %d, G2 = %d\n", G1, G2);
dfs(a, 0);
int ans = min(st[G1], st[G2]);
if (ans >= 0x7f7f7f7f) puts("Impossible");
else printf("%d\n", ans);
return 0;
}

M Unique Snowflakes

滑动窗口型问题,我好像写了一个st表加二分的方法……(离谱)。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
for (c = getchar(); !isdigit(c); c = getchar());
for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 1e6 + 5;
const int logN = 30;
int a[N], lst[N], f[N][logN];
int T, n;

map<int, int> c;

void init() {
c.clear();
memset(a, 0, sizeof a);
memset(lst, 0, sizeof a);
memset(f, 0, sizeof f);
}

int ask(int L, int R) {
int k = log2(R - L + 1);
return max(f[L][k], f[R - (1 << k) + 1][k]);
}

int main() {
read(T);
while (T--) {
init();
read(n);
for (int i = 1; i <= n; i++) {
read(a[i]);
if (!c[a[i]]) {
c[a[i]] = i;
} else {
lst[i] = c[a[i]];
c[a[i]] = i;
}
f[i][0] = lst[i];
}
for (int j = 1; j <= 21; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
int ans = -1;
for (int i = 1; i <= n; i++) {
int L = i, R = n, mid;
while (L <= R) {
mid = (L + R) / 2;
int mx = ask(i, mid);
if (mx < i) L = mid + 1;
else R = mid - 1;
}
int tmp = L - i;
ans = max(ans, tmp);
}
printf("%d\n", ans);
}
return 0;
}

N Hero

一开始写了一个奇怪的贪心给WA了,实际上直接利用 \(\displaystyle\frac{\text{HP}_i}{\text{DPS}_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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
for (c = getchar(); !isdigit(c); c = getchar());
for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

#define INF 0x3f3f3f3f

class hero {
public:
int HP, DPS;
hero(int _HP = -1, int _DPS = -1) {
HP = _HP, DPS = _DPS;
}
bool operator < (const hero o) const {
return HP * o.DPS < DPS * o.HP;
}
};

hero a[25];
int n;
int sum_HP, sum_DPS;
bool vis[25];

void init() {
sum_DPS = sum_HP = 0;
memset(a, -1, sizeof a);
memset(vis, 0, sizeof vis);
}

int main() {
while (~scanf("%d", &n)) {
init();
int dps, hp;
for (int i = 1; i <= n; i++) {
read(dps), read(hp);
a[i] = hero(hp, dps);
sum_HP += hp;
sum_DPS += dps;
}
int ans = 0;

#if 1
sort(a + 1, a + n + 1);
int ts = 0;
for (int i = 1; i <= n; i++) {
ans += a[i].HP * (sum_DPS - ts);
ts += a[i].DPS;
}
printf("%d\n", ans);

#endif

#if 0

for (int j = 1; j <= n; j++) {
int good = -1, td = -INF;
int tmp_s = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
tmp_s += a[i].DPS;
}
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
int st = a[i].HP * (tmp_s - a[i].DPS);
if (st > td) {
td = st;
good = i;
}
}
}
// printf("j = %d good = %d td = %d\n", j, good, td);
vis[good] = true;
ans += td;
}
int oth = sum_HP * sum_DPS;
ans = oth - ans;
printf("%d\n", ans);

#endif

}
return 0;
}