[关闭]
@zzzc18 2017-10-23T08:11:04.000000Z 字数 3038 阅读 468

2017.10.23 NOIP 模拟赛

TEST


Problem

problem.pdf276.9kB


好久没动博客了。。。


Solution

T1

两种做法

法一:

先按出现的位置排序然后连边的条件就可以改为
此时,又可以发现
所以每次我们查询对于满足的所有 里的最大团大小(最大团最后加入的点应该是 )
由于可知,这个满足条件的 对应的最大团可以把 加进去,最大团大小变大
具体怎么实现,就是一个权值线段树,存团的大小

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int MAXN = 400000+9;
  6. int n;
  7. struct PAIR{
  8. int loc,val;
  9. }num[MAXN];
  10. int b[MAXN];
  11. int len;
  12. int ans=1;
  13. struct T{
  14. int ls,rs,left_range,right_range;
  15. int val;
  16. }tree[MAXN*4];
  17. int cnt;
  18. int lazy[MAXN*4];
  19. bool cmp(const PAIR &A,const PAIR &B){
  20. return A.loc<B.loc;
  21. }
  22. void update(int x){
  23. tree[x].val=max(tree[tree[x].ls].val,tree[tree[x].rs].val);
  24. }
  25. void pushdown(int x){
  26. if(lazy[x]==0)return;
  27. if(tree[x].ls){
  28. tree[tree[x].ls].val=max(tree[tree[x].ls].val,lazy[x]);
  29. lazy[tree[x].ls]=max(lazy[tree[x].ls],lazy[x]);
  30. }
  31. if(tree[x].rs){
  32. tree[tree[x].rs].val=max(tree[tree[x].rs].val,lazy[x]);
  33. lazy[tree[x].rs]=max(lazy[tree[x].rs],lazy[x]);
  34. }
  35. lazy[x]=0;
  36. }
  37. int Build(int l,int r){
  38. int now=++cnt;
  39. tree[now].left_range=l;
  40. tree[now].right_range=r;
  41. if(l==r){
  42. tree[now].val=0;
  43. return now;
  44. }
  45. int mid=(l+r)>>1;
  46. tree[now].ls=Build(l,mid);
  47. tree[now].rs=Build(mid+1,r);
  48. update(now);
  49. return now;
  50. }
  51. int getmax(int k,int l,int r){
  52. pushdown(k);
  53. if(l<=tree[k].left_range && tree[k].right_range<=r){
  54. return tree[k].val;
  55. }
  56. int mid=tree[k].left_range + tree[k].right_range >> 1;
  57. int re=0;
  58. if(l<=mid)re=max(re,getmax(tree[k].ls,l,r));
  59. if(r>=mid+1)re=max(re,getmax(tree[k].rs,l,r));
  60. update(k);
  61. return re;
  62. }
  63. void modify(int k,int pos,int val){
  64. pushdown(k);
  65. if(tree[k].left_range==tree[k].right_range){
  66. tree[k].val=val;
  67. lazy[k]=val;
  68. return;
  69. }
  70. int mid=tree[k].left_range + tree[k].right_range >> 1;
  71. if(pos<=mid)modify(tree[k].ls,pos,val);
  72. else modify(tree[k].rs,pos,val);
  73. update(k);
  74. }
  75. void solve(){
  76. Build(1,len);
  77. for(int i=1;i<=n;i++){
  78. int pos=lower_bound(b+1,b+len+1,num[i].loc-num[i].val)-b;
  79. int tmp=getmax(1,1,pos);
  80. ans=max(ans,tmp+1);
  81. pos=lower_bound(b+1,b+len+1,num[i].loc+num[i].val)-b;
  82. modify(1,pos,tmp+1);
  83. }
  84. printf("%d\n",ans);
  85. }
  86. int main(){
  87. freopen("clique.in","r",stdin);
  88. freopen("clique.out","w",stdout);
  89. scanf("%d",&n);
  90. int i;
  91. for(i=1;i<=n;i++){
  92. scanf("%d%d",&num[i].loc,&num[i].val);
  93. }
  94. sort(num+1,num+n+1,cmp);
  95. int tmp=0;
  96. for(i=1;i<=n;i++){
  97. b[++tmp]=num[i].loc-num[i].val;
  98. b[++tmp]=num[i].loc+num[i].val;
  99. }
  100. sort(b+1,b+tmp+1);
  101. len=unique(b+1,b+tmp+1)-(b+1);
  102. solve();
  103. return 0;
  104. }

法二:

好了,以上方法说明我弱智
将点看成区间(因为 )
那么两个点有连边当且仅当两个区间没有公共点。
贪心地选取更多的区间,看一下代码

  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. int n,x[200100],w[200100],ans,to;
  5. struct MU{
  6. int l,r;
  7. }a[200100];
  8. bool cmp(MU u,MU v){
  9. if(u.r==v.r)
  10. return u.l<v.l;
  11. return u.r<v.r;
  12. }
  13. int main(){
  14. freopen("clique.in","r",stdin);
  15. freopen("clique.out","w",stdout);
  16. scanf("%d",&n);
  17. for(int i=1;i<=n;i++) {
  18. scanf("%d%d",&x[i],&w[i]);
  19. a[i].l=x[i]-w[i];a[i].r=x[i]+w[i];
  20. }
  21. sort(a+1,a+n+1,cmp);
  22. ans=1;to=a[1].r;
  23. for(int i=2;i<=n;i++){
  24. if(a[i].l>=to){
  25. ans++;to=a[i].r;
  26. }
  27. }
  28. printf("%d\n",ans);
  29. fclose(stdin);fclose(stdout);return 0;
  30. }

T2

其实,因为
可以直接用线段树进行暴力修改,维护区间最值与区间和,区间取模时,线段树内操作时,如果当区间的最大值为 或 小于取模的值时,可以直接
考试的时候觉得这太坑没写,直接交了个40pts暴力


T3

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注