题解 Codeforces Round #569 (Div. 2)

rank：1306/11165 rate: +43 1424 → 1467

Codeforces Round #569 (Div. 2)

热身题。解决这道题需要的知识：读懂题面

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int n,cnt;

inline int read();
inline ll readll();

int main(){
    #ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    #endif

    n=read();

    if(n==1){
        cout<<1<<endl;
        return 0;
    }

    for(int i=-(n-1);i<=(n-1);++i){
        for(int j=-(n-1);j<=(n-1);++j){
            if(abs(i)+abs(j)<=(n-1)) cnt++;
        }
    }

    cout<<cnt<<endl;

    return 0;
}

inline int read(){
    char tmp=getchar(); int sum=0; bool flag=false;
    while(tmp<'0'||tmp>'9'){
        if(tmp=='-') flag=true;
        tmp=getchar();
    }
    while(tmp>='0'&&tmp<='9'){
        sum=(sum<<1)+(sum<<3)+tmp-'0';
        tmp=getchar();
    }
    return flag?-sum:sum;
}

inline ll readll(){
    char tmp=getchar(); ll sum=0; bool flag=false;
    while(tmp<'0'||tmp>'9'){
        if(tmp=='-') flag=true;
        tmp=getchar();
    }
    while(tmp>='0'&&tmp<='9'){
        sum=(sum<<1)+(sum<<3)+tmp-'0';
        tmp=getchar();
    }
    return flag?-sum:sum;
}

刚开始以为是什么牛批的数位dp，后来才发现是贪心。考场的时候自己尝试贪心了一下，但被system check hack掉了

再总结一下思路：首先为了绝对值最大，把所有的正数转换为整数；然后为了避免得到负数，倘若有奇数个负数，就将最大的那个取反

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int MAX=1e5+5,INF=0x3f3f3f3f;

int n,minn,neg,pos;
int num[MAX];

inline int read();
inline ll readll();

int main(){
    #ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    #endif

    n=read();
    for(int i=1;i<=n;++i) num[i]=read();
    for(int i=1;i<=n;++i) {if(num[i]>=0) num[i]=-num[i]-1; if(num[i]<0) neg++;}
    for(int i=1;i<=n;++i) {if(abs(num[i])>minn) minn=abs(num[i]),pos=i;}

    if(neg%2==1) num[pos]=-num[pos]-1;

    for(int i=1;i<=n;++i) printf("%d ",num[i]);

    return 0;
}

inline int read(){
    char tmp=getchar(); int sum=0; bool flag=false;
    while(tmp<'0'||tmp>'9'){
        if(tmp=='-') flag=true;
        tmp=getchar();
    }
    while(tmp>='0'&&tmp<='9'){
        sum=(sum<<1)+(sum<<3)+tmp-'0';
        tmp=getchar();
    }
    return flag?-sum:sum;
}

inline ll readll(){
    char tmp=getchar(); ll sum=0; bool flag=false;
    while(tmp<'0'||tmp>'9'){
        if(tmp=='-') flag=true;
        tmp=getchar();
    }
    while(tmp>='0'&&tmp<='9'){
        sum=(sum<<1)+(sum<<3)+tmp-'0';
        tmp=getchar();
    }
    return flag?-sum:sum;
}

有点忘了题面了..不过难度不大，好像是关于循环的。

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int MAX=1e5+5,INF=0x3f3f3f3f;

int n,q,tar,pos;
int a[MAX],line[MAX],rec[MAX][2];

deque <int> ord;

inline int read();
inline ll readll();

int main(){
    #ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    #endif

    n=read(); q=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        if(a[i]>tar) tar=a[i],pos=i;
    }

    for(int i=1;i<=n;++i) ord.push_back(a[i]);
    for(int i=1;i<=pos-1;++i){
        int a=ord.front(); ord.pop_front();
        int b=ord.front(); ord.pop_front();
        if(a>b){
            ord.push_front(a); ord.push_back(b);
            rec[i][0]=a; rec[i][1]=b;
        }
        else{
            ord.push_front(b); ord.push_back(a);
            rec[i][0]=a; rec[i][1]=b;
        }
    }
    ord.pop_front();
    for(int i=1;i<n;++i){
        line[i]=ord.front(); ord.pop_front();
    }

    for(int k=1;k<=q;++k){
        ll q=readll();
        if(q<pos){
            printf("%d %d\n",rec[q][0],rec[q][1]);
        }
        else{
            q-=(pos-1);
            q%=(n-1);
            printf("%d %d\n",tar,line[q?q:n-1]);
        }
    }

    return 0;
}

inline int read(){
    char tmp=getchar(); int sum=0; bool flag=false;
    while(tmp<'0'||tmp>'9'){
        if(tmp=='-') flag=true;
        tmp=getchar();
    }
    while(tmp>='0'&&tmp<='9'){
        sum=(sum<<1)+(sum<<3)+tmp-'0';
        tmp=getchar();
    }
    return flag?-sum:sum;
}

inline ll readll(){
    char tmp=getchar(); ll sum=0; bool flag=false;
    while(tmp<'0'||tmp>'9'){
        if(tmp=='-') flag=true;
        tmp=getchar();
    }
    while(tmp>='0'&&tmp<='9'){
        sum=(sum<<1)+(sum<<3)+tmp-'0';
        tmp=getchar();
    }
    return flag?-sum:sum;
}

刚读这道题的时候意为是某种神级搜索题。嗯？矢量？不可重复？状压？广搜？..总之考场一顿思索没有结果。题解：规律题 去您的规律..

感觉官方题解解释的就很清晰，附上地址

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX=1e6+5;

int n,m;

inline int read();

