[关闭]
@y20070316 2017-02-14T06:11:24.000000Z 字数 6142 阅读 935

GDKOI2017模拟赛

OI 校内赛

【bzoj1824】path - A*+堆求K短路

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  7. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  9. #define X first
  10. #define Y second
  12. #define LL long long
  14. LL rd(void);
  16. const int N=1024;
  17. const LL MAX=(LL)1e16;
  19. int n,m;
  20. struct Ed {
  21.     int v;
  22.     LL d;
  23.     Ed(int _v=0,LL _d=0) {
  24.         v=_v;
  25.         d=_d;
  26.     }
  27. };
  28. vector<Ed> fac_g[N],rev_g[N];
  29. int s,t,k;
  31. int vis[N];
  32. LL h[N];
  33. priority_queue< pair<LL,int> > q;
  35. struct Info {
  36.     LL f;
  37.     LL g;
  38.     int id;
  39.     Info(LL _f=0,LL _g=0,int _id=0) {
  40.         f=_f;
  41.         g=_g;
  42.         id=_id;
  43.     }
  44.     friend int operator < (Info a,Info b) {
  45.         return a.f>b.f;
  46.     }
  47. };
  48. priority_queue<Info> q2;
  49. int cnt;
  51. int main(void) {
  52.     #ifndef ONLINE_JUDGE
  53.         freopen("A.in","r",stdin);
  54.         freopen("A.out","w",stdout);
  55.     #endif
  57.     n=rd(),m=rd();
  58.     F(i,1,m) {
  59.         int x=rd(),y=rd();
  60.         LL z=rd();
  61.         fac_g[x].push_back(Ed(y,z));
  62.         rev_g[y].push_back(Ed(x,z));
  63.     }
  64.     s=rd(),t=rd(),k=rd();
  66.     fill(h,h+N,MAX);
  67.     q.push(make_pair(0,t));
  68.     while (!q.empty()) {
  69.         pair<LL,int> x=q.top();
  70.         q.pop();
  71.         if (vis[x.Y])
  72.             continue;
  73.         h[x.Y]=-x.X;
  74.         vis[x.Y]=1;
  75.         F(i,1,rev_g[x.Y].size())
  76.             if (!vis[rev_g[x.Y][i-1].v])
  77.                 q.push(make_pair(-h[x.Y]-rev_g[x.Y][i-1].d,rev_g[x.Y][i-1].v));
  78.     }
  79.     if (h[s]==MAX) {
  80.         printf("-1\n");
  81.         return 0;
  82.     }
  84.     q2.push(Info(0+h[s],0,s));
  85.     while (!q2.empty()) {
  86.         Info x=q2.top();
  87.         q2.pop();
  88.         if (x.id==t) {
  89.             cnt++;
  90.             if (cnt==k) {
  91.                 printf("%lld\n",x.g);
  92.                 return 0;
  93.             }
  94.         }
  95.         F(i,1,fac_g[x.id].size())
  96.             q2.push(Info(x.g+fac_g[x.id][i-1].d+h[fac_g[x.id][i-1].v],x.g+fac_g[x.id][i-1].d,fac_g[x.id][i-1].v));
  97.     }
  98.     printf("-1\n");
  100.     return 0;
  101. }
  103. LL rd(void) {
  104.     LL x=0,f=1; char c=getchar();
  105.     while (!isdigit(c)) {
  106.         if (c=='-') f=-1;
  107.         c=getchar();
  108.     }
  109.     while (isdigit(c)) {
  110.         x=x*10+c-'0';
  111.         c=getchar();
  112.     }
  113.     return x*f;
  114. }

【xsy1822】set - 可持久化并查集

