首页 题解

链接：Codeforces Round #843 (Div. 2)

# A2. Gardener and the Capybaras (hard version)

AA 比较简单，贪心找一段足够小或足够大的串当成 b\text{b} 即可。

#include <bits/stdc++.h>
#define pb push_back
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(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}
# B. Gardener and the Array
简单结论。
如果一个数字 cic_i 包含的所有二进制位中有至少一位在所有数中只出现了一次，那么这个 cic_i 就是必要的。
如果 nn 个数中有至少一个数不是必要的，那么就是 'Yes'，否则是 'No'。
对于如何判断一个数是否是必要的，我们开个桶记录每个二进制数位出现了多少次。如果只出现了 1 次，那么包含这个二进制数位的数就是必要的。
#include <bits/stdc++.h>
#define pb push_back
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(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> T;
    while(T--) solve();
    return 0;
}
# C. Interesting Sequence
简单题（感觉比 BB 简单）.
按位考虑，稍微讨论一下可以得出从 nn 变成 xx，需要的各种限制，输出最小的即可。
#include <bits/stdc++.h>
#define pb push_back
#define int long long
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(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> T;
    while(T--) solve();
    return 0;
}
# D. Friendly Spiders
把 3e53e5 以内的质数全都筛出来。
然后对于每个 aia_i 分解质因数，从 aia_i 向他们的质数连边，然后 bfs\text{bfs} 一遍即可。
#include <bits/stdc++.h>
#define pb push_back
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(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    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
结论题（
设 bb 是 aa 的前缀和数组。
那么每次操作相当于在 bb 中任选一些数，令它们 +1+1 或 −1-1。
所以最后的答案就是 mx−mnmx - mn，初值都为 0。
#include <bits/stdc++.h>
#define pb push_back
#define int long long
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(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    T = read();
    while(T--) solve();
    return 0;
}
# F. Laboratory on Pluto
这里只讲 u=2u = 2 的做法。
首先一个比较显然的结论，空的格子只会在四个角上，并且每个角的空格都是阶梯状的。
所以我们先单独考虑一个角。
不难发现，删掉一个角后，每一行的格子数单调不降或单调不升的，这让我们想起了什么？
没错，就是整数划分。
相当于把 nn 划分成 aa （行数） 个数的和。
然后我们现在有四个角要如何处理呢？
也很简单，暴力卷积卷 3 次即可。
最后就是统计答案了。
这一部分也很简单，枚举合法的长宽 a,ba, b，然后算一下被删掉的格子数，加到答案里即可。
#include <bits/stdc++.h>
#define pb push_back
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(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    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;
}