Codeforces Round 747 div.2 A-E

A. Consecutive Sum Riddle

题意：给定一个 \(n\)，要找出 \(l,r\) 使得 \(\sum_{i=l}^{r}i=n\)

解：显然，从 \(-n+1\) 加到 \(n\) 即可

void solve(){
    ll n;
    cin >> n;
    cout << -n+1 << ' ' << n << '\n';
}

B. Special Numbers

题意：找第 \(k\) 个 \(n\) 好数，\(n\) 好数就是可以被 \(n\) 的不同次幂组成，比如 \(n^0+n^2...\) 的方式表示

解：把 \(k\) 转化为二进制，然后每一位按照 \(n\) 的次幂加权计算即可

void solve(){
    ll n, k;
    cin >> n >> k;
    ll ans = 0, t = 1;
    while(k > 0){
        if(k & 1){
            ans = (ans + t) % mode;
        }
        k >>= 1;
        t = t * n % mode;
    }
    cout << ans << '\n';
}

C. Make Them Equal

题意：给出一个字符串 \(s\) 和字符 \(c\)，可以进行若干次操作，每次操作可以选择一个数 \(x\)，然后令字符串中所有下标不能被 \(x\) 的整除的位置上的字符变成 \(c\)，问最少多少次操作可以使字符串全变成 \(c\)

解：由于 \(n>2\)，两次操作分别选择 \(n\) 和 \(n-1\) 一定可以完成，那么只需要考虑能不能一次完成

一次完成要求存在一个数 \(x\)，串中所有可以被 \(x\) 整除的位置上都已经是 \(c\) 了，暴力枚举即可，复杂度比较玄学但它就是 \(nlogn\)

后来又听了无敌的会长的优化方案：只需要枚举 \(n/2\) 以上的 \(x\) 即可，因为更小的 \(x\) 总有一个倍数比它更优，复杂度 \(2n\)

void solve(){
    int n;
    char c;
    string s;
    cin >> n >> c >> s;
    s = "0" + s;
    for(int i=1;i<=n;i++){
        bool flg = true;
        for(int j=i;j<=n;j+=i){
            if(s[j] != c){
                flg = false;
                break;
            }
        }
        if(flg){
            if(i == 1){
                cout << "0\n";
                return;
            }
            cout << 1 << '\n';
            cout << i << '\n';
            return;
        }
    }
    cout << 2 << '\n';
    cout << n-1 << ' ' << n << '\n';
}

D. The Number of Imposters

题意：有 \(n\) 个人和 \(m\) 个陈述，每个陈述形如：\(i,j,imposter/crewmate\) 表示 \(i\) 说 \(j\) 是说真话的人/说谎者，问说谎话的人最多有几个

解：注意到一个性质：如果 \(i\) 说 \(j\) 说的是谎话，那么 \(i\) 和 \(j\) 必定相反；如果 \(i\) 说 \(j\) 说的是真话，那么 \(i\) 和 \(j\) 相同。

那么每个陈述都可以转化为一条边，对每个联通块进行染色后取较多的颜色加入贡献即可

int st[maxn];
struct Edge{
    int t, nt, tp;
}e[maxn << 1];
int head[maxn], ecnt = 0;

inline void add(int x, int y, int tp){
    e[++ecnt].t = y;
    e[ecnt].tp = tp;
    e[ecnt].nt = head[x];
    head[x] = ecnt;
}

int num[2];
bool dfs(int p){
    for(int i=head[p];i;i=e[i].nt){
        int v = e[i].t;
        if(st[v] == -1){
            st[v] = st[p] ^ e[i].tp;
            num[st[v]]++;
            if(!dfs(v)) return false;
        }else{
            if(st[v] != (st[p] ^ e[i].tp)) return false;
        }
    }
    return true;
}

void solve(){
    int n, m;
    cin >> n >> m;

    ecnt = 0;
    for(int i=1;i<=n;i++){
        head[i] = 0;
        st[i] = -1;
    }

    for(int i=1;i<=m;i++){
        int x, y; string s;
        cin >> x >> y >> s;
        int tp = (s[0] == 'i');
        add(x, y, tp);
        add(y, x, tp);
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(st[i] == -1){
            st[i] = 1;
            num[1] = 1;
            num[0] = 0;
            if(!dfs(i)){
                cout << "-1\n";
                return;
            }
            ans += max(num[0], num[1]);
        }
    }
    cout << ans << '\n';
}

E1. Rubik's Cube Coloring (easy version)

题意：给一颗 \(k\) 层的完全二叉树，每个节点有一个颜色（共六种），要求每个节点和其相邻节点颜色不能相同，并且规定了三对不能相邻的颜色，问有多少中染色方案

解：答案为 \(4^{2^n-2}\times 6\)

ll qpow(ll x, ll p){
    ll r = 1;
    while(p > 0){
        if(p & 1) r = r * x % mode;
        x = x * x % mode;
        p >>= 1;
    }
    return r;
}

void solve(){
    int n;
    cin >> n;
    cout << qpow(4, (1ll << n) - 2) * 6 % mode << '\n';
}