【非官方题解/AKer】巅峰赛#20题解

arrowpoint

2025-04-27 23:15:57

发布于：广东

23阅读

0回复

0点赞

T1：简单模拟，只需要检测到 | 后输出后面读到的所有内容即可。

个人难度：红

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 10005;
int n,m,a[N];
char s[N];

signed main(){
	ios::sync_with_stdio(false);
	cin>>(s+1);
	n = strlen(s+1);
	bool flag = 0;
	for(int i=1;i<=n;i++){
		if(flag) cout<<s[i];
		if(s[i]=='|') flag = 1;
	}
	
	return 0;
}

T2：构造题。

个人难度：橙

首先不考虑封印格子的情况，容易想到最佳策略是填充一条对角线上的所有格子，不难证明不存在更优的填充方案。

(画图软件画的，略有抽象)

接下来考虑封印的情况。若 $n$ 为偶数，由于两条对角线没有交点，因此封印一条对角线上的点仍可以使用另一条对角线，无影响。

若 $n$ 为奇数，则可以封印两条对角线的交点。此时我们这样构造。

const int N = 10005;
int n,m,a[N];
int k;

signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>k;
	if(n==1){
		cout<<"No";
		return 0;
	}
  if(k>=n) cout<<"Yes";
  else cout<<"No";	
	
	return 0;
}

T3：模拟题。

个人难度：黄

考虑平局的分数一定形如 $(0,0),(1,1),(2,2),...,(n,n)$ 。因此我们可以维护一个当前到达的最高的一个平局分数，暴力模拟即可。

注意若当前已经是一个平局状况，要防止重复统计，即将维护的那个分数 $+1$ 。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e6+10;
int n,m,a[N],b[N];

signed main(){
	ios::sync_with_stdio(false);
	cin>>n;
	int tmp = 0,ans = 0;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		if(tmp<=min(a[i],b[i])){
			ans += min(a[i],b[i])-tmp+1;
		}
		if(a[i]==b[i]) tmp = a[i]+1;
		else tmp = max(a[i],b[i]);
	}
	cout<<ans;
	
	return 0;
}

T4/T6：诈骗题/题目性质题

个人难度：绿

注意到 $f(x) = |a^c-b^c| = |(a-b)(a^{c-1}+a^{c-2}b+a^{c-3}b^2+...+ab^{c-2}+b^{c-1})|$ 。

题目中 $a,b,c$ 都是正奇数，因此因式分解后面的一项相当于 $c$ 个奇数相加，即奇数个奇数相加，而这必定也是奇数。不难证明一个数乘以奇数后二进制后 $0$ 的个数不变，所以 $f(x)$ 的美丽度只与 $a-b$ 有关。

因此我们只需要预处理前 $n$ 个正奇数两两作差所有不同的数的美丽度即可。

接着考虑期望， $E(X) = \sum p_ix_i$ ，而所有的 $p_i$ 相等，而总情况数为 $A_n^3$ 。但是我们注意到结果与 $c$ 取什么和 $a,b$ 的顺序无关。因此我们可以规定 $a<b$ 的同时不枚举 $c$ 。这样 $E(X) = SUM(X)/C_n^2$ ， $SUM(X) = \sum_{i=1}^{n-1} (n-i-1)\times g(2n)$ ，其中 $g(x)$ 为 $x$ 的美丽度。

inline int get(int x){
	int res = 0;
	while(!(x&1)){
		x >>= 1;
		res++;
	}
	return res;
}

signed main(){
	ios::sync_with_stdio(false);
	for(int i=2;i<=2e6+2;i+=2){
		num[i] = get(i);
		pre[i] = pre[i-2]+num[i];
	}
	ans[2] = 1;
	for(int i=3;i<=1e6;i++){
		ans[i] = (ans[i-1]+pre[2*i-2])%M;
	}
	cin>>t;
	while(t--){
		cin>>n;
		int tmp = qpow(((n*(n-1)%M)*qpow(2,M-2)%M),M-2);
		cout<<(ans[n]*tmp)%M<<endl;
	}
	
	return 0;
}

