博客

前两题太水了就不写了。

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);
		}
	}	
}