2020-10-2 大二2020下训练三

Powered by:AB_IN 局外人

A 宋哥爬树

一开始wa了4发，就是因为好多有个地方没想到。

分三种情况

当$z\le x$时，一步就可以到达目的地。当$x\le y$时，不管怎样也到不了终点。（终点最小是$1$）其次，就是算$tmp=\frac{z-x}{x-y}$。$tmp$要先变成不小于它的最大整数（因为小数可能是没走全的）。此时$tmp$变成了在终点前小于$x$的点，故最后加1即可。 #include <bits/stdc++.h> using namespace std; int t,x,y,z,ans; double tmp; int main() { ios::sync_with_stdio(0); cin>>t; for(int k=1;k<=t;k++){ cin>>x>>y>>z; if(z<=x) printf("Case #%d: 1\n",k); else if(x<=y) printf("Case #%d: QAQ\n",k); else{ tmp=(z-x)*pow((x-y),-1); ans=ceil(tmp)+1; printf("Case #%d: %d\n",k,ans); } } return 0; }

B 宋哥看星星

生成$k$个最小生成树。 （没想到一开始$n=k$的情况） 这样写更方便，不用开始和结尾都判断一下$n$与$k$的关系。每有一条边生成，$k$就自增，$k$最后要是和$n$相等了，说明成了。

#include <bits/stdc++.h> #define ll long long #define rep(i,x,y) for (ll i=(x);i<=(y);i++) using namespace std; const ll maxn=1e6+10; ll n,m,u,v,w,ans,k; ll fa[maxn]; struct sa{ ll u,v,w; }e[maxn]; bool cmp(struct sa x,struct sa y){ return x.w<y.w; } ll find(ll x) { if(fa[x] == x) return x; return fa[x] = find(fa[x]); } int t; int main() { cin>>t; for(int j=1;j<=t;j++){ ans=0; memset(e,0,sizeof(e)); cin>>n>>m>>k; rep(i,1,m) cin>>e[i].u>>e[i].v>>e[i].w; sort(e+1,e+1+m,cmp); rep(i,1,n) fa[i]=i; for(int i=1;i<=m&&k!=n;i++){ w=e[i].w; u=find(e[i].u);v=find(e[i].v); if(u!=v){ fa[u]=v; ans+=w; k++; } } if(k==n) printf("Case #%d: %lld\n",j,ans); else printf("Case #%d: QAQ\n",j); } return 0; }

C 破解棋局

博弈论。 当$n\ne m\ne 1$时，$Alice$先手拿(2,2),那么就只会剩下两个边界了，分别是（1,1）到（1，n) 和(1,1)到（n，1）。之后不管$Bob$怎么拿，$Alice$只要拿和他拿的对称的点即可，这样$Bob$必输。

#include <bits/stdc++.h> using namespace std; int x,y,c; int main() { while(~scanf("%d%d",&x,&y)){ if(x==1&&y==1){ printf("Bob\n"); } else printf("Alice\n"); } }

D 军哥排队

奇偶分情况模拟即可。

#include <bits/stdc++.h> #define ll long long const ll mod=1e9+7; using namespace std; ll a[10010]; ll t,n,x; ll qm (ll a, ll b ,ll c){ ll ret=1%c; while(b){ if(b&1) ret=ret*a%c; a=a*a%c; b=b>>1; } return ret; } int main() { cin>>t; for(int j=1;j<=t;j++){ int f=0; cin>>n; memset(a,0,sizeof(a)); for(int i=1;i<=n;i++){ cin>>x; a[x]++; } if(n&1){ if(a[0]!=1){ f=1; } for(int i=2;i<=n-1;i+=2){ if(a[i]!=2){ f=1; break; } } if(f) cout<<"0"<<endl; else cout<<qm(2,(n-1)/2,mod)<<endl; } else{ for(int i=1;i<=n-1;i+=2){ if(a[i]!=2){ f=1; break; } } if(f) cout<<"0"<<endl; else cout<<qm(2,(n)/2,mod)<<endl; } } return 0; }

完结。