[关闭]
@01010101 2018-11-05T21:37:12.000000Z 字数 4318 阅读 977

noip2012

noip


DAY1T1Vigenère 密码

一个简单模拟

DAY1T2国王游戏

贪心,不太好想。关键是涉及高精度的除法

DAY1T3开车旅行

好题。考虑在暴力往前走的基础上如何优化,由于走的是一条链:倍增 把a走一次,b走一次看成一个整体进行倍增。

如何找最大次大也值得思考:双向链表(我不熟),set(不怎么会用迭代器)。。。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <set>
  5. #include <algorithm>
  6. #define ll long long
  7. using namespace std;
  8. const int N=100005;
  9. const int D=20;
  10. int n,x0,m,k,x1,na[N],nb[N],ans;
  11. ll ansa=1e5,ansb=0LL,fa[N][D+2],fb[N][D+2],f[N][D+2];
  12. struct city{
  13. int id,h;
  14. bool operator < (const city &b) const{
  15. return h<b.h;
  16. }
  17. }c[N];
  18. struct node{
  19. int id,delta;
  20. bool operator < (const node &b) const{
  21. if(delta!=b.delta) return delta<b.delta;
  22. return c[id].h<c[b.id].h;
  23. }
  24. }tmp[5];
  25. set <city> s;
  26. void init(int i){
  27. set<city>::iterator it=s.find(c[i]);
  28. int j=0;
  29. if(it!=s.begin()){
  30. --it;
  31. tmp[++j]=(node){it->id,abs(it->h-c[i].h)};
  32. if(it!=s.begin()){
  33. --it;
  34. tmp[++j]=(node){it->id,abs(it->h-c[i].h)};
  35. ++it;
  36. }
  37. ++it;
  38. }
  39. if((++it)!=s.end()){
  40. tmp[++j]=(node){it->id,abs(it->h-c[i].h)};
  41. if((++it)!=s.end())
  42. tmp[++j]=(node){it->id,abs(it->h-c[i].h)};
  43. }
  44. sort(tmp+1,tmp+j+1);
  45. nb[i]=tmp[1].id;
  46. if(j==1) return;
  47. na[i]=tmp[2].id;
  48. }
  49. void query(int st,int x,ll &ta,ll &tb){
  50. for(int i=D;i>=0;--i)
  51. if(f[st][i]&&fa[st][i]+fb[st][i]<=x){
  52. ta+=fa[st][i];
  53. tb+=fb[st][i];
  54. x-=fa[st][i]+fb[st][i];
  55. st=f[st][i];
  56. }
  57. if(!na[st]) return;
  58. int tmpans=abs(c[na[st]].h-c[st].h);
  59. if(tmpans<=x) ta+=tmpans;
  60. }
  61. int main(){
  62. // freopen("a.txt","r",stdin);
  63. scanf("%d",&n);
  64. for(int i=1;i<=n;++i){
  65. scanf("%d",&c[i].h);
  66. c[i].id=i;
  67. }
  68. for(int i=n;i>=1;--i){
  69. s.insert(c[i]);
  70. if(i!=n)
  71. init(i);
  72. }
  73. for(int i=1;i<=n;++i){//把a和b合在一起走2^j步。
  74. int p1=na[i],p2=nb[na[i]];
  75. fa[i][0]=p1?abs(c[p1].h-c[i].h):0;
  76. fb[i][0]=p2?abs(c[p2].h-c[p1].h):0;
  77. f[i][0]=p2;
  78. }
  79. for(int j=1;j<=D;++j){
  80. for(int i=1;i<=n;++i){
  81. f[i][j]=f[f[i][j-1]][j-1];
  82. fa[i][j]=fa[i][j-1]+fa[f[i][j-1]][j-1];
  83. fb[i][j]=fb[i][j-1]+fb[f[i][j-1]][j-1];
  84. }
  85. }
  86. scanf("%d",&x0);
  87. ans=0;
  88. for(int i=1;i<=n;++i){
  89. ll ta=0LL,tb=0LL;
  90. query(i,x0,ta,tb);
  91. if(tb&&(!ans||ansa*tb>ansb*ta)){
  92. ansa=ta;
  93. ansb=tb;
  94. ans=i;
  95. }
  96. }
  97. printf("%d\n",ans);
  98. scanf("%d",&m);
  99. while(m--){
  100. scanf("%d%d",&k,&x1);
  101. ll ta=0LL,tb=0LL;
  102. query(k,x1,ta,tb);
  103. printf("%lld %lld\n",ta,tb);
  104. }
  105. return 0;
  106. }

DAY2T1同余方程

数论模板题

DAY2T2借教室

第一想法线段树,第二想法区间修改+区间查询(最值)线段树,最后发现题解是二分+差分

DAY2T3疫情控制