int main(){
    #ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    #endif

    n=read(); m=read();

    for(int j=1;j<=m/2;++j){
        for(int i=1;i<=n;++i){
            printf("%d %d\n%d %d\n",i,j,n-i+1,m-j+1);
        }
    }
    if(m%2==1){
        int l=1,r=n,tar=m/2+1;
        while(l<=r){
            if(l<=r) printf("%d %d\n",l,tar),l++;
            if(l<=r) printf("%d %d\n",r,tar),r--;
        }
    }

    return 0;
}

inline int read(){
    char tmp=getchar(); int sum=0; bool flag=false;
    while(tmp<'0'||tmp>'9'){
        if(tmp=='-') flag=true;
        tmp=getchar();
    }
    while(tmp>='0'&&tmp<='9'){
        sum=(sum<<1)+(sum<<3)+tmp-'0';
        tmp=getchar();
    }
    return sum;
}

线段树的玄学题。到现在为止虽然通过了，但个人感觉对正解理解非常不透彻，还是说这道题就是这么的迷？

贪心的发现：同学的顺序没有卵用。在保证钱的种类数和个数一定时，答案是唯一的

考虑一下“菜i可不可以被购买”和“价格大于等于i的菜个数减去钱大于等于i的同学数”之间的关系

菜i可以被购买

那么一定满足价格大于等于i的菜个数大于钱大于等于i的同学数

菜i不可以被购买

那么一定不满足价格大于等于i的菜个数大于钱大于等于i的同学数 吗..?

非也。

！这就是一个菜不可以被购买，但是却满足差大于等于1的情况。那该怎么办..

考量一下，发现这种情况出现的必要条件就是右侧存在答案更优的菜。也就是说类似于二分答案的单调性。

维护权值线段树，遇到菜则价格处+1，遇到同学则价格处-1

我们用线段树维护一下每一个节点的后缀和，并为每一个区间维护一个max。不断经可能向右取max大于等于1的菜，即有可能成为答案。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ST segment_tree::

const int MAX=4000005,TOP=1000000;

namespace segment_tree{
    int pre[MAX],sum[MAX],lazy[MAX],maxx[MAX];

    void build(int p,int l,int r){
        if(l==r) {sum[p]=maxx[p]=pre[l]; return;}
        int mid=(l+r)>>1;
        build(p<<1,l,mid); build(p<<1|1,mid+1,r);
        sum[p]=sum[p<<1]+sum[p<<1|1];
        maxx[p]=max(maxx[p<<1],maxx[p<<1|1]);
    }

    void add(int p,int l,int r,int del){
        sum[p]+=(r-l+1)*del;
        lazy[p]+=del;
        maxx[p]+=del;
    }

    void pushdown(int p,int l,int r){
        int mid=(l+r)>>1;
        add(p<<1,l,mid,lazy[p]);
        add(p<<1|1,mid+1,r,lazy[p]);
        lazy[p]=0;
    }

    void modify(int p,int l,int r,int L,int R,int del){
        if(L<=l&&r<=R) return add(p,l,r,del);
        int mid=(l+r)>>1;
        pushdown(p,l,r);
        if(L<=mid) modify(p<<1,l,mid,L,R,del);
        if(mid+1<=R) modify(p<<1|1,mid+1,r,L,R,del);
        sum[p]=sum[p<<1]+sum[p<<1|1];
        maxx[p]=max(maxx[p<<1],maxx[p<<1|1]);
    }

    int qsum_sum(int p,int l,int r,int L,int R){
        if(L<=l&&r<=R) return sum[p];
        pushdown(p,l,r);
        int mid=(l+r)>>1,ans=0;
        if(L<=mid) ans+=qsum_sum(p<<1,l,mid,L,R);
        if(mid+1<=R) ans+=qsum_sum(p<<1|1,mid+1,r,L,R);
        return ans;
    }

    int query(int p,int l,int r){
        if(l==r) return l;
        pushdown(p,l,r);
        int mid=(l+r)>>1;
        if(maxx[p<<1|1]>=1) return query(p<<1|1,mid+1,r);
        else if(maxx[p<<1]>=1) return query(p<<1,l,mid);
        else return -1;
    }
}

int n,m,q;
int a[TOP],b[TOP];

inline int read();

int main(){
    #ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    #endif

    n=read(); m=read();
    for(int i=1;i<=n;++i) a[i]=read(),ST pre[a[i]]++;
    for(int i=1;i<=m;++i) b[i]=read(),ST pre[b[i]]--;
    for(int i=TOP;i>=1;--i) ST pre[i]=ST pre[i]+ST pre[i+1];
    ST build(1,1,TOP);  

    q=read();
    for(int i=1;i<=q;++i){
        int type,pos,x; type=read(); pos=read(); x=read();
        switch(type){
            case 1:
            ST modify(1,1,TOP,1,a[pos],-1);
            ST modify(1,1,TOP,1,x,1);
            a[pos]=x;
            printf("%d\n",ST query(1,1,TOP));
            break;
            case 2:
            ST modify(1,1,TOP,1,b[pos],1);
            ST modify(1,1,TOP,1,x,-1);
            b[pos]=x;
            printf("%d\n",ST query(1,1,TOP));
            break;
        }
    }

    return 0;
}

inline int read(){
    char tmp=getchar(); int sum=0; bool flag=false;
    while(tmp<'0'||tmp>'9'){
        if(tmp=='-') flag=true;
        tmp=getchar();
    }
    while(tmp>='0'&&tmp<='9'){
        sum=(sum<<1)+(sum<<3)+tmp-'0';
        tmp=getchar();
    }
    return flag?-sum:sum;
}