链接：Codeforces Round #843 (Div. 2)
# A2. Gardener and the Capybaras (hard version)
比较简单，贪心找一段足够小或足够大的串当成 即可。
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
using namespace std;
const int N = 4e5 + 10;
int T, n;
char s[N], a[N], b[N], c[N];
inline void solve(){
scanf("%s", s + 1), n = strlen(s + 1);
if(s[1] == 'a'){
int pos = 0;
for(int i = 1; i <= n; ++i)
if(s[i] == 'b') {pos = i - 1; break;}
if(!pos){
printf("%c ", s[1]);
for(int i = 2; i < n; ++i) printf("%c", s[i]);
printf(" %c\n", s[n]);
}else{
if(pos == n - 1) pos--;
for(int i = 1; i <= pos; ++i) putchar(s[i]);
putchar(' ');
for(int i = pos + 1; i < n; ++i) putchar(s[i]);
printf(" %c\n", s[n]);
}
}else{
int pos = 0;
for(int i = 1; i <= n; ++i)
if(s[i] == 'a') {pos = i - 1; break;}
if(!pos){
printf("%c ", s[1]);
for(int i = 2; i < n; ++i) printf("%c", s[i]);
printf(" %c\n", s[n]);
}else{
if(pos == n - 1) pos = 1;
for(int i = 1; i <= pos; ++i) putchar(s[i]);
printf(" %c ", s[pos + 1]);
for(int i = pos + 2; i <= n; ++i) putchar(s[i]);
puts("");
}
}
}
signed main(){
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
scanf("%d", &T);
while(T--) solve();
return 0;
}
# B. Gardener and the Array
简单结论。
如果一个数字 包含的所有二进制位中有至少一位在所有数中只出现了一次，那么这个 就是必要的。
如果 个数中有至少一个数不是必要的，那么就是 'Yes'，否则是 'No'。
对于如何判断一个数是否是必要的，我们开个桶记录每个二进制数位出现了多少次。如果只出现了 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
using namespace std;
const int N = 2e5 + 10;
int T, n;
int vis[N], id[N];
vector <int> p[N];
inline bool cmp(int a, int b){
return p[a].size() > p[b].size();
}
inline void solve(){
cin >> n;
for(int i = 1; i <= n; ++i){
int k, x; cin >> k;
for(int j = 1; j <= k; ++j)
cin >> x, p[i].pb(x), vis[x]++;
}
int cnt = 0;
for(int i = 1; i <= n; ++i){
int flag = 0;
for(auto x : p[i]){
if(vis[x] == 1) flag = 1;
}
cnt += flag;
}
if(cnt < n) cout << "Yes" << '\n';
else cout << "No" << '\n';
for(int i = 1; i <= n; ++i){
for(auto x : p[i]) vis[x] = 0;
p[i].clear();
}
}
signed main(){
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
ios :: sync_with_stdio(false);
cin >> T;
while(T--) solve();
return 0;
}
# C. Interesting Sequence
简单题（感觉比 简单）.
按位考虑，稍微讨论一下可以得出从 变成 ，需要的各种限制，输出最小的即可。
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
using namespace std;
int T, n, x;
inline void solve(){
cin >> n >> x;
if(n == x) return cout << n << '\n', void();
int num = 0, flag = -1;
for(int i = 0; i <= 60; ++i){
int a = (n >> i) & 1ll, b = (x >> i) & 1ll;
if(!a && b) return cout << "-1" << '\n', void();
if(a && b && flag == -1) flag = i;
if(a && !b){
if(flag != -1 && i > flag) return cout << "-1" << '\n', void();
if(flag == -1) num = i;
}
}
int ok = 0;
for(int i = num; i <= flag; ++i)
if(!((n >> i) & 1)) {ok = 1; break;}
if(!ok && ~flag) return cout << "-1" << '\n', void();
int ans = ((n >> num) << num) + (1ll << num);
cout << ans << '\n';
}
signed main(){
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
ios :: sync_with_stdio(false);
cin >> T;
while(T--) solve();
return 0;
}
# D. Friendly Spiders
把 以内的质数全都筛出来。
然后对于每个 分解质因数，从 向他们的质数连边，然后 一遍即可。
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
using namespace std;
namespace IO{
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
template <typename T> inline void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 3e5 + 10;
int n, s, t;
int a[N];
int p[N], tot, vis[N << 1];
inline void euler(int n){
for(int i = 2; i <= n; ++i){
if(!vis[i]) p[++tot] = i;
for(int j = 1; j <= tot && i * p[j] <= n; ++j){
vis[i * p[j]] = 1;
if(i % p[j] == 0) break;
}
}
}
vector <int> G[N << 1];
int id[N], uid[N];
inline void divide(int x, int num){
for(int i = 2; i * i <= x; ++i){
if(x % i == 0){
G[num].pb(uid[i]), G[uid[i]].pb(num);
while(x % i == 0) x /= i;
}
}
if(x > 1) G[num].pb(uid[x]), G[uid[x]].pb(num);
}
inline int gcd(int a, int b){
return !b ? a : gcd(b, a % b);
}
int dep[N << 1], pre[N << 1];
int ans[N], cnt;
inline void bfs(int s){
memset(vis, 0, sizeof(vis));
queue <int> q;
q.push(s), dep[s] = 0;
while(!q.empty()){
int x = q.front(); q.pop();
for(auto y : G[x])
if(!vis[y]) dep[y] = dep[x] + 1, pre[y] = x, vis[y] = 1, q.push(y);
}
}
signed main(){
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
n = read(), euler(3e5);
for(int i = 1; i <= tot; ++i) id[i] = n + i, uid[p[i]] = n + i;
for(int i = 1; i <= n; ++i)
a[i] = read(), divide(a[i], i);
s = read(), t = read();
if(s == t){
printf("1\n%d\n", s);
return 0;
}
if(gcd(a[s], a[t]) > 1){
printf("%d\n%d %d\n", 2, s, t);
return 0;
}
bfs(s);
if(!dep[t]) return puts("-1"), 0;
write((dep[t] >> 1) + 1), puts("");
for(int i = t; i != s; i = pre[i]) if(i <= n) ans[++cnt] = i;
ans[++cnt] = s;
for(int i = cnt; i >= 1; --i) write(ans[i]), putchar(' ');
puts("");
return 0;
}
# E. The Human Equation
结论题（
设 是 的前缀和数组。
那么每次操作相当于在 中任选一些数，令它们 或 。
所以最后的答案就是 ，初值都为 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
using namespace std;
namespace IO{
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
template <typename T> inline void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 2e5 + 10;
int T, n;
int a[N];
inline void solve(){
n = read();
int mx = 0, mn = 0;
for(int i = 1; i <= n; ++i) a[i] = a[i - 1] + read(), mx = max(mx, a[i]), mn = min(mn, a[i]);
write(mx - mn), puts("");
}
signed main(){
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
T = read();
while(T--) solve();
return 0;
}
# F. Laboratory on Pluto
这里只讲 的做法。
首先一个比较显然的结论，空的格子只会在四个角上，并且每个角的空格都是阶梯状的。
所以我们先单独考虑一个角。
不难发现，删掉一个角后，每一行的格子数单调不降或单调不升的，这让我们想起了什么？
没错，就是整数划分。
相当于把 划分成 （行数） 个数的和。
然后我们现在有四个角要如何处理呢？
也很简单，暴力卷积卷 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
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
using namespace std;
namespace IO{
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
template <typename T> inline void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 1010;
int T, u, mod, n;
inline int add(int x) {return x >= mod ? x - mod : x;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}
inline void solve1(){
n = read();
int res = 1e9, a = 0;
for(int i = 1; i * i <= n; ++i){
int j = ceil(1.0 * n / i);
if(2 * (i + j) < res) res = 2 * (i + j), a = i;
}
int b = ceil(1.0 * n / a);
cout << a << " " << b << '\n';
for(int i = 1; i <= a - 1; ++i){
for(int j = 1; j <= b; ++j) putchar('#');
puts("");
}
for(int i = 1; i <= n - (a - 1) * b; ++i) putchar('#');
for(int i = n - (a - 1) * b + 1; i <= b; ++i) putchar('.');
puts("");
}
int dp[N][N], f[N], g[N], h[N];
inline int Len(int a) {return a + (n + a - 1) / a;}
inline void solve2(){
n = read();
int r = 1;
for(int i = max(1, (int)sqrt(n) - 100); i <= min(n, (int)sqrt(n) + 100); ++i)
if(Len(i) < Len(r)) r = i;
write(2 * Len(r)), putchar(' ');
int ans = 0;
for(int a = max(1, (int)sqrt(n) - 100); a <= min(n, (int)sqrt(n) + 100); ++a){
if(Len(r) != Len(a)) continue;
int b = (n + a - 1) / a;
if(a > b) break;
int k = a * b - n;
ans = add(ans + mul(h[k], 1 + (a != b)));
}
write(ans), puts("");
}
signed main(){
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
T = read(), u = read();
if(u == 2){
mod = read();
for(int i = 1; i <= 1000; ++i) dp[i][1] = 1;
for(int i = 2; i <= 1000; ++i)
for(int j = 2; j <= i; ++j)dp[i][j] = add(dp[i - 1][j - 1] + dp[i - j][j]);
f[0] = 1;
for(int i = 1; i <= 1000; ++i)
for(int j = 1; j <= i; ++j) f[i] = add(f[i] + dp[i][j]);
for(int i = 0; i <= 1000; ++i)
for(int j = 0; i + j <= 1000; ++j)
g[i + j] = add(g[i + j] + mul(f[i], f[j]));
for(int i = 0; i <= 1000; ++i)
for(int j = 0; i + j <= 1000; ++j)
h[i + j] = add(h[i + j] + mul(f[i], g[j]));
for(int i = 0; i <= 1000; ++i) g[i] = h[i], h[i] = 0;
for(int i = 0; i <= 1000; ++i)
for(int j = 0; i + j <= 1000; ++j)
h[i + j] = add(h[i + j] + mul(f[i], g[j]));
}
while(T--){
if(u == 1) solve1();
else solve2();
}
return 0;
}
