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

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];
  26. set <city> s;
  27. void init(int i){
  28.     set<city>::iterator it=s.find(c[i]);
  29.     int j=0;
  30.     if(it!=s.begin()){
  31.         --it;
  32.         tmp[++j]=(node){it->id,abs(it->h-c[i].h)};
  33.         if(it!=s.begin()){
  34.             --it;
  35.             tmp[++j]=(node){it->id,abs(it->h-c[i].h)};
  36.             ++it;
  37.         }
  38.         ++it;
  39.     }
  40.     if((++it)!=s.end()){
  41.         tmp[++j]=(node){it->id,abs(it->h-c[i].h)};
  42.         if((++it)!=s.end())
  43.             tmp[++j]=(node){it->id,abs(it->h-c[i].h)};
  44.     }
  45.     sort(tmp+1,tmp+j+1);
  46.     nb[i]=tmp[1].id;
  47.     if(j==1) return;
  48.     na[i]=tmp[2].id;
  49. }
  51. void query(int st,int x,ll &ta,ll &tb){
  52.     for(int i=D;i>=0;--i)
  53.         if(f[st][i]&&fa[st][i]+fb[st][i]<=x){
  54.             ta+=fa[st][i];
  55.             tb+=fb[st][i];
  56.             x-=fa[st][i]+fb[st][i];
  57.             st=f[st][i];
  58.         }
  59.     if(!na[st]) return;
  60.     int tmpans=abs(c[na[st]].h-c[st].h);
  61.     if(tmpans<=x) ta+=tmpans;
  62. }
  63. int main(){
  64. //  freopen("a.txt","r",stdin);
  65.     scanf("%d",&n);
  66.     for(int i=1;i<=n;++i){
  67.         scanf("%d",&c[i].h);
  68.         c[i].id=i;
  69.     }
  70.     for(int i=n;i>=1;--i){
  71.         s.insert(c[i]);
  72.         if(i!=n)
  73.             init(i);
  74.     }
  75.     for(int i=1;i<=n;++i){//把a和b合在一起走2^j步。 
  76.         int p1=na[i],p2=nb[na[i]];
  77.         fa[i][0]=p1?abs(c[p1].h-c[i].h):0;
  78.         fb[i][0]=p2?abs(c[p2].h-c[p1].h):0;
  79.         f[i][0]=p2;
  80.     }
  81.     for(int j=1;j<=D;++j){
  82.         for(int i=1;i<=n;++i){
  83.             f[i][j]=f[f[i][j-1]][j-1];
  84.             fa[i][j]=fa[i][j-1]+fa[f[i][j-1]][j-1];
  85.             fb[i][j]=fb[i][j-1]+fb[f[i][j-1]][j-1];
  86.         }
  87.     }
  88.     scanf("%d",&x0);
  89.     ans=0;
  90.     for(int i=1;i<=n;++i){
  91.         ll ta=0LL,tb=0LL;
  92.         query(i,x0,ta,tb);
  93.         if(tb&&(!ans||ansa*tb>ansb*ta)){
  94.             ansa=ta;
  95.             ansb=tb;
  96.             ans=i;
  97.         }
  98.     } 
  99.     printf("%d\n",ans);
  100.     scanf("%d",&m);
  101.     while(m--){
  102.         scanf("%d%d",&k,&x1);
  103.         ll ta=0LL,tb=0LL;
  104.         query(k,x1,ta,tb);
  105.         printf("%lld %lld\n",ta,tb);
  106.     }
  107.     return 0;
  108. }

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];
  22. struct edge{
  23.     int v,w,nxt;
  24. }e[N<<1];
  25. void adde(int u,int v,int w){
  26.     e[kk].v=v;
  27.     e[kk].w=w;
  28.     e[kk].nxt=head[u];
  29.     head[u]=kk++;
  30. }
  31. void dfs(int u,int fa,int w){
  32.     f[u][0]=fa;g[u][0]=w;
  33.     for(int i=head[u];i!=-1;i=e[i].nxt){
  34.         int v=e[i].v;
  35.         if(v!=fa){
  36.             dfs(v,u,e[i].w);
  37.         }
  38.     }
  39. }
  41. struct army{int ct;ll t;}rst[N];
  42. struct pat{int ct;ll nd;}p[N];
  44. bool cmp1(army a,army b){
  45.     if(a.ct!=b.ct) return a.ct<b.ct;
  46.     return a.t<b.t;
  47. }
  48. bool cmp3(army a,army b){return a.t>b.t;}
  49. bool cmp2(pat a,pat b){ return a.ct<b.ct;}
  50. bool cmp4(pat a,pat b){ return a.nd>b.nd;}
  52. void dfs2(int u,int fa){
  53.     if(vis[u]) return;
  54.     int flg=-1;
  55.     for(int i=head[u];i!=-1;i=e[i].nxt){
  56.         int v=e[i].v;
  57.         if(v!=fa){
  58.             if(flg==-1) flg=0;
  59.             dfs2(v,u);
  60.             leaf[u]+=leaf[v];
  61.         }
  62.     } 
  63.     if(flg==-1) leaf[u]=1;
  64. }
  66. bool Check(ll X){
  67.     for(int i=1;i<=n;++i) {
  68.         vis[i]=0;
  69.         p[i].nd=0;
  70.         p[i].ct=0;
  71.         rst[i].t=0;
  72.         rst[i].ct=0;
  73.         leaf[i]=0;
  74.     }
  75.     cnt=0;
  76.     for(int i=1;i<=m;++i){
  77.         int pos=ar[i];ll R=X;
  78.         for(int j=D;j>=0;--j)
  79.             if(g[pos][j]<=R&&f[pos][j]!=1) {
  80.                 R-=g[pos][j];//!!
  81.                 pos=f[pos][j];
  82.             }
  84.         if(f[pos][0]==1&&g[pos][0]<=R){
  85.             rst[i].t=R-g[pos][0];
  86.             rst[i].ct=pos;
  87.         }
  88.         else    vis[pos]=1;
  89.     }
  90.     dfs2(1,1);
  91.     for(int i=head[1];i!=-1;i=e[i].nxt){
  92.         int v=e[i].v;
  93.         if(leaf[v]){
  94.             p[++cnt].nd=e[i].w;
  95.             p[cnt].ct=v;
  96.         }
  97.     }
  98.     sort(rst+1,rst+m+1,cmp1);
  99.     sort(p+1,p+cnt+1,cmp2);
  100.     int tmp=1;
  101.     for(int i=1;i<=cnt;++i){
  102.         while(rst[tmp].ct<p[i].ct&&tmp<=m) tmp++;
  103.         if(rst[tmp].ct==p[i].ct&&rst[tmp].t<p[i].nd) {
  104.             p[i].nd=0;
  105.             rst[tmp++].t=0;
  106.         }
  107.     }
  108.     sort(rst+1,rst+m+1,cmp3);
  109.     sort(p+1,p+cnt+1,cmp4);
  110.     for(int i=1;i<=cnt;++i)
  111.         if(rst[i].t<p[i].nd) return false;
  112.     return true;
  113. }
  115. int main(){
  116.     int a,b,c;
  117. //  freopen("a.txt","r",stdin);
  118. //  freopen("a.out","w",stdout);
  119.     memset(head,-1,sizeof(head));
  120.     n=read();
  121.     for(int i=1;i<n;++i){
  122.         a=read();b=read();c=read();
  123.         adde(a,b,c);adde(b,a,c);
  124.         r+=c;
  125.     }
  126.     dfs(1,1,0);
  127.     for(int i=1;i<=D;++i)
  128.         for(int j=1;j<=n;++j){
  129.             f[j][i]=f[f[j][i-1]][i-1];
  130.             g[j][i]=g[f[j][i-1]][i-1]+g[j][i-1];
  131.         }
  133.     m=read();
  134.     for(int i=1;i<=m;++i)   {
  135.         ar[i]=read();
  136.     }
  138.     while(l<=r){
  139.         mid=(l+r)>>1;
  140.         if(Check(mid)) {ans=mid;r=mid-1;}
  141.         else l=mid+1;
  142.     }
  143.     printf("%lld\n",ans);
  144.     return 0;
  145. }

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

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