比赛链接 / 官方题解链接
这场出题人真惨～
A. Puzzle Pieces
Solution
若 $n=1$ 或 $m=1$ 或 $n=m=2$，那么可行；否则不可行，因为无法拼出 $2\times3$ 的格子。
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int T, n, m;
int main(){
for(read(T); T; T--){
read(n, m);
if(n == 1) puts("YES");
else if(m == 1) puts("YES");
else if(n == 2 && m == 2) puts("YES");
else puts("NO");
}
return 0;
}
|
B. Card Constructions
Solution
可以推导出通项公式：$a_n=\frac{3n^2+n}{2}$，那么不断二分最大金字塔数量。
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
LL a[100005];
int T, n;
int main(){
int id = 0;
for(int i = 1; i <= 100000; i++){
a[++id] = (3ll * i * i + i) / 2;
if(a[id] > 1e9) break;
}
for(read(T); T; T--){
read(n);
int ans = 0;
while(n){
int p = lower_bound(a+1, a+id, n) - a;
if(a[p] > n) p--;
if(p == 0) break;
n -= a[p];
ans++;
}
printf("%d\n", ans);
}
return 0;
}
|
C. Hilbert’s Hotel
Solution
如果 $0\sim n-1$ 在变换后恰好占据了模 $n$ 的不同余数的位置，那么可行；否则不可。
Code
>folded1
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;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 200005;
int T, n, a[N], s[N];
int main(){
for(read(T); T; T--){
read(n);
memset(s, 0, sizeof s);
for(int i = 0; i < n; i++){
read(a[i]);
int res = ((i + a[i]) % n + n) % n;
s[res]++;
}
bool b = true;
for(int i = 0; i < n; i++)
if(s[i] != 1){
b = false;
break;
}
if(b) puts("YES");
else puts("NO");
}
return 0;
}
|
D. Monopole Magnets
Solution
如果某一行或某一列有间隔的黑块，那么一定无解——因为这一行必须要放一个 $S$，而这个 $S$ 可以把走到黑块上的 $N$ 勾引到白块上去。
如果某一行是全白色，那么必须要有一列也是全白色，否则这一行放不了 $S$；某一列全白色同理。
上述两个条件满足后，只需要在所有黑块上放 $S$，那么在每个黑色连通块上放一个 $N$ 就可以了。所以答案就是黑色连通块的个数。
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 1005;
int n, m;
char g[N][N];
int l[N][N], u[N][N];
bool brow[N], bcol[N];
int fa[N*N];
int findfa(int x){ return fa[x] == x ? x : fa[x] = findfa(fa[x]); }
inline void unionn(int x, int y){
if(findfa(x) != findfa(y))
fa[findfa(y)] = findfa(x);
}
int main(){
read(n, m);
for(int i = 1; i <= n; i++)
scanf("%s", g[i] + 1);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(j == 1) l[i][j] = 0;
else l[i][j] = g[i][j-1] == '#' ? j-1 : l[i][j-1];
if(i == 1) u[i][j] = 0;
else u[i][j] = g[i-1][j] == '#' ? i-1 : u[i-1][j];
if(g[i][j] == '#'){
if(l[i][j] != 0 && l[i][j] != j-1) return puts("-1"), 0;
if(u[i][j] != 0 && u[i][j] != i-1) return puts("-1"), 0;
brow[i] = bcol[j] = true;
}
}
}
for(int i = 1; i <= n; i++){
if(brow[i] == false){
bool ok = false;
for(int j = 1; j <= m; j++)
if(bcol[j] == false)
ok = true;
if(!ok) return puts("-1"), 0;
}
}
for(int j = 1; j <= m; j++){
if(bcol[j] == false){
bool ok = false;
for(int i = 1; i <= n; i++)
if(brow[i] == false)
ok = true;
if(!ok) return puts("-1"), 0;
}
}
for(int i = 1; i <= n*m; i++) fa[i] = i;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
int p = (i - 1) * m + j;
if(g[i][j] == '.') continue;
if(i > 1 && g[i-1][j] == '#') unionn(p, p-m);
if(i < n && g[i+1][j] == '#') unionn(p, p+m);
if(j > 1 && g[i][j-1] == '#') unionn(p, p-1);
if(j < m && g[i][j+1] == '#') unionn(p, p+1);
}
}
int cnt = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cnt += g[i][j] == '#' && findfa((i-1)*m+j) == (i-1)*m+j;
printf("%d\n", cnt);
return 0;
}
|
E. Quantifier Question
Solution
如果对于条件 $a<b$，我们连一条从 $a$ 到 $b$ 的有向边，那么得到了一个有向图。如果该有向图有环，那么显然无解；否则该有向图是一个 $DAG$. 对于每一个点，我们可以通过拓扑序和逆拓扑序得到与它具有比较关系的最小编号，如果这个最小编号小于它本身，那么这个点必须填 $\exists$，否则填 $\forall$.
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 200005;
int n, m;
char ans[N];
vi edge[2][N];
int ind[2][N];
int mn[2][N], tot;
void topo(int k){
queue<int> q;
for(int i = 1; i <= n; i++)
if(!ind[k][i])
q.push(i);
while(!q.empty()){
int cur = q.front(); q.pop();
tot++;
for(auto to: edge[k][cur]){
ind[k][to]--;
mn[k][to] = min(mn[k][to], mn[k][cur]);
if(!ind[k][to]) q.push(to);
}
}
}
int main(){
read(n, m);
for(int i = 1; i <= m; i++){
int j, k; read(j, k);
edge[0][j].pb(k); ind[0][k]++;
edge[1][k].pb(j); ind[1][j]++;
}
for(int i = 1; i <= n; i++) mn[0][i] = mn[1][i] = i;
topo(0);
if(tot < n){ puts("-1"); return 0; }
topo(1);
int cnt = 0;
for(int i = 1; i <= n; i++){
if(mn[0][i] == i && mn[1][i] == i)
ans[i] = 'A', cnt++;
else ans[i] = 'E';
}
printf("%d\n", cnt);
for(int i = 1; i <= n; i++) putchar(ans[i]);
puts("");
return 0;
}
|
F. Résumé Review
Solution
【参考官方题解】如果我们将第 $i$ 个数从 $x-1$ 增加到 $x$，那么答案增量为：
这是一个关于 $x$ 的递减函数。如果正向考虑，我们需要每次找到最大的增量，使该数加一，但是这肯定超时。正向麻烦时考虑反向——我们二分一个增量下限 $A$，对 $1\sim n$ 的每一个数来说，只要增量大于等于 $A$，就往上加——这一点可以二分上述公式中的 $x$ 完成。统计我们加的数 $cnt$，如果 $cnt>=k$，那么增大下限 $A$，使 $cnt$ 减小；否则减小下限 $A$，使 $cnt$ 增大。如此二分可以最终找到最大增量下限 $A$ 使得 $cnt$ 刚好大于或等于 $k$. 如果 $cnt=k$，那便是极好的；如果 $cnt>k$，我们一定可以找到一些数，它们的最后一个增量恰好等于 $A$——否则的话这个 $A$ 还可以增大，就不是最大增量下限了。对于这些数，我们往回撤销掉它们的增量，直到 $cnt=k$.
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 100005;
int n;
LL k, a[N], b[N], cnt;
vi v;
bool check(LL A){
cnt = 0;
v.clear();
for(int i = 1; i <= n; i++){
if(a[i] - 1 < A){ b[i] = 0; continue; }
LL l = 1, r = a[i];
while(l < r){
LL mid = (l + r + 1) / 2;
if(a[i] - 3 * mid * mid + 3 * mid - 1 >= A)
l = mid;
else r = mid - 1;
}
b[i] = l;
cnt += l;
if(a[i] - 3 * l * l + 3 * l - 1 == A)
v.pb(i);
}
return cnt >= k;
}
int main(){
read(n, k);
for(int i = 1; i <= n; i++) read(a[i]);
LL L = -4e18, R = 1e9;
while(L < R){
LL mid = (L + R + 1) / 2;
if(check(mid)) L = mid;
else R = mid - 1;
}
check(L);
for(auto i: v)
if(cnt > k && b[i] > 0)
cnt--, b[i]--;
for(int i = 1; i <= n; i++)
printf("%lld ", b[i]);
return 0;
}
|