1、2题过于简单不展示

T3最大MEX值

正确代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    //freopen("C.in","r",stdin);
    //freopen("C.out","w",stdout);
    int n,k;
    cin>>n>>k;
    vector<int> a(n);
    unordered_set<int> e;
    for (int i=0;i<n;i++){
        cin>>a[i];
        e.insert(a[i]);
    }
    int mex=0;
    while(e.count(mex)&&mex<k){
        mex++;
    }
    cout<<mex;
    return 0;
}

T4标记

解决方案

设$g = gcd(N, D)$，则标记过程会形成g条独立的链：

• 每条链的长度为$N/g$
• 第i条链的起始点为$i (0 ≤ i < g)$
• 每条链内部的标记顺序是等差数列，公差为$D mod N$因 此，第K次标记的位置可以表示为：
• 链编号：$(K-1)$
• 链内位置：$(K-1)/g * D$
• 最终位置 = 链编号 + 链内位置

正确代码

#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
int main(){
    //freopen("D.in","r",stdin);
    //freopen("D.out","w",stdout);
    int t;
    cin>>t;
    while(t--){
        long long n,d,k;
        cin>>n>>d>>k;
        k--;
        long long g=gcd(n,d);
        long long m=n/g;
        long long c=k/m;
        long long p=(k%m*d+c)%n;
        cout<<p<<endl;
    }
    return 0;
}

T5构成回文

解决方案

正确代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int> p[N];
int main(){
    //freopen("E.in","r",stdin);
    //freopen("E.out","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        p[x].push_back(i);
    }
    long long t=0;
    for(int k=1;k<=n;k++){
        t+=1LL*(n-k+1)*(k/2);
    }
    for(int x=1;x<=n;x++){
        if(p[x].size()==0) continue;
        int l=0,r=p[x].size()-1;
        while(l<r){
            if(p[x][l]<n-p[x][r]+1)
                t-=1LL*(r-l)*p[x][l],l++;
            else
                t-=1LL*(r-l)*(n-p[x][r]+1),r--;
        }
    }
    cout<<t;
    return 0;
}

注：所有freopen已注释