做题记录2.0

这里的题目相对会更难一些。

CF1856D More Wrong

题意

给定一个长度为 $n$ 的排列。每次询问一个区间 $[l,r]$，代价为 $(r-l)^2$，返回该区间内逆序对的数量。要求找出区间内最大元素的下标，总代价不超过 $5\times n^2$。

数据范围：$2\leq n\leq 2000$。

题解

单独询问一个区间得到它的逆序对数量是没有什么用的，我们考虑两次询问 $[l,r-1]$ 和 $[l,r]$，如果后一次询问的返回值和前一次一样，就可以确定 $r$ 是区间 $[l,r]$ 内的最大值。但由于询问次数不多，所以我们不能固定左端点为 $1$，不断移动右端点。还需要一个更高效的询问方式。

我们考虑分治：假设我们要询问区间 $[l,r]$ 内最大值的位置，令 $m=\lfloor\dfrac{n}{2}\rfloor$。假设我们已经求出了 $[l,m]$ 的最大值的位置 $i$ 和 $[m+1,r]$ 的最大值的位置 $j$。那么我们只需要询问 $[l,j-1]$ 和 $[l,j]$，若两次返回值一样，那么最大值的位置是 $j$，否则就是 $i$。

这样的策略总次数不会超过 $4\times n^2$，可以用数学归纳法证明：

考虑上面的询问策略，当两个子区间确定后，我们还需要询问两次，其代价为

$$(j-1-l)^2+(j-l)^2\leq2\times (r-l)^2$$

设确定一个长度为 $i$ 的区间需要的次数为 $g_i$。$n=1$ 时，$g_1=0<4$。

然后求解 $g_n$，令 $m=\lceil\dfrac{n}{2}\rceil$，

$$\begin{aligned} g_n &\leq 2(n-1)^2+g_m+g_{n-m}\\ &\leq 2(n-1)^2+4(m^2+(n-m)^2)\\ &=6n^2+8m^2+2-8nm-4n\\ &\leq 4n^2+2(n-2m)^2+2-4n\\ &\leq 4n^2+2+2-4n\\ &\leq 4n^2 \end{aligned}$$

证明完毕。

代码

#include <bits/stdc++.h>
using namespace std;
int solve(int l,int r)
{
    if(l==r) return l;
    int m=(l+r)/2;
    int i=solve(l,m),j=solve(m+1,r);
    int x,y;
    if(l==j-1) x=0;
    else
    {
        cout<<"? "<<l<<' '<<j-1<<endl;
        cin>>x;
    }
    cout<<"? "<<l<<' '<<j<<endl;
    cin>>y;
    return x==y?j:i;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        int ans=solve(1,n);
        cout<<"! "<<ans<<endl;
    }
    return 0;
}

CF1799D2 Hot Start Up (hard version)

题意

有一台两个 CPU 的电脑。有 $k$ 种程序，第 $i$ 种程序需要花 $cold_i$ 时间执行，但是如果该 CPU 上一次执行的也是该程序，那么只需要花 $hot_i$ 时间（$hot_i\leq cold_i$）。

现在有一个长度为 $n$ 的序列 $a$，代表一些待执行的程序。需要按顺序执行，并且只有前一个被执行完毕，下一个才能开始被执行。求最短用时。

数据范围：$1\leq n,k\leq 3\times 10^5$。

题解

首先很容易想到一个状态：$f_{i,j,k}$ 表示处理完前 $i$ 个，CPU1上一个处理的是 $j$，CPU2上一个处理的是 $k$ 的最短用时。但这样的状态是 $O(nk^2)$ 的，显然不能通过。

可以注意到：每次执行完 $a_i$ 以后，必然有一个 CPU 处理的是 $a_i$，我们只关心另一个是什么就可以了。于是，可以减少一维状态，即 $f_{i,j}$ 表示处理完前 $i$ 个，另一个CPU 上一个处理的是 $j$ 的最短用时，可以利用滚动数组压掉一维：记转移后的为 $nf$，每次转移完将 $nf$ 赋值给 $f$ 即可。所以，转移方程可以这样写：

记当前的程序为 $x$，若上一个程序也是 $x$，

