2022杭电多校第一场

A

B. Dragon slayer

• 题意

• 思路

• 代码

C. Backpack

• 题意
  求刚好装满背包的所有物品的价值的异或和最大是多少，不存在输出-1。
• 思路
  是一个背包模型，可以考虑三维dp，$dp[i,j,k]$表示前$i$个物品，异或和是$j$，占用的体积恰好是$k$的方案是否存在。很显然状态转移就是简单的选或者不选两种情况可以转移过来：$dp[i,j,k]=dp[i,j,k]|dp[i,j\oplus w,k-v]$。其中，$x=a\oplus b$，已知$x$和$a$求b，则有$b=a\oplus x$。这个代码如下，会TLE。

while(t--)
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<=1024;i++) for(int j=0;j<=1024;j++) f[i][j]=0;
	f[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&v,&w);
		f[w][v]=1;
		for(int j=0;j<1024;j++)
		{
			for(int k=v;k<=m;k++)
				f[j][k]|=f[j^w][k-v];
		}
	}
	int ans=-1;
	for(int i=0;i<1024;i++) if(f[i][m]) ans=i;
	cout<<ans<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

于是考虑使用bitset进行压位，将循环体积的那一层循环优化掉，代码如下：

• 代码

#include
using namespace std;
#define N 1050
int n,m,t,x,y;
bitset<N> f[N],g[N];
int main()
{
	cin>>t;
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(int j=0;j<1024;++j) f[j].reset();
		f[0][0]=1;
		for(int i=1;i<=n;++i)
		{
			cin>>x>>y;
			for(int j=0;j<1024;++j)
			{
				g[j]=f[j];
				g[j]<<=x;
			}
			for(int j=0;j<1024;++j)
			{
				f[j]|=g[j^y];
			}
		}
		int ans=-1;
		for(int i=0;i<1024;i++) if(f[i][m]) ans=i;
		cout<<ans<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

D

E

F

G

H

I. Laser

• 题意
  给定n对敌人的坐标$(x_i,y_i)$，现在有一个激光发射器，他可以向8个方向（东、南、西、北、西北、东北、西南、东南）发射以自己为中心的8条射线。问是否存在一个点可以摆放 这个激光发射器，使得他发射一次就可以杀掉所有的敌人。
• 思路
  假设任意一个点Q在一条水平直线上，任意找到一个点P不在这条水平直线上。那么发射中心必须在以点Q为中中心的“米”字与点P所在直线的三个交点上。那么只要枚举这三个交点，$O(n)$判断是否能杀掉所有敌人。
  同理，假设任意一个点Q在一条竖直直线上/主对角线上/副对角线上，将上述操作重复4次即可，为了方便实现，我们对坐标进行旋转，将所有的线旋转到水平这种情况下。
• 代码

#include
using namespace std;
#define ll long long
#define N 500010
int t,n;
ll a[N],b[N],x[N],y[N];

bool work(ll xx,ll yy)
{
	for(int i=1;i<=n;i++) 
		if(!(x[i]==xx || y[i]==yy || yy-xx==y[i]-x[i] || yy+xx==y[i]+x[i]))
			return false;
	return true;
}

bool check()
{
	int p=0;
	for(int i=2;i<=n;i++)
	{
		if(x[i]==x[1]) continue;
		p=1;
		if(work(x[1],y[i])) return true; //注意这里是找到一个不在这条线上的点 以这个点做“米”字与原来那条确定的线的交点。
		if(work(x[1],y[i]-(x[i]-x[1]))) return true;
		if(work(x[1],y[i]+(x[i]-x[1]))) return true;
 		break;
	}
	if(p==0) return true; //注意特判在一条线上的点
	return false;
}

int main()
{
	cin>>t;
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]);
		bool is_ok=false;
		for(int i=1;i<=n;i++)x[i]=a[i],y[i]=b[i];
		if(check()) is_ok=true; 
		for(int i=1;i<=n;i++)x[i]=b[i],y[i]=a[i];
		if(check()) is_ok=true; 
		for(int i=1;i<=n;i++)x[i]=a[i]+b[i],y[i]=a[i]-b[i];
		if(check()) is_ok=true; 
		for(int i=1;i<=n;i++)x[i]=a[i]-b[i],y[i]=a[i]+b[i];
		if(check()) is_ok=true; 
		if(is_ok) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

J

K. Random

• 题意
  给定n个分布在$[0,1]$之间的数，现在有m次操作，每次操作有$1/2$的概率删除现在所有数中的最小数，有$1/2$的概率删除现在所有数中的最大数。问最后剩下的数的和的期望是多少（答案mod1e9+7）。
• 思路
  算每次操作后n个位置剩下数的概率（多观察几个就会发现是$n-m$），最后将这些概率加起来乘以$1/2$（每个数的期望值是$1/2$）,由于要取模操作，因此需要使用逆元。
• 代码

#include
using namespace std;
#define ll long long 
const ll mod =1e9+7;
ll n,m,t;
ll qmi(ll a, ll k, ll p)    
{
    ll res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * a % p;
        a = (ll)a * a % p;
        k >>= 1;
    }
    return res%p;
}

int main()
{
	cin>>t;

	while(t--)
	{
		cin>>n>>m;
		if(n==m) printf("0\n");
		else
		{
			if(m==0) printf("%lld\n",(n*qmi(2,mod-2,mod))%mod);
			else
			{
				printf("%lld\n",((n-m)%mod*qmi(2,mod-2,mod))%mod);
			}
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

L. Alice and Bob

• 题意
  黑板上有很多数，范围是0-n之间。Alice和Bob玩游戏，Alice每次将黑板上的数分成两个集合。Bob每次将其中一个集合删除，另一个集合中的每个数减一。当出现一个0时，Alice Win；当数字全部删除后Bob Win。两人都绝顶聪明，现给定0-n每个数的个数，问最后谁Win。
• 思路
  观察发现当有2个1,4个2,8个3…时先手必赢。两个大的数可以变成一个小一的数。因此循环a[i]+=a[i+1]/2。最后判断a[0]是否大于1即可。
• 代码

#include
using namespace std;
#define N 1000010
int t,a[N],n;
int main()
{
	cin>>t;
	while(t--)
	{
		scanf("%d",&n);
		for(int i=0;i<=n;i++) scanf("%d",&a[i]);
		for(int i=n;i>=1;i--) a[i-1]+=a[i]/2;
		if(a[0]>0) printf("Alice\n");
		else printf("Bob\n");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17