A. Square Year
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 t;
string s;
void f(int num) {
for (int i = 0; i <= 100; ++i) {
for (int j = 0; j <= 100; ++j) {
if ((i + j) * (i + j) == num) {
cout << i << ' ' << j << '\n';
return;
}
}
}
cout << -1 << '\n';
}
int32_t main() {
cin >> t;
while (t--) {
cin >> s;
int num = stoi(s);
f(num);
}
}
|
B. Not Quite a Palindromic String
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
| #include <bits/stdc++.h>
using namespace std;
int t, n, k;
string s;
int get_pair(const string& str) {
int i = 0, j = str.length() - 1, cnt = 0;
while (i < j) {
if (str[i] == str[j]) cnt++;
i++;
j--;
}
return cnt;
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> t;
while (t--) {
cin >> n >> k >> s;
int c0 = count(s.begin(), s.end(), '0');
int c1 = n - c0;
int max_pair = (c0 / 2) + (c1 / 2);
int min_pair = abs(c0 - c1) / 2;
if (k < min_pair || k > max_pair) {
cout << "No\n";
continue;
}
int pairs = get_pair(s);
if ((abs(pairs - k) % 2) == 0)
cout << "Yes\n";
else
cout << "No\n";
}
}
|
C. Need More Arrays
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
| #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cout << 0 << "\n";
continue;
}
long long answer = 0;
int currentBlockLen = 0;
int lastDistinct = a[0] - 2;
for (int i = 0; i < n; ++i) {
if (i > 0 && a[i] == a[i-1]) {
continue;
}
int v = a[i];
if (v - lastDistinct == 1) {
currentBlockLen++;
} else {
if (currentBlockLen > 0) {
answer += (currentBlockLen + 1) / 2;
}
currentBlockLen = 1;
}
lastDistinct = v;
}
if (currentBlockLen > 0) {
answer += (currentBlockLen + 1) / 2;
}
cout << answer << "\n";
}
return 0;
}
|
D. Come a Little Closer
你最多可以将一个怪物移动到场上未被其他怪物占据的任意一个格子一次。
之后，你必须选择场上的一个矩形；选中矩形内的所有怪物将被摧毁。你必须为选中矩形内的每个格子支付 1 个金币。
你的任务是找到摧毁所有怪物所需的最少金币数。
只需要每次记录 怪物群构建的矩形 的四个角坐标即可？
存在某个点，与角点交换后使矩形面积变小。目的是找到这个点。
时间不够了，寄了。
抄
代码要点说明
预处理 x_min, x_min2, cntMinX, x_max, x_max2, cntMaxX
x_min 与 cntMinX：记录当前最小的 $x$ 值及其出现次数。
x_min2 ：记录次小的 $x$ 值（当且仅当该最小值只出现 1 次且正好删掉时，新的最小才会降到次小）。
同理维护 x_max, cntMaxX, x_max2，以及对 $y$ 方向的同样四个变量。
删除第 $i$ 只怪物后四条边的更新
如果当前点的 $x_i \neq x_{\min}$，那么剩余的 $n-1$ 点的最小 $x$ 依然是 $x_{\min}$；否则要看 cntMinX。
如果 cntMinX>=2，说明即使删掉一个最小值，剩余还有其他等于 $x_{\min}$ 的点，边界不变；
如果 cntMinX==1，删除它之后只能退到第二小 x_min2 作为新边界。
右边界、$y$ 方向上下边界同理。这样常数步就算出了剩余 $n-1$ 只怪物的“最小包围矩形”边界 $(x_L,x_R,y_L,y_R)$。
判断包围矩形内部是否已被占满
记剩余 $(n-1)$ 只怪物的包围矩形宽 $w=x_R-x_L+1$，高 $h=y_R-y_L+1$，则该矩形格子总数 $w\times h$。
若 $(n-1) < w,h$，说明矩形内至少有一个空格，可以把被删除的怪物放在空格里，“不扩充”仍只需付 $(w\times h)$ 个金币。
若 $(n-1) = w,h$，说明所有格子正好被其他怪物占完，放不下，多一只就必须把矩形在宽或高方向至少向外扩 1 格，得到的最少花费是 $\min((w+1)\times h,;w\times(h+1))$。
答案
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
| #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<long long> X(n), Y(n);
for (int i = 0; i < n; i++) {
cin >> X[i] >> Y[i];
}
if (n == 1) {
cout << 1 << "\n";
continue;
}
const long long INF = (long long)4e18;
long long x_min = INF, x_min2 = INF;
long long x_max = -INF, x_max2 = -INF;
int cntMinX = 0, cntMaxX = 0;
long long y_min = INF, y_min2 = INF;
long long y_max = -INF, y_max2 = -INF;
int cntMinY = 0, cntMaxY = 0;
long long x = X[i], y = Y[i];
x_min2 = x_min;
x_min = x;
cntMinX = 1;
}
else if (x == x_min) {
cntMinX++;
}
else if (x < x_min2) {
x_min2 = x;
}
x_max2 = x_max;
x_max = x;
cntMaxX = 1;
}
else if (x == x_max) {
cntMaxX++;
}
else if (x > x_max2) {
x_max2 = x;
}
y_min2 = y_min;
y_min = y;
cntMinY = 1;
}
else if (y == y_min) {
cntMinY++;
}
else if (y < y_min2) {
y_min2 = y;
}
y_max2 = y_max;
y_max = y;
cntMaxY = 1;
}
else if (y == y_max) {
cntMaxY++;
}
else if (y > y_max2) {
y_max2 = y;
}
}
long long answer = LLONG_MAX;
for (int i = 0; i < n; i++) {
long long x = X[i], y = Y[i];
if (x != x_min) {
new_xL = x_min;
}
else {
if (cntMinX >= 2) new_xL = x_min;
else new_xL = x_min2;
}
if (x != x_max) {
new_xR = x_max;
}
else {
if (cntMaxX >= 2) new_xR = x_max;
else new_xR = x_max2;
}
if (y != y_min) {
new_yL = y_min;
}
else {
if (cntMinY >= 2) new_yL = y_min;
else new_yL = y_min2;
}
if (y != y_max) {
new_yR = y_max;
}
else {
if (cntMaxY >= 2) new_yR = y_max;
else new_yR = y_max2;
}
long long w = new_xR - new_xL + 1;
long long h = new_yR - new_yL + 1;
long long area_base = w * h;
if ((long long)(n - 1) < area_base) {
cost_i = area_base;
} else {
cost_i = min( (w + 1) * h, w * (h + 1) );
}
answer = min(answer, cost_i);
}
cout << answer << "\n";
}
return 0;
}
|
