Codeforces Round 747

A:Consecutive Sum Riddle

Description

给定 \(n\)，求 \(l,r\) 满足 \(\displaystyle\sum_{i=l}^r i = n\)。

多测。

限制：\(1\le t\le 10^4,1\le n\le 10^{18}\)

Solution

令 \(l = 1-n,r=n\) 即可，容易发现答案恰好为 \(n\)。

Code

inline void solve() {
    int_fast64_t n ;
    in(n),out(' ',-(n - 1),n) ;
    fastio::putc('\n') ;
}  

B:Special Numbers

Description

若 \(p\) 为 \(n\) 的特殊数，则 \(p=n^{q_0}+n^{q_1}+\cdots+n^{q_m}(q_i\ge 0)\) 且所有 \(q_i\) 互不相同。

给定 \(n,k\)，求 \(n\) 的特殊数中，第 \(k\) 小的是哪个。

多测。

限制：\(2\le n\le 10^9,1\le k\le 10^9,1\le t\le 10^4\)

Solution

考虑特殊数的组成，在 \(n\) 进制下一定是若干位 \(1\)，也就是说，对于只有 \(0,1\) 组成的 \(n\) 进制数求 \(k\) 小，只需要将 \(k\) 转化为 \(2\) 进制之后，再将这个 \(2\) 进制对应的 \(1\) 的每一位乘上对应的次方即可。

具体看代码。

Code

inline void solve() {
    int n,k,ans = 0;
    cin >> n >> k ;
    std::vector<int> bit ;
    while (k) {
        bit.push_back(k & 1);
        k >>= 1;
    }
    for (int i = 0; i < bit.size(); ++i) 
        ans = (ans + fp(n,i) * bit[i]) % mod ;
    cout << ans << '\n' ; 
}

C:Make Them Equal

Description

给长度为 \(n\) 的字符串 \(s\) 和一个字符 \(c\)，每次可以选择一个 \(x\)，使得不是 \(x\) 的倍数的位置变成 \(c\)，问要使所有字母都变成 \(c\) 至少需要几次操作。

限制：\(3\le n\le 3\times 10^5\)

Solution

首先容易发现答案一定不会超过 \(2\)，因为可以选择 \(n,n-1\)，这样子所有的一定都变成 \(c\) 了，接下来考虑答案小于 \(2\) 的情况。

• 如果都是 \(c\)，那么次数为 \(0\)。

然后对于 \(2\le i\le n\)，每个检验一下能否使别的都变成 \(c\)。

Code

inline void solve() {
    cin >> n >> c >> (s + 1) ;
    int f = 0 ;
    for (int i = 1; i <= n; ++i) 
        if (s[i] != c) {
            f = 1;
            break ;
        }
    if (!f) 
        return cout << "0\n",void() ;
    for (int i = 2; i <= n; ++i) {
        int f = 0;
        for (int j = i; j <= n; j += i) {
            if (s[j] != c) {
                f = 1;
                break ;
            }
        }
        if (f == 0) 
            return cout << "1\n" << i << '\n',void() ;
    }
    cout << 2 << "\n" << n << " " << n - 1 << '\n';
}

D:The Number of Imposters

Description

\(n\) 个人，每个人有一种身份，身份只有 imposter 和 crewmate 两种，\(m\) 种关系，关系分为两种：

x y imposter：\(x\) 认为 \(y\) 是 imposter。

x y crewmate：\(x\) 认为 \(y\) 是 crewmate。

其中 imposter 只说假话，crewmate 只说真话，在所有合法方案中，最大化 imposter 的个数。

限制：\(1\le n\le 2\times 10^5,0\le m\le 5\times 10^5\)

Solution

这种题，一看就是图论了。

考虑对于第二种关系，将 \(x,y\) 连边，对于第一种关系，将 \(x\) 和 \(y\) 连虚边，即通过一个 middle node 连边，这样子的原因之后说。

我们发现，如果是第一种关系的话，x y 之间的关系一定是不同的，而第二种关系一定是相同的。

那么对于连出的每个连通块，我们给任意一个点赋一种身份都可以得到一个答案，对两个答案取最大值即可。

矛盾：如果相邻的两个点颜色相同，那么就存在矛盾（这就是为什么要连虚边）。

容易发现各个连通块之间互不关联， 所以贪心地对每个连通块取答案最大即可。

时间复杂度：\(\mathcal O(n+m)\)。

Code

void dfs(int now) {
    for (auto it : v[now]) {
        if (col[it] == col[now]) 
            return ok = false,void() ;
        if (col[it] == -1) {
            col[it] = col[now] ^ 1 ;
            if (it <= n) ++t[col[it]] ;
            dfs(it) ;
        }
    }
}

namespace {

inline void solve() {
    int cnt,ans = 0;
    cin >> n >> m, ok = 1,cnt = n;
    for (int i = 1; i <= n + m; ++i) col[i] = -1 ;
    for (int i = 1; i <= n + m; ++i) v[i].clear() ;
    for (int i = 1,x,y; i <= m; ++i) {
        char s[10] ;
        cin >> x >> y >> s; 
        if (s[0] == 'i') 
            v[x].push_back(y),v[y].push_back(x) ;
        else 
            v[x].push_back(++cnt),v[cnt].push_back(x),v[y].push_back(cnt),v[cnt].push_back(y) ;
    }
    for (int i = 1; i <= n; ++i) {
        if (col[i] != -1) 
            continue ;
        t[0] = 1,t[1] = 0,col[i] = 0;
        dfs(i) ;
        ans += max(t[0],t[1]) ;
    }
    if (!ok) ans = -1 ;
    cout << ans << '\n' ;
}

inline void HL() {
    int t; 
    cin >> t ;
    for (; t; --t) 
        solve() ;
}

}