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';
}