陕西省赛第十届重现复盘

我是个菜菜。

按个人认为难度进行排名。

B Card

• 可以知道如果一个数翻转后增加的价值为 $b-a$ ，那么可以很容易的想到要选对增加价值降序排列后前 $k$ 个数进行翻转。注意，由于一定要选满 $k$ 个数，所以存在价值减少的情况。
• 计算出所有数翻转后的价值增量 $b_i-a_i$ 和翻转前价值总和 $\sum _{i-1}^n a$，对于每一次询问，选择前 $k$ 个可以选择的数，答案则为 $\sum _{i=1}^n a+\sum _{j=1}^k(b_j-a_j)$ ，此处 $j=1..k$ 指可以选择的前 $j$ 个数。
• 如果直接遍历会 TLE 。事实上由于 $k$ 在每次询问时固定，可以选择提前计算出前 $k$ 个数中不能选择的个数记为 $t$，再从后面 $n-k$ 个数中遍历选择 $t$ 个数即可。

//@HoshiuZ
#include<bits/stdc++.h>
#define N 100010
#define ll long long 

using namespace std;

int n,k,q,m,id[N],pos[N];
ll a[N],b[N];

struct node{
    int pos;
    ll val;
    bool operator < (const node &x) const{
        return val>x.val;
    }
}c[N];

ll sum=0,S=0;
bool vh[N];
void work() {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) sum+=a[i];
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
    for(int i=1;i<=n;i++) {
        c[i].val=b[i]-a[i];
        c[i].pos=i;
    }
    sort(c+1,c+n+1);
    for(int i=1;i<=k;i++) S+=c[i].val;
    for(int i=1;i<=n;i++) pos[c[i].pos]=i;
    scanf("%d",&q);
    for(int i=1;i<=q;i++) {
        scanf("%d",&m);
        for(int j=1;j<=m;j++) scanf("%d",&id[j]);
        int cnt=0;
        ll tS=S;
        for(int j=1;j<=m;j++) {
            if(pos[id[j]]<=k) {
                cnt++;
                tS-=c[pos[id[j]]].val;
            }
            vh[id[j]]=true;
        }
        int now=0;
        for(int j=k+1;j<=n;j++) {
            if(now==cnt) break;
            if(!vh[c[j].pos]) {
                now++;
                tS+=c[j].val;
            }
        }
        printf("%lld\n",sum+tS);
        for(int j=1;j<=m;j++) vh[id[j]]=false; 
    }
}  

int main() {
    work();
    return 0;
}

//@Dreamskycx
//Waiting...