2022杭电多校第一场

Dragon slayer（暴力 BFS DFS）

题意
有一个$n\times m(1⩽n,m⩽15)$的网格，网格的左上角坐标为$(0,0)$，右下角坐标为$(n,m)$。英雄的坐标是$(x_s+0.5,y_s+0.5)$，龙的坐标是$(x_t+0.5,y_t+0.5)$。网格内有一些水平或竖直的墙壁，总数为$K(1⩽K⩽15)$。英雄知道龙所在的位置，英雄可以使用特殊技能让墙永远消失。求英雄最少使用多少次特殊技能可以到达龙的位置。

分析
题目数据范围较小，可以暴力枚举哪些墙可以通过，在所有可能情况中求英雄到达龙的位置经过的最少的墙的数量。由于英雄可以多次经过同一堵墙，而同一堵墙只需要使用一次特殊技能，建图求最短路的方式求出来的结果可能偏大。在本题中，英雄位于网格的中央，墙位于网格的边界，在编码时需要注意。时间复杂度$O(2^{k}nm)$。

AC代码

typedef long long ll;
const int N=17;
int f[1<<N];
struct node {
	int l1,r1,l2,r2;
}p[N];
int LW[N][N],DW[N][N],vis[N][N]; //LW:水平墙,DW:竖直墙 
int n,m,k,sx,sy,tx,ty;
bool flag;

void dfs(int x,int y)
{
	if(flag) return ;
	if(x==tx&&y==ty)
	{
		flag=true;
		return ;
	}
	if(vis[x][y]) return ;
	vis[x][y]=1;
	if(y<m-1&&!DW[x][y+1]) //右 
	{
		dfs(x,y+1);
	}
	if(x<n-1&&!LW[x+1][y]) //下
	{
		dfs(x+1,y);
	}
	if(y>0&&!DW[x][y]) //左
	{
		dfs(x,y-1);
	}
	if(x>0&&!LW[x][y]) //上 
	{
		dfs(x-1,y);
	}
}

bool check(int x)
{
	memset(LW,0,sizeof(LW));
	memset(DW,0,sizeof(DW));
	memset(vis,0,sizeof(vis));
	for(int i=0;i<k;i++)
	{
		if(!(x>>i&1))
		{
			int l1=p[i].l1,r1=p[i].r1,l2=p[i].l2,r2=p[i].r2;
			if(l1==l2)
			{
				if(r1>r2) swap(r1,r2);
				for(int j=r1;j<r2;j++) LW[l1][j]=1;
			}
			else
			{
				if(l1>l2) swap(l1,l2);
				for(int j=l1;j<l2;j++) DW[j][r1]=1;
			}
		}
	}
	flag=false;
	dfs(sx,sy);
	return flag;
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m>>k;
		cin>>sx>>sy>>tx>>ty;
		for(int i=0;i<k;i++) cin>>p[i].l1>>p[i].r1>>p[i].l2>>p[i].r2;
		int ans=k;
		for(int i=0;i<1<<k;i++) f[i]=0;
		for(int i=0;i<1<<k;i++)
		{
			if(f[i]) continue;
			if(check(i))
			{
				ans=min(ans,__builtin_popcount(i));
				for(int j=0;j<k;j++) f[i|(1<<j)]=1;  //剪枝
			}
		}
		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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

Backpack（bitset优化DP）

题意
给定$n$个物品和一个体积为$m$的背包，求在背包装满的情况下物品价值的最大异或和。如果背包无法装满则输出$-1$.

分析
异或和不具有最优子结构，不能直接按照完全背包的状态转移进行处理。对于一种体积，所有可能的异或和都可能对最终答案有贡献，因此需要记录每种体积所有异或值，这样时间复杂度就是$O(n^3)$，不能通过本题。考虑改变状态表示求每种异或和的可能体积和。用$f[i][j]$表示异或和为$i$体积为$j$的方案是否存在，可得状态转移方程$f[i][j]=g[i\oplus w][j-v]$，其中$f[i][j]$是当前状态，$g[i][j]$是上一层的状态，状态的第二维可以用bitset优化，时间复杂度$O(\frac{n^3}{32})$。

AC代码

typedef long long ll;
const int N=1030;
bitset<N> f[N],g[N];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=0;i<=1023;i++) f[i].reset();
        f[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            int a,b;
            cin>>a>>b;
            for(int j=0;j<=1023;j++) g[j]=f[j];
            for(int j=1023;j>=0;j--)
            {
                f[j]|=g[j^b]<<a;
            }
        }
        int ans=-1;
        for(int i=1023;i>=0;i--)
        {
            if(f[i][m])
            {
                ans=i;
                break;
            }
        }
        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
33
34
35
36
37

Random（概率期望）

题意
有$n$个$[0,1]$区间的随机数，有$m$次操作，每次有$\frac{1}{2}$的概率删掉最大值或最小值，求最终剩下的数的和的期望。

分析
这$n$个数是均匀分布的，每个数的期望是$\frac{1}{2}$，在删除操作之间，$n$个数的和的期望是$\frac{n}{2}$，每次删除操作造成期望的减少量是$\frac{1}{2}$，因此最终的答案就是$\frac{n-m}{2}$。

AC代码

typedef long long ll;
const int mod=1e9+7;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll m,n;
        cin>>n>>m;
        cout<<(n-m)*((mod+1)/2)%mod<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15