• 2022杭电多校联赛第一场 题解

    比赛传送门
    作者： fn

    目录

    签到题

    1011题 Random / 随机

    题目大意
    在 [ 0 , 1 ] [0,1] [0,1] 之间随机生成 n n n 个数字
    进行 m m m 次运算， 1 / 2 1/2 1/2 概率删除最大值， 1 / 2 1/2 1/2 概率删除最小值
    计算期望值之和，对 1 0 9 + 7 10^9+7 109+7 取模

    考察内容
    数学知识

    分析
    显然，可以把每个数看作0.5，答案就是 ( n − m ) / 2 (n-m)/2 (n−m)/2。
    除法用乘法逆元计算。

    #include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const ll mod=1e9+7;
ll n,m;

ll power(ll a,ll b){ // a^b%mod
	ll c=1;
	for(;b;b>>=1){
		if(b&1)c=c*a%mod;
		a=a*a%mod;
	}
	return c;
}

int main(){ 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>n>>m;
		cout<<(n-m)*power(2,mod-2)%mod<<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

    基本题

    1012题 Alice and Bob / 爱丽丝和鲍勃

    题目大意
    黑板上有 m m m 个 0 0 0 到 n n n 之间的整数。
    游戏规则如下：
    爱丽丝先手，如果黑板上还有数字，并且黑板上没有值为0的数字，爱丽丝可以将黑板上剩余的数字分成两组。
    鲍勃后手，他选择其中一个集合并擦除该集合中的所有数字，然后将所有剩余的数字减去一。

    在任何时候，如果黑板上有一个值为0的数字，爱丽丝获胜；否则，如果黑板上的所有数字都被删除，鲍勃获胜。
    爱丽丝和鲍勃都采用最优策略，请确定谁将赢得比赛。

    考察内容
    博弈论，找规律

    分析
    找规律，如果 0 0 0 的个数 a [ 0 ] ≥ 1 a[0]≥1 a[0]≥1 ，则Alice直接获胜。
    如果 1 1 1 的个数 a [ 1 ] ≥ 2 a[1]≥2 a[1]≥2 ，则Alice可以把其中两个1分到两个不同的集合中，从而获胜。
    如果 1 1 1 的个数 a [ 1 ] ≥ 1 a[1]≥1 a[1]≥1 并且 2 2 2 的个数 a [ 2 ] ≥ 2 a[2]≥2 a[2]≥2，则Alice可以把1和两个2分到两个不同的集合中，从而获得一个0或者两个1，从而获胜。
    如果 2 2 2 的个数 a [ 2 ] ≥ 4 a[2]≥4 a[2]≥4，同理，Alice可以获胜。
    …

    容易发现规律，2个 a [ i ] a[i] a[i] 可以变成1个 a [ i − 1 ] a[i-1] a[i−1]，反向遍历一遍，判断 a [ 0 ] a[0] a[0] 是否 ≥ 1 ≥1 ≥1 即可

    #include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e6+10;
ll n,m,a[N];

int main(){ 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>n;
		for(int i=0;i<=n;i++){
			cin>>a[i];
		}
		
		for(int i=n;i>=1;i--){
			if(a[i]>=2){
				a[i-1]+=a[i]/2;
			} 
		}
		
		if(a[0]>=1){
			cout<<"Alice"<<endl;
		}
		else{
			cout<<"Bob"<<endl;
		}
	}
	return 0;
}
/*
1
1
0 2

*/ 

    • 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

    1002题 Dragon slayer / 屠龙者

    题目大意
    给定一个矩形区域。左下角为 ( 0 , 0 ) (0,0) (0,0)，右上角为 ( n , m ) (n,m) (n,m) 。
    起点是 ( x s + 0.5 ， y s + 0.5 ) (x_s+0.5，y_s+0.5) (xs​+0.5，ys​+0.5) ，终点是 ( x t + 0.5 ， y t + 0.5 ) (x_t+0.5，y_t+0.5) (xt​+0.5，yt​+0.5) 。

    该区域有 k k k 堵水平或垂直的墙。你可以在区域内的任何方向移动，但不能穿过墙壁，包括墙壁的末端。

    起点到终点可能会被墙挡住。你每次技能可以使一堵墙消失，求到达终点最少需要使用多少次技能。

    1 ≤ n , m , K ≤ 15 1≤n, m, K≤15 1≤n,m,K≤15

    考察内容
    dfs，FloodFill算法

    分析
    地图大小全部*2，让人落在整数点上。每次走两格。
    dfs枚举每堵墙是否存在，FloodFill从起点开始染色，通过终点是否被染色来判断是否能够到达终点，如果能够到达则更新答案（答案就是没选中的墙的数量）。
    复杂度为 O ( 2 15 ∗ 1 5 2 ) O(2^{15}*15^2) O(215∗152) ，约 7 ∗ 1 0 6 7*10^6 7∗106 ，可以通过。

    #include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;

