【非官方题解/AKer】巅峰赛#20题解
2025-04-27 23:15:57
发布于：广东
184阅读
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：构造题。
个人难度：橙
首先不考虑封印格子的情况，容易想到最佳策略是填充一条对角线上的所有格子，不难证明不存在更优的填充方案。
(画图软件画的，略有抽象)
接下来考虑封印的情况。若 为偶数，由于两条对角线没有交点，因此封印一条对角线上的点仍可以使用另一条对角线，无影响。
若 为奇数，则可以封印两条对角线的交点。此时我们这样构造。
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：模拟题。
个人难度：黄
考虑平局的分数一定形如 。因此我们可以维护一个当前到达的最高的一个平局分数，暴力模拟即可。
注意若当前已经是一个平局状况，要防止重复统计，即将维护的那个分数 。
#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：诈骗题/题目性质题
个人难度：绿
注意到 。
题目中 都是正奇数，因此因式分解后面的一项相当于 个 奇数相加，即奇数个奇数相加，而这必定也是奇数。不难证明一个数乘以奇数后二进制后 的个数不变，所以 的美丽度只与 有关。
因此我们只需要预处理前 个正奇数两两作差所有不同的数的美丽度即可。
接着考虑期望，，而所有的 相等，而总情况数为 。但是我们注意到结果与 取什么和 的顺序无关。因此我们可以规定 的同时不枚举 。这样 ，，其中 为 的美丽度。
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..#.
......
其中满足要求的点为 。那么我们可以先交换第 列，第 行，使两个障碍物与之相邻。
.....X
......
......
.#....
.s#...
......
接着按顺序交换第 行，第 列，即可将 卡到角落。
.....X
......
......
......
#.....
s#....
最后将 Alice 放到 即可。不难发现若有一个点的所在行或者所在列都有障碍物，则一定可以这样构造出特定解。
那么如果没有这样的点呢？这就意味着任意两个障碍物所对应的矩形的顶点都有障碍物。简单推导后可以知道，在这种情况下，每一行以及每一列要么没有任何障碍物，要么障碍物排布完全相同。
就像这样：
.....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;
}
有帮助，赞一个