---

前言
补题记录+题解
赛时过的题就不写题解了，没过的写写题解。
做题情况：

• AtCoder Beginner Contest 416（2025.7.26）
  现场完成：A题
  赛后补题：B/C题

题目传送门

A Vacation Validation

#include<bits/stdc++.h>
using namespace std;
#define int long longsigned main(){int n,l,r;cin>>n>>l>>r;string s;cin>>s;int f=1;for(int i=l-1;i<r;i++){if(s[i]!='o'){f=0;break;}}if(f) cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}

---

B 1D Akari（补）

//思路：从左到右遍历，记一个f初始为1，遇到非'#'的位置且f=1可以填'o'，然后f=0，否则遇到'#'则f=1。 
#include<bits/stdc++.h>
using namespace std;
#define int long longsigned main(){string s;cin>>s;int l=s.size();bool f=true;for(int i=0;i<l;i++){if(s[i]!='#'){if(f){s[i]='o';f=false;}else s[i]='.';}else f=true;}cout<<s<<endl;return 0;
}

---

C Concat (X-th)（补）

题目考查

递归

题意简述

给定N个字符串S1,…,SN​构造长度为K（K已知）的序列A1,…,AK，定义字符串f(A1​,…,AK​)为SA1+SA2+⋯+SAK（此处+表示字符串连接操作）
当所有NK个序列对应的f(A1​,…,AK​)按字典序排序后，请找出其中第X小的字符串。

解法思路 ：

因为数据范围不大，所以递归模拟一遍所有排列方式，再排个序就行。

AC代码

//递归 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=15;
int n,k,x;
vector<string> s(N),t;void f(int num,string ss){if(num==k+1){t.push_back(ss);return ;}for(int i=0;i<n;i++) f(num+1,ss+s[i]);
}signed main(){cin>>n>>k>>x;for(int i=0;i<n;i++) cin>>s[i];f(1,"");sort(t.begin(),t.end());//字典序排序cout<<t[x-1]<<endl;return 0;
}

---

D Match, Mod, Minimize 2（补）

题目分数/评级

400分

题目考查

双指针

时间复杂度

O（nlogn）
原因：

• 输入：O（n）
• sort遍历；nlogn
• 双指针：O（n）（原因：j没回退）
• 输出：O(1)

题意简述

给两个长度均为n的无序数组a和b，给定一个正整数m，要求重排a数组之后，求∑​(1到n)((ai​+bi​)mod m)的最小值

• 0≤ai​,bi​< m

解法思路 ：

由题给的范围可知，(ai+bi)%m等价于ai+bi-m ，整体看起来，∑​(1到n)((Ai​+Bi​)modM)等价于 ∑​(1到n)(((ai​+bi)-m*k)。想要结果最小，只需要让k尽可能大就行。即只需要让ai+bi>=m的组合尽可能多就行
步骤：

• 分别存入a和b并排序
• 用双指针遍历a和b，一个从a的头一个从b的尾，寻找ai+bi>=m的数量，并k++
• 输出∑​(1到n)(ai​+bi​)-k*m即可

AC代码

//思路：(ai+bi)%M->ai+bi-M 
#include<bits/stdc++.h>
using namespace std;
#define int long longsigned main(){int T;cin>>T;while(T--){int n,m,sum=0;cin>>n>>m;vector<int> a(n+1),b(n+1);for(int i=1;i<=n;i++){//存入 cin>>a[i];sum+=a[i];}for(int i=1;i<=n;i++){cin>>b[i];sum+=b[i];}sort(a.begin(),a.end());sort(b.begin(),b.end());//		for(int i=1;i<=n;i++) cout<<a[i]<<" ";
//		cout<<endl;
//		for(int i=1;i<=n;i++) cout<<b[i]<<" ";
//		cout<<endl;int k=0;for(int i=n,j=1;j<=n&&i>=1;i--){//双指针while(j<=n&&a[i]+b[j]<m) j++;if(j>n) break;k++,j++;}cout<<sum-(k*m)<<endl;}return 0;
}

---

总结

记录一个菜鸡的成长——如有疏漏欢迎指正