ll n,m,k;
ll xs,ys,xt,yt;
		
int mp[35][35]; // 是否有墙 
int color[35][35]; // 答案 

const int X[4]={2,0,-2,0},Y[4]={0,2,0,-2};

ll ans=0;

void fillcolor(ll x,ll y,ll num){
	if(color[x][y]<=num)return;
	color[x][y]=num;

	for(int i=0;i<4;i++){
		int dx=x+X[i]; int dy=y+Y[i];
		if(dx>=0 && dx<=n && dy>=0 && dy<=m){
			int cnt=0;
			if(mp[x+X[i]/2][y+Y[i]/2]){ // 要开墙 
				cnt=1; 
			}
			
			if(cnt==0){ // 不需要开墙 
				fillcolor(dx,dy,num+cnt);
			}
		}
	}
}

bool ck(){
	for(int i=1;i<=n;i+=2){
		for(int j=1;j<=m;j+=2){
			color[i][j]=1e9+10;
		}
	}
	fillcolor(xs,ys,0);
	if(color[xt][yt]==0){
		return 1; // 可以到达 
	}
	return 0;
}

ll x1[20],y1[20],x2[20],y2[20];

int note[20];
void dfs(ll x,ll y){
	note[y]=x;
	
	if(y==k){ // 递归边界 
		for(int i=0;i<=n;i++){
			for(int j=0;j<=m;j++){
				mp[i][j]=0; // 初始化mp 
			}
		}
		
		ll c1=0; 
		for(int i=1;i<=k;i++){
			if(note[i]==1){ // 选中这面墙 
				if(x1[i]==x2[i]){
					for(int j=y1[i];j<=y2[i];j++){
						mp[x1[i]][j]=1;
					}
				}
				else if(y1[i]==y2[i]){
					for(int j=x1[i];j<=x2[i];j++){
						mp[j][y1[i]]=1;
					}
				}
			}
			else{
				c1++; // 使用了技能，不选这面墙 
			}
		}
		
		if(ck()){
			ans=min(ans,c1); // 更新答案 
		}
		return;
	}	
	
	// y
	dfs(1,y+1);
	dfs(0,y+1);
}

int main(){ // AC. 每次可以让一整面墙消失 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>n>>m>>k; 
		n<<=1; m<<=1;
		
		for(int i=0;i<=n;i++){
			for(int j=0;j<=m;j++){
				mp[i][j]=0;
			}
		}
		
		cin>>xs>>ys>>xt>>yt;
		ans=abs(xt-xs)+abs(yt-ys); // ans不超过两点间的曼哈顿距离 
		ans=min(ans,k); // ans不超过k 
		// ans<=k<=15
		
		xs=xs*2+1; ys=ys*2+1; xt=xt*2+1; yt=yt*2+1;
		
		for(int i=1;i<=k;i++){
			cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
			x1[i]<<=1; y1[i]<<=1;  
			x2[i]<<=1; y2[i]<<=1;  
		}
		
		dfs(0,0);
		
		cout<<ans<<endl;	
	}
	return 0;
}
/*
1
3 2 2 
0 0 2 1
0 1 3 1
1 0 1 2

1
3 2 2 
0 0 2 1
2 1 2 2
1 0 1 1
*/ 

    • 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
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136

    进阶题

    1009题 Laser / 激光

    题目大意
    二维平面上有 n n n 个敌人，第 i i i 个敌人的位置是 ( x i , y i ) (x_i, y_i) (xi​,yi​) 。

    你现在有一个激光武器，你可以把它放在任何一点 ( x , y ) (x, y) (x,y) （x, y是实数）上，武器发射激光，把垂直、水平、左右斜线的敌人摧毁。

    求是否可以摧毁所有敌人。

    考察内容
    数学知识，枚举，暴力

    分析

    方法一， O ( 4 ! n ) O(4!n) O(4!n)
    直接暴力讨论。
    假设第一个点是水平的，然后能囊括哪些点，然后下一个没囊括的点是竖直点之类，再下一个没囊括的点是左下到右上的斜线，以此类推。
    四种方向，复杂度为 O ( 4 ! n ) O(4!n) O(4!n) 。常数只有24，不会tle。

    方法二， O ( 4 ∗ 3 n ) ) O(4*3n)) O(4∗3n))
    选中一个点，讨论这个点的四种情况（垂直、水平、左右斜线）。
    每种情况对应一条线，因为线上只有不在这条线上的点作出的线和这条线的交点可以选，所以只有 3 ∗ n 3*n 3∗n 个可选的中心点用于放置激光武器。
    枚举每个中心点，复杂度为 O ( 4 ∗ 3 n ) ) O(4*3n)) O(4∗3n))

    方法一的代码如下：

    #include 