$$nf_i=\min(nf_i,f_i+hot_x)\\ nf_x=\min(nf_x,f_i+cold_x)$$

若上一个程序不是 $x$，不妨设为 $y$，

$$nf_i=\min(nf_i,f_i+cold_x)\\ nf_y=\min(nf_y,f_i+cold_x)\\ nf_y=\min(nf_y,f_x+hot_x)$$

这样我们得到了一个 $O(nk)$ 的做法。但它还需要进行优化：我们注意到，每次的操作都是全局加，全局求最值，单点修改，这可以用线段树维护。不过，也有一种不需要线段树的做法：我们维护 $mn$ 为所有 $f$ 的最小值，$s$ 为全局的增加量。若当前程序和上一个程序相同，那么 $s\leftarrow s+hot_x$，因为最小值不会发生改变。若当前程序和上一个程序不同，那么 $s\leftarrow s+cold_x$。但是 $nf_y$ 可以由 $f_x+hot_x$ 转移而来，它可能成为新的最小值，所以需要比较一下并更新。最终的答案就是 $mn+s$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int a[N],cold[N],hot[N];
ll f[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n,k;cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=k;i++) cin>>cold[i];
        for(int i=1;i<=k;i++) cin>>hot[i];
        for(int i=1;i<=k;i++) f[i]=0x3f3f3f3f;
        ll mn=0,s=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]==a[i-1]) s+=hot[a[i]];
            else
            {
                f[a[i-1]]=min(f[a[i]]+hot[a[i]],mn+cold[a[i]])-cold[a[i]];
                mn=min(mn,f[a[i-1]]);
                s+=cold[a[i]];
            }
        }
        cout<<mn+s<<'\n';
    }
    return 0;
}

CF1784B Letter Exchange

题意

有 $m$ 个人，每个人有三张卡片。卡片一共有三种，w、i、n，每种卡片各有 $m$ 张。每次操作可以选择两个人，各拿出一张卡片进行交换。求最小的操作次数，使得每个人三种卡片各拿一张。

数据范围：$2\leq m\leq 10^5$。

题解

将 win 映射为 $012$。若一个人多出卡片 $x$，缺少卡片 $y$，那么连边 $(x,y)$。

首先，我们先处理类似 $(x,y),(y,x)$ 的连边。因为只需要一次交换就使得两个人的卡片更加”均衡“。然后，剩下的边一定是$(0,1),(1,2),(2,0)$ 或者是 $(1,0),(2,1),(0,2)$。用两次交换满足三个人。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int cnt,id[150],c[3];
char rid[3];
vector<int> g[3][3];
struct node
{
    int a,b,c,d;
}ans[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    id['w']=0,id['i']=1,id['n']=2;
    rid[0]='w',rid[1]='i',rid[2]='n';
    int t;cin>>t;
    while(t--)
    {
        cnt=0;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++) g[i][j].clear();
        int n;cin>>n;
        for(int i=1;i<=n;i++)
        {
            string s;cin>>s;
            c[0]=c[1]=c[2]=0;
            for(int j=0;j<3;j++) c[id[(int)s[j]]]++;
            for(int j=0;j<3;j++)
                for(int k=0;k<3;k++)
                    if(c[j]>1&&c[k]<1) g[j][k].push_back(i); 
        }
        for(int i=0;i<3;i++)
            for(int j=i+1;j<3;j++)
            {
                while(!g[i][j].empty()&&!g[j][i].empty())
                {
                    int x=g[i][j].back(),y=g[j][i].back();
                    g[i][j].pop_back(),g[j][i].pop_back();
                    ans[++cnt]={x,i,y,j};
                }
            }
        int p=0,q=1,r=2;
        if(!g[0][2].empty()) swap(q,r);
        for(int i=0;i<(int)g[p][q].size();i++)
        {
            int x=g[p][q][i],y=g[q][r][i],z=g[r][p][i];
            ans[++cnt]={x,p,y,q};
            ans[++cnt]={y,p,z,r};
        }
        cout<<cnt<<'\n';
        for(int i=1;i<=cnt;i++) cout<<ans[i].a<<' '<<rid[ans[i].b]<<' '<<ans[i].c<<' '<<rid[ans[i].d]<<'\n';
    }
    return 0;
}

