300iq Contest 1 简要题解

咕咕咕

codeforces

B. Best Subsequence

description

给出\(n,k\)以及\(\{w_1,w_2,...,w_n\}\)，你需要找出一个长度为\(k\)的子序列\(1 \le i_1 < i_2 < ... < i_k \le n\)，最小化\(\max\{w_{i_1}+w_{i_2},w_{i_2}+w_{i_3},...,w_{i_{k-1}}+w_{i_k},w_{i_k}+w_{i_1}\}\)。

$1 \le k \le n \le 2\times 10^5, $

solution

假设答案是\(mid\)，那么子序列中相邻（首尾也算相邻）两个数中至少有一个不超过\(\lfloor\frac{mid}{2}\rfloor\)。

二分\(mid\)，找出所有不超过\(\lfloor\frac{mid}{2}\rfloor\)的数，显然这些树构成的子序列是合法的，接着相邻两个数中至多插入一个新数，线性扫一遍统计即可。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int n,k,w[N],p[N];
int check(int mid){
    int cnt=0,res=0;
    for(int i=1;i<=n;++i)if(w[i]<=mid/2)p[++cnt]=i;
    if(cnt<=1)return cnt;
    for(int i=1;i<cnt;++i)
        for(int j=p[i]+1;j<p[i+1];++j)
            if(w[j]+max(w[p[i]],w[p[i+1]])<=mid){
                ++res;break;
            }
    for(int j=p[cnt]+1;j<=n;++j)
        if(w[j]+max(w[p[cnt]],w[p[1]])<=mid)
            return cnt+res+1;
    for(int j=1;j<p[1];++j)
        if(w[j]+max(w[p[cnt]],w[p[1]])<=mid)
            return cnt+res+1;
    return cnt+res;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)scanf("%d",&w[i]);
    int l=2,r=2e9,res;
    while(l<=r){
        int mid=l+(r-l>>1);
        if(check(mid)>=k)res=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d\n",res);return 0;
}

C. Cool Pairs

description

给出两个\(n\)阶排列\(p,q\)和一个参数\(k\)，要求构造两个序列\(a,b\)满足：

• \(-n \le a_i, b_i \le n\)。
• \(a_{p_1} \le a_{p_2} \le ... \le a_{p_n}, b_{q_1} \le b_{q_2} \le ... \le b_{q_n}\)。
• 满足\(i<j, a_i<b_j\)的\((i,j)\)数量恰好为\(k\)。

\(1 \le n \le 3\times 10^5, 0 \le k \le \frac{n(n-1)}{2}.\)

solution

按照如下方法构造：

• \(a_{p_i}=i-1-n\)。
• 存在一个\(x\in[1,n]\)，使\(\forall i\in[1,x), b_{q_i}=0, \forall i\in(x,n], b_{q_i}=n\)。

可以发现这样构造出来的满足\(i<j, a_i<b_j\)的\((i,j)\)数量为\(\sum_{i=1}^{x-1}(q_i-1)+y\)，其中\(y\)是一个与\(b_{q_x}\)取值有关的在\([0,q_x)\)范围内的数。易证明这种构造方法可以对任意合法的\(k\)构造出解。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=3e5+5;
int n,a[N],b[N],c[N];long long k;
int main(){
    scanf("%d%lld",&n,&k);
    for(int i=1,x;i<=n;++i)scanf("%d",&x),a[x]=i-1-n,b[i]=n;
    for(int i=1,x;i<=n;++i){
        scanf("%d",&x);
        if(x-1<=k)b[x]=0,k-=x-1;
        else{
            for(int j=1;j<x;++j)c[j]=a[j];
            sort(c+1,c+x);
            b[x]=-c[k+1];break;
        }
    }
    puts("Yes");
    for(int i=1;i<=n;++i)printf("%d ",a[i]);puts("");
    for(int i=1;i<=n;++i)printf("%d ",b[i]);puts("");
    return 0;
}

D. Dates

description

在接下来的\(t\)天时间里，有\(n\)个女孩子想要和\(\text{y}\color{red}{\text{yb}}\) 约会。第\(i\)个女孩子想要在\([l_i,r_i]\)中的某一天和\(\text{y}\color{red}{\text{yb}}\)约会，且约会后\(\text{y}\color{red}{\text{yb}}\)会得到\(p_i\)的偷税值。在这里，我们保证\(l_i\le l_{i+1}, r_i \le r_{i+1}\)。\(\text{y}\color{red}{\text{yb}}\)在第\(i\)天至多和\(a_i\)个女孩子约会，他希望你能帮他求出他能够获得的最大偷税值之和。

