2022杭电第一场题解

87 阅读 0 评论 58 点赞

我是靠谱客的博主谦让小伙，最近开发中收集的这篇文章主要介绍2022杭电第一场题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

K Random

在[0,1]随机生成n个数字,并进行m次操作，1/2的概率删除最大数，1/2的概率删除最小数。计算剩余数之和的期望值，并对1000000007取模。

答案为（n-m）/2 求出2的逆元即可

#include<bits/stdc++.h>
using namespace std;
template <typename tn>void read(tn &n){
    tn f=1,t=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)) t=t*10+ch-'0',ch=getchar();
    n=f*t;
}
inline void out(int x){
	if(x>9)out(x/10);
	putchar(x%10+'0');
}
int T,n,m,p=1e9+7;
long long Ans;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	read(T);
	for(int i=1;i<=T;++i){
		read(n),read(m);
		if(n<=m){
			cout<<"0"<<endl;
			continue;
		}
		Ans=(long long)(n-m)*500000004;
		Ans%=p;
		cout<<Ans<<endl;
	} 
	return 0;
}

L Alice and Bob

有m个0-n之间的数
Alice先手，将当前的数分为两组，Bob选择移除其中一组数，另一组数字全部减1，轮流进行。
当数字中出现0时Alice获胜，当没有数字时Bob获胜
在最优策略情况下，谁赢。

将每个值为的数字视为 2^(n-i),那么Alice的胜利条件就是最终局面中能出现2^n。
Alice将数字分成两个集合，Bob将其中一个集合减1，就相当于将这个集合中的数全部乘2，然后将另一个集合删去。
如果Alice能将集合中的数字按照值二等分，那么无论Bob怎么操作，黑板上所有数字的总和实际是不变的。
如果集合中的数字总和超过2^n,由于所有数字都是不超过2^n的2的幂次，那么Alice的每次分割总能使得两边集合的值均不小于 2^(n-1)。
因此直接判断所有数字的2的幂次的总和即可。

#include<bits/stdc++.h>
using namespace std;
template <typename tn>void read(tn &n){
    tn f=1,t=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)) t=t*10+ch-'0',ch=getchar();
    n=f*t;
}
inline void out(int x){
	if(x>9)out(x/10);
	putchar(x%10+'0');
}
int main(){
    int n,T;
    read(T);
    while(T--){
    	read(n);
    	for(int i=0;i<=n;i++)
        read(a[i]);
    	for(int i=n;i>=1;i--)
    	if(a[i]>=2)a[i-1]+=a[i]/2;
    	if(a[0]>=1)puts("Alice");
    	else puts("Bob");
    } 
	return 0;
}

B Dragon slayer

对于一给定区域，最下角(0,0)，右上角(n,m),起点(xs+0.5,ys+0.5),终点是(xt+0.5,yt+0.5)
有 k 堵水平或垂直的墙。你可以在区域内的任何方向移动，但不能穿过墙，你可以花费一点体力使墙永久消失。
问至少要耗费多少体力。
1 ≤ n , m , K ≤ 15 1≤n, m, K≤15 1≤n,m,K≤15

签到题。墙的数量只有 15 ，爆搜或者状压都能比较轻松的通过。

#include<bits/stdc++.h>
using namespace std;
template <typename tn>void read(tn &n){
    tn f=1,t=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)) t=t*10+ch-'0',ch=getchar();
    n=f*t;
}
inline void out(int x){
	if(x>9)out(x/10);
	putchar(x%10+'0');
}
int n,m,K,sx,sy,tx,ty;
struct edge{
	int x[2],y[2]; 
}e[20];
int mp[20][20],Lw[20][20],Dw[20][20];
bool dfs(int x,int y){
	mp[x][y]=1;
	if(x==tx && y==ty)return 1;
	bool re=0;
	//x-1 y
	if(x>=1 && Lw[x][y]==0 && mp[x-1][y]==0)re|=dfs(x-1,y);
	//x+1 y
	if(x+1<n && Lw[x+1][y]==0 && mp[x+1][y]==0)re|=dfs(x+1,y);
	//x y-1
	if(y>=1 && Dw[x][y]==0 && mp[x][y-1]==0)re|=dfs(x,y-1);
	//x y+1
	if(y+1<m && Dw[x][y+1]==0 && mp[x][y+1]==0)re|=dfs(x,y+1);
	return re;
}
bool check(int s){
	memset(mp,0,sizeof(mp));
	memset(Lw,0,sizeof(Lw));
	memset(Dw,0,sizeof(Dw));
	for(int i=0;i<K;++i)
	if((s&(1<<i))==0){
		if(e[i].x[0]==e[i].x[1]){
			for(int j=e[i].y[0];j<e[i].y[1];++j)
			Lw[e[i].x[0]][j]=1;
		}
		else{
			for(int j=e[i].x[0];j<e[i].x[1];++j)
			Dw[j][e[i].y[0]]=1;
		}
	}
	return dfs(sx,sy);
}
int popcount(int x){
	int re=0;
	while(x){
		if(x&1)++re;
		x>>=1;
	}
	return re;
}
int f[(1<<15)+5];
void solve(){
	cin>>n>>m>>K>>sx>>sy>>tx>>ty;
	for(int i=0;i<K;++i){
		cin>>e[i].x[0]>>e[i].y[0]>>e[i].x[1]>>e[i].y[1];
		if(e[i].x[0]==e[i].x[1]&&e[i].y[0]>e[i].y[1]){
			swap(e[i].y[0],e[i].y[1]);
		}
		if(e[i].y[0]==e[i].y[1]&&e[i].x[0]>e[i].x[1]){
			swap(e[i].x[0],e[i].x[1]);
		}
	}
	int ans=K;
	for(int s=0;s<(1<<K);++s){
		f[s]=0;
	}
	for(int s=0;s<(1<<K);++s){
		if(f[s]){
			continue;
		}
		f[s]=check(s);
		if(f[s]){
			ans=min(ans,popcount(s));
			for(int j=0;j<K;++j){
				f[s|(1<<j)]|=f[s];
			}
		}
	}
	cout<<ans<<endl;
	return;
}
int main(){
    int T;
    read(T);
    while(T--){
    	solve();
    } 
	return 0;
}