CF1772F Copy of a Copy of a Copy

题意

给出一个 $n\times m$ 的 $01$ 矩阵，每次可以进行以下两种操作之一：

• 选择一个格子，满足上下左右四个的格子都存在，且都恰好与它相反，将该格子翻转。
• 拷贝一份当前矩阵。

已知一共进行了 $k$ 次拷贝操作，现在给出得到的 $k+1$ 个矩阵，但它们的顺序被打乱了。要求找出初始的 $01$ 矩阵并给出操作序列。

数据范围：$3\leq n,m\leq 30,0\leq k\leq 100$。

题解

本题最重要的观察是：当一个格子翻转后，它不能再被翻转了，而且该翻转操作不会带来新的可翻转的格子。即在每次翻转操作后，可翻转的格子数量都会减少。所以，我们按照可翻转的格子数量进行排序，然后直接模拟求出操作序列就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=105;
int dir[4][2]={-1,0,0,1,0,-1,1,0};
char g[N][35][35];
pair<int,int> p[N];
vector<vector<int>> ans;
bool check(int t,int i,int j)
{
    for(int kk=0;kk<4;kk++)
    {
        int x=i+dir[kk][0],y=j+dir[kk][1];
        if(g[t][x][y]==g[t][i][j]) return 0;
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;cin>>n>>m>>k;
    k++;
    for(int t=1;t<=k;t++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>g[t][i][j];
    for(int t=1;t<=k;t++)
    {
        int cnt=0;
        for(int i=2;i<n;i++)
            for(int j=2;j<m;j++)
                if(check(t,i,j)) cnt++;
        p[t]={-cnt,t};
    }
    sort(p+1,p+k+1);
    for(int t=1;t<k;t++)
    {
        for(int i=2;i<n;i++)
            for(int j=2;j<m;j++)
                if(g[p[t+1].second][i][j]!=g[p[t].second][i][j]) ans.push_back({1,i,j});
        ans.push_back({2,p[t+1].second});
    }
    cout<<p[1].second<<'\n';
    cout<<ans.size()<<'\n';
    for(auto i:ans)
    {
        for(auto j:i) cout<<j<<' ';
        cout<<'\n';
    }
    return 0;
}

CF1733D2 Zero-One (Hard Version)

题意

给定两个长度为 $n$ 的 $01$ 串 $a,b$。每次操作可以选择两个位置 $l,r$，并将 $a_l,a_r$ 取反。若 $l,r$ 相邻，则此次操作的代价为 $x$，否则代价为 $y$。求将 $a$ 变成 $b$ 的最小花费，若无法将 $a$ 变成 $b$ 输出 $-1$。

数据范围：$5\leq n\leq 5000,1\leq x,y\leq 10^9$。

题解

记 $m$ 为 $a$ 和 $b$ 中不同位置的个数，若 $m$ 为奇数，显然无解。否则作以下讨论：

• $x\geq y$，若 $m=2$ 且这两个位置相邻，则答案为 $\min(x,2y)$（$n\geq 5$），否则答案为 $\dfrac{m}{2}\times y$。

• $x<y$，考虑dp：记 $f_i$ 表示前 $i$ 个不同的位置被解决所需要的最小代价。那么每个位置有两种解决办法：如果采用 $x$ 代价，即不断交换相邻的元素，那么它一定是和它前面的元素交换。若采用 $y$ 代价，即和任一位置元素交换，我们其实不关心它和谁交换，只需要知道一共有多少个数采用了这种交换方式。所以，有如下转移：$f_i=\min(f_{i-2}+x\times(pos_i-pos_{i-1}),f_{i-1}+\dfrac{y}{2})$。

  补充说明：

  1. 由于最终 $m$ 是偶数，每次前一种转移使下标增加 $2$，后一种使下标增加 $1$，所以最终采用后一种转移的位置恰好有偶数个。在实现时，可以整体乘上 $2$，避免出现分数。
  2. 有可能转移的位置会出现相邻的情况，但这一定是不优的。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5005;
ll f[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        ll n,x,y;cin>>n>>x>>y;
        string s1,s2;cin>>s1>>s2;
        vector<int> diff;
        for(int i=0;i<n;i++)
            if(s1[i]!=s2[i]) diff.push_back(i);
        int m=(int)diff.size();
        if(m&1) cout<<-1<<'\n';
        else
        {
            if(x>=y)
            {
                if(m==2&&diff[1]-diff[0]==1) cout<<min(x,2*y)<<'\n';
                else cout<<m/2*y<<'\n';
            }
            else
            {
                for(int i=0;i<=m;i++) f[i]=1e18;
                f[0]=0,f[1]=y;
                for(int i=2;i<=m;i++) f[i]=min(f[i-2]+2*x*(diff[i-1]-diff[i-2]),f[i-1]+y);
                cout<<f[m]/2<<'\n';
            }
        }
    }
    return 0;
}

CF1700D River Locks

题意

有 $n$ 个水缸，每个水缸上面有一条管道，每秒会放一单位的水。当一个水缸装满水后，水会流入下一个水缸，若最后一个水缸装满水，水就浪费了。有 $q$ 次询问，每次询问至少要打开多少管道才能在 $t$ 秒内装满所有水缸，若不能则输出 $-1$。

数据范围：$1\leq n,q\leq 2\times10^5$。

题解

首先考虑一个必要条件，前 $i$ 个水缸只能由前 $i$ 个管道供水，所以 $\lceil\dfrac{\sum\limits_{j=1}^iv_i}{i}\rceil\leq t$。然后，我们转换一下思维：对于打开 $k$ 个管道，这样来看：先打开第一个管道 $t$ 秒，然后打开第二个，依此类推。所以，只有最后一个管道的水会被浪费，直接用 $\lceil\dfrac{\sum v}{t}\rceil$ 作为答案即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    ll mx=0,sum=0;
    for(int i=1;i<=n;i++)
    {
        int v;cin>>v;
        sum+=v;
        mx=max(mx,(sum-1)/i+1);
    }
    int q;cin>>q;
    while(q--)
    {
        int t;cin>>t;
        if(t<mx) cout<<-1<<'\n';
        else cout<<(sum-1)/t+1<<'\n';
    }
    return 0;
}