T5：大模拟
首先分析题目，不难发现无论怎样操作，每一行，每一列的总障碍数都不变，都只能改变它们的相对位置。

不难注意到一种情况：如果有一个点的所在行或者所在列都有障碍物，那么我们可以先把这两个障碍物移动到与它相邻的位置，再把这个整体移到某一个角落（这个角落位置根据移动的两个障碍物与这个点的相对方位决定）。如对于

.....X
.#....
......
......
.s..#.
......

其中满足要求的点为 $s$ 。那么我们可以先交换第 $3,5$ 列，第 $2,4$ 行，使两个障碍物与之相邻。

.....X
......
......
.#....
.s#...
......

接着按顺序交换第 $(5,6),(4,5)$ 行，第 $(1,2),(2,3)$ 列，即可将 $s$ 卡到角落。

.....X
......
......
......
#.....
s#....

最后将 Alice 放到 $s$ 即可。不难发现若有一个点的所在行或者所在列都有障碍物，则一定可以这样构造出特定解。

那么如果没有这样的点呢？这就意味着任意两个障碍物所对应的矩形的顶点都有障碍物。简单推导后可以知道，在这种情况下，每一行以及每一列要么没有任何障碍物，要么障碍物排布完全相同。

就像这样：

.....X
##..#.
##..#.
......
##..#.
......

在这种情况下，如果没有某一行或者某一列全是障碍物，那么答案必定是 $No$ 。这是因为无论你怎样操作，都会留有空隙。

而如果有呢？

那我们可以这样：在其中找一个不与 $X$ 在同一行及同一列的点，将这个点所在行/列移动到第 $1$ 行/列，将 $X$ 所在行/列移动到最后一行/列。这样全是障碍物的那一行/列必定在中间。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 1e6+10;
int n,m;
char s[N];
int sx,sy;
int tx1,ty1,tx2,ty2;
int nex,ney;
int cnt = 0;
vector<char> vec[N];
vector<int> line[N],col[N];
struct node{
	int t,x,y;
}op[N];
struct edge{
	int x,y;
};
int id,idx;

inline void init(){
	for(int i=0;i<=n+1;i++){
		for(int j=0;j<=m+1;j++){
			line[i][j] = col[i][j] = 0;
		}
	}
}