以后写完题目的时候，若样例比较费，要自己再手出一下。

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <algorithm>
  4. using namespace std;
  6. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  8. int rd(void);
  10. const int M=32768;
  11. const int S=1048576;
  13. int n,m;
  15. int tot,root[M];
  16. struct Info {
  17.     int f;
  18.     int g;
  19.     Info(int _f=0,int _g=0) {
  20.         f=_f;
  21.         g=_g;
  22.     }
  23. };
  24. struct Tree {
  25.     int l,r;
  26.     int lc,rc;
  27.     Info data;
  28. }tr[S];
  30. int Copynode(int frm) {
  31.     int x=++tot;
  32.     tr[x]=tr[frm];
  33.     return x;
  34. }
  36. int Build(int l,int r) {
  37.     int x=++tot;
  38.     tr[x].l=l,tr[x].r=r;
  39.     if (l!=r) {
  40.         int mid=(l+r)>>1;
  41.         tr[x].lc=Build(l,mid);
  42.         tr[x].rc=Build(mid+1,r);
  43.     }
  44.     else tr[x].data=Info(l,0);
  45.     return x;
  46. }
  48. Info Query(int x,int loc) {
  49.     if (tr[x].l==tr[x].r)
  50.         return tr[x].data;
  51.     int mid=(tr[x].l+tr[x].r)>>1;
  52.     if (loc<=mid)
  53.         return Query(tr[x].lc,loc);
  54.     else return Query(tr[x].rc,loc);
  55. }
  57. Info Find(int rt,int loc) {
  58.     Info f_pos=Query(rt,loc);
  59.     while (loc!=f_pos.f) {
  60.         loc=f_pos.f;
  61.         f_pos=Query(rt,loc);
  62.     }
  63.     return f_pos;
  64. }
  66. int Modify(int frm,int loc,Info data) {
  67.     int x=Copynode(frm);
  68.     if (tr[x].l==tr[x].r) {
  69.         tr[x].data=data;
  70.         return x;
  71.     }
  72.     int mid=(tr[x].l+tr[x].r)>>1;
  73.     if (loc<=mid)
  74.         tr[x].lc=Modify(tr[frm].lc,loc,data);
  75.     else tr[x].rc=Modify(tr[frm].rc,loc,data);
  76.     return x;
  77. }
  79. int main(void) {
  80.     #ifndef ONLINE_JUDGE
  81.         freopen("B.in","r",stdin);
  82.         freopen("B.out","w",stdout);
  83.     #endif
  85.     n=rd(),m=rd();
  86.     root[0]=Build(1,n);
  88.     F(i,1,m) {
  89.         int kd=rd();
  90.         if (kd==1) {
  91.             int a=rd(),b=rd();
  92.             Info fa=Find(root[i-1],a);
  93.             Info fb=Find(root[i-1],b);
  94.             if (fa.f==fb.f)
  95.                 root[i]=root[i-1];
  96.             else {
  97.                 if (fa.g>fb.g)
  98.                     swap(fa,fb);
  99.                 int t=Modify(root[i-1],fa.f,Info(fb.f,fa.g));
  100.                 root[i]=Modify(t,fb.f,Info(fb.f,max(fa.g+1,fb.g)));
  101.             }
  102.         }
  103.         else if (kd==2) {
  104.             int k=rd();
  105.             root[i]=root[k];
  106.         }
  107.         else {
  108.             int a=rd(),b=rd();
  109.             Info fa=Find(root[i-1],a);
  110.             Info fb=Find(root[i-1],b);
  111.             printf("%d\n",fa.f==fb.f);
  112.             root[i]=root[i-1];
  113.         }
  114.     }
  116.     return 0;
  117. } 
  119. int rd(void) {
  120.     int x=0,f=1; char c=getchar();
  121.     while (!isdigit(c)) {
  122.         if (c=='-') f=-1;
  123.         c=getchar();
  124.     }
  125.     while (isdigit(c)) {
  126.         x=x*10+c-'0';
  127.         c=getchar();
  128.     }
  129.     return x*f;
  130. }

【xsy1825】sequence - 非旋Treap