CF1854B Earn or Unlock

题意

有 $n$ 张牌，第 $i$ 张牌上有数字 $a_i$。初始只有第一张牌解锁，每次可以执行以下两种操作之一：

• 解锁前 $a_i$ 张未解锁的牌（不超过剩余未解锁牌的总数）
• 获得 $a_i$ 分数

操作完后丢弃这张牌。当牌堆里没有解锁的牌时，游戏结束。要求最大化得分。

数据范围：$1\leq n\leq 10^5,0\leq a_i\leq 10^5$。

题解

一个重要的观察是：若一共解锁了 $k$ 张牌，那么答案是 $\sum\limits_{i=1}^ka_i-k+1$。那么，我们只需要判断是否能恰好解锁 $k$ 张牌。设 $f_i$ 表示恰好能解锁 $i$ 张牌，那么转移为 $f|=f<<a_i$。为了避免使用未解锁的牌，计算完后需要将 $f_i$ 置为 $0$。利用bitset优化转移。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll ans,a[N];
bitset<N> f;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    f[1]=1;
    for(int i=1;i<=n;i++)
    {   
        cin>>a[i];
        f|=f<<a[i];
        a[i]+=a[i-1];
        if(f[i]) ans=max(ans,a[i]-i+1);
        f[i]=0;
    }
    for(int i=n+1;i<=2*n;i++)
        if(f[i]) ans=max(ans,a[n]-i+1);
    cout<<ans<<'\n';
    return 0;
}

CF1858D Trees and Segments

题意

给出一个长度为 $n$ 的 $01$ 串，使得最长 $0$ 连续段长度 $\times a$ 加上最长 $1$ 连续段长度最大。

数据范围：$1\leq n\leq 3000,0\leq k\leq n$。

题解

考虑枚举最长的 $0$ 的连续段记作 $[l,r]$，那么剩余的次数为 $k$ 减去连续段中 $1$ 的数量。那么我们需要在 $[1,l-1]$ 或 $[r+1,n]$ 中选一个区间 $[l',r']$，使得 $[l',r']$ 中 $0$ 的个数不超过剩余次数并且长度最长。

