1405C - Balanced Bitstring

你有一個長度為 $n n$ 的 $0101$ 串,其中每一個長度為 $k k$ 的子陣列中有相同的 $0101$ 個數.
但是這個 $0101$ 串被動了手腳,也就是有些位被弄成了?,你需要判斷它是否能還原成一個滿足上述性質的串.

首先,顯然 $s [i] = s [i ? k] = s [i + k] . . . s[i]=s[i-k]=s[i+k]...$
也就是模 $k k$ 的剩余系,都必須相同.
最后再判斷一下 $0101$ 個數是否超過 $k / 2 k/2$ 即可.

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;

int T,n,k,val[N];
char s[N];

int main() {
    cin>>T; while(T--) {
        scanf("%d %d",&n,&k);
        for(int i=0;i<k;i++) val[i]=0;
        scanf("%s",s);
        for(int i=0;i<n;i++) if(s[i]!='?') val[i%k]|=s[i]-'0'+1;
        bool flag=1; int c0=0,c1=0;
        for(int i=0;i<k;i++)
            if(val[i]==3) {flag=0; break;}
            else if(val[i]==1) c0++;
            else if(val[i]==2) c1++;
        if(!flag) {puts("NO"); continue;}
        if(c0>k/2||c1>k/2) puts("NO");
        else puts("YES");
    }
}

1405D - Tree Tag

$A l i c e Alice$ 和 $b r z brz$ 在樹上玩貓捉老鼠.
給定兩者的初始位置和最大移動距離,然后如果 $A l i c e Alice$ 和 $b r z brz$ 能出現在同一位置,那么 $A l i c e Alice$ 贏,否則 $b r z brz$ 贏. 兩個人都絕頂聰明, 現在你給他們當裁判.

首先,如果初始 $b r z brz$ 在 $A l i c e Alice$ 的"射程"范圍內,那么 $A l i c e Alice$ 必勝.
否則, $b r z brz$ 的最優策略就是在直徑上跑,只要 $d b > 2 d a & & d b > d i a m e t e r db>2da ~\& \&~ db>diameter$ , $b r z brz$ 就一定能贏.
其余情況,皆為 $A l i c e Alice$ 獲勝.

int n,u,v,A,B,dep[N],fa[N],f[N],c;
struct edge{int y,next; }a[N]; int len,last[N];
void ins(int x,int y) {a[++len]=(edge){y,last[x]}; last[x]=len;}
 
void dfs(int x) {
	f[x]=0;
	for(int k=last[x],y;k;k=a[k].next) 
		if((y=a[k].y)^fa[x]) {
			fa[y]=x;
			dep[y]=dep[x]+1;
			dfs(y);
			c=max(c,f[x]+f[y]+1);
			f[x]=max(f[x],f[y]+1);
		}
	c=max(c,f[x]);
}
 
int dis(int x,int y) {
	int ans=0;
	while(x^y) {
		if(dep[x]<dep[y]) swap(x,y);
		x=fa[x]; ans++;
	}
	return ans;
}
 
int main() {
	int _;qr(_); while(_--) {
		qr(n); qr(u); qr(v); qr(A); qr(B); c=0; len=0;
		for(int i=1;i<=n;i++) fa[i]=last[i]=0;
		for(int i=1,x,y;i<n;i++) qr(x),qr(y),ins(x,y),ins(y,x);
		dfs(1);
		if(dis(u,v)<=A) puts("Alice");
		else if(2*A<B&&2*A<c) puts("Bob");
		else puts("Alice"); 
	}
	return 0;
}

1405E - Fixed Point Removal

給定一個序列,如果 $a_{i} = i a_i=i$ 話即可洗掉 $i i$ ,后面的位置順位.
對于每個詢問,我們考慮只處理 $[l, r] [l,r]$ 至多能洗掉多少個位置.
( $n, q \leq 1 e 5 n,q\le 1e5$ )

首先,令 $a_{i} = i ? a_{i} a_i=i-a_i$ 表示前面需要洗掉的數的個數.
定義 $f (l, r) f(l,r)$ 表示 $[l, r] [l,r]$ 最多能洗掉多少個數.
那么可以得到轉移方程:
$f [l] [r] = {\begin{cases} f [l] [r ? 1] + 1 & (0 \leq a [r] \leq f [l] [r ? 1]) \\ f [l] [r ? 1] & (e l s e) \end{cases} f[l][r]=\begin{cases} f[l][r-1]+1&(0\le a[r]\le f[l][r-1]) \\ f[l][r-1]&(else) \end{cases}$
我們離線所有的詢問,然后考慮用樹狀陣列維護從每個位置 $l l$ 到當前位置 $r r$ 的 $f (l, r) f(l,r)$ .
容易發現 $f (l, r) f(l,r)$ 對于相同的 $r r$ 具有單調性,所以我們每次可以在樹狀陣列上倍增找到分界點.
然后對分界點前面的每個位置 $+ 1 +1$ .
詢問就是回傳 $f (l, r) f(l,r)$ 啦~.

#include<bits/stdc++.h>
#define fi first
#define se second
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define IT iterator 
#define vi vector<int>
#define TP template<class o>
#define SZ(a) ((int)a.size())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N=3e5+10,size=1<<20,mod=998244353,inf=2e9;

//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {
    char c=gc; x=0; int f=1;
    while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
    while(isdigit(c)) x=x*10+c-'0',c=gc;
    x*=f;
}
template<class o> void qw(o x) {
    if(x/10) qw(x/10);
    putchar(x%10+'0');
}
template<class o> void pr1(o x) {
    if(x<0)x=-x,putchar('-');
    qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
    if(x<0)x=-x,putchar('-');
    qw(x); putchar('\n');
}