注意字符串的空间问题。
至少要开大2，而不是1！！

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cctype>
  4. #include <ctime>
  5. #include <algorithm>
  6. #include <cassert>
  7. using namespace std;
  9. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  11. #define LL long long
  13. LL rd(void);
  15. const int N=262144;
  17. int n;
  18. char s[16];
  20. int m;
  21. int root,tot;
  22. struct Treap {
  23.     int lc,rc;
  25.     LL key;
  26.     int fix;
  28.     int siz;
  30.     int rev_tag;
  31.     LL delta;
  32.     LL min_val;
  33. }tr[N];
  34. struct D {
  35.     int lc,rc;
  36.     D(int _lc=0,int _rc=0) {
  37.         lc=_lc,rc=_rc;
  38.     }
  39. };
  41. int Newnode(LL val) {
  42.     int x=++tot;
  44.     tr[x].lc=tr[x].rc=0;
  46.     tr[x].key=val;
  47.     tr[x].fix=rand();
  49.     tr[x].siz=1;
  51.     tr[x].rev_tag=0;
  52.     tr[x].delta=0;
  53.     tr[x].min_val=val;
  55.     return x;
  56. }
  58. void Update(int x) {
  59.     int lc=tr[x].lc;
  60.     int rc=tr[x].rc;
  62.     tr[x].siz=tr[lc].siz+1+tr[rc].siz;
  64.     tr[x].min_val=tr[x].key;
  65.     if (lc>0)
  66.         tr[x].min_val=min(tr[x].min_val,tr[lc].min_val);
  67.     if (rc>0)
  68.         tr[x].min_val=min(tr[x].min_val,tr[rc].min_val);
  69. }
  71. void Rev(int x) {
  72.     tr[x].rev_tag^=1;
  73.     swap(tr[x].lc,tr[x].rc);
  74. }
  76. void Push_del(int x,LL d) {
  77.     tr[x].key+=d;
  78.     tr[x].delta+=d;
  79.     tr[x].min_val+=d;
  80. }
  82. void Clear(int x) {
  83.     int lc=tr[x].lc;
  84.     int rc=tr[x].rc;
  86.     if (tr[x].rev_tag) {
  87.         if (lc>0)
  88.             Rev(lc);
  89.         if (rc>0)
  90.             Rev(rc);
  91.         tr[x].rev_tag=0;
  92.     }
  94.     if (tr[x].delta!=0) {
  95.         if (lc>0)
  96.             Push_del(lc,tr[x].delta);
  97.         if (rc>0)
  98.             Push_del(rc,tr[x].delta);
  99.         tr[x].delta=0;
  100.     }
  101. }
  103. int Merge(int x,int y) {
  104.     if (!x||!y)
  105.         return x+y;
  106.     if (tr[x].fix<tr[y].fix) {
  107.         Clear(x);
  108.         tr[x].rc=Merge(tr[x].rc,y);
  109.         Update(x);
  110.         return x;
  111.     }
  112.     else {
  113.         Clear(y);
  114.         tr[y].lc=Merge(x,tr[y].lc);
  115.         Update(y);
  116.         return y;
  117.     }
  118. }
  120. D Split(int x,int rk) {
  121.     if (!rk)
  122.         return D(0,x);
  123.     Clear(x);
  124.     D t;
  125.     if (rk<=tr[tr[x].lc].siz) {
  126.         t=Split(tr[x].lc,rk);
  127.         tr[x].lc=t.rc;
  128.         Update(x);
  129.         t.rc=x;
  130.     }
  131.     else {
  132.         t=Split(tr[x].rc,rk-tr[tr[x].lc].siz-1);
  133.         tr[x].rc=t.lc;
  134.         Update(x);
  135.         t.lc=x;
  136.     }
  137.     return t;
  138. }
  140. void Add(int &rt,int x,int y,LL d) {
  141.     D tx=Split(rt,y);
  142.     D ty=Split(tx.lc,x-1);
  143.     Push_del(ty.rc,d);
  144.     rt=Merge(Merge(ty.lc,ty.rc),tx.rc);
  145. }
  147. void Reverse(int &rt,int x,int y) {
  148.     D tx=Split(rt,y);
  149.     D ty=Split(tx.lc,x-1);
  150.     Rev(ty.rc);
  151.     rt=Merge(Merge(ty.lc,ty.rc),tx.rc);
  152. }
  154. void Revolve(int &rt,int x,int y,int t) {
  155.     D tx=Split(rt,y);
  156.     D ty=Split(tx.lc,x-1);
  157.     t%=tr[ty.rc].siz;
  158.     D tz=Split(ty.rc,tr[ty.rc].siz-t);
  159.     rt=Merge(Merge(ty.lc,Merge(tz.rc,tz.lc)),tx.rc);
  160. }
  162. void Insert(int &rt,int rk,LL val) {
  163.     D tx=Split(rt,rk);
  164.     int x=Newnode(val);
  165.     rt=Merge(Merge(tx.lc,x),tx.rc);
  166. }
  168. void Delete(int &rt,int rk) {
  169.     D tx=Split(rt,rk-1);
  170.     D ty=Split(tx.rc,1);
  171.     rt=Merge(tx.lc,ty.rc);
  172. }
  174. LL GetMin(int rt,int x,int y) {
  175.     D tx=Split(rt,y);
  176.     D ty=Split(tx.lc,x-1);
  177.     LL ans=tr[ty.rc].min_val;
  178.     rt=Merge(Merge(ty.lc,ty.rc),tx.rc);
  179.     return ans;
  180. }
  182. int main(void) {
  183.     #ifndef ONLINE_JUDGE
  184.         freopen("C.in","r",stdin);
  185.         freopen("C.out","w",stdout);
  186.     #endif
  188.     srand(time(0));
  189.     n=rd();
  190.     F(i,1,n) {
  191.         LL x=rd();
  192.         root=Merge(root,Newnode(x));
  193.     }
  195.     m=rd();
  196.     F(i,1,m) {
  197.         scanf("%s",s+1);
  198.         if (s[1]=='A') {
  199.             int x=rd(),y=rd();
  200.             LL d=rd();
  201.             Add(root,x,y,d);
  202.         }
  203.         else if (s[1]=='R'&&s[4]=='E') {
  204.             int x=rd(),y=rd();
  205.             Reverse(root,x,y);
  206.         }
  207.         else if (s[1]=='R'&&s[4]=='O') {
  208.             int x=rd(),y=rd(),t=rd();
  209.             Revolve(root,x,y,t);
  210.         }
  211.         else if (s[1]=='I') {
  212.             int x=rd(); LL p=rd();
  213.             Insert(root,x,p);
  214.         }
  215.         else if (s[1]=='D') {
  216.             int x=rd();
  217.             Delete(root,x);
  218.         }
  219.         else if (s[1]=='M') {
  220.             int x=rd(),y=rd();
  221.             LL ans=GetMin(root,x,y);
  222.             printf("%lld\n",ans);
  223.         }
  224.     }
  226.     return 0;
  227. }
  229. LL rd(void) {
  230.     LL x=0,f=1; char c=getchar();
  231.     while (!isdigit(c)) {
  232.         if (c=='-') f=-1;
  233.         c=getchar();
  234.     }
  235.     while (isdigit(c)) {
  236.         x=x*10+c-'0';
  237.         c=getchar();
  238.     }
  239.     return x*f;
  240. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注