题解 |

首次AK纪念嘿嘿

A

签到，手速题

B

显然平摊成1后sum最小

void solve(){
    int m;
    cin>>m;
    if(m>2){
        cout<<m<<endl;
        for(int i=1;i<=m;++i){
            cout<<1<<' ';
        }
    }
    else {
        cout<<1<<endl;
        cout<<m;
    }
}

C

首先排序 n<10时，直接输出即可 n>=10，按照0到9往里填，每隔10个填一次，O(N)

const int maxn=2e5+10;
int a[maxn];
int b[maxn],n,kk=1;
void tian(int k){
    if(!k)k+=10;
    for(int i=k;i<=n;i+=10){
        b[i]=a[kk];
        kk++;
    }
}
void solve(){
	cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
//         a[i].pos=i;
    }
    sort(a+1,a+1+n);
//     cout<<a[1].val<<endl;
    if(n<10){
        for(int i=1;i<=n;++i){
            cout<<a[i]<<' ';
        }
    }
    else{
        for(int i=0;i<=9;++i){
            tian(i);
        }
        for(int i=1;i<=n;++i){
            cout<<b[i]<<' ';
        }
    }
}

D

首先，我们通过线性筛预处理，发现maxn开到3e6~5e6左右时包含的质数超过了本题最大n 2e5，而这个预处理的复杂度是可以接受的 考虑极限情况，即给定数组全为不同的质数，也不会超过2e5个， 所以我们只需以k=0(prime[0]=2)为基准点，出现的数都用标记一下，出现当前最小质数时prime[k]时令k++至第一个未出现的，由于k和i都只会向前，所以这个复杂度类似于双指针，O(2*n);

const int maxn=5e6+10;
int prime[maxn],a[maxn],ans[maxn];
bool mp[maxn]={0};
unordered_map<int,bool> st;
int read(){
    int x=0;
    char c=getchar();
    while(c>='0'&&c<='9'){
        x=(x*10)+(c^48);
        c=getchar();
    }
    return x;
}
void init(){
    mp[0]=mp[1]=1;
    int m=maxn-10;
    int k=0;
    for(int i=2;i<=m;++i){
        if(!mp[i])prime[k++]=i;
        for(int j=0;j<k&&i*prime[j]<=m;++j){
            mp[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
//     cout<<k<<endl;
}
void solve(){
    init();
    int n,q,k=0,x;
// 	cin>>n>>q;
    n=read(),q=read();
    for(int i=1;i<=n;++i){
//         cin>>a[i];
        a[i]=read();
    }
    ans[0]=prime[k];
    for(int i=1;i<=n;++i){
        if(a[i]==prime[k]){
            ++k;
            while(st[prime[k]])++k;
            ans[i]=prime[k];
        }
        else{
            ans[i]=prime[k];
        }
        st[a[i]]=1;
    }
    while(q--){
//         cin>>x;
        x=read();
        cout<<ans[x]<<endl;
    }
}

E

大水题，个人认为应该和C换换 ZZ贡献固定，只需保存所有两个大Z中间的小z数，尽量用k减即可

F

将花费视作边权 坑点:变化属性后影响后续边权 解释:实际上边权只有两种：相同时为min(x,y+z),不同时为min(y,x+z)，因为变化是除了当前点所有一起变的 套最短路板子即可