可以预处理出 $f_{i,j},g_{i,j}$ 分别表示以 $i$ 为起点的子串，以 $i$ 结尾的子串满足 $0$ 的个数不超过 $j$ 的最大长度。

那么枚举 $[l,r]$，剩余次数为 $k'$，最长 $1$ 的连续段长度为

$$\max\{\max_{i=r+1}^nf_{i,k'},\max_{i=1}^{l-1}g_{i,k'}\}$$

记为 $ans_i$。那么答案就是 $\max\{a\times i+ans_i\}$。注意需要判断 $ans_i$ 能否取到。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3005;
int f[N][N],g[N][N],ans[N];
bool vis[N];
string s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n,k;cin>>n>>k>>s;
        for(int i=1;i<=n;i++) ans[i]=vis[i]=0;
        for(int i=0;i<=k;i++) f[n+1][i]=0;
        for(int i=1;i<=n;i++)
        {
            int cur=0,x=i-1;
            for(int j=0;j<=k;j++)
            {
                while(cur<j+1&&x<=n)
                {
                    x++;
                    if(s[x-1]=='0') cur++;
                }
                f[i][j]=x-i;
            }
        }
        for(int i=n;i;i--)
            for(int j=0;j<=k;j++)
                f[i][j]=max(f[i][j],f[i+1][j]);
        for(int i=n;i;i--)
        {
            int cur=0,x=i+1;
            for(int j=0;j<=k;j++)
            {
                while(cur<j+1&&x>=1)
                {
                    x--;
                    if(s[x-1]=='0') cur++;
                }
                g[i][j]=i-x;
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=0;j<=k;j++)
                g[i][j]=max(g[i][j],g[i-1][j]);
        vis[0]=1;
        ans[0]=max(g[n][k],f[1][k]);
        for(int i=1;i<=n;i++)
        {
            int tot=0;
            for(int j=i;j<=n;j++)
            {
                if(s[j-1]=='1') tot++;
                if(tot>k) break;
                ans[j-i+1]=max(ans[j-i+1],f[j+1][k-tot]);
                ans[j-i+1]=max(ans[j-i+1],g[i-1][k-tot]);
                vis[j-i+1]=1; 
            }
        }
        for(int i=1;i<=n;i++)
        {
            ll cur=0;
            for(int j=0;j<=n;j++)
            {
                if(!vis[j]) continue;
                cur=max(cur,1ll*i*j+ans[j]);
            }
            cout<<cur<<" \n"[i==n];
        }
    }
    return 0;
}

CF1848F Vika and Wiki

题意

给出一个长度为 $n$ 的数组 $a$。每次操作同时将所有 $a_i$ 置为 $a_i\oplus a_{(i+1)\bmod n}$。问最少多少次操作后数组变为全 $0$。

数据范围：$1\leq n\leq 2^{20}$，$n$ 是 $2$ 的幂次。

题解

记 $f_{i,j}$ 为 $a_i$ 第 $j$ 次操作后得到的数，容易发现 $f_{i,2^k}=f_{i,0}\oplus f_{i+2^k,0}$。那么我们可以利用倍增的思想，按二进制位从高到低枚举，求出不能变为全 $0$ 的最大操作次数。具体地，我们从高到低枚举 $k$，如果移动 $2^k$ 可以变为全零，就不管，否则我们给答案加上 $2^k$，并置 $a_i=a_i\oplus a_{(i+2^k)\bmod n}$。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=(1<<20)+5;
int a[N],b[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    int cnt=0;
    for(int i=0;i<n;i++) 
    {
        cin>>a[i];
        if(!a[i]) cnt++;
    }
    if(cnt==n)
    {
        cout<<0<<'\n';
        return 0;
    }
    int k=log2(n),ans=0;
    for(int i=k-1;i>=0;i--)
    {
        int cnt=0;
        for(int j=0;j<n;j++)
        {
            b[j]=a[j]^a[(j+(1<<i))%n];
            if(!b[j]) cnt++;
        }
        if(cnt<n)
        {
            ans+=(1<<i);
            for(int j=0;j<n;j++) a[j]=b[j];
        }
    }
    cout<<ans+1<<'\n';
    return 0;
}

