CF1450 题解

Author： RainAir
发布时间：December 7, 2020
1855views
4 comments
362 words
Categories：题解

A

把 $b$ 都提到最前面就好了。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 200+5;
char str[MAXN];
int cnt[26],n;

int main(){
    int T;scanf("%d",&T);
    while(T--){
        CLR(cnt,0);scanf("%d",&n);
        scanf("%s",str+1);
        FOR(i,1,n) ++cnt[str[i]-'a'];
        FOR(i,1,cnt[1]) putchar('b');
        FOR(i,0,25){
            if(i == 1) continue;
            FOR(j,1,cnt[i]) putchar('a'+i);
        }
        puts("");
    }
    return 0;
}

B

我们证明答案一定 $\leq 1$：假设答案 $\geq 2$，考虑最后一步和倒数第二步，倒数第二步会把最后一步操作的点直接拉过来，所以最后一步的操作是无效的，可以删去。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100+5;
int n,x[MAXN],y[MAXN],k;

inline void Solve(){
    scanf("%d%d",&n,&k);
    FOR(i,1,n) scanf("%d%d",x+i,y+i);
    FOR(i,1,n){
        int mx = 0;
        FOR(j,1,n) mx = std::max(mx,std::abs(x[i]-x[j])+std::abs(y[i]-y[j]));
        if(mx <= k){
            puts("1");
            return;
        }
    }
    puts("-1");
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

C1

感觉比较难。。发现三个相邻的点 $i+j \bmod 3$ 两两不同，于是按照 $i+j \bmod 3$ 分类，找一个最小的将其全部翻转即可。

C2

会了 C1 稍微想想就会了。我们现在把 X 分成三类 $x_0,x_1,x_2$，把 O 分成三类 $o_1,o_2,o_3$，显然我们只需要选一对 $p \neq q$，将 $x_p$ 全都变为 O，并且将 $x_q$ 全都变为 X，可以得到这样是 $\leq \frac{1}{3}$ 的。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 300+5;
char str[MAXN][MAXN];int n;
int mp[MAXN][MAXN];
int cnt[2][3],ps[2];

inline void Solve(){
    scanf("%d",&n);CLR(cnt,0);
    FOR(i,1,n){
        scanf("%s",str[i]+1);
        FOR(j,1,n){
            if(str[i][j] != '.') ++cnt[str[i][j]=='X'][(i+j)%3];
        }
    }
    ps[0] = ps[1] = -1;
    int mn = 1e9;
    FOR(i,0,2){
        FOR(j,0,2){
            if(i == j) continue;
            if(mn > cnt[0][i]+cnt[1][j]){
                mn = cnt[0][i] + cnt[1][j];
                ps[0] = i;ps[1] = j;
            }
        }
    }
    FOR(i,1,n){
        FOR(j,1,n){
            if(str[i][j] == '.') putchar(str[i][j]);
            else{
                if(str[i][j] == 'O') putchar((i+j)%3 == ps[0] ? 'X' : 'O');
                else putchar((i+j)%3 == ps[1] ? 'O' : 'X');
            }
        }
        puts("");
    }
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

D

特判 $k=1$ 和 $k=n$。

考虑 $k \in [2,n-1]$ 的情况：首先最小值 $1$ 肯定要出现且仅出现一次，发现只需要出现一次的位置一定是边界，所以等价于要判断是否只有一个 $1$ 并且这个 $1$ 在边界上，然后删掉这个 $1$ 变成了一个子问题。我们就可以求出最长能凑出多少的排列了。

感觉比 C 简单。。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 3e5 + 5;
int n,a[MAXN];
bool vis[MAXN];
bool f[MAXN];
int cnt[MAXN];

inline void Solve(){
    scanf("%d",&n);FOR(i,1,n) cnt[i] = 0;
    FOR(i,1,n) scanf("%d",a+i),vis[i] = 0,++cnt[a[i]];
    FOR(i,1,n) vis[a[i]] = 1,f[i] = 0;f[0] = 1;
    int sm = 0;
    FOR(i,1,n) f[i] = f[i-1]&vis[i],sm += vis[i];
    std::reverse(f+1,f+n+1);
    int l = 1,r = n,now = 1;
    while(l <= r){
        if(a[l] != now && a[r] != now) break;
        --cnt[now];
        if(cnt[now]) break;
        if(a[l] == now) ++l,++now;
        else if(a[r] == now) --r,++now;
    }
    --now;
    FOR(i,1,n-now-1) f[i] = 0;
    if(sm == n) f[1] = 1;
    if(vis[1]) f[n] = 1;
    FOR(i,1,n) putchar('0'+f[i]);puts("");
}

int main(){
    int T;scanf("%d",&T);while(T--) Solve();
    return 0;
}

E

其实是个差分约束题（

首先相邻两个人一定奇偶性不同，所以如果不是二分图直接无解。

考虑一条无向边 $(u,v)$，相当于有限制 $|a_u-a_v| = 1$，不妨先写成 $|a_u-a_v| \leq 1$；

考虑一条有向边 $u \to v$，相当于有限制 $a_v-a_u=1$，也就是 $a_v-a_u \leq 1$ 和 $a_v-a_u \geq 1$。

我们按照上面不等式建差分约束然后跑最短路，枚举一个起点，求出距离起点最远的距离，显然这个距离的最大值就是答案。

首先答案一定不能超过这个值，所以我们只要构造出一组合法的解就好了。

我们取能取到最大值的起点，将点 $i$ 的权值直接设为起点到 $i$ 的最短路就好了。因为这是一个二分图，所以无向边的情况不可能有 $a_u=a_v$（因为都是连的 $1$ 边，如果有这个情况说明一定不是二分图了）。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 200+5;

int G[MAXN][MAXN],dis[MAXN][MAXN];
int n,m;
bool flag=1;
int col[MAXN];
bool vis[MAXN];

inline void dfs(int v){
    vis[v] = 1;
    FOR(i,1,n){
        if(G[v][i] == 1e8 || v == i) continue;
        if(vis[i]) flag &= (col[v]^col[i]);
        else col[i] = col[v]^1,dfs(i);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,1,n) FOR(j,1,n) G[i][j] = 1e8;
    FOR(i,1,n) G[i][i] = 0;
    while(m--){
        int i,j,w;scanf("%d%d%d",&j,&i,&w);
        if(!w){
            G[j][i] = std::min(G[j][i],1);
            G[i][j] = std::min(G[i][j],1);
        }
        else{
            G[j][i] = std::min(G[j][i],1);
            G[i][j] = std::min(G[i][j],-1);
        }
    }
    dfs(1);
    if(!flag){
        puts("NO");
        return 0;
    }
    FOR(i,1,n) FOR(j,1,n) dis[i][j] = G[i][j];
    int cir = 1e9;
    FOR(k,1,n){
        FOR(i,1,k-1){
            FOR(j,1,k-1){
                if(i == j) continue;
                cir = std::min(cir,G[k][i]+G[j][k]+dis[i][j]);
            }
        }
        FOR(i,1,n){
            FOR(j,1,n){
                dis[i][j] = std::min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
//    FOR(i,1,n) FOR(j,1,n) if(G[i][j] != 1e9 && i != j) printf("%d %d %d\n",i,j,G[i][j]);
    if(cir < 0){
        puts("NO");
        return 0;
    }
    int mx = 0,ps = -1;
    FOR(i,1,n){
        int c = -1e9;
        FOR(j,1,n) c = std::max(c,dis[i][j]);
        if(mx < c){
            mx = c;ps = i;
        }
    }
    puts("YES");
    printf("%d\n",mx);
    FOR(i,1,n) printf("%d%c",dis[ps][i]," \n"[i==n]);
    return 0;
}

F

还是结论题，完全不会

这个操作实际上就是将原排列分成尽量少的段，将这些段翻转和重排后要求相邻的值不能相同。

那么我们先考虑如何判断对于一个分成了 $k+1$ 段的切割方案，是否存在一种操作方案，能重排后相邻值不相同。

首先我们要保证每段内部不能有相邻相同的对，因为操作影响不到内部的点。

设 $f(c)$ 表示颜色 $c$ 在端点上的出现次数，一个显然的限制是 $f(c) \leq k+2$，我们现在说明只要满足这个限制的所有切割方案都是合法的：

考虑对 $k$ 归纳，如果 $k=0$ 时只有一段，命题显然成立；对于 $k \geq 1$ 的部分，考虑取最大值的 $f(x)$，找出一端是颜色 $x$ 的段，再随便找一个一端是颜色 $y(y \neq x)$ 的段，将 $x,y$ 对着拼在一起，现在相当于是一个 $k-1$ 的局面，我们发现 $f(x)-1 \leq k-1+2$，$f(z) \leq k-1 \leq k$（因为如果非最大值 $> k$ 那么和就超过 $k+2$ 了），所以这个局面是合法的，归纳得证。

所以我们先将所有相邻相同的地方都分开，然后看下是否满足条件，如果满足条件直接输出 $k$，否则我们要多切出一些段来让其满足条件。设最大值为 $f(x)$，分类讨论一下发现每次切开的两边的颜色都不能是 $x$，切到满足条件为止就好了。如果全都切完了还不满足条件就无解。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
int n,a[MAXN],f[MAXN];

inline void Solve(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i),f[i] = 0;
    int k = 0;
    ++f[a[1]];++f[a[n]];
    FOR(i,2,n){
        if(a[i] == a[i-1]){
            ++k;++f[a[i]];++f[a[i-1]];
        }
    }
    int mx = 0,ps = -1;
    FOR(i,1,n){
        if(mx < f[i]-k-2){
            mx = f[i]-k-2;
            ps = i;
        }
    }
    if(!mx){
        printf("%d\n",k);
        return;
    }
    int r = 0;
    FOR(i,2,n) if(a[i] != a[i-1] && a[i] != ps && a[i-1] != ps) ++r;
    if(mx <= r){
        printf("%d\n",k+mx);
    }
    else{
        puts("-1");
    }
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

G

先咕了，等个谁写个中文题解（

H1

先考虑如何求 $f(c)$：首先发现如果有相邻相同颜色的点可以都删掉，于是我们只需要考虑黑白交替的 $f(c)$ 答案是啥：不难发现是黑色点数量除二。

所以我们可以用栈来搞这个东西：每次加入一个新球，如果栈顶和这个球颜色相同就一块弹出栈，否则弹出栈并让答案 $+1$。不妨考虑哪些黑色点对答案有贡献：我们如果假设第一个点是黑色点的话，第一个点有贡献当且仅当下一个黑色点也是奇数位置的点（说明有一个白色和它配对掉了），如果下一个黑色点是偶数位置的话说明它和上一个黑色点消去了，设奇数位置，偶数位置黑色点数量为 $B_1,B_2$，白色为 $W_1,W_2$，答案就是$\frac{1}{2}|B_1-B_2|$。

如果枚举 $B_1,B_2$ 然后计数很麻烦，考虑 $B_2+W_2=\frac{n}{2}$，所以这个式子可以换成 $\frac{1}{2}|B_1-\frac{n}{2}+W_2|$，我们枚举 $i=B_1+W_2$，设空位置数量为 $p$ ，已经有的 $b_1+w_2=c$，方案数就是 $\binom p {i-c}$，所以答案就是：

$$ \frac{1}{2^p}\sum_{i=0,i \equiv \frac{n}{2} \pmod 2}^n \binom p {i-c} |i-\frac{n}{2}| $$

我们改为枚举 $i-c$，设 $d=c-\frac{n}{2}$式子化简为：

$$ \frac{1}{2^p}\sum_{i=0,i \equiv d \pmod 2}^n \binom p i |i-d| $$

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 3e5 + 5;
const int ha = 998244353;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

int fac[MAXN],inv[MAXN];

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    return (n < 0 || m < 0 || n < m) ? 0 : 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

char str[MAXN];
int n,m;

int main(){
    prework();
    scanf("%d%d",&n,&m);
    scanf("%s",str+1);
    int B1=0,W2=0,p=0;
    FOR(i,1,n){
        B1 += (str[i] == 'b' && (i&1));
        W2 += (str[i] == 'w' && (!(i&1)));
        p += (str[i] == '?');
    }
    int ans = 0;
    FOR(x,0,n){
        int c = C(p,x),d = std::abs(x-(n/2)+B1+W2);
        if(d&1) continue;
        c = 1ll*c*d%ha;
        add(ans,c);
    }
    ans = 1ll*ans*qpow(qpow(2,p))%ha;
    printf("%d\n",ans);
    return 0;
}

H2

首先要解决 $i \equiv d \pmod 2$ 的限制的问题，发现 $\binom n m = \binom {n-1}{m}+\binom{n-1}{m-1}$，所以我们将式子写开，就去掉了这个限制。

现在我们考虑如何维护如下式子的值：

$$ \begin{aligned} \sum_{i=0}^n \binom p i |i-d| = \sum_{i=0}^d \binom p i d-\sum_{i=0}^d \binom p i i+\sum_{i=d+1}^n \binom p i i - \sum_{i=d+1}^n \binom p i d \end{aligned} $$

发现 $\binom n m m= \binom {n-1}{m-1}n$，区间求和可以拆成前缀和询问，所以我们相当于要快速维护

$$ \sum_{i=0}^{lim} \binom p i $$

我们发现 $lim$ 和 $i$ 的变化都是 $O(1)$ 的，所以我们只需要考虑 $lim,p$ 加减 $1$ 的变化即可。

$lim$ 加一直接加上对应的项即可。

$\binom {p+1}{i} = \binom p i + \binom p {i-1}$，所以 $p$ 加一只需要额外维护一下 $0\ldots lim-1$ 的求和即可。

注意特判 $p=1$ 的边界。代码咕了。

Last modification：December 7th, 2020 at 09:32 pm

如果觉得我的文章对你有用，请随意赞赏

4 comments

suncongbo
January 18th, 2021 at 08:37 am

你好菜啊，还没有我太阳亿万分之一强

Reply
suncongbo
January 18th, 2021 at 08:36 am

楼上都菜我又强又真 10ms不切还是人吗？

Reply
寒雨微凝
January 18th, 2021 at 08:32 am

不对，说错了，10s就能切完，就你这水平还想进省队？

Reply
寒雨微凝
January 18th, 2021 at 07:23 am

你好菜啊，这都不会，我 10min 切完

Reply

CF1450 题解

RainAir • 2020 年 12 月 07 日

A

把 $b$ 都提到最前面就好了。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 200+5;
char str[MAXN];
int cnt[26],n;

int main(){
    int T;scanf("%d",&T);
    while(T--){
        CLR(cnt,0);scanf("%d",&n);
        scanf("%s",str+1);
        FOR(i,1,n) ++cnt[str[i]-'a'];
        FOR(i,1,cnt[1]) putchar('b');
        FOR(i,0,25){
            if(i == 1) continue;
            FOR(j,1,cnt[i]) putchar('a'+i);
        }
        puts("");
    }
    return 0;
}

B

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100+5;
int n,x[MAXN],y[MAXN],k;

inline void Solve(){
    scanf("%d%d",&n,&k);
    FOR(i,1,n) scanf("%d%d",x+i,y+i);
    FOR(i,1,n){
        int mx = 0;
        FOR(j,1,n) mx = std::max(mx,std::abs(x[i]-x[j])+std::abs(y[i]-y[j]));
        if(mx <= k){
            puts("1");
            return;
        }
    }
    puts("-1");
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

C1

感觉比较难。。发现三个相邻的点 $i+j \bmod 3$ 两两不同，于是按照 $i+j \bmod 3$ 分类，找一个最小的将其全部翻转即可。

C2

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 300+5;
char str[MAXN][MAXN];int n;
int mp[MAXN][MAXN];
int cnt[2][3],ps[2];

inline void Solve(){
    scanf("%d",&n);CLR(cnt,0);
    FOR(i,1,n){
        scanf("%s",str[i]+1);
        FOR(j,1,n){
            if(str[i][j] != '.') ++cnt[str[i][j]=='X'][(i+j)%3];
        }
    }
    ps[0] = ps[1] = -1;
    int mn = 1e9;
    FOR(i,0,2){
        FOR(j,0,2){
            if(i == j) continue;
            if(mn > cnt[0][i]+cnt[1][j]){
                mn = cnt[0][i] + cnt[1][j];
                ps[0] = i;ps[1] = j;
            }
        }
    }
    FOR(i,1,n){
        FOR(j,1,n){
            if(str[i][j] == '.') putchar(str[i][j]);
            else{
                if(str[i][j] == 'O') putchar((i+j)%3 == ps[0] ? 'X' : 'O');
                else putchar((i+j)%3 == ps[1] ? 'O' : 'X');
            }
        }
        puts("");
    }
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

D

特判 $k=1$ 和 $k=n$。

感觉比 C 简单。。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 3e5 + 5;
int n,a[MAXN];
bool vis[MAXN];
bool f[MAXN];
int cnt[MAXN];

inline void Solve(){
    scanf("%d",&n);FOR(i,1,n) cnt[i] = 0;
    FOR(i,1,n) scanf("%d",a+i),vis[i] = 0,++cnt[a[i]];
    FOR(i,1,n) vis[a[i]] = 1,f[i] = 0;f[0] = 1;
    int sm = 0;
    FOR(i,1,n) f[i] = f[i-1]&vis[i],sm += vis[i];
    std::reverse(f+1,f+n+1);
    int l = 1,r = n,now = 1;
    while(l <= r){
        if(a[l] != now && a[r] != now) break;
        --cnt[now];
        if(cnt[now]) break;
        if(a[l] == now) ++l,++now;
        else if(a[r] == now) --r,++now;
    }
    --now;
    FOR(i,1,n-now-1) f[i] = 0;
    if(sm == n) f[1] = 1;
    if(vis[1]) f[n] = 1;
    FOR(i,1,n) putchar('0'+f[i]);puts("");
}

int main(){
    int T;scanf("%d",&T);while(T--) Solve();
    return 0;
}

E

其实是个差分约束题（

首先相邻两个人一定奇偶性不同，所以如果不是二分图直接无解。

考虑一条无向边 $(u,v)$，相当于有限制 $|a_u-a_v| = 1$，不妨先写成 $|a_u-a_v| \leq 1$；

考虑一条有向边 $u \to v$，相当于有限制 $a_v-a_u=1$，也就是 $a_v-a_u \leq 1$ 和 $a_v-a_u \geq 1$。

我们按照上面不等式建差分约束然后跑最短路，枚举一个起点，求出距离起点最远的距离，显然这个距离的最大值就是答案。

首先答案一定不能超过这个值，所以我们只要构造出一组合法的解就好了。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 200+5;

int G[MAXN][MAXN],dis[MAXN][MAXN];
int n,m;
bool flag=1;
int col[MAXN];
bool vis[MAXN];

inline void dfs(int v){
    vis[v] = 1;
    FOR(i,1,n){
        if(G[v][i] == 1e8 || v == i) continue;
        if(vis[i]) flag &= (col[v]^col[i]);
        else col[i] = col[v]^1,dfs(i);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,1,n) FOR(j,1,n) G[i][j] = 1e8;
    FOR(i,1,n) G[i][i] = 0;
    while(m--){
        int i,j,w;scanf("%d%d%d",&j,&i,&w);
        if(!w){
            G[j][i] = std::min(G[j][i],1);
            G[i][j] = std::min(G[i][j],1);
        }
        else{
            G[j][i] = std::min(G[j][i],1);
            G[i][j] = std::min(G[i][j],-1);
        }
    }
    dfs(1);
    if(!flag){
        puts("NO");
        return 0;
    }
    FOR(i,1,n) FOR(j,1,n) dis[i][j] = G[i][j];
    int cir = 1e9;
    FOR(k,1,n){
        FOR(i,1,k-1){
            FOR(j,1,k-1){
                if(i == j) continue;
                cir = std::min(cir,G[k][i]+G[j][k]+dis[i][j]);
            }
        }
        FOR(i,1,n){
            FOR(j,1,n){
                dis[i][j] = std::min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
//    FOR(i,1,n) FOR(j,1,n) if(G[i][j] != 1e9 && i != j) printf("%d %d %d\n",i,j,G[i][j]);
    if(cir < 0){
        puts("NO");
        return 0;
    }
    int mx = 0,ps = -1;
    FOR(i,1,n){
        int c = -1e9;
        FOR(j,1,n) c = std::max(c,dis[i][j]);
        if(mx < c){
            mx = c;ps = i;
        }
    }
    puts("YES");
    printf("%d\n",mx);
    FOR(i,1,n) printf("%d%c",dis[ps][i]," \n"[i==n]);
    return 0;
}

F

还是结论题，完全不会

这个操作实际上就是将原排列分成尽量少的段，将这些段翻转和重排后要求相邻的值不能相同。

那么我们先考虑如何判断对于一个分成了 $k+1$ 段的切割方案，是否存在一种操作方案，能重排后相邻值不相同。

首先我们要保证每段内部不能有相邻相同的对，因为操作影响不到内部的点。

设 $f(c)$ 表示颜色 $c$ 在端点上的出现次数，一个显然的限制是 $f(c) \leq k+2$，我们现在说明只要满足这个限制的所有切割方案都是合法的：

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
int n,a[MAXN],f[MAXN];

inline void Solve(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i),f[i] = 0;
    int k = 0;
    ++f[a[1]];++f[a[n]];
    FOR(i,2,n){
        if(a[i] == a[i-1]){
            ++k;++f[a[i]];++f[a[i-1]];
        }
    }
    int mx = 0,ps = -1;
    FOR(i,1,n){
        if(mx < f[i]-k-2){
            mx = f[i]-k-2;
            ps = i;
        }
    }
    if(!mx){
        printf("%d\n",k);
        return;
    }
    int r = 0;
    FOR(i,2,n) if(a[i] != a[i-1] && a[i] != ps && a[i-1] != ps) ++r;
    if(mx <= r){
        printf("%d\n",k+mx);
    }
    else{
        puts("-1");
    }
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

G

先咕了，等个谁写个中文题解（

H1

先考虑如何求 $f(c)$：首先发现如果有相邻相同颜色的点可以都删掉，于是我们只需要考虑黑白交替的 $f(c)$ 答案是啥：不难发现是黑色点数量除二。

$$ \frac{1}{2^p}\sum_{i=0,i \equiv \frac{n}{2} \pmod 2}^n \binom p {i-c} |i-\frac{n}{2}| $$

我们改为枚举 $i-c$，设 $d=c-\frac{n}{2}$式子化简为：

$$ \frac{1}{2^p}\sum_{i=0,i \equiv d \pmod 2}^n \binom p i |i-d| $$

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 3e5 + 5;
const int ha = 998244353;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

int fac[MAXN],inv[MAXN];

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    return (n < 0 || m < 0 || n < m) ? 0 : 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

char str[MAXN];
int n,m;

int main(){
    prework();
    scanf("%d%d",&n,&m);
    scanf("%s",str+1);
    int B1=0,W2=0,p=0;
    FOR(i,1,n){
        B1 += (str[i] == 'b' && (i&1));
        W2 += (str[i] == 'w' && (!(i&1)));
        p += (str[i] == '?');
    }
    int ans = 0;
    FOR(x,0,n){
        int c = C(p,x),d = std::abs(x-(n/2)+B1+W2);
        if(d&1) continue;
        c = 1ll*c*d%ha;
        add(ans,c);
    }
    ans = 1ll*ans*qpow(qpow(2,p))%ha;
    printf("%d\n",ans);
    return 0;
}

H2

首先要解决 $i \equiv d \pmod 2$ 的限制的问题，发现 $\binom n m = \binom {n-1}{m}+\binom{n-1}{m-1}$，所以我们将式子写开，就去掉了这个限制。

现在我们考虑如何维护如下式子的值：

$$ \begin{aligned} \sum_{i=0}^n \binom p i |i-d| = \sum_{i=0}^d \binom p i d-\sum_{i=0}^d \binom p i i+\sum_{i=d+1}^n \binom p i i - \sum_{i=d+1}^n \binom p i d \end{aligned} $$

发现 $\binom n m m= \binom {n-1}{m-1}n$，区间求和可以拆成前缀和询问，所以我们相当于要快速维护

$$ \sum_{i=0}^{lim} \binom p i $$

我们发现 $lim$ 和 $i$ 的变化都是 $O(1)$ 的，所以我们只需要考虑 $lim,p$ 加减 $1$ 的变化即可。

$lim$ 加一直接加上对应的项即可。

$\binom {p+1}{i} = \binom p i + \binom p {i-1}$，所以 $p$ 加一只需要额外维护一下 $0\ldots lim-1$ 的求和即可。

注意特判 $p=1$ 的边界。代码咕了。

CF1450 题解

A

B

C1

C2

D

E

F

G

H1

H2

4 comments

Leave a Comment Cancel reply

NOI2021 退役记

I'm back

SDOI2020 退役记

点双连通分量 & 圆方树学习笔记

CSP2019 游记

「初赛」无向连通图计数

「CF1097G」Vladislav and a Great Legend

「CF487E」Tourists

「NOI2019」序列

「BZOJ3118」Orz The Mst

CF1450 题解

A

B

C1

C2

D

E

F

G

H1

H2