很edu的一场，建议全部补完喵~。

A.回文(version 1）

按题意模拟一下即可。

注意题目给的是 $x^2$ 不是 $x$ 。

时间复杂度 $O(1)$ 。

n = int(input())
def f(x):
    return str(x) == str(x)[::-1]
print("YES" if f(n) and f(int(n**0.5))  and int(n**0.5) == n**0.5 else "NO")

B.未知(version 1)

由于 $x\le y$ ，因此 $x \oplus y > 0 = y \oplus y$ ，取 $y$ 即可。

时间复杂度 $O(1)$ 。

for _ in range(int(input())):
    print(input().split()[1])

C.回文(version 2)

不妨考虑从外往内匹配。

如果两个字符相同，则两段指针直接内移，否则尝试两个 $n$ 和 $m$ 匹配即可。

时间复杂度 $O(n)$ 。

void solve(){
    string s;cin>>s;
    ll l = 0, r = s.size()-1;
    while(l<=r){
        if(s[l]==s[r]){
            l++,r--;
        }
        else if(s[l]=='n'){
            if(s[l+1]=='n') l+=2,r--;
            else{
                cout<<"NO\n";
                return;
            }
        }
        else{
            if(s[r-1]=='n') r-=2,l++;
            else{
                cout<<"NO\n";
                return;
            }
        }
    }
    cout<<"YES\n";
}

D.未知(version 2)

考虑对所有 $i$ 预处理所有的 $(j, k)$ 满足 $j^k = i$ ，但是至少有 $10^9 * 1 = 10^9$ （ $i^1 = i$ ）对。

注意到当 $i*i > 1e9$ 时，只有 $(i, 1)$ 一对满足要求的，因此这一部分可以直接判断而不预处理。

剩下的对数，共有 $1+\sum_{i=2}^{\lfloor \sqrt{10^9}\rfloor}\bigl(\lfloor \log_i(10^9)\rfloor+1\bigr) \approx 10^5$ 对，可以直接预处理出来。

则对于每个 $a_i$ ，我们检查所有满足 $(j, k)$ ：

如果 $j=k$ 则其他元素里必须有两个 $j$ 。
否则其他元素里必须有一个 $j$ 和一个 $k$ 。

时间复杂度 $O(n)$ 。

unordered_map<ll, vector<PLL>> memo;
ll c = 0;
void init(){
    memo[1].pb({1, 1});
    for(ll i=2;i*i<=1e9;i++){
        ll cur = i;
        ll cnt = 1;
        c++;
        while(cur<=1e9){
            cur*=i;
            cnt++;
            memo[cur].pb({i, cnt});
            c++;
        }
        
    }
}

void solve(){
    ll n = read();
    vector<ll> a(n);
    unordered_map<ll, ll> memo2;
    for(ll i=0;i<n;i++) a[i] = read(), memo2[a[i]]++;
    for(ll i=0;i<n;i++){
        memo2[a[i]]--;
        for(auto [t, p]:memo[a[i]]){
            if(t==p&&memo2[t]>=2){
                puts("YES");
                return;
            }
            else if(memo2[t]&&memo2[p]){
                puts("YES");
                return;
            }
        }
        if(a[i]*a[i]>1e9){
            if(memo2[1]&&memo2[a[i]]){
                puts("YES");
                return;
            }
        }
        memo2[a[i]]++;
        
    }
    puts("NO");
}

E.未知(version 3)

考虑边界情况，不妨考虑从距离 $1 \sim m$ 以此接上去（具体可见下图）：

如果每个叶子结点都是由根节点接一条链到达距离 $i$ 的，则需要 $1 + \sum_{i=1}^{m} i = 1+\frac{(m+1)*m}{2}$ 个点。
如果每个叶子结点尽可能和其他链复用节点，若已经有了 $1 \sim i-1$ 距离的节点，则至少从 $i-1$ 的链末尾的父节点开始接（否则会把叶子结点变没）。此时新增两个节点，因此需要 $2*m$ 个点。

则 $n \in [2*m, 1+\frac{(m+1)*m}{2}]$ 均可以构造，否则不能。

不妨考虑先把距离为 $m$ 的那条链构造出来作为主链，在从距离 $1\sim m-1$ 依次接上去。

此时需要在主链上复用的节点数量为 $t = 1+\frac{(m+1)*m}{2} - n$ 。

对于距离为 $i$ 的点，最多可以复用 $u = min(t, i-1)$ 个节点，在从主链上 $u+1$ 节点的位置开始接。

时间复杂度 $O(n)$ 。

void solve(){
    ll n = read(), m = read();
    if(!(2*m<=n&&n<=1+(1+m)*m/2)){
        puts("NO");
        return;
    }
    puts("YES");
    for(ll i=2;i<=m+1;i++){
        print(PLL{i, i-1});
    }
    ll need = 1+(1+m)*m/2 - n;
    ll cur = m+2;
    for(ll i=1;i<m;i++){
        ll use = min(i-1, need);
        need -= use;
        ll pre = use + 1;
        for(ll j=use+1;j<=i;j++){
            print(PLL{pre, cur});
            pre = cur;
            cur++;
        }
    }
}

F.回文(version 3)

不妨将三种情况分开讨论。

$x=1$ 显然答案即为 $r-l+1$ 。
$x=2$ 答案即为相同字符的匹配对数，答案即为 $\sum_{c='a'}^{'z'} \binom{cnt_{c, r} - cnt_{c, l}}{2}$ 。
$x=3$ 还需要在相同字符见插入一个字母。

设对于某个字符 $[l, r]$ 内有 $p_1 \dots p_k$ 个节点，则该字符的贡献为：
$\sum_{i=1}^{k} \sum_{j=1}^{i-1} p_i - p_j -1$
考虑如何通过前缀预处理 $O(1)$ 得到这个答案。（以单个字符为例，显然不同字符之间的答案可以直接累加）

设 $[1, i]$ 有 $cnt_{i}$ 个字符， $[1, i]$ 所有字符的位置之和为 $psum_{i}$

不妨先求 $[1, i]$ 的字符答案，设为 $ans_{i}$ 。

则对于新增一个位置 $i$ ，答案的变化值为 $(i-1)*cnt_{i-1} - psum_{i}$ 。

再考虑如何求解 $[l, r]$ 的答案。

如果直接 $ans_{r} - ans_{l-1}$ ，会多计算 $[1, l-1]$ 和 $[l, r]$ 匹配的部分。

对于 $[l, r]$ 内的每个元素，多计算了 $cnt_{l-1} * (i-1) - psum_{l-1}$ ，求和得到
$cnt_{l-1} * ((psum_r-psum_{l-1}) - (cnt_r - cnt_{l-1}))- psum_{l-1}*(cnt_r - cnt_{l-1})$
因此 $[l, r]$ 内的答案为
$ans_{r} - ans_{l-1} - (cnt_{l-1} * ((psum_r-psum_{l-1}) - (cnt_r - cnt_{l-1}))- psum_{l-1}*(cnt_r - cnt_{l-1}))$

时间复杂度 $O(n+q)$ 。

void solve(){
    ll n, q;cin>>n>>q;
    string s;cin>>s;
    s = ' ' + s;
    vector<vector<ll>> pre(n+1, vector<ll>(26));// cnt
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<26;j++){
            pre[i][j] = (pre[i-1][j] + ((s[i]-'a')==j));
        }
    }
    vector<vector<ll>> pre2(n+1, vector<ll>(26));// psum 
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<26;j++){
            pre2[i][j] = (pre2[i-1][j] + ((s[i]-'a')==j)*i);
        }
    }
    vector<vector<ll>> pre3(n+1, vector<ll>(26));// ans
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<26;j++){
            pre3[i][j] = pre3[i-1][j];
            if((s[i]-'a')==j){
                pre3[i][j] += (i-1)*pre[i-1][j]-pre2[i-1][j];
            }
        }
    }
    while(q--){
        ll l, r, x;cin>>l>>r>>x;
        if(x == 1) cout<<r-l+1<<'\n';
        else if(x == 2){
            ll ans = 0;
            for(ll i=0;i<=25;i++) ans += (pre[r][i] - pre[l-1][i])*((pre[r][i] - pre[l-1][i])-1)/2;
            cout<<ans<<'\n';
        }
        else{
            ll ans = 0;
            for(ll i=0;i<=25;i++){
                ans += (pre3[r][i]-pre3[l-1][i]);
                ans -= pre[l-1][i]*((pre2[r][i]-pre2[l-1][i])-(pre[r][i]-pre[l-1][i]))-(pre[r][i]-pre[l-1][i])*pre2[l-1][i];
            }
            cout<<ans<<'\n';
        }
    }
}

题解 | #牛客周赛Round141题解#

A.回文(version 1）

B.未知(version 1)

C.回文(version 2)

D.未知(version 2)

E.未知(version 3)

F.回文(version 3)