CF1619H Permutation and Queries

题意

给出一个长度为 $n$ 的排列 $p$。每次执行以下两种操作之一：

• 交换 $p_x,p_y$
• 询问在执行 $k$ 次 $i\leftarrow p_i$ 后 $i$ 的值

数据范围：$1\leq n,q\leq 10^5$。

题解

可能会想到倍增，但是每次修改的时候不好更新答案。而题目1e5的数据开了4s时限，所以很有可能是个根号做法。

我们对每个点维护跳 $k$ 步能跳到的位置，每次交换操作只需要更新 $x,y$ 前 $k$ 个位置，复杂度为 $O(k)$，每次查询复杂度为 $O(\dfrac{n}{k})$，取 $k=\sqrt{n}$ 时最优。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,q,p[N],pre[N],nxt[N],jmp[N];
void update(int x)
{
    jmp[x]=x;
    for(int j=1;j<=m;j++) jmp[x]=nxt[jmp[x]];
    for(int j=1,k=pre[x];j<m;j++,k=pre[k]) jmp[k]=pre[jmp[nxt[k]]];
}
void update(int x,int y)
{
    swap(pre[nxt[x]],pre[nxt[y]]);
    swap(nxt[x],nxt[y]);
    update(x),update(y);
}
int query(int x,int y)
{
    int ans=x;
    while(y>=m)
    {
        ans=jmp[ans];
        y-=m;
    }
    while(y)
    {
        ans=nxt[ans];
        y--;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q;
    m=sqrt(n);
    for(int i=1;i<=n;i++) 
    {
        cin>>p[i];
        nxt[i]=p[i];
        pre[p[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        jmp[i]=i;
        for(int j=1;j<=m;j++) jmp[i]=nxt[jmp[i]];
    }
    while(q--)
    {
        int op,x,y;cin>>op>>x>>y;
        if(op==1) update(x,y);
        else cout<<query(x,y)<<'\n';
    }
    return 0;
}

CF1618G Trader Problem

题意

初始你手上有 $n$ 个物品，价值为 $a_i$，商人有 $m$ 个物品，价值为 $b_i$。每次操作你可以选择手上一个价值为 $x$ 的物品，和商人交换一个价值不超过 $x+k$ 的物品。共有 $q$ 次询问，每次给出 $k$，不限制操作次数下，要求最大化手上物品价值之和。

数据范围：$1\leq n,m,q\leq 2\times 10^5$。

题解

将所有物品进行排序，对于一个给定的 $k$，相邻的价值之差不超过 $k$ 的物品都可以合并成一段，每段的贡献就是前 $x$ 大数之和，$x$ 为段内初始在你手上的物品数量。那么我们将 $k$ 离线下来，从小到大枚举 $k$，就是一个不断合并的过程。我们利用并查集维护，记录下每个连通块内手上物品的个数，利用前缀和就可以快速更新答案。注意，每个连通块的代表元要选择最大的数 $y$，这样 $sum_y-sum_{y-num_y}$ 就是连通块的贡献。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=4e5+5;
int f[N],siz[N];
pii qry[N],a[N];
ll res,sum[N],ans[N];
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
map<int,vector<int>> mp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,q;cin>>n>>m>>q;
    for(int i=1;i<=n+m;i++) cin>>a[i].first,a[i].second=i;
    sort(a+1,a+n+m+1);
    for(int i=1;i<=n+m;i++)
    {
        if(a[i].second<=n) res+=a[i].first;
        siz[i]=(a[i].second<=n);
        sum[i]=sum[i-1]+a[i].first;
        f[i]=i;
        if(i>1) mp[a[i].first-a[i-1].first].push_back(i-1);
    }
    for(int i=1;i<=q;i++) cin>>qry[i].first,qry[i].second=i;
    sort(qry+1,qry+q+1);
    auto it=mp.begin();
    for(int i=1;i<=q;i++)
    {
        if(qry[i].first==qry[i-1].first) 
        {
            ans[qry[i].second]=res;
            continue;
        }
        while(it!=mp.end()&&it->first<=qry[i].first)
        {
            for(auto j:it->second)
            {
                int x=find(j),y=find(j+1);
                res-=(sum[x]-sum[x-siz[x]]+sum[y]-sum[y-siz[y]]);
                siz[y]+=siz[x],f[x]=y;
                res+=(sum[y]-sum[y-siz[y]]);
            }
            it++;
        }
        ans[qry[i].second]=res;
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}

CF1617D2 Too Many Impostors (hard version)

题意

有 $n$ 个数，有 $k$ 个 $0$，$n-k$ 个 $1$。保证 $n$ 是 $3$ 的倍数且 $\dfrac{n}{3}<k<\dfrac{2n}{3}$。每次询问可以选择三个位置 $a,b,c$，返回其中较多的那个数。要求不超过 $n+6$ 次询问，确定所有 $0$ 的位置。

数据范围：$6\leq n<10^4$。

题解

首先三个三个询问，必然有至少一组答案是 $0$，有一组答案是 $1$，记为 $(p_0,p_0+1,p_0+2),(q_0,q_0+1,q_0+2)$。再询问 $(p_0+1,p_0+2,q_0),(p_0+2,q_0,q_0+1)$ ，就在 $\dfrac{n}{3}+2$ 次询问中确定了一个 $0$ 和一个 $1$ 的位置，记为 $s,t$。

然后考虑用两次询问确定一个组内的答案：若该组答案是 $0$，询问 $(i,i+1,t)$。然后可以确定其中是两个 $0$ 或是一个 $0$ 一个 $1$，分别询问剩下那一个或其中的一个就可以了。答案是 $1$ 也是同理。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int ans1[N],ans[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        int s,t,p0,p1,x;
        for(int i=1;i<=n;i+=3)
        {
            cout<<"? "<<i<<' '<<i+1<<' '<<i+2<<endl;
            cin>>ans1[i];
            if(ans1[i]==0) p0=i;
            else p1=i;
        }
        cout<<"? "<<p0+1<<' '<<p0+2<<' '<<p1<<endl;
        cin>>x;
        if(x==1) s=p0,t=p1;
        else 
        {
            cout<<"? "<<p0+2<<' '<<p1<<' '<<p1+1<<endl;
            cin>>x;
            if(x==1) s=p0+1,t=p1+1;
            else s=p0+2,t=p1+2;
        }
        for(int i=1;i<=n;i+=3)
            if(ans1[i]==0)
            {
                cout<<"? "<<i<<' '<<i+1<<' '<<t<<endl;
                cin>>x;
                if(x==0) 
                {
                    ans[i]=ans[i+1]=0;
                    if(i+2!=s) 
                    {
                        cout<<"? "<<s<<' '<<t<<' '<<i+2<<endl;
                        cin>>ans[i+2];
                    }
                    else ans[i+2]=0;
                }
                else
                {
                    ans[i+2]=0;
                    if(i!=s) 
                    {
                        cout<<"? "<<s<<' '<<t<<' '<<i<<endl;
                        cin>>ans[i];
                    }
                    else ans[i]=0;
                    ans[i+1]=1-ans[i];
                }
            }
            else
            {
                cout<<"? "<<i<<' '<<i+1<<' '<<s<<endl;
                cin>>x;
                if(x==1)
                {
                    ans[i]=ans[i+1]=1;
                    if(i+2!=t) 
                    {
                        cout<<"? "<<s<<' '<<t<<' '<<i+2<<endl;
                        cin>>ans[i+2];
                    }
                    else ans[i+2]=1;
                }
                else
                {
                    ans[i+2]=1;
                    if(i!=t)
                    {
                        cout<<"? "<<s<<' '<<t<<' '<<i<<endl;
                        cin>>ans[i];
                    }
                    else ans[i]=1;
                    ans[i+1]=1-ans[i];
                }
            }
        vector<int> pos;
        for(int i=1;i<=n;i++)
            if(ans[i]==0) pos.push_back(i);
        cout<<"! "<<pos.size()<<' ';
        for(auto i:pos) cout<<i<<' ';
        cout<<endl;
    }
    return 0;
}