投稿
  1. 云图网首页
  2. 技术专区
  3. 编程笔记

2022“杭电杯”中国大学生算法设计超级联赛（1）

• 编程笔记 • 阅读 45


链接

/(String/)

我必须立刻对串串使用 /(kmp/) ，并让 /(nxt_i/) 向 /(i/) 连边，于是可得一个森林。对于任意点 /(x/) ，若 /(y/) 是 /(x/) 的祖先或自身，则有 /(S_{1,y} = S_{x-y+1,x}/) ，满足条件 /(1,2/) 。考虑条件 /(3/) ，需满足 /(2y>x/) 且 /(2y/) 与 /(x/) 模 /(k/) 同余，前者可以根据单调性用队列维护，后者用桶记录。此外该题栈太小，不能递归。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=2e6+3,p=998244353;
struct hh{
    int to,nxt;
}e[N<<1];
struct kk{
    int op,id,l,r;
}sta[N];
int n,k,num,fir[N],nxt[N],buk[N],len[N],f[N],tp,ans;
char s[N];
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL int mod(int x){return x>=p?x-p:x;}
IL void add(int x,int y){
    e[++num]=(hh){y,fir[x]},fir[x]=num;
}
void init()
{
    memset(nxt,0,sizeof(nxt));
    int j=0;
    for(int i=1;i<n;++i){
        while(j>0&&s[i+1]!=s[j+1]) j=nxt[j];
        if(s[i+1]==s[j+1]) ++j;
        nxt[i+1]=j;
    }
}
void dfs(){
    sta[++tp]=(kk){1,0,1,0};
    int l=1,r=0;
    while(tp){
        kk u=sta[tp--];
        if(u.op==1){
            sta[++tp]=(kk){-1,u.id,l,r};
            if(u.id){
                while(l<=r&&2*len[l]<=u.id) buk[2*len[l]%k]--,++l;
                len[++r]=u.id,buk[2*u.id%k]++,f[u.id]=buk[u.id%k];
            }
            for(int i=fir[u.id],v;v=e[i].to;i=e[i].nxt)
              sta[++tp]=(kk){1,v,l,r};
        }
        else{
            if(u.id){
                for(int i=u.l;i<l;++i) ++buk[2*len[i]%k];
                --buk[2*u.id%k],l=u.l,r=u.r;
            }
        }
    }
}
void solve(){
    memset(fir,0,sizeof(fir)),num=0;
    scanf("%s",s+1);
    n=strlen(s+1);
    init(),k=in();
    for(int i=1;i<=n;++i) add(nxt[i],i);
    dfs();
    ans=1;
    for(int i=1;i<=n;++i) ans=1ll*(f[i]+1)*ans%p;
    printf("%d/n",ans);
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

/(Dragon slayer/)

枚举墙的状态并 /(bfs/) 判断可行性。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=18;
struct hh{
    int x,y;
}s,t;
struct kk{
    int x1,y1,x2,y2;
}q[N];
int n,m,k,num,w[N][N][4],bo[N][N],ans=1e9;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
queue<hh>Q;
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL void add(int x1,int y1,int x2,int y2,int op){
    if(x1==x2){
        if(y1>y2) swap(y1,y2);
        for(int j=y1+1;j<=y2;++j)
            w[x1][j][2]+=op,w[x1+1][j][3]+=op;
    }
    else{
        if(x1>x2) swap(x1,x2);
        for(int j=x1+1;j<=x2;++j)
            w[j][y1][0]+=op,w[j][y1+1][1]+=op;
    }
}
int bfs(){
    memset(bo,0,sizeof(bo));
    while(Q.size()) Q.pop();
    Q.push(s),bo[s.x][s.y]=1;
    while(Q.size()){
        hh u=Q.front();Q.pop();
        if(u.x==t.x&&u.y==t.y){return 1;}
        for(int i=0;i<4;++i)
        if(!w[u.x][u.y][i]){
            int xn=u.x+dx[i],yn=u.y+dy[i];
            if(!xn||xn>n||!yn||yn>m) continue;
            if(bo[xn][yn]) continue;
            bo[xn][yn]=1;
            Q.push((hh){xn,yn});
        }
    }
    return 0;
}
void solve(){
    n=in(),m=in(),k=in();
    s=(hh){in()+1,in()+1},t=(hh){in()+1,in()+1};
    ans=1e9;
    for(int i=1;i<=k;++i) q[i]=(kk){in(),in(),in(),in()};
    for(int i=0;i<(1<<k);++i){
        int cnt=0;
        for(int j=0;j<k;++j)
          if((i>>j)&1) ++cnt,add(q[j+1].x1,q[j+1].y1,q[j+1].x2,q[j+1].y2,1);
        if(bfs()) ans=min(ans,k-cnt);
        for(int j=0;j<k;++j)
          if((i>>j)&1) add(q[j+1].x1,q[j+1].y1,q[j+1].x2,q[j+1].y2,-1);
    }
    printf("%d/n",ans);
}
int main()
{
    int t=in();
    while(t--) solve();
    return 0;
}

/(Backpack/)

令 /(f_{i,j,k}/) 为枚举到第 /(i/) 个物品，是否存在价值异或和为 /(j/)，体积和为 /(k/) 的情况。/(f_{i,j,k} = f_{i-1,j,k} | f_{i-1,j /oplus{v_i},k-w_i}/) ，实际用 /(bitset/) 降低时间复杂度。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=(1<<10);
int n,m,w[N],v[N];
bitset<N>f[2][N];
IL int in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    int x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
int main()
{
    int T=in();
    while(T--){
        n=in(),m=in();
        f[0][0][0]=1;
        for(int i=1,op=1;i<=n;++i,op^=1){
            v[i]=in(),w[i]=in();
            for(int j=0;j<N;++j)
              f[op][j^w[i]]=f[op^1][j^w[i]]|(f[op^1][j]<<v[i]);
        }
        int pos=-1;
        for(int i=0;i<N;++i)
          if(f[n&1][i][m]) pos=i;
        printf("%d/n",pos);
        for(int i=0;i<N;++i) f[0][i].reset(),f[1][i].reset();
    }
      return 0;
}

/(Ball/)

枚举两两之间的距离，若为质数，则统计距离一个点小于该距离，距离另一个点大于该距离的点的数量（或情况相反），用 /(bitset/) 维护。从小到大枚举边，便于维护 /(bitset/) 与去重。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=4e6+3,M=2e3+3;
struct hh{
    int x,y;
    bool operator<(const hh &a) const{
    return y<a.y;}
}a[N];
struct kk{
    int x,y,dis;
    bool operator<(const kk &a) const{
    return dis<a.dis;}
}b[N];
int n,m,num,vis[N],pri[N],pos[M][2];
LL ans;
bitset<M>bit[M][2],b1,b2,b3;
IL LL in(){
    char c;LL f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
void init(){
    for(int i=2;i<N;++i){
        if(!vis[i]) vis[i]=i,pri[++num]=i;
        for(int j=1;j<=num&&pri[j]<=vis[i]&&i*pri[j]<N;++j)
          vis[i*pri[j]]=pri[j];
    }
}
IL int get_dis(hh &a,hh &b){
    return abs(a.x-b.x)+abs(a.y-b.y);
}
IL void gx(kk u){
    bit[u.x][0][u.y]=1,bit[u.y][0][u.x]=1;
    bit[u.x][1][u.y]=0,bit[u.y][1][u.x]=0;
}
void solve(){
    n=in(),m=in(),num=ans=0;
    for(int i=1;i<=n;++i) a[i]=(hh){in(),in()},bit[i][1].reset(),bit[i][0].reset();
    for(int i=1;i<=n;++i)
      for(int j=1;j<i;++j)
        b[++num]=(kk){i,j,get_dis(a[i],a[j])};
    sort(b+1,b+num+1);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
          if(i^j) bit[i][1][j]=1;
    }
    for(int i=1;i<=num;++i){
        gx(b[i]);
        if(vis[b[i].dis]==b[i].dis){
          int x=b[i].x,y=b[i].y;
          ans+=(bit[x][0]&bit[y][1]).count()+(bit[y][0]&bit[x][1]).count();
      }
    }
    printf("%lld/n",ans);
}
int main()
{
    init();
    int t=in();
    while(t--) solve();
    return 0;
}

/(Grammar/)

直接按顺序遍历，若遇到环（字符无限的情况），求出该环的字符长度，对 /(y/) 取模后继续走；若无环，要记忆化搜索，求出 /(non-terminal symbol/) 的实际长度，否则会T。

此外，萌新第一次知道 /(s.size()/) 返回 /(ull/)，若 /(-1/) 与 /(s.size()/) 比较则 /(-1/) 转化成 /(ull/) ，得到 /(-1 > s.size()/) 。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=1e3+3;
const LL inf=1e18+10;
int n,m,len[N],to[N],flag,bo[N];
string s[N];
LL y,L[N],suml[N];
struct hh{
    int to,w;
};
vector<hh>e[N];
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL int turn(int k,int l,int r){
    int x=s[k][l]-'0';
    for(int i=l+1;i<=r;++i) x=x*10+s[k][i]-'0';
    return x;
}
void dfs(int u,int op){
    if(!u) return;
    LL le=0;
    if(op){
        for(int i=0;i<e[u].size();++i){
            hh v=e[u][i];
            if(y<=v.w){
                printf("%c/n",s[to[u]][le+y-1]);
                flag=1;return;
            }
            else{
                y-=v.w,le+=v.w;
                dfs(v.to,op);
                if(flag) return;
            }
        }
    }
    else{
        bo[u]=1;L[u]=y;
        for(int i=0;i<e[u].size();++i){
            hh v=e[u][i];
            if(y<=v.w){
                printf("%c/n",s[to[u]][le+y-1]);
                flag=1;return;
            }
            le+=v.w,y-=v.w;
            if(bo[v.to]){
                LL xh=L[v.to]-y;
                y%=xh;
                if(y==0){
                    printf("%c/n",s[to[u]][le+y-1]);
                    flag=1;return;
                }
                dfs(v.to,1);
                if(flag) return;
            }
            else{
                if(!suml[v.to]||suml[v.to]>=y) dfs(v.to,0);
                else y-=suml[v.to];
            }
            if(flag) return;
        }
        bo[u]=0,suml[u]=L[u]-y;
    }
}
void solve(){
    n=in(),m=in();
    for(int i=1;i<=n;++i) s[i].clear(),e[i].clear();
    for(int i=1;i<=n;++i){
        cin>>s[i];
        len[i]=s[i].size();
        int pos=0;
        for(;pos<=len[i];++pos)
          if(s[i][pos]=='-') break;
        int id=turn(i,1,pos-2);
        to[id]=i;
        s[i].erase(0,pos+2);
        int las=-1;
        for(int j=0;j<s[i].size();++j){
            if(s[i][j]=='['){
                int st=j;
                while(s[i][j]^']') ++j;
                int v=turn(i,st+1,j-1);
                e[id].push_back((hh){v,st-1-las});
                las=st-1,s[i].erase(st,j-st+1),j=st-1;
            }
        }
        int ll=s[i].size();
        if(las<ll-1) e[id].push_back((hh){0,ll-1-las});
    }
    while(m--){
        flag=0;
        LL x=in();y=in();
        memset(bo,0,sizeof(bo)),
        memset(L,0,sizeof(L)),
        memset(suml,0,sizeof(suml));
        dfs(x,0);
        if(!flag) printf("-1/n");
    }
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

/(Treasure/)

惨遭卡常。。。明明本机才运行 /(1.5s/) 啊喂！

十分明显要用 /(kruskal/) 重构树，对宝藏分类讨论，构建虚树，直接 /(DP/)，用树上差分统计对答案的贡献。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define max(x,y) (x>y?x:y)
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int N=2e5+3;
struct kk{
	int x,y,w;
	bool operator<(const kk &a) const{
	return w<a.w;}
}l[N];
struct hh{
	int to,nxt,w;
}e[N<<1];
struct zz{
	int c;LL val;
}a[N];
int n,m,q,nn,cnt,num,dep[N],fir[N],fa[N][19];
int len[N][19],dfn[N],siz[N],f[N];
int sta[N],tp,S[N];
vector<int>col[N],ee[N];
vector<kk>E[N];

void print(long long x) {
    if(x>9) print(x/10);
    *O++=x%10+'0';
}

struct BIT{
	LL c[N];
	IL int lb(int x){return x&-x;}
	IL void add(int x,LL y){
		for(;x<=nn;x+=lb(x)) c[x]+=y;
	}
	IL LL ask(int y){
		LL res=0;
		for(;y;y-=lb(y)) res+=c[y];
		return res;
	}
	IL void clear(){memset(c+1,0,8*(2*n-1));}
}T;

IL void clear(){
	num=cnt=0,memset(fir+1,0,4*(2*n-1));
	for(int i=1;i<=2*n-1;++i) a[i]=(zz){0,0};
	for(int i=1;i<=n;++i) col[i].clear(),E[i].clear();
	memset(fa,0,sizeof(fa));
	T.clear();
}

IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}

bool cmp1(int x,int y){return dfn[x]<dfn[y];}

IL int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

IL void add(int x,int y,int w){
	e[++num]=(hh){y,fir[x],w},fir[x]=num;
}

IL void Add(int c,int x,int y,int op){
	ee[x].push_back(y);
	if(op) E[c].push_back((kk){x,y,0});
}

IL void kruskal(){
	sort(l+1,l+m+1);
	for(int i=1;i<=2*n-1;++i) f[i]=i;
	for(int i=1;i<=m;++i){
		int x=l[i].x,y=l[i].y;
		int fx=find(x),fy=find(y);
		if(fx==fy) continue;
		f[fx]=f[fy]=++nn;
		add(nn,fx,l[i].w),add(nn,fy,l[i].w);
	}
}

void dfs1(int u,int f){
	fa[u][0]=f,siz[u]=1,dfn[u]=++cnt,dep[u]=dep[f]+1;
	for(int i=0;fa[u][i];++i)
	  fa[u][i+1]=fa[fa[u][i]][i],
	  len[u][i+1]=max(len[u][i],len[fa[u][i]][i]);
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
	  len[v][0]=e[i].w,dfs1(v,u),siz[u]+=siz[v];
}

IL int Lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=17;~i;--i)
	  if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	if(x==y) return x;
	for(int i=17;~i;--i)
	  if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}

