【2019.10.30】

Prob Sol

这几天休息状态不好..所以考试状态也很差。

今天两题的暴力都没打好，不太行。

啊，但这几次考试如果说有起什么作用的话，就是我的心态变稳了吧，不会像之前那样没考好/一道题没打好就很影响状态了。我们的策略是拿到一切暴力分，在此基础上努力想正解多拿分。

事情做就是了，想太多对自己没好处。

T1.

暴力是真的暴力，也很好写。

正解我是觉得之前没做过类似操作的话根本就想不到，%h用DP写的（太强啦）。

主要是1.去掉绝对值的操作 2.把点看成区间，转化为求最大的区间不覆盖问题 3.如果没做过求无向图的最大团那可能连概念都读不懂8

解决办法没啥，多做题多总结，注意要系统化的训练啦。

#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define For(i,l,r) for(ri i=l;i<=r;i++)
#define Dfor(i,r,l) for(ri i=r;i>=l;i--)
using namespace std;
const int M=1e5+5;
int n,x,y,lef=-0x3f3f3f,ans;
struct seg{
    int l,r;
}e[M<<1];
inline ll read(){
    ll f=1,sum=0;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();}
    return f*sum;
}
inline void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline bool cmp(seg a,seg b){return a.r<b.r;}
int main(){
    freopen("x.in","r",stdin);
    freopen("x.out","w",stdout);
    n=read();
    For(i,1,n){
        x=read(),y=read();
        e[i]=(seg){x-y,x+y};
    }
    sort(e+1,e+n+1,cmp);
    For(i,1,n){
        if(lef<e[i].l) ans++,lef=e[i].r;
    }
    printf("%d",ans);
    return 0;
}

View Code

T2.