// find函数的作用是寻找满足要求的点
inline bool find(int d1,int d2){ // 此处如果开4个数组可以简洁非常多，只用一次循环。但是那样会MLE。所以将2个数组用4次以省下一半空间
	if(d1==0){
		if(d2==0){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=m;j++){
					line[i][j] = line[i][j-1],col[i][j] = col[i-1][j];
					if(vec[i][j]=='#') line[i][j] = j,col[i][j] = i;
				}
			}
		}
		else{
			for(int i=1;i<=n;i++){
				for(int j=m;j>=1;j--){
					line[i][j] = line[i][j+1],col[i][j] = col[i-1][j];
					if(vec[i][j]=='#') line[i][j] = j,col[i][j] = i;
				}
			}
		}
	}
	else{
		if(d2==0){
			for(int i=n;i>=1;i--){
				for(int j=1;j<=m;j++){
					line[i][j] = line[i][j-1],col[i][j] = col[i+1][j];
					if(vec[i][j]=='#') line[i][j] = j,col[i][j] = i;
				}
			}
		}
		else{
			for(int i=n;i>=1;i--){
				for(int j=m;j>=1;j--){
					line[i][j] = line[i][j+1],col[i][j] = col[i+1][j];
					if(vec[i][j]=='#') line[i][j] = j,col[i][j] = i;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(vec[i][j]=='X' || vec[i][j]=='#') continue;
			if(line[i][j] && col[i][j]){
				tx1 = i,ty1 = line[i][j];
				tx2 = col[i][j],ty2 = j;
				return 1;
			}
		}
	}
	return 0;
}

void pr(){ // 输出方案
	cout<<"Yes\n"<<idx<<endl;
	for(int i=1;i<=idx;i++){
		if(op[i].t==0) cout<<"l ";
		else cout<<"r ";
		cout<<op[i].x<<' '<<op[i].y<<endl;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int j=0;j<=m+1;j++){
		line[0].push_back(0);
		col[0].push_back(0);
	}
	int r1,r2;
	for(int i=1;i<=n;i++){
		cin>>(s+1);
		vec[i].push_back(' ');
		line[i].push_back(0);
		col[i].push_back(0);
		for(int j=1;j<=m;j++){
			vec[i].push_back(s[j]);
			line[i].push_back(0);
			col[i].push_back(0);
			if(s[j]=='X'){
				sx = i,sy = j;
			}
			if(s[j]=='#'){
				++cnt;
				if(cnt==1){
					r1 = i,r2 = j;
				}
			}
			if(s[j]=='.'){
				nex = i,ney = j;
			}
		}
		line[i].push_back(0);
		col[i].push_back(0);
find(0,0),find(0,1),find(1,0),find(1,1);
		if(id1){
			for(int i=1;i<=n;i++){
				if(i==sx) continue;
				for(int j=1;j<=m;j++){
					if(vec[i][j]=='.'){
						nex = i,ney = j;
						flag = 1;
						break;
					}
				}
				if(flag) break;
			}
		}
		if(flag){
			if(nex!=1){
				op[++idx] = {1,nex,1};
				if(sx==1) sx = nex;
				nex = 1;
			}
			if(sx!=n){
				op[++idx] = {1,sx,n};
			}
			pr();
			cout<<nex<<' '<<ney;
			return 0;
		}
		flag = 0;
		if(id2){
			for(int j=1;j<=m;j++){
				if(j==sy) continue;
				for(int i=1;i<=n;i++){
					if(vec[i][j]=='.'){
						nex = i,ney = j;
						flag = 1;
						break;
					}
				}
				if(flag) break;
			}
		}
		if(flag){
			if(ney!=1){
				op[++idx] = {0,ney,1};
				if(sy==1) sy = ney;
				ney = 1;
			}
			if(sy!=m){
				op[++idx] = {0,sy,m};
			}	
			pr();
			cout<<nex<<' '<<ney;
			return 0;
		}
		cout<<"No";
		return 0;
	}
  // 否则按第一种情况构造解
	int c1,c2;
	if(abs(ty1-ty2)!=1){
		if(ty1<ty2){
			c1 = 1;
			op[++idx] = {0,ty1,ty2-1};
		}
else{
			c1 = 2;
			op[++idx] = {0,ty1,ty2+1};
		}
	}
	else{
		if(ty1>ty2) c1 = 2;
		else c1 = 1;
	}
	if(abs(tx1-tx2)!=1){
		if(tx1>tx2){
			c2 = 1;
			op[++idx] = {1,tx2,tx1-1};
		}
		else{
			c2 = 2;
			op[++idx] = {1,tx2,tx1+1};
		}
	}
	else{
		if(tx1>tx2) c2 = 1;
		else c2 = 2;
	}
	if(c1==1){
		if(ty2!=m) op[++idx] = {0,ty2,m},op[++idx] = {0,ty2-1,m-1};
	}
	else{
		if(ty2!=1) op[++idx] = {0,ty2,1},op[++idx] = {0,ty2+1,2};
	}
	if(c2==1){
		if(tx1!=n) op[++idx] = {1,tx1,n},op[++idx] = {1,tx1-1,n-1};
	}
	else{
		if(tx1!=1) op[++idx] = {1,tx1,1},op[++idx] = {1,tx1+1,2};
	}
	for(int i=1;i<=idx;i++){
		assert(op[i].x!=op[i].y);
	}
	pr();
	if(c2==1){
		if(c1==1) cout<<n<<' '<<m;
		else cout<<n<<' '<<1;
	}
	else{
		if(c1==1) cout<<1<<' '<<m;
		else cout<<1<<' '<<1;	
	}	
	
	return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 4

arrowpoint
顶

3小时前来自广东
0
‮队团加不）童帅_者仇复
%%%

3小时前来自广东
0
‮队团加不）童帅_者仇复
顶

3小时前来自广东
0
arrowpoint
在手机上操作的，可能代码粘贴有误，不过意思大家应该都能理解

16小时前来自广东
0

全部评论 4

热门讨论