IL void ins(int c,int x){
	if(!tp){sta[++tp]=x;return;}
	int lca=Lca(sta[tp],x);
	if(lca==sta[tp]){sta[++tp]=x;return;}
	while(dep[lca]<dep[sta[tp-1]]) Add(c,sta[tp-1],sta[tp],1),--tp;
	Add(c,lca,sta[tp],1),--tp;
	if(lca!=sta[tp]) sta[++tp]=lca;
	sta[++tp]=x;
}

void dfs2(int u,int op){
	for(int i=0;i<ee[u].size();++i)
	  dfs2(ee[u][i],op),a[u].val=max(a[u].val,a[ee[u][i]].val),T.add(dfn[u],-op*a[ee[u][i]].val);
	T.add(dfn[u],op*a[u].val);
}

void dele(int u){
	for(int i=0;i<ee[u].size();++i) dele(ee[u][i]);
	if(u>n) a[u].val=0;
	ee[u].clear();
}

IL int Find(int x,int L){
	for(int i=17;~i;--i)
	  if(fa[x][i]&&len[x][i]<=L) x=fa[x][i];
	return x;
}
void solve(){
	n=nn=in(),m=in(),q=in();clear();
	for(int i=1;i<=n;++i) col[a[i].c=in()].push_back(i);
	for(int i=1;i<=n;++i) a[i].val=in();
	for(int i=1;i<=m;++i) l[i]=(kk){in(),in(),in()};
	kruskal(),len[nn][0]=0,dfs1(nn,0);
	for(int i=1;i<=n;++i)
	  if(col[i].size()){
	  	sort(col[i].begin(),col[i].end(),cmp1);
	  	for(int j=0;j<col[i].size();++j) ins(i,col[i][j]);
	  	while(tp>1) Add(i,sta[tp-1],sta[tp],1),--tp;tp=0;
	  	int st=sta[1];S[i]=st;
	  	dfs2(st,1),dele(st);
	  }
	int op,x,y;
	while(q--){
		op=in(),x=in(),y=in();
		if(!op){
			int c=a[x].c;
		  	for(int i=0;i<E[c].size();++i) Add(c,E[c][i].x,E[c][i].y,0);
		  	dfs2(S[c],-1),a[x].val+=y;
		  	dfs2(S[c],1),dele(S[c]);
		}
		else{
			int F=Find(x,y);
			LL ans=T.ask(dfn[F]+siz[F]-1)-T.ask(dfn[F]-1);
			print(ans),*O++='/n';
		}
	}
}
int main()
{
    int T=in();
    while(T--) solve();
    fwrite(obuf,O-obuf,1,stdout);
    return 0;
}

