[关闭]
@KirinBill 2018-03-08T15:14:49.000000Z 字数 5872 阅读 633

2018.03.08 HAOI 模拟赛

套题

目录


福斯特

2yZT8d.png
2yZP90.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. using std::max;
  4. const int MAXN=30005;
  5. const long long OFFSET=1e12;
  6. int n,k,r;
  7. long long sufa[MAXN],sufb[MAXN],sufc[MAXN];
  8. class CMT{
  9. private:
  10. int cnt;
  11. int rt[MAXN];
  12. struct node{int ls,rs,cnt;}d[MAXN*45];
  13. int copy_nd(int u){
  14. d[++cnt]=d[u];
  15. return cnt;
  16. }
  17. void ist(int pre,int &now,long long l,long long r,long long val){
  18. now=copy_nd(pre);
  19. ++d[now].cnt;
  20. if(l==r) return;
  21. long long mid=(l+r)/2;
  22. if(val<=mid) ist(d[pre].ls,d[now].ls,l,mid,val);
  23. else ist(d[pre].rs,d[now].rs,mid+1,r,val);
  24. }
  25. int lt_cnt(int pre,int now,long long l,long long r,long long val){
  26. if(r<val) return d[now].cnt-d[pre].cnt;
  27. long long mid=(l+r)/2;
  28. int ret=lt_cnt(d[pre].ls,d[now].ls,l,mid,val);
  29. if(val>mid+1) ret+=lt_cnt(d[pre].rs,d[now].rs,mid+1,r,val);
  30. return ret;
  31. }
  32. public:
  33. void ist(int pre,int now,long long val){ist(rt[pre],rt[now],0,OFFSET<<1,val+OFFSET);}
  34. int lt_cnt(int pre,int now,long long val){return lt_cnt(rt[pre],rt[now],0,OFFSET<<1,val+OFFSET);}
  35. }T1,T2;
  36. inline void prepare(){
  37. for(int i=1;i<=n;++i){
  38. sufc[i]-=sufb[i];
  39. sufb[i]-=sufa[i];
  40. }
  41. for(int i=n-1;i;--i){
  42. sufa[i]+=sufa[i+1];
  43. sufb[i]+=sufb[i+1];
  44. sufc[i]+=sufc[i+1];
  45. }
  46. for(int i=1,lim=n-r+1;i<=lim;++i){
  47. T1.ist(i-1,i,sufb[i]-sufb[i+r]);
  48. T2.ist(i-1,i,sufb[i]-sufc[i+r]);
  49. }
  50. }
  51. //不重叠
  52. inline int cal1(long long mid){
  53. int ret=0;
  54. mid-=sufa[1];
  55. for(int i=r+1,lim=n-r+1;i<=lim;++i)
  56. ret+=T1.lt_cnt(0,i-r,mid-sufb[i]+sufb[i+r]);
  57. return ret;
  58. }
  59. //重叠
  60. inline int cal2(long long mid){
  61. int ret=0;
  62. mid-=sufa[1];
  63. for(int i=2,lim=n-r+1;i<=lim;++i)
  64. ret+=T2.lt_cnt(max(0,i-r),i-1,mid+sufb[i+r]-sufc[i]);
  65. return ret;
  66. }
  67. inline int rank(long long mid){
  68. return cal1(mid)+cal2(mid);
  69. }
  70. inline long long bin_chop(long long l,long long r){
  71. long long mid;
  72. while(l<=r){
  73. mid=l+r>>1;
  74. if(rank(mid)<k) l=mid+1;
  75. else r=mid-1;
  76. }
  77. return r;
  78. }
  79. int main(){
  80. freopen("fst.in","r",stdin);
  81. freopen("fst.out","w",stdout);
  82. scanf("%d%d%d",&n,&r,&k);
  83. long long minans=0;
  84. for(int i=1;i<=n;++i){
  85. scanf("%d",&sufa[i]);
  86. minans+=sufa[i];
  87. }
  88. for(int i=1;i<=n;++i)
  89. scanf("%d",&sufb[i]);
  90. long long maxans=0;
  91. for(int i=1;i<=n;++i){
  92. scanf("%d",&sufc[i]);
  93. maxans+=sufc[i];
  94. }
  95. prepare();
  96. printf("%lld",bin_chop(minans,maxans));
  97. return 0;
  98. }

赛肯德

2yZ9Ba.png
2yZFhJ.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <queue>
  4. #include <vector>
  5. #include <functional>
  6. #include <cstring>
  7. #include <climits>
  8. using std::sort;
  9. using std::min;
  10. using std::max;
  11. using std::priority_queue;
  12. using std::vector;
  13. using std::greater;
  14. const int MAXN=3005,MAXM=3005;
  15. int n,m,k;
  16. int he[MAXN],w[MAXM];
  17. struct line{int to,nex,w;}ed[MAXM<<1];
  18. struct node{
  19. int id;
  20. long long dis;
  21. node(int _id=0,long long _dis=0):id(_id),dis(_dis){}
  22. bool operator >(const node &that)const{
  23. return dis>that.dis;
  24. }
  25. };
  26. inline void addE(int u,int v,int w){
  27. static int cnt;
  28. ed[++cnt]=(line){v,he[u],w};
  29. he[u]=cnt;
  30. }
  31. inline long long Dijkstra(int dta){
  32. static long long dis[MAXN];
  33. static bool use[MAXN];
  34. static priority_queue<node,vector<node>,greater<node> > hp;
  35. memset(dis,0x7f,sizeof(dis));
  36. memset(use,false,sizeof(use));
  37. dis[1]=0;
  38. hp.push(node(1,0));
  39. int u;
  40. long long d;
  41. while(hp.size()){
  42. u=hp.top().id;
  43. hp.pop();
  44. if(use[u]) continue;
  45. use[u]=true;
  46. for(int i=he[u],v;i;i=ed[i].nex){
  47. v=ed[i].to,d=dis[u]+max(0,ed[i].w-dta);
  48. if(dis[v]>d){
  49. dis[v]=d;
  50. hp.push(node(v,d));
  51. }
  52. }
  53. }
  54. return dis[n];
  55. }
  56. inline long long solve(){
  57. long long ret=LLONG_MAX;
  58. for(int i=0;i<=m;++i)
  59. ret=min(ret,Dijkstra(w[i])+(long long)k*w[i]);
  60. return ret;
  61. }
  62. int main(){
  63. freopen("skd.in","r",stdin);
  64. freopen("skd.out","w",stdout);
  65. scanf("%d%d%d",&n,&m,&k);
  66. for(int i=1,u,v;i<=m;++i){
  67. scanf("%d%d%d",&u,&v,&w[i]);
  68. addE(u,v,w[i]),addE(v,u,w[i]);
  69. }
  70. printf("%lld",solve());
  71. return 0;
  72. }

鏼尔德

2yZxw1.png
2yZUJu.png

思路

代码

先不放了,改完再说。

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