---

前言
補題記錄+題解
賽時過的題就不寫題解了，沒過的寫寫題解。
做題情況：

• 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;
}

---

總結

記錄一個菜雞的成長——如有疏漏歡迎指正