07-10 12:59 阅读 62

Codeforces Round #721 (Div. 2)

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

A. And Then There Were K

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

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

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

#include 
#include 
#include  
#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<

B1 - Palindrome Game (easy version)

此版本的串为回文串.

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

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

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

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

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

#include 
#include 
#include   
#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 
#include 
#include   
#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  
#include 
#include 
#include   
#define N  100009 
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
vectorv[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

D.MEX Tree

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

同时要求包含和不包含不好做，不妨考虑差分.

令 $\mathrm{dp[i]}$ 表示 $\mathrm{mex}$ 值至少为 $\mathrm{i}$ 的路径条数.

求解的时候维护 $1$ ~ $\mathrm{i}$ 这些点所构成的链，然后每次计算包含这条链的路径数即可.

#include 
#include 
#include  
#include 
#include 
#define N  200009 
#define pb push_back 
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin)    
using namespace std;  
int n ; 
int size[N]; 
int val[N], mk[N], hd[N], fa[N],to[N<<1],nex[N<<1], edges; 
ll dp[N];  
void add(int u, int v) {
    nex[++edges]=hd[u]; 
    hd[u]=edges; 
    to[edges]=v; 
}
void dfs(int x, int ff) {   
    fa[x]=ff; 
    size[x]=1; 
    for(int i=hd[x];i;i=nex[i]) {
        int v=to[i];  
        if(v==ff) continue;  
        dfs(v, x); 
        size[x]+=size[v];  
    }
}
void solve() { 
    scanf("%d",&n);   
    for(int i=1;i<=n;++i) val[i]=i-1; 
    for(int i=1;i 1 && R > 1) {
                dp[i + 1] = 1ll*size[L]*size[R]; 
            }   
            else {
                if(L == 1) dp[i + 1] = 1ll*size[R]*(n - size[son]);     
                if(R == 1) dp[i + 1] = 1ll*size[L]*(n - size[son]);
            }
        }  
    }
    for(int i=0;i<=n;++i) {
        printf("%lld ",dp[i]-dp[i+1]); 
    }
    printf("\n");  
    for(int i=0;i<=n+1;++i) {
        dp[i]=0; 
        hd[i]=0,size[i]=fa[i]=mk[i]=val[i]=0; 
    }
    for(int i=0;i<=edges;++i) nex[i]=to[i]=0; 
    edges=0; 
} 
int main() { 
    // setIO("input");  
    int T; 
    scanf("%d",&T);  
    while(T--) solve(); 
    return 0; 
}

E.Partition Game

考虑朴素 DP

令 $\mathrm{f[i][j]}$ 表示 DP 到 $\mathrm{i}$, 分了 $\mathrm{j}$ 段的最小值.

考虑用线段树维护这个 DP.

每次维护右端点为 $\mathrm{i}$ 时左端点的答案.

右端点向右移动时对应的就是一段区间加法，用线段树来维护即可.

#include 
#include 
#include 
#include   
#define N 35008  
#define ll long long 
#define pb push_back 
#define ls now<<1 
#define rs now<<1|1
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
const ll inf=10000000000000ll; 
struct Segment_Tree {
    ll lazy[N<<2],mn[N<<2];         
    void mark(int now, int v) {
        lazy[now]+=v; 
        mn[now]+=v; 
    }
    void pushdown(int now) {
        if(lazy[now]) {
            mark(ls, lazy[now]); 
            mark(rs, lazy[now]); 
        }
        lazy[now]=0; 
    }
    void pushup(int now) {
        mn[now]=min(mn[ls],mn[rs]); 
    }
    void modify(int l,int r,int now,int p,int v) {
        if(l==r) {
            mn[now]=v; 
            return ; 
        }
        pushdown(now); 
        int mid=(l+r)>>1; 
        if(p<=mid) modify(l,mid,ls,p,v); 
        else modify(mid+1,r,rs,p,v); 
        pushup(now);  
    }
    void update(int l,int r,int now,int L,int R,int v) {
        if(l>r||L>R) return ;  
        if(l>=L&&r<=R) {
            mark(now, v); 
            return ; 
        }
        pushdown(now); 
        int mid=(l+r)>>1;  
        if(L<=mid)  update(l,mid,ls,L,R,v); 
        if(R>mid)   update(mid+1,r,rs,L,R,v);  
        pushup(now); 
    }    
    ll query(int l,int r,int now,int L, int R) {
        if(l>=L&&r<=R) return mn[now]; 
        pushdown(now); 
        int mid=(l+r)>>1;  
        if(L<=mid&&R>mid) return min(query(l,mid,ls,L,R), query(mid+1,r,rs,L,R)); 
        else if(L<=mid)   return query(l,mid,ls,L,R); 
        else return query(mid+1,r,rs,L,R);   
    }
    void build(int l,int r,int now) {
        mn[now]=inf;  
        lazy[now]=0; 
        if(l==r) return ;      
        int mid=(l+r)>>1;  
        build(l,mid,ls); 
        build(mid+1,r,rs); 
    } 
}T;       
int A[N], lst[N];
ll dp[N];   
int main() {
    // setIO("input");
    int n,K;  
    scanf("%d%d",&n,&K);  
    for(int i=1;i<=n;++i) {
        scanf("%d",&A[i]); 
    }         
    T.build(0,n,1);      
    T.modify(0,n,1,0,0);  
    // 0 -> f[0][0]=0;  
    for(int i=1;i<=K;++i) {     
        for(int j=1;j<=n;++j) lst[A[j]]=0; 
        for(int j=1;j<=n;++j) {
            // 考虑加入 j 的影响.  
            int v=A[j];  
            if(lst[v]) {
                // [lst[v]+1, i] 的左端点不变.  
                // [1, lst[v]] 左端点的答案 + det; 
                int det=j-lst[v];           
                // [1, lst[v]] -> 对应到 [0, lst[v]-1] 计算.   
                T.update(0,n,1,0,lst[v]-1,det);  
            }     
            dp[j]=T.query(0,n,1,0,j-1);     
            lst[v]=j;  
        }    
        T.build(0,n,1);    // 将线段树清空.  
        for(int j=1;j<=n;++j) T.modify(0,n,1,j,dp[j]);              
    }
    printf("%lld\n",dp[n]);
    return 0;
}

原文：https://www.cnblogs.com/brady12/p/15302961.html