int n,q,a[N],c[N],ans[N];
vector<pii> b[N];
//樹狀陣列維護以每個位置開頭的最多洗掉數量

void add(int x,int d) {for( ;x<=n;x+=x&-x) c[x]+=d; }
int ask(int x) {int y=0; for(;x;x-=x&-x) y+=c[x]; return y;}

int main() {
    qr(n); qr(q);
    for(int i=1;i<=n;i++) qr(a[i]);
    for(int i=1,l,r;i<=q;i++) qr(l),qr(r),b[n-r].pb(mk(l+1,i));
    for(int i=1;i<=n;i++) {
        a[i]=i-a[i];
        if(a[i]>=0) {
            int x=0;
            for(int s=0,j=21;j>=0;j--)
                if(x+(1<<j)<=i&&s+c[x+(1<<j)]>=a[i]) 
                    {x+=1<<j; s+=c[x];}
            add(1,1); add(x+1,-1);
        }
        for(auto p:b[i]) ans[p.se]=ask(p.fi);
    }
    for(int i=1;i<=q;i++) pr2(ans[i]);
    return 0;
}

1404D - Game of Pairs

$A l i c e Alice$ and $b r z brz$ 在玩游戲. 在給定 $n n$ 的情況下,
$A l i c e Alice$ 先把 $[1, 2 n] [1,2n]$ 丟到 $n n$ 個 $p a i r pair$ 內,然后 $b r z brz$ 從每個 $p a i r pair$ 中選擇一個數,
如果這些數之和可以被 $2 n 2n$ 整除,那么 $b r z brz$ 贏.否則 $A l i c e Alice$ 贏.
這是一道互動題,你可以選擇做 $b r z brz$ 還是 $A l i c e Alice$ ,但是要保證自己必勝.

容易想到這樣一個構造 $(1, n + 1), (2, n + 2), (3, n + 3) . . . . . (1,n+1),(2,n+2),(3,n+3).....$ ,這樣的話每個對在 $m o d ?? n \mod n$ 意義下一樣.
$s u m \equiv n (n ? 1) / 2 \equiv \frac{n}{2} ? (n ? 1) (m o d ?? n) sum\equiv n(n-1)/2\equiv \dfrac n 2\cdot (n-1)(\mod n)$
所以 $n ∣? s u m \to 2 n ∣? s u m n\not|sum\rightarrow 2n\not|sum$ .
這種情況的條件是 $2 ∣ n 2|n$ ,此時我們當 $A l i c e Alice$ 必勝.

否則,我們令同 $p a i r pair$ 的數連邊,同時連 $(i, i + n) (? i \in [1, n]) (i,i+n)(\forall i\in [1,n])$ .
此時我們可以連出這樣的一張圖(這是一個 $n = 5 n=5$ 的情況),圖由若干個長度為偶數的環組成.
在這里插入圖片描述

我們給每個環黑白染色,那么顯然我們只能取一種顏色.
$n ∣ n (n ? 1) / 2 n|n(n-1)/2$ ,也就是我們取一種顏色一定能搞出 $n n$ 的倍數,所以選出來 $s u m \equiv 0 (m o d ?? 2 n) o r s u m \equiv n (m o d ?? 2 n) sum\equiv 0(\mod 2n) ~or ~ sum\equiv n(\mod 2n)$
此時 $n ∣ (1 + 2 + . . . 2 n) n|(1+2+...2n)$ ,所以如果 $s u m \equiv n (m o d ?? 2 n) sum\equiv n(\mod 2n)$ ,我們取相反顏色即可.

int n,col[N],pos[N];
vi p[N];
ll s[5];

void dfs(int x,int c) {
    if(col[x]>=0) return ;
    col[x]=c; s[c]+=x; c^=1;
    if(x<=n) dfs(x+n,c);
    else dfs(x-n,c);
    dfs(p[pos[x]][0],c);
    dfs(p[pos[x]][1],c);
}

