前两题太水了就不写了。
C - Dice and Coin
题意：给一个n面的色子，每次掷到正面就翻一倍，否则得零分，如果最后所得分数大于等于k，那么你赢，否则如果得0分，那么就输掉了比赛。问你有多大纪律赢。
思路：a*2^n=k,n=log2(k/a);然后计算即可。
#include<bits/stdc++.h> using namespace std; int main(){ int n,k; scanf("%d%d",&n,&k); double ans=0.0; for(int i=1;i<=n;i++){ if(i>k){ ans=ans+(1.0)/(double)n; } else{ int t=log2(k/i); if(i*pow(2,t)!=k) t=t+1; ans=ans+(1.0)/(double)(n*pow(2,t)); } } printf("%.12lf\n",ans); }D - Even Relation
题意：有一棵树，任意两个节点间的距离如果是偶数就涂一样的颜色，否则涂不一样的颜色。
思路：按题意建树，模拟即可。
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+5; struct node{ int to,nxt; int w; }e[maxn]; int head[maxn]; int ans[maxn]; int cnt; void add(int u,int v,int w){ e[++cnt]=(node){v,head[u],w}; head[u]=cnt; } void dfs(int u,int fa){ for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(v==fa) continue; if(e[i].w%2) ans[v]=ans[u]^1; else ans[v]=ans[u]; dfs(v,u); } } int main(){ int n; scanf("%d",&n); for(int i,u,v,w;i<n-1;i++){ scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } dfs(1,0); for(int i=1;i<=n;i++) printf("%d\n",ans[i]); }E - 1 or 2
题意：有n个数字，只有1或2，给出了其中m个他们之间的关系，还有可以之接问第几个数字是多少，问知道所有数字的最少花费。
思路：建图跑最短路，已经知道关系的最少花费是0，想要知道数字的花费是1.
#include<bits/stdc++.h> using namespace std; struct node{ int u,v,w; }a[200005]; int fa[200005]; int find(int x){ if(x!=fa[x]) return fa[x]=find(fa[x]); return fa[x]; } int cmp(node a,node b){ return a.w<b.w; } int main(){ int n,m; scanf("%d%d",&n,&m); int u,v,w; int cnt=0; for(int i=0;i<m;i++){ scanf("%d%d%d",&a[cnt].u,&a[cnt].v,&w); a[cnt++].w=0; } for(int i=1;i<=n;i++) a[cnt].u=n+1,a[cnt].v=i,a[cnt++].w=1; for(int i=1;i<=n;i++) fa[i]=i; sort(a,a+cnt,cmp); int ans=0; for(int i=0;i<cnt;i++){ int fx=find(a[i].u),fy=find(a[i].v); if(fx!=fy){ ans+=a[i].w; fa[fy]=fx; } else continue; } printf("%d\n",ans); }F - XOR Matching
题意：构造题，给定m和k，构造2^(m+1)个数，使得i到j的异或和等于k并且数组里面的数只能是0到2^m-1，并且出现两次；
思路：如果k大于2^m那么肯定不行，题目意思只要一段区间首尾相同，区间异或和是k就行了，那么我们把k放第一位，接下来2^m个数按顺序放0到2^m-1,再放一个k，再按倒序放2^m-1到0即可。
#include<bits/stdc++.h> using namespace std; int main(){ int m,k; scanf("%d%d",&m,&k); if(k==0){ for(int i=0;i<(1<<m);i++) printf("%d %d ",i,i); printf("\n"); } else if(m==1){ if(k>=1) puts("-1"); else puts("1 1 0 0"); } else{ if(k>=(1<<m)) puts("-1"); else{ printf("%d ",k); for(int i=0;i<(1<<m);i++) if(i!=k) printf("%d ",i); printf("%d ",k); for(int i=(1<<m)-1;i>=0;i--) if(i!=k) printf("%d ",i); } } }