$1 \le n, t \le 3\times 10^5, $

solution

按照\(p_i\)从大到小依次加入区间，每次判断加入后是否仍存在完美匹配，这种做法的正确性显然。

根据\(Hall\)定理，判断是否存在完美匹配，只需要判断是否任意\(1 \le L \le R \le t\)均满足\(\sum_{i=L}^Ra_i \ge \sum[l_i \ge L][r_i \le R]\)。

然后由于保证了\(l_i\le l_{i+1}, r_i \le r_{i+1}\)，因而枚举\(1 \le L \le R \le t\)可以替换为枚举\(1 \le L' \le R' \le n\)即枚举“区间的区间”。设\(b_i\in\{0,1\}\)表示第\(i\)个区间是否被选，那么需要满足的限制就变成了：\(\sum_{i=L}^Rb_i\le \sum_{i=l_L}^{r_R}a_i\)。

记\(sa_i,sb_i\)分别为\(a_i\)和\(b_i\)的前缀和，那么限制为\(sb_R-sb_{L-1}\le sa_{r_R}-sa_{l_L-1}\)即\(sb_R-sa_{r_R}\le sb_{L-1}-sa_{l_L-1}\)。再记\(c_i=sb_i-sa_{r_i},d_i=sb_{i-1}-sa_{l_i-1}\)，限制为\(c_R\le d_L\)。

考虑每次加入一个区间即企图将某一个\(b_x\)由\(0\)改为\(1\)，观察发现只会有\(c_{x...n}\)与\(d_{1...x}\)的大小关系会受到影响，因而维护后缀\(c_i\)的最大值和前缀\(d_i\)的最小值判断即可。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')w=0,ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
#define ll long long
const int N=3e5+5;
struct segment_tree{
    ll op,arr[N],val[N<<2],tag[N<<2];
    ll merge(ll x,ll y){return op?max(x,y):min(x,y);}
    void build(int x,int l,int r){
        if(l==r){val[x]=arr[l];return;}
        tag[x]=0;int mid=l+r>>1;
        build(x<<1,l,mid);build(x<<1|1,mid+1,r);
        val[x]=merge(val[x<<1],val[x<<1|1]);
    }
    void init(int n,ll _op){
        op=_op;build(1,1,n);
    }
    void modify(int x,int l,int r,int ql,int qr,ll v){
        if(l>=ql&&r<=qr){val[x]+=v;tag[x]+=v;return;}
        int mid=l+r>>1;
        if(ql<=mid)modify(x<<1,l,mid,ql,qr,v);
        if(qr>mid)modify(x<<1|1,mid+1,r,ql,qr,v);
        val[x]=merge(val[x<<1],val[x<<1|1])+tag[x];
    }
    ll query(int x,int l,int r,int ql,int qr){
        if(l>=ql&&r<=qr)return val[x];
        int mid=l+r>>1;
        if(qr<=mid)return query(x<<1,l,mid,ql,qr)+tag[x];
        if(ql>mid)return query(x<<1|1,mid+1,r,ql,qr)+tag[x];
        return merge(query(x<<1,l,mid,ql,qr),query(x<<1|1,mid+1,r,ql,qr))+tag[x];
    }
}T1,T2;
int n,m,p[N],id[N];ll sa[N],ans;
bool cmp(int x,int y){return p[x]>p[y];}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)scanf("%lld",&sa[i]),sa[i]+=sa[i-1];
    for(int i=1,l,r;i<=n;++i){
        scanf("%d%d%d",&l,&r,&p[i]);id[i]=i;
        T1.arr[i]=-sa[r];T2.arr[i]=-sa[l-1];
    }
    T1.init(n,1);T2.init(n,0);sort(id+1,id+n+1,cmp);
    for(int i=1;i<=n;++i)
        if(T1.query(1,1,n,id[i],n)<T2.query(1,1,n,1,id[i])){
            T1.modify(1,1,n,id[i],n,1);
            if(id[i]<n)T2.modify(1,1,n,id[i]+1,n,1);
            ans+=p[id[i]];
        }
    printf("%lld\n",ans);return 0;
}

to be continued ...

300iq Contest 1 简要题解

原文：https://www.cnblogs.com/zhoushuyu/p/11393323.html