好题,从某节点往上走用倍增!!贪心+二分倍增实现。漏了一个情况。
一个节点不是先守好自己。而是在能守别人的时候尽可能守住别人。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #define ll long long
  6. using namespace std;
  7. int read(){
  8. char ch;int op=1;
  9. while((ch=getchar())<'0'||ch>'9') if(ch=='-') op=-1;
  10. int ret=ch-'0';
  11. while((ch=getchar())>='0'&&ch<='9') ret=ret*10+ch-'0';
  12. return ret*op;
  13. }
  14. const int D=18;
  15. const int N=50000+10;
  16. const int inf=0x3f3f3f3f;
  17. int n,m,kk,cnt;
  18. int head[N],f[N][D+2],vis[N],ar[N],leaf[N];
  19. ll l,r,mid,ans;
  20. ll g[N][D+2];
  21. struct edge{
  22. int v,w,nxt;
  23. }e[N<<1];
  24. void adde(int u,int v,int w){
  25. e[kk].v=v;
  26. e[kk].w=w;
  27. e[kk].nxt=head[u];
  28. head[u]=kk++;
  29. }
  30. void dfs(int u,int fa,int w){
  31. f[u][0]=fa;g[u][0]=w;
  32. for(int i=head[u];i!=-1;i=e[i].nxt){
  33. int v=e[i].v;
  34. if(v!=fa){
  35. dfs(v,u,e[i].w);
  36. }
  37. }
  38. }
  39. struct army{int ct;ll t;}rst[N];
  40. struct pat{int ct;ll nd;}p[N];
  41. bool cmp1(army a,army b){
  42. if(a.ct!=b.ct) return a.ct<b.ct;
  43. return a.t<b.t;
  44. }
  45. bool cmp3(army a,army b){return a.t>b.t;}
  46. bool cmp2(pat a,pat b){ return a.ct<b.ct;}
  47. bool cmp4(pat a,pat b){ return a.nd>b.nd;}
  48. void dfs2(int u,int fa){
  49. if(vis[u]) return;
  50. int flg=-1;
  51. for(int i=head[u];i!=-1;i=e[i].nxt){
  52. int v=e[i].v;
  53. if(v!=fa){
  54. if(flg==-1) flg=0;
  55. dfs2(v,u);
  56. leaf[u]+=leaf[v];
  57. }
  58. }
  59. if(flg==-1) leaf[u]=1;
  60. }
  61. bool Check(ll X){
  62. for(int i=1;i<=n;++i) {
  63. vis[i]=0;
  64. p[i].nd=0;
  65. p[i].ct=0;
  66. rst[i].t=0;
  67. rst[i].ct=0;
  68. leaf[i]=0;
  69. }
  70. cnt=0;
  71. for(int i=1;i<=m;++i){
  72. int pos=ar[i];ll R=X;
  73. for(int j=D;j>=0;--j)
  74. if(g[pos][j]<=R&&f[pos][j]!=1) {
  75. R-=g[pos][j];//!!
  76. pos=f[pos][j];
  77. }
  78. if(f[pos][0]==1&&g[pos][0]<=R){
  79. rst[i].t=R-g[pos][0];
  80. rst[i].ct=pos;
  81. }
  82. else vis[pos]=1;
  83. }
  84. dfs2(1,1);
  85. for(int i=head[1];i!=-1;i=e[i].nxt){
  86. int v=e[i].v;
  87. if(leaf[v]){
  88. p[++cnt].nd=e[i].w;
  89. p[cnt].ct=v;
  90. }
  91. }
  92. sort(rst+1,rst+m+1,cmp1);
  93. sort(p+1,p+cnt+1,cmp2);
  94. int tmp=1;
  95. for(int i=1;i<=cnt;++i){
  96. while(rst[tmp].ct<p[i].ct&&tmp<=m) tmp++;
  97. if(rst[tmp].ct==p[i].ct&&rst[tmp].t<p[i].nd) {
  98. p[i].nd=0;
  99. rst[tmp++].t=0;
  100. }
  101. }
  102. sort(rst+1,rst+m+1,cmp3);
  103. sort(p+1,p+cnt+1,cmp4);
  104. for(int i=1;i<=cnt;++i)
  105. if(rst[i].t<p[i].nd) return false;
  106. return true;
  107. }
  108. int main(){
  109. int a,b,c;
  110. // freopen("a.txt","r",stdin);
  111. // freopen("a.out","w",stdout);
  112. memset(head,-1,sizeof(head));
  113. n=read();
  114. for(int i=1;i<n;++i){
  115. a=read();b=read();c=read();
  116. adde(a,b,c);adde(b,a,c);
  117. r+=c;
  118. }
  119. dfs(1,1,0);
  120. for(int i=1;i<=D;++i)
  121. for(int j=1;j<=n;++j){
  122. f[j][i]=f[f[j][i-1]][i-1];
  123. g[j][i]=g[f[j][i-1]][i-1]+g[j][i-1];
  124. }
  125. m=read();
  126. for(int i=1;i<=m;++i) {
  127. ar[i]=read();
  128. }
  129. while(l<=r){
  130. mid=(l+r)>>1;
  131. if(Check(mid)) {ans=mid;r=mid-1;}
  132. else l=mid+1;
  133. }
  134. printf("%lld\n",ans);
  135. return 0;
  136. }

模拟
贪心+高精度除法
倍增
数论同余方程
二分+差分
二分+倍增

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