/(Path/)

拆点，直接 /(dij/)，同时用链表维护一个还没有被跳过的点的集合。当经过一条特殊边时，遍历集合，能白嫖的直接白嫖并删去点，因为后续的情况的离起始点距离肯定比现在长，都是白嫖，肯定先白嫖更好（

不能白嫖的就老老实实 /(dij/)，集合中不是直接相连的点直接删去，而重复遍历的相连的点的数量级是O(m)的，故不会 /(T/) 。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=1e6+3;
const LL inf=1e18+10;
struct hh{
    int to,nxt,w,op;
}e[N<<1];
struct kk{
    int id,op;LL dis;
    bool operator<(const kk &a) const{
    return dis>a.dis;}
};
struct lian{
    int pre[N],nxt[N];
    IL void init(int n){
        for(int i=0;i<=n;++i) nxt[i]=i+1;
        for(int i=1;i<=n+1;++i) pre[i]=i-1;
    }
    IL void dele(int x){
        pre[nxt[x]]=pre[x],
        nxt[pre[x]]=nxt[x];
    }
}st;
int n,m,S,K,num,fir[N],bo[N][2],b[N];
LL dis[N][2];
priority_queue<kk>q;
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL void add(int x,int y,int w,int t){
    e[++num]=(hh){y,fir[x],w,t},fir[x]=num;
}
void dij(){
    dis[S][0]=0;
    q.push((kk){S,0,0});
    while(q.size()){
        kk u=q.top();q.pop();
        if(bo[u.id][u.op]) continue;
        bo[u.id][u.op]=1;
        if(u.op){
            for(int i=fir[u.id],v;v=e[i].to;i=e[i].nxt){
                b[v]=1;
                if(dis[v][e[i].op]>dis[u.id][u.op]+e[i].w-K){
                  dis[v][e[i].op]=dis[u.id][u.op]+e[i].w-K;
                  q.push((kk){v,e[i].op,dis[v][e[i].op]});
              }
            }
            int pos=st.nxt[0];
            while(pos!=n+1){
                if(!b[pos]){
                    int v=pos;
                    if(dis[v][0]>dis[u.id][u.op]){
                        dis[v][0]=dis[u.id][u.op];
                        q.push((kk){v,0,dis[v][0]});
                    }
                    st.dele(pos),pos=st.nxt[pos];
                }
                else pos=st.nxt[pos];            
            }
            for(int i=fir[u.id],v;v=e[i].to;i=e[i].nxt) b[v]=0;
        }
        else{
            for(int i=fir[u.id],v;v=e[i].to;i=e[i].nxt){
                if(dis[v][e[i].op]>dis[u.id][u.op]+e[i].w){
                  dis[v][e[i].op]=dis[u.id][u.op]+e[i].w;
                  q.push((kk){v,e[i].op,dis[v][e[i].op]});
              }
            }
        }
    }
}
void solve(){
    int x,y,w,t;
    n=in(),m=in(),S=in(),K=in();
    st.init(n);st.dele(S);
    memset(fir,0,4*n+4),num=0;
    for(int i=1;i<=n;++i) dis[i][0]=dis[i][1]=inf,bo[i][0]=bo[i][1]=0;
    for(int i=1;i<=m;++i){
        x=in(),y=in(),w=in(),t=in();
        add(x,y,w,t);
    }
    dij();
    for(int i=1;i<=n;++i){
        LL Min=min(dis[i][0],dis[i][1]);
        if(Min==inf) printf("-1 ");
        else printf("%lld ",Min);
    }
    printf("/n");
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

/(Laser/)

对一个点只可能在四种直线上，对其他不在该直线的点可能在三种直线上，分类讨论，两个点即可得出目标位置，再判断是否合法即可。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const LL N=5e5+3;
LL n;
struct hh{
    LL x,y;
}a[N];
IL LL in(){
    char c;LL f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL LL chk(hh p){
    for(LL i=1;i<=n;++i){
        LL x=p.x-a[i].x,y=p.y-a[i].y;
        if(x&&y&&(x-y)&&(x+y)) return 0;
    }
    return 1;
}
void solve(){
    n=in();
    for(LL i=1;i<=n;++i) a[i]=(hh){in()*2,in()*2};
    LL pos=2;
    for(;pos<=n;++pos)
      if(a[pos].x^a[1].x) break;
    if(pos==n+1) return (void)(puts("YES"));
    if(chk((hh){a[1].x,a[pos].y})) return (void)(puts("YES"));
    if(chk((hh){a[1].x,a[pos].y-(a[pos].x-a[1].x)})) return (void)(puts("YES"));
    if(chk((hh){a[1].x,a[pos].y+(a[pos].x-a[1].x)})) return (void)(puts("YES"));
    pos=2;
    for(;pos<=n;++pos)
      if(a[pos].x-a[1].x^a[pos].y-a[1].y) break;
    if(pos==n+1) return (void)(puts("YES"));
    if(chk((hh){a[1].x-a[1].y+a[pos].y,a[pos].y})) return (void)(puts("YES"));
    if(chk((hh){a[pos].x,a[pos].x+a[1].y-a[1].x})) return (void)(puts("YES"));
    if(chk((hh){(a[pos].x+a[pos].y-a[1].y+a[1].x)>>1,(a[pos].x+a[pos].y+a[1].y-a[1].x)>>1})) return (void)(puts("YES"));
    pos=2;
    for(;pos<=n;++pos)
      if(a[pos].y^a[1].y) break;
    if(pos==n+1) return (void)(puts("YES"));
    if(chk((hh){a[pos].x,a[1].y})) return (void)(puts("YES"));
    if(chk((hh){a[pos].x-(a[pos].y-a[1].y),a[1].y})) return (void)(puts("YES"));
    if(chk((hh){a[pos].x+(a[pos].y-a[1].y),a[1].y})) return (void)(puts("YES"));
    pos=2;
    for(;pos<=n;++pos)
      if(a[pos].x+a[pos].y^a[1].x+a[1].y) break;
    if(pos==n+1) return (void)(puts("YES"));
    if(chk((hh){a[pos].x,a[1].x+a[1].y-a[pos].x})) return (void)(puts("YES"));
    if(chk((hh){a[1].x+a[1].y-a[pos].y,a[pos].y})) return (void)(puts("YES"));
    if(chk((hh){(a[1].y+a[1].x-a[pos].y+a[pos].x)>>1,(a[1].x+a[1].y+a[pos].y-a[pos].x)>>1})) return (void)(puts("YES"));
    puts("NO");
}
int main()
{
    LL T=in();
    while(T--) solve();
      return 0;
}

/(Random/)

我都已经随机了，你再随机就改变不了什么了（确信

显然剩下数字的期望值是 /(1/2/)。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=1e5+3,p=1e9+7;
int n,m,k;
IL int in(){
  char c;int f=1;
  while((c=getchar())<'0'||c>'9')
    if(c=='-') f=-1;
  int x=c-'0';
  while((c=getchar())>='0'&&c<='9')
    x=x*10+c-'0';
  return x*f;
}
IL int ksm(int a,int b){
    int c=1;
    while(b){
        if(b&1) c=1ll*c*a%p;
        a=1ll*a*a%p,b>>=1;
    }
    return c;
}
int main()
{
    int T=in(),inv=ksm(2,p-2);
    while(T--){
        n=in(),m=in();
        n-=m;
        printf("%lld/n",1ll*inv*n%p);
    }
  return 0;
}

/(Alice and Bob/)

我们可以把某个数值的数平均分开，于是两个 /(x/) 就可以等价为 /(x-1/)，判断是否可以等价出 /(0/) 即可。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=1e6+3;
int n,a[N];
IL int in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    int x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
int main()
{
    int T=in();
    while(T--){
        n=in();
        for(int i=0;i<=n;++i) a[i]=in();
        for(int i=n;i;--i) a[i-1]+=a[i]>>1;
        if(a[0]) puts("Alice");else puts("Bob");
    }
      return 0;
}

原创文章，作者：kirin，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/275683.html

赞 (0)
0 0
上一篇 2022年7月20日 20:53
下一篇 2022年7月20日 21:03

相关推荐

发表回复

登录后才能评论