牛客IOI周赛24提高
A
大模拟,没什么好说的
为了简化操作,运用c++STL
对于牌堆,明显可以用队列模拟
对于玩家的牌,用vector储存,出牌可直接调用库函数
对牌单独定义结构体吗,方便操作
对于名字,不要打一堆if
尽量所有函数式编程,尽量复用代码,缩短代码长度,减少调试难度
以下给出2个代码
std
#include<bits/stdc++.h> using namespace std; struct card{ string col; string pattern; card(){}; card(string a,string b): col(a),pattern(b){}; }consult; int n,Round,direction=1; string name[5]={"xiran","sanqiu","shixin"}; queue<card> pai; vector<card> v[5]; void get_card(int x,int ad) { while(ad--){ if(pai.size()==0){ puts("There are no cards to take");//无牌可拿 for(int i=0;i<3;i++){ for(int j=0;j<v[i].size();j++) cout<<v[i][j].col<<" "<<v[i][j].pattern<<" "; puts(""); } exit(0); } v[x].push_back(pai.front()); pai.pop(); } } void next(int x){Round=((Round+x*direction)%3+3)%3;} void discard(int i) { card k= v[Round][i]; consult=k;//参考牌替换 pai.push(k);//加入牌堆 v[Round].erase(v[Round].begin()+i,v[Round].begin()+i+1);//删除此玩家的手牌 if(k.pattern=="Skip"){next(2);} else if(k.pattern=="Reverse"){direction=-direction;next(1);} else if(k.pattern=="Draw_Two"){next(1);get_card(Round,2);next(1);} else{next(1);} } void work() { for(int i=0;i<v[Round].size();i++) if(v[Round][i].col==consult.col||v[Round][i].pattern==consult.pattern){ discard(i); return; } //无牌可出 while(1){ get_card(Round,1);// 获得一张牌 int k=v[Round].size()-1; if(v[Round][k].col==consult.col||v[Round][k].pattern==consult.pattern){ discard(k); return; } } } int main() { consult=card("g","1");//规定初始参考牌为 绿色的1 cin>>n; for(int i=1;i<=n;i++){ string a,b; cin>>a>>b; pai.push( card(a,b) );//加入牌堆 } for(int i=0;i<3;i++) get_card(i,7);//每人获得7张的初始牌 while(v[0].size()&&v[1].size()&&v[2].size()){ work(); } for(int i=0;i<3;i++) if(!v[i].size()) cout<<name[i]<<"\n"; for(int i=0;i<3;i++){ for(int j=0;j<v[i].size();j++) cout<<v[i][j].col<<" "<<v[i][j].pattern<<" "; puts(""); } return 0; }
审题人代码
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct node{ char col; string act; }card[4][10005]; node allofcard[10005]; bool aim[4][10005]; int nowcard[4]; int leacard[4]; void print() { for(int j=1;j<=nowcard[1];j++) { if(aim[1][j]==0) cout<<card[1][j].col<<" "<<card[1][j].act<<" "; } cout<<endl; for(int j=1;j<=nowcard[2];j++) { if(aim[2][j]==0) cout<<card[2][j].col<<" "<<card[2][j].act<<" "; } cout<<endl; for(int j=1;j<=nowcard[3];j++) { if(aim[3][j]==0) cout<<card[3][j].col<<" "<<card[3][j].act<<" "; } } int main() { int n; scanf("%d",&n); int cnt=0; int now=1; for(int i=1;i<=n;i++) { if(now==4) { cin>>allofcard[++cnt].col; getchar(); cin>>allofcard[cnt].act; } else { cin>>card[now][++cnt].col; getchar(); cin>>card[now][cnt].act; nowcard[now]++; if(cnt==7) now++,cnt=0; } } if(now<=3) { printf("There are no cards to take\n"); print(); return 0; } for(int i=1;i<=3;i++) leacard[i]=nowcard[i]; int order=1; char stacol='g'; string stact="1"; int peo=1; int pointo=1; // cout<<"——————————————————————————————"<<endl; while(1) { bool flag=false; for(int i=1;i<=nowcard[peo];i++) { if(!aim[peo][i]&&(card[peo][i].col==stacol||card[peo][i].act==stact)) { aim[peo][i]=1; leacard[peo]--; flag=true; stacol=card[peo][i].col; stact=card[peo][i].act; // cout<<stacol<<" "<<stact<<endl; allofcard[++cnt].col=stacol; allofcard[cnt].act=stact; if(leacard[peo]==0) { if(stact=="Draw_Two") { int now1=peo; now1+=order; if(now1>3) now1=1; if(now1<1) now1=3; if(pointo>cnt) { printf("There are no cards to take\n"); print(); return 0; } card[now1][++nowcard[now1]]=allofcard[pointo++]; leacard[now1]++; if(pointo>cnt) { printf("There are no cards to take\n"); print(); return 0; } leacard[now1]++; card[now1][++nowcard[now1]]=allofcard[pointo++]; } if(peo==1) cout<<"xiran"<<endl; else if(peo==2) cout<<"sanqiu"<<endl; else cout<<"shixin"<<endl; print(); return 0; } if(stact=="Skip") { peo+=order; if(peo>3) peo=1; if(peo<1) peo=3; } else if(stact=="Reverse") { order*=-1; } else if(stact=="Draw_Two") { peo+=order; if(peo>3) peo=1; if(peo<1) peo=3; if(pointo>cnt) { printf("There are no cards to take\n"); print(); return 0; } card[peo][++nowcard[peo]]=allofcard[pointo++]; leacard[peo]++; if(pointo>cnt) { printf("There are no cards to take\n"); print(); return 0; } leacard[peo]++; card[peo][++nowcard[peo]]=allofcard[pointo++]; } break; } } if(leacard[peo]==0) { if(stact=="Draw_Two") { int now1=peo; now1+=order; if(now1>3) now1=1; if(now1<1) now1=3; if(pointo>cnt) { printf("There are no cards to take\n"); print(); return 0; } card[now1][++nowcard[now1]]=allofcard[pointo++]; leacard[now1]++; if(pointo>cnt) { printf("There are no cards to take\n"); print(); return 0; } leacard[now1]++; card[now1][++nowcard[now1]]=allofcard[pointo++]; } if(peo==1) cout<<"xiran"<<endl; else if(peo==2) cout<<"sanqiu"<<endl; else cout<<"shixin"<<endl; print(); return 0; } if(!flag) { if(pointo>cnt) { printf("There are no cards to take\n"); print(); return 0; } while(!(allofcard[pointo].col==stacol||allofcard[pointo].act==stact)) { card[peo][++nowcard[peo]]=allofcard[pointo++]; leacard[peo]++; if(pointo>cnt) { printf("There are no cards to take\n"); print(); return 0; } } stacol=allofcard[pointo].col; stact=allofcard[pointo].act; pointo++; allofcard[++cnt].col=stacol; allofcard[cnt].act=stact; // cout<<stacol<<" "<<stact<<endl; if(stact=="Skip") { peo+=order; if(peo>3) peo=1; if(peo<1) peo=3; } else if(stact=="Reverse") { order*=-1; } else if(stact=="Draw_Two") { peo+=order; if(peo>3) peo=1; if(peo<1) peo=3; if(pointo>cnt) { printf("There are no cards to take\n"); print(); return 0; } card[peo][++nowcard[peo]]=allofcard[pointo++]; leacard[peo]++; if(pointo>cnt) { printf("There are no cards to take\n"); print(); return 0; } leacard[peo]++; card[peo][++nowcard[peo]]=allofcard[pointo++]; } } peo+=order; if(peo>3) peo=1; if(peo<1) peo=3; } }
B
众所周知,这是一道签到题
原式子可以化为: =
可把看作一个整体
判断是否矛盾即得答案
#include<bits/stdc++.h> using namespace std; int n; int a[10005][10005]; int c[10005][10005]; int k[10005]; void work() { cin>>n; memset(k,0,sizeof(k)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ scanf("%d",&a[i][j]); k[i]^=a[i][j]; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&c[i][j]); for(int j=1;j<=n;j++){ int flag=-1,t; for(int i=1;i<=n;i++){ t=c[i][j]^k[i]; if(flag==-1) flag=t; else if(flag!=t) { puts("NO"); return; } } } puts("YES"); return; } int T; int main() { cin>>T; while(T--) work(); return 0; }
C
考点:可持久化01树,LCA,贪心
对整个图建可持久化01树,其父版本是图上的父亲
对于每次询问,LCA得出其最近公共祖先
利用01树找到表演风格相差最大的城市
利用差分求出其他城市的异或和
最后通过贪心计算答案
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int tot; int cnt; int x[N]; int n,m,w; int head[N]; int tr[N<<6][2]; int f[N][20],dep[N]; int siz[N<<6],Xor[N],rt[N]; struct Edge{ int u,v; }edge[N<<1]; void add(int x,int y){ edge[++tot].u=head[x]; edge[tot].v=y; head[x]=tot; return ; } void insert(int now,int pre,int val){ for(int i=1<<30; i; i>>=1){ bool k=val&i; tr[now][k^1]=tr[pre][k^1]; tr[now][k]=cnt++; siz[tr[now][k]]=siz[tr[pre][k]]+1; now=tr[now][k]; pre=tr[pre][k]; } } void dfs(int now,int fa){ f[now][0]=fa; dep[now]=dep[fa]+1; Xor[now]=Xor[fa]^x[now]; for(int i=1; i<20; ++i) f[now][i]=f[f[now][i-1]][i-1]; for(int i=head[now]; i; i=edge[i].u){ int to=edge[i].v; if(to==fa) continue; rt[to]=cnt++; insert(rt[to],rt[now],x[to]); dfs(to,now); } } int query(int now,int pre,int val){ int res=0; for(int i=1<<30; i; i>>=1){ bool k=val&i; if(siz[tr[pre][k^1]]>siz[tr[now][k^1]]){ res+=i; now=tr[now][k^1]; pre=tr[pre][k^1]; }else{ now=tr[now][k]; pre=tr[pre][k]; } } return res; } int LCA(int x,int y){ if(dep[x]<dep[y]) swap(x,y); for(int i=19; i>=0; --i){ if(dep[f[x][i]]>=dep[y]) x=f[x][i]; if(x==y) return x; } for(int i=19; i>=0; --i) if(f[x][i]!=f[y][i]){ x=f[x][i]; y=f[y][i]; } return f[x][0]; } int solve(int u,int v,int p){ int lca=LCA(u,v); int maxx=0,ans=0; int res=Xor[u]^Xor[v]; maxx=max(maxx,query(rt[lca],rt[u],p)); maxx=max(maxx,query(rt[lca],rt[v],p)); maxx=max(maxx,x[lca]^p); res=res^x[lca]^maxx^p; for(int i=30; i>=0; --i){ if((ans|(1<<i))>w) continue; if(res&(1<<i)) continue; ans|=(1<<i); } return ans|res; } int main(){ scanf("%d%d%d",&n,&m,&w); for(int i=1,p,q; i<n; ++i){ scanf("%d%d",&p,&q); add(p,q); add(q,p); } for(int i=1; i<=n; ++i) scanf("%d",&x[i]); cnt=1; rt[1]=cnt++; insert(rt[1],0,x[1]); dfs(1,0); for(int i=1,u,v,s; i<=m; ++i){ scanf("%d%d%d",&u,&v,&s); printf("%d\n",solve(u,v,s)); } return 0; }
D
简单矩阵乘法
可以矩阵套矩阵,也可以只建一个矩阵
std写得是矩阵套矩阵的写法
第一个矩阵(最大的矩阵)
矩阵大小:
矩阵意义:对于代表从i走到j需要的最少体力
矩阵嵌套:对于是一个小矩阵,小矩阵定义参见下方
第二个矩阵(小矩阵)
矩阵大小:
矩阵意义:对于代表走过新路的第i条到第j条的最少体力
矩阵转移
见代码
std
#include<bits/stdc++.h> using namespace std; long long n,m,k,a,b; struct ppp { long long f[12][12]; ppp operator*(const ppp x) { ppp y; memset(y.f,10,sizeof(y.f)); for(long long i=0; i<=b; i++) for(long long j=i; j<=b; j++) for(long long k=i; k<=j; k++) y.f[i][j]=min(y.f[i][j],f[i][k]+x.f[k][j]); return y; } }; ppp Min(ppp x,ppp y) { for(long long i=0; i<=b; i++) for(long long j=0; j<=b; j++) x.f[i][j]=std::min(x.f[i][j],y.f[i][j]); return x; } struct oppo { ppp f[30][30]; oppo operator*(const oppo x) { oppo y; memset(y.f,10,sizeof(y.f)); for(long long k=1; k<=n; k++) for(long long i=1; i<=n; i++) for(long long j=1; j<=n; j++) y.f[i][j]=Min(f[i][k]*x.f[k][j],y.f[i][j]); return y; } } cs,ans; void ksm(long long g) { memset(ans.f,10,sizeof(ans.f)); for(long long i=1; i<=n; i++) ans.f[i][i].f[0][0]=0; while(g) { if(g&1) ans=ans*cs; g>>=1; cs=cs*cs; } long long st=LONG_LONG_MAX; for(long long j=1; j<=n; j++) st=min(st,ans.f[1][j].f[0][b]); if(st!=ans.f[0][0].f[0][0]) cout<<st<<"\n"; else puts("-1"); } int main() { cin>>n>>m>>k>>a>>b; memset(cs.f,10,sizeof(cs.f)); for(long long i=1; i<=m; i++) { long long s,t,u; scanf("%lld%lld%lld",&s,&t,&u); for(long long j=0; j<=b; j++) cs.f[s][t].f[j][j]=u; } for(long long i=1; i<=a; i++) { long long s,t,u; scanf("%lld%lld",&s,&t); for(long long j=1; j<=b; j++) { scanf("%lld",&u); cs.f[s][t].f[j-1][j]=u; } } ksm(k+b); return 0; }
后记
菜鸡出题人选择了一个不好的时间,好多小伙伴都来不了QWQ
想了很久还是决定添上A题(大模拟)
到现在没有发现什么锅,我很开心QWQ
希望大家享受这次的比赛吧