int main() {
    qr(n);
    if(n%2==0) {
        puts("First");
        for(int i=0;i<2*n;i++) pr1(i%n+1);
        return 0;
    }
    puts("Second"); fflush(stdout);
    for(int i=1,x;i<=n*2;i++) qr(x),pos[i]=x,p[x].pb(i),col[i]=-1;
    for(int i=1;i<=n*2;i++) dfs(i,0);
    int t=(s[0]%(2*n))?1:0;
    for(int i=1;i<=n*2;i++) if(col[i]==t) pr1(i);
    return 0;
}

1404E - Bricks

$b r z brz$ 要求裝修工 $l z y lzy$ 鋪一個 $n ? m n*m$ 的地板,有些格子是黑色,有些格子是白色.
$l z y lzy$ 只有寬為1的磚(只能橫豎放置).
$b r z brz$ 有一個嚴苛的要求: 只能用磚覆寫黑色格子,且每個格子只能被一個磚覆寫.同時最小化用的磚數.

我們一開始把所有的黑格都用 $1 ? 1 1*1$ 的覆寫,然后我們考慮把一些分割(分割表示兩個 $1 ? 1 1*1$ 的格子的公共邊)去掉,使得一些區域形成一個連通塊.
可以發現一個不合法的區域形如L形. 也就是有些分割不能同時被去掉.
左右的分割和上下的分割內部不連邊,也就是個二分圖.
所以我們只要求出二分圖的最大獨立集即可.

#include<bits/stdc++.h>
#define fi first
#define se second
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define IT iterator 
#define vi vector<int>
#define TP template<class o>
#define SZ(a) ((int)a.size())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N=8e4+10,M=210,size=1<<20,mod=998244353,inf=2e9;

//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {
    char c=gc; x=0; int f=1;
    while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
    while(isdigit(c)) x=x*10+c-'0',c=gc;
    x*=f;
}
template<class o> void qw(o x) {
    if(x/10) qw(x/10);
    putchar(x%10+'0');
}
template<class o> void pr1(o x) {
    if(x<0)x=-x,putchar('-');
    qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
    if(x<0)x=-x,putchar('-');
    qw(x); putchar('\n');
}

int n,m,U[M][M],L[M][M],tot,st,ed;
char s[M][M];
struct edge{int y,next,c; } a[N*6]; int len=1,last[N],cur[N];
void ins(int x,int y,int c) {a[++len]=(edge){y,last[x],c}; last[x]=len; }
void add(int x,int y,int c) {ins(x,y,c); ins(y,x,0);}

int d[N],q[N];
bool bfs() {
    for(int i=1;i<=ed;i++) d[i]=0,cur[i]=last[i];
    int l,r; q[l=r=1]=st; d[st]=1;
    for(int x=st;l<=r;x=q[++l])
        for(int k=last[x],y;k;k=a[k].next)
            if(!d[y=a[k].y]&&a[k].c) d[y]=d[x]+1,q[++r]=y;
    return d[ed];
}

int dfs(int x,int f) {
    if(x==ed) return f;
    int s=0,t;
    for(int &k=cur[x],y,z;k;k=a[k].next) {
        y=a[k].y; z=min(a[k].c,f-s);
        if(d[y] == d[x] + 1 && z) {
            s += t = dfs(y,z);
            a[k].c -= t;
            a[k^1].c += t;
            if(s == f) return f;
        }
    }
    if(!s) d[x]=0;
    return s;
}

int dicnic() {
    int ans=0;
    while(bfs()) ans += dfs(st,inf);
    return ans;
}

int main() {
    qr(n); qr(m); int ans=0;
    for(int i=1;i<=n;i++) {
        scanf("%s",s[i]+1);
        for(int j=1;j<=m;j++)
            if(s[i][j]=='#') {
                ans++; 
                if(s[i-1][j]=='#') U[i][j]=++tot,ans--;
                if(s[i][j-1]=='#') L[i][j]=++tot,ans--;
            }
    }
    st = ++tot; ed = ++tot;
    const int dx[]={1,1,0,0},dy[]={0,-1,0,-1};
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) {
            int x=L[i][j];
            if(U[i][j]) add(U[i][j],ed,1);
            if(!x) continue;
            add(st,x,1); 
            for(int t=0;t<4;t++) {
                int tx=i+dx[t],ty=j+dy[t];
                if(U[tx][ty]) add(x,U[tx][ty],1);
            }
        }
    pr2(ans+dicnic()); return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/1487.html

標籤：區塊鏈

上一篇：棋盤問題（dfs，遞回）

下一篇：Codeforces Round #668 (Div. 2)D. Tree Tag(樹形DP樹的直徑 + 博弈論)

Codeforces Round #668 (Div. 1) Solution

1405C - Balanced Bitstring

1405D - Tree Tag

1405E - Fixed Point Removal

1404D - Game of Pairs

1404E - Bricks