Codeforces Round #721 (Div. 2)

2024-03-04 07:53:04

Codeforces Round #721 (Div. 2)

来源：https://codeforces.com/contest/1527

A. And Then There Were K

不妨打一个表看看有没有什么规律.

发现每个数字 $\mathrm{x}$ 的答案是 $\mathrm{x}$ 二进制展开中最高次位减一.

直接对每个数 $O( \log n) $ 扫一下即可.

#include <cstdio>
#include <cstring>
#include <algorithm> 
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
ll calc(ll x) {
    for(int i=32;i>=0;--i) {
        if(x&(1ll<<i)) {
            return (1ll<<i)-1;  
        }
    }
} 
int main() {
    // setIO("input");   
    int T; 
    scanf("%d",&T); 
    while(T--) {
        ll n ; 
        scanf("%lld",&n); 
        printf("%lld\n",calc(n)); 
    }
    return 0; 
}

B1 - Palindrome Game (easy version)

此版本的串为回文串.

假如 0 的个数为偶数，则后手可以一直模仿先手.

剩 2 个数时，先手将 $0$ 变 $1$ 后使用一次跳步，可以少取 2 次.

假如 0 的个数为奇数，且只有一个 0 则后手胜，否则先手胜.

这是因为先手可以先取中间的 0，然后转化成一个偶数的子问题.

先手在第一步吃亏一步，后面后手吃亏 2 步，先手胜.

#include <cstdio>
#include <vector>
#include <cstring>  
#define N 10007 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
char str[N]; 
void solve() {
    int n ; 
    scanf("%d",&n); 
    scanf("%s",str+1);    
    int cnt=0; 
    for(int i=1;i<=n;++i) if(str[i]=='0') ++cnt;           
    if(cnt > 1 && (cnt % 2 == 1))   printf("ALICE\n"); 
    else printf("BOB\n"); 
}
int main() {
    // setIO("input"); 
    int T; 
    scanf("%d",&T); 
    while(T--) solve(); 
    return 0; 
}

B2. Palindrome Game (hard version)

假设最开始不是回文串：

如果长度为偶数，则先手可以一直使用跳步，后手要凑成回文串.

在差一步能凑成回文串时先手走那一步，然后就变成 B1 中长度为偶数先手必败子问题了.

故 ALICE 获胜.

若长度为奇数，则要看中间位置是否为 0.

若中间位置为 1，则与偶数情况无异，ALICE 获胜.

若中间位置为 0，则先手走中间位置后又变成上面 ALICE 获胜子问题.

唯一使得 ALICE 不胜的情况就是中间位置为 0，且一共只有两个 0.

这样 ALICE 走完第一步后 BOB 走完第二步两者就打平了.

#include <cstdio>
#include <vector>
#include <cstring>  
#define N 10007 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
char str[N]; 
void solve() {
    int n ; 
    scanf("%d",&n); 
    scanf("%s",str+1);    
    int cnt=0; 
    int flag=0; 
    for(int i=1;i<=n;++i) {
        if(str[i]=='0') ++cnt;           
        if(str[i] != str[n-i+1]) flag=1;   
    }
    if(!flag) {
        if(cnt > 1 && (cnt % 2 == 1))   printf("ALICE\n"); 
        else printf("BOB\n"); 
    }
    else {
        if(n % 2 == 1 && str[(1+n)/2] == '0' && cnt == 2) printf("DRAW\n"); 
        else printf("ALICE\n");   
    }
}
int main() {
    // setIO("input"); 
    int T; 
    scanf("%d",&T); 
    while(T--) solve(); 
    return 0; 
}

C.Sequence Pair Weight

将每一种数字单独提取出来并单独计算贡献.

枚举右端点，然后每一个左端点的贡献就是该左端点的位置.

扫一遍即可.

#include <cstdio> 
#include <cstring>
#include <algorithm>
#include <vector>  
#define N  100009 
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
vector<int>v[N];
int a[N],A[N],n;  
void solve() {
    scanf("%d",&n);    
    for(int i=1;i<=n;++i) scanf("%d",&a[i]), A[i]=a[i]; 
    sort(A+1,A+1+n);  
    for(int i=1;i<=n;++i) {
        a[i]=lower_bound(A+1,A+1+n,a[i])-A;  
        v[a[i]].pb(i); 
    }
    ll ans=0ll; 
    for(int i=1;i<=n;++i) {
        if(v[i].size() < 2) continue;  
        ll sum=0ll; 
        for(int j=0;j<v[i].size();++j) {
            ans += 1ll*(n - v[i][j] + 1) * sum;   
            sum += v[i][j];  
        }
    }
    printf("%lld\n",ans);  
    for(int i=1;i<=n;++i) {
        v[i].clear(); 
    }
} 
int main() { 
    // setIO("input");  
    int T; 
    scanf("%d",&T); 
    while(T--) solve(); 
    return 0; 
}

D.MEX Tree

直接做肯定不好做.

根据 $\mathrm{mex}$ 的定义，若 $\mathrm{mex=i}$, 则路径需要包含 $1$ ~ $\mathrm{i-1}$, 且不包含 $\mathrm{i}$

码农公寓