2019-10-30测试总结
Eqvpkbz's Site

2019-10-30测试总结

前言

最近的状态是不是又变差了啊

老是提不起搞OI的精神,导致现在的测试总结还有3篇没有写完

加油努力一点吧

还有以后就不放题目了

本来就不是给别人看的哇

$X$

一开始的时候把题意理解成了强连通分量???

其实就是$K_n$

然后先是一遍加边,暴力找子集,加点剪枝,再$O(n ^ 2)$判环,$n \leqslant 18$还是能过的

然后看一边部分分中的$y_i = 0$比较好打就直接打了

考试交上去发现数组开大了,全部RE

果然想要多拿点分这个思想是不现实的

正解很妙很妙

先是把题目中的加边条件看作是两个区间之间的操作,对应的,就可以贪心地做一波了

很好的图论题转换为区间题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define file(SSS) freopen(SSS".in","r",stdin),freopen(SSS".out","w",stdout)
#define file_close fclose(stdin),fclose(stdout)
const int Maxn = 200009;
const long long INF = 2147483647;
struct seg {int l, r;}a[Maxn];
int n,x,y;
bool cmp(const seg u, const seg v){return u.r < v.r;}
int main() 
{
    file("x");
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d%d",&x,&y);
        a[i] = (seg){x - y, x + y};
    }
    sort(a + 1, a + n + 1,cmp);
    int ans = 0, lef = -INF;
    for(int i = 1;i <= n;i ++)
        if (lef < a[i].l) lef = a[i].r, ++ ans;
    printf("%d",ans);
    file_close;
    return 0;
}