[关闭]
@Jerusalem 2016-02-14T20:18:41.000000Z 字数 1689 阅读 1344

Vol6


BZOJ1107

显然,i能作为出发点的充分必要条件是它能够到达左右端点。

引入辅助函数f(i),表示i作为出发点到达左端点至少需要新建多少条路。将所有向左的道路按高度排序,以编号为关键字求LIS,然后f(i)就等于i-1-{max:n[i]

然后,能够到达左右端点的点一定是连续的,这是显然的。于是我们枚举这区间的左右端点,容易证明,区间[l,r]里的点都能够作为出发点的充分必要条件是f(r)+g(l)<=k。(注意到f和g无关,于是必要性是显然的,而注意到任意i

注意题目要求减掉不需要加边就可作为出发点的点数量。

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <iostream>
  7. using namespace std;
  8. const int maxn=100005,INF=0x3f3f3f3f;
  9. struct Node{
  10. int high;
  11. int Num;
  12. Node(){
  13. high=Num=0;
  14. }
  15. Node(int high_,int num_){
  16. high=high_;
  17. Num=num_;
  18. }
  19. bool operator <(const Node& a)const{
  20. if(high==a.high)
  21. return Num<a.Num;
  22. return high>a.high;
  23. }
  24. };
  25. Node l[maxn],r[maxn];
  26. int g[maxn];
  27. int lt[maxn],rt[maxn];
  28. int nl,nr;
  29. int n,m,k,p;
  30. void Clear()
  31. {
  32. memset(g,0x3f,sizeof(g));
  33. g[0]=0;
  34. }
  35. int Find(int key,int size)
  36. {
  37. int l=0,r=size;
  38. while(l+1<r){
  39. int mid=(l+r)/2;
  40. if(g[mid]<key)
  41. l=mid;
  42. else
  43. r=mid;
  44. }
  45. return l;
  46. }
  47. void First()
  48. {
  49. Clear();
  50. for(int i=1;i<=nl;i++){
  51. int calc=Find(l[i].Num,nl)+1;
  52. g[calc]=min(g[calc],l[i].Num);
  53. }
  54. for(int i=0;i<=nl&&g[i]<n;i++)
  55. for(int j=g[i]+1;j<=g[i+1]&&j<=n;j++)
  56. lt[j]=j-i-1;
  57. Clear();
  58. for(int i=1;i<=nr;i++){
  59. int calc=Find(r[i].Num,nr)+1;
  60. g[calc]=min(g[calc],r[i].Num);
  61. }
  62. for(int i=0;i<=nr&&g[i]<n;i++)
  63. for(int j=g[i]+1;j<=g[i+1]&&j<=n;j++)
  64. rt[n-j+1]=j-i-1;
  65. }
  66. void Solve()
  67. {
  68. int ans=0;
  69. //for(int i=1;i<=n;i++)
  70. // printf("%d %d\n",rt[i],lt[i]);
  71. for(int i=1,j=1;i<=n;i++){
  72. while(j<=i&&rt[j]+lt[i]>k)
  73. j++;
  74. ans=max(ans,i-j+1);
  75. }
  76. for(int i=1;i<=n;i++)
  77. if(lt[i]==0&&rt[i]==0)
  78. ans--;
  79. printf("%d\n",ans);
  80. }
  81. void Readdata()
  82. {
  83. freopen("loli.in","r",stdin);
  84. scanf("%d%d%d%d",&n,&m,&p,&k);
  85. for(int i=1;i<=p;i++){
  86. int a,b,c;
  87. scanf("%d%d%d",&a,&b,&c);
  88. if(c==1)
  89. l[++nl]=Node(b,a);
  90. else
  91. r[++nr]=Node(b,n-a);
  92. }
  93. sort(l+1,l+nl+1);
  94. sort(r+1,r+nr+1);
  95. }
  96. void Close()
  97. {
  98. fclose(stdin);
  99. fclose(stdout);
  100. }
  101. int main()
  102. {
  103. Readdata();
  104. First();
  105. Solve();
  106. Close();
  107. return 0;
  108. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注