using namespace std;

typedef long long ll;
typedef pair<ll,ll> PII;
const int INF=0x3f3f3f3f;

inline ll read(){
    char ch;ll x=0;bool f=true;
    for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;
    for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;
    return f?x:-x;
}
void solve(){ // 暴力讨论
    int n=read();
    vector<PII> s(n);
    vector<int> v={0,1,2,3,4};
    function<ll(ll,ll,ll)> check=[&](ll x,ll y,ll c)->ll{
        if(c==1)return x;
        if(c==2)return y;
        if(c==3)return x+y;
        return x-y;
    };
    for(int i=0;i<n;i++)
        s[i].first=read()*2,s[i].second=read()*2;
    function<PII(int,int,PII,PII)> _hack=[&](int a,int b,PII x,PII y)->PII{
        if(a>b)swap(a,b),swap(x,y);
        if(a==1&&b==2)return {x.first,y.second};
        if(a==1&&b==3)return {x.first,y.first+y.second-x.first};
        if(a==1&&b==4)return {x.first,x.first-(y.first-y.second)};
        if(a==2&&b==3)return {y.first+y.second-x.second,x.second};
        if(a==2&&b==4)return {(y.first-y.second)+x.second,x.second};
        if(a==3&&b==4)return {(x.first+x.second+y.first-y.second)/2,x.first+x.second-(x.first+x.second+y.first-y.second)/2};
    };
    do{
        int idx=0;
        vector<ll> p(5);
        vector<PII> c; 
        for(int i=0;i<=n;i++){
            if(i==n)return cout<<"YES\n",void();
            int flag=true;
            for(int j=1;j<=idx;j++){
                if(p[v[j]]==check(s[i].first,s[i].second,v[j]))
                    flag=false;
            }
            if(flag){
                idx++;
                c.push_back({s[i].first,s[i].second});
                if(idx>=5)break;
                p[v[idx]]=check(s[i].first,s[i].second,v[idx]);
                if(c.size()==2){
                    PII var=_hack(v[1],v[2],c[0],c[1]);
                    idx++;
                    p[v[idx]]=check(var.first,var.second,v[idx]);
                    idx++;
                    p[v[idx]]=check(var.first,var.second,v[idx]);
                }
            }
        }
    }while(next_permutation(v.begin()+1,v.end()));
    cout<<"NO\n";
}

int main(){
    int T=1;
    T=read();
    for(int i=1;i<=T;i++)solve();

    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
  • 相关阅读:
    图像处理ASIC设计方法 笔记2 图像边界镜像处理
    ES中个别字段属性说明
    Nacos和Eureka的区别
    【手把手带你学JavaSE】全方面带你了解异常
    档案数字化管理能够带来哪些好处
    WPF中非递归（无后台代码）动态实现TreeView
    链表题目 : 链表的中间结点 与 链表中倒数第k个结点(leetcode 和 牛客)
    命令行下Git调用IDEA的diff功能
    使用 message buffer 传递数据
    【机器学习】数值分析02——任意方程求根
  • 原文地址：https://blog.csdn.net/weixin_51937688/article/details/125877799