• 22/8/3-杭电多校5

    1010，1003，1012；

    1，1010；

    只有是两边都是全部牌都不一样，即第三条规则，那么yahaha是无法叫的，一定会被challenge；

    会输，其余情况都是赢；

    2，1003；

    难点在于如何将两层的图建好；

    一开始找了一个虚拟节点，将所有来到该节点路径的边权设为p，所有从该节点的路径设为0；

    但是每两层要换一个；

    按理说同层之间还是可以相互到达，且路径为p，但是没wa；

    code：

    1. #pragma GCC optimize(2)
    2. #include
    3. #define rep1(i,a,n) for(register int i=(a);i<(n);++i) 
    4. #define rep2(i,a,n) for(register int i=(a);i<=(n);++i) 
    5. #define per1(i,n,a) for( int i=(n);i>(a);i--) 
    6. #define per2(i,n,a) for( int i=(n);i>=(a);i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define pro_q priority_queue
    11. #define eb emplace_back
    12. #define endl "\n"
    13. #define lowbit(m) ((-m)&(m))
    14. #define dbug(y) cout<<(y)<<"\n"
    15. #define dbug2(a,b) cout<<(a)<<" "<<(b)<<"\n"
    16. #define dbug3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<"\n"
    17. #define dbug4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<"\n"
    18. #define yi first
    19. #define er second
    20. #define tulun int e[N],ne[N],h[N],w[N],idx;
    21. #define add2(a,b) e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    22. #define add3(a,b,c) w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    23. #define T_solve() int T;cin>>T;while(T--)solve();
    24. #define pi 3.14159265358979323846
    25. using namespace std;
    26. typedef long long LL;
    27. typedef pair<int,int> PII;
    28. typedef pair<long long,long long> PLL;
    29. typedef double dob;
    30.  
    31. const int N=3e6+10;
    32.  
    33. int e[N],ne[N],h[N],idx;
    34. LL w[N];
    35. void add(int a,int b,int c)
    36. {
    37.     w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    38. }
    39. int k,p;
    40. int s,t;
    41. int d[N];
    42. int q[N<<1];
    43. int ceng_db[N];
    44. vector<int>ceng[N];
    45. int n,maxd;
    46. void bfs()
    47. {
    48.     int hh=0,tt=0;
    49.     q[0]=1;
    50.     d[1]=1;
    51.     ceng_db[1]=1;
    52.     while(hh<=tt)
    53.     {
    54.         int t=q[hh++];
    55.         bool f=0;
    56.         for(int i=h[t];~i;i=ne[i])
    57.         {
    58.             int j=e[i];
    59.             if(!d[j])
    60.             {
    61.                 d[j]=d[t]+1;
    62.                 maxd=max(maxd,d[j]);
    63.                 if(!f)
    64.                 {
    65.                     f=1;
    66.                     ceng_db[d[j]]=j;
    67.                 }
    68.                 q[++tt]=j;
    69.             }
    70.         }
    71.     }
    72.     rep2(i,1,n)
    73.     {
    74.         ceng[d[i]].emplace_back(i);
    75.     }
    76. }
    77. LL dist[N];
    78. int st[N];
    79. void dijkstra()
    80. {
    81.     pro_q,greater>heap;
    82.     heap.push({0,s});
    83.     dist[s]=0;
    84.     while(heap.size())
    85.     {
    86.         auto tt=heap.top();
    87.         heap.pop();
    88.         int t=tt.second;
    89.         if(st[t])continue;
    90.         st[t]=1;
    91.         for(int i=h[t];~i;i=ne[i])
    92.         {
    93.             int j=e[i];
    94.          //   dbug4(j,dist[j],dist[t],w[i]);
    95.             if(dist[j]>dist[t]+w[i])
    96.             {
    97.                 dist[j]=dist[t]+w[i];
    98.             //    dbug3(t,j,dist[j]); 
    99.                 heap.push({dist[j],j});
    100.             }
    101.         }
    102.     }
    103. }
    104. void solve()
    105. {
    106.     memset(h,-1,h);
    107.     maxd=0;
    108.     idx=0;
    109.     cin>>n;
    110.     memset(st,0,st);
    111.     memset(dist,0x3f,dist);
    112.     memset(d,0,d);
    113.     rep2(i,0,n+5)ceng[i].clear();
    114.     rep2(i,1,n-1)
    115.     {
    116.         int a,b,c;
    117.         cin>>a>>b>>c;
    118.         add(a,b,c);
    119.         add(b,a,c);
    120.     }
    121.     cin>>k>>p;
    122.     cin>>s>>t;
    123.     bfs();
    124.     int superv=n+1;
    125.     rep2(i,1,maxd-k)
    126.     {
    127.         int nn=i+k;
    128.         int siz1=ceng[i].size();
    129.         int siz2=ceng[nn].size();
    130.         rep1(j,0,siz1)
    131.         {
    132.             add(superv,ceng[i][j],0);
    133.             add(ceng[i][j],superv,p);
    134.         }
    135.         rep1(j,0,siz2)
    136.         {
    137.             add(ceng[nn][j],superv,p);
    138.             add(superv,ceng[nn][j],0);
    139.         }
    140.         superv++;
    141.     }
    142.     //rep2(i,1,n+1)dbug2(i,dist[i]);
    143.     dijkstra();
    144.     dbug(dist[t]);
    145.  
    146. }
    147.  
    148. signed main()
    149. {
    150.     quick_cin();
    151.     T_solve();
    152.     return 0;
    153. }

    真正维护好同层之间关系的是每层用两个点，d1，d2；

    上一层都指向d1，边权为p，然后d1指向下一层，边权为0；

    下一层都指向d2，边权为p，然后d2指向上一层，边权为0；

    这样同层之间达到路径就是2p；

    code：唯一区别就是建图；

    1. #pragma GCC optimize(2)
    2. #include
    3. #define rep1(i,a,n) for(register int i=(a);i<(n);++i) 
    4. #define rep2(i,a,n) for(register int i=(a);i<=(n);++i) 
    5. #define per1(i,n,a) for( int i=(n);i>(a);i--) 
    6. #define per2(i,n,a) for( int i=(n);i>=(a);i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define pro_q priority_queue
    11. #define eb emplace_back
    12. #define endl "\n"
    13. #define lowbit(m) ((-m)&(m))
    14. #define dbug(y) cout<<(y)<<"\n"
    15. #define dbug2(a,b) cout<<(a)<<" "<<(b)<<"\n"
    16. #define dbug3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<"\n"
    17. #define dbug4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<"\n"
    18. #define yi first
    19. #define er second
    20. #define tulun int e[N],ne[N],h[N],w[N],idx;
    21. #define add2(a,b) e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    22. #define add3(a,b,c) w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    23. #define T_solve() int T;cin>>T;while(T--)solve();
    24. #define pi 3.14159265358979323846
    25. using namespace std;
    26. typedef long long LL;
    27. typedef pair<int,int> PII;
    28. typedef pair<long long,long long> PLL;
    29. typedef double dob;
    30.  
    31. const int N=3e6+10;
    32.  
    33. int e[N],ne[N],h[N],idx;
    34. LL w[N];
    35. void add(int a,int b,int c)
    36. {
    37.     w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    38. }
    39. int k,p;
    40. int s,t;
    41. int d[N];
    42. int q[N<<1];
    43. int ceng_db[N];
    44. vector<int>ceng[N];
    45. int n,maxd;
    46. void bfs()
    47. {
    48.     int hh=0,tt=0;
    49.     q[0]=1;
    50.     d[1]=1;
    51.     ceng_db[1]=1;
    52.     while(hh<=tt)
    53.     {
    54.         int t=q[hh++];
    55.         bool f=0;
    56.         for(int i=h[t];~i;i=ne[i])
    57.         {
    58.             int j=e[i];
    59.             if(!d[j])
    60.             {
    61.                 d[j]=d[t]+1;
    62.                 maxd=max(maxd,d[j]);
    63.                 if(!f)
    64.                 {
    65.                     f=1;
    66.                     ceng_db[d[j]]=j;
    67.                 }
    68.                 q[++tt]=j;
    69.             }
    70.         }
    71.     }
    72.     rep2(i,1,n)
    73.     {
    74.         ceng[d[i]].emplace_back(i);
    75.     }
    76. }
    77. LL dist[N];
    78. int st[N];
    79. void dijkstra()
    80. {
    81.     pro_q,greater>heap;
    82.     heap.push({0,s});
    83.     dist[s]=0;
    84.     while(heap.size())
    85.     {
    86.         auto tt=heap.top();
    87.         heap.pop();
    88.         int t=tt.second;
    89.         if(st[t])continue;
    90.         st[t]=1;
    91.         for(int i=h[t];~i;i=ne[i])
    92.         {
    93.             int j=e[i];
    94.          //   dbug4(j,dist[j],dist[t],w[i]);
    95.             if(dist[j]>dist[t]+w[i])
    96.             {
    97.                 dist[j]=dist[t]+w[i];
    98.             //    dbug3(t,j,dist[j]); 
    99.                 heap.push({dist[j],j});
    100.             }
    101.         }
    102.     }
    103. }
    104. void solve()
    105. {
    106.     memset(h,-1,h);
    107.     maxd=0;
    108.     idx=0;
    109.     cin>>n;
    110.     memset(st,0,st);
    111.     memset(dist,0x3f,dist);
    112.     memset(d,0,d);
    113.     rep2(i,0,n+5)ceng[i].clear();
    114.     rep2(i,1,n-1)
    115.     {
    116.         int a,b,c;
    117.         cin>>a>>b>>c;
    118.         add(a,b,c);
    119.         add(b,a,c);
    120.     }
    121.     cin>>k>>p;
    122.     cin>>s>>t;
    123.     bfs();
    124.     int superv=n+1;
    125.     rep2(i,1,maxd-k)
    126.     {
    127.         int nn=i+k;
    128.         int d1=superv;
    129.         superv++;
    130.         int d2=superv;
    131.         int siz1=ceng[i].size();
    132.         int siz2=ceng[nn].size();
    133.         rep1(j,0,siz1)
    134.         {
    135.             add(d2,ceng[i][j],0);
    136.             add(ceng[i][j],d1,p);
    137.         }
    138.         rep1(j,0,siz2)
    139.         {
    140.             add(ceng[nn][j],d2,p);
    141.             add(d1,ceng[nn][j],0);
    142.         }
    143.     }
    144.     //rep2(i,1,n+1)dbug2(i,dist[i]);
    145.     dijkstra();
    146.     dbug(dist[t]);
    147.  
    148. }
    149. signed main()
    150. {
    151.     quick_cin();
    152.     T_solve();
    153.     return 0;
    154. }

    3，1012；

    开个线段树统计1~m窗口的人数和编号；

    关键在于如何更新队伍人数；

    开个小根堆记录离开时间和所在窗口，每次只要到了时间，都给他离开掉；

    1. #pragma GCC optimize(2)
    2. #include
    3. #define rep1(i,a,n) for(register int i=(a);i<(n);++i) 
    4. #define rep2(i,a,n) for(register int i=(a);i<=(n);++i) 
    5. #define per1(i,n,a) for( int i=(n);i>(a);i--) 
    6. #define per2(i,n,a) for( int i=(n);i>=(a);i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define pro_q priority_queue
    11. #define eb emplace_back
    12. #define endl "\n"
    13. #define lowbit(m) ((-m)&(m))
    14. #define dbug(y) cout<<(y)<<"\n"
    15. #define dbug2(a,b) cout<<(a)<<" "<<(b)<<"\n"
    16. #define dbug3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<"\n"
    17. #define dbug4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<"\n"
    18. #define yi first
    19. #define er second
    20. #define tulun int e[N],ne[N],h[N],w[N],idx;
    21. #define add2(a,b) e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    22. #define add3(a,b,c) w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    23. #define T_solve() int T;cin>>T;while(T--)solve();
    24. #define pi 3.14159265358979323846
    25. using namespace std;
    26. typedef long long LL;
    27. #define int LL
    28. typedef pair<int,int> PII;
    29. typedef pair<long long,long long> PLL;
    30. typedef double dob;
    31. const int N=2e6+10;
    32. int n,m,a[N];
    33. int leave[N];
    34. struct node1
    35. {
    36.     int start,len;
    37.     bool operator <(const node1 &B)const
    38.     {
    39.         return start
    40.     }
    41. }p[N];
    42. struct node2
    43. {
    44.     int l,r;
    45.     int id,minv;
    46. }tr[N<<2];
    47. void pushup(int u)
    48. {
    49.     tr[u].minv=min(tr[u<<1].minv,tr[u<<1|1].minv);
    50.     if(tr[u<<1].minv==tr[u].minv)tr[u].id=tr[u<<1].id;
    51.     else tr[u].id=tr[u<<1|1].id;
    52. }
    53. void build(int u,int l,int r)
    54. {
    55.     tr[u]={l,r,l,0};
    56.     if(l==r)return;
    57.     int mid=l+r>>1;
    58.     build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    59.     pushup(u);
    60. }
    61. void modify(int u,int x,int v)
    62. {
    63.     if(x==tr[u].l&&x==tr[u].r)
    64.     {
    65.         tr[u].minv+=v;
    66.     }
    67.     else
    68.     {
    69.         int mid=tr[u].l+tr[u].r>>1;
    70.         if(x<=mid)modify(u<<1,x,v);
    71.         if(x>mid)modify(u<<1|1,x,v);
    72.         pushup(u);
    73.     }
    74. }
    75. int query(int u,int l,int r)
    76. {
    77.     return tr[u].id; 
    78. }
    79. void solve()
    80. {
    81.     cin>>n>>m;
    82.     rep2(i,1,n)
    83.     {
    84.         int a,b;
    85.         cin>>a>>b;
    86.         p[i]={a,b};
    87.     }
    88.     rep2(i,1,m)leave[i]=0;
    89.     build(1,1,m);
    90.     sort(p+1,p+n+1);
    91.     pro_q,greater>q;
    92.     int ans=0;
    93.     rep2(i,1,n)
    94.     {
    95.         while(q.size()&&q.top().first<=p[i].start)
    96.         {
    97.             modify(1,q.top().second,-1);
    98.             q.pop();
    99.         }
    100.         int pos=query(1,1,m);
    101.         modify(1,pos,1);
    102.         leave[pos]=max(p[i].start,leave[pos])+p[i].len;
    103.         q.push({leave[pos],pos});
    104.         ans=max(leave[pos],ans);
    105.     }
    106.     dbug(ans);
    107. }
    108. signed main()
    109. {
    110.     quick_cin();
    111.     T_solve();
    112.     return 0;
    113. }
    1. #pragma GCC optimize(2)
    2. #include
    3. #define rep1(i,a,n) for(register int i=(a);i<(n);++i) 
    4. #define rep2(i,a,n) for(register int i=(a);i<=(n);++i) 
    5. #define per1(i,n,a) for( int i=(n);i>(a);i--) 
    6. #define per2(i,n,a) for( int i=(n);i>=(a);i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define pro_q priority_queue
    11. #define eb emplace_back
    12. #define endl "\n"
    13. #define lowbit(m) ((-m)&(m))
    14. #define dbug(y) cout<<(y)<<"\n"
    15. #define dbug2(a,b) cout<<(a)<<" "<<(b)<<"\n"
    16. #define dbug3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<"\n"
    17. #define dbug4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<"\n"
    18. #define yi first
    19. #define er second
    20. #define tulun int e[N],ne[N],h[N],w[N],idx;
    21. #define add2(a,b) e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    22. #define add3(a,b,c) w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    23. #define T_solve() int T;cin>>T;while(T--)solve();
    24. #define pi 3.14159265358979323846
    25. using namespace std;
    26. typedef long long LL;
    27. #define int LL
    28. typedef pair<int,int> PII;
    29. typedef pair<long long,long long> PLL;
    30. typedef double dob;
    31. const int N=2e6+10;
    32. int n,m,a[N];
    33. int leave[N];
    34. struct node1
    35. {
    36.     int start,len;
    37.     bool operator <(const node1 &B)const
    38.     {
    39.         return start
    40.     }
    41. }p[N];
    42. struct node2
    43. {
    44.     int l,r;
    45.     int id,minv;
    46. }tr[N<<2];
    47. void pushup(int u)
    48. {
    49.     tr[u].minv=min(tr[u<<1].minv,tr[u<<1|1].minv);
    50.     if(tr[u<<1].minv==tr[u].minv)tr[u].id=tr[u<<1].id;
    51.     else tr[u].id=tr[u<<1|1].id;
    52. }
    53. void build(int u,int l,int r)
    54. {
    55.     tr[u]={l,r,l,0};
    56.     if(l==r)return;
    57.     int mid=l+r>>1;
    58.     build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    59.     pushup(u);
    60. }
    61. void modify(int u,int x,int v)
    62. {
    63.     if(x==tr[u].l&&x==tr[u].r)
    64.     {
    65.         tr[u].minv+=v;
    66.     }
    67.     else
    68.     {
    69.         int mid=tr[u].l+tr[u].r>>1;
    70.         if(x<=mid)modify(u<<1,x,v);
    71.         if(x>mid)modify(u<<1|1,x,v);
    72.         pushup(u);
    73.     }
    74. }
    75. int query(int u,int l,int r)
    76. {
    77.     return tr[u].id; 
    78. }
    79. void solve()
    80. {
    81.     cin>>n>>m;
    82.     rep2(i,1,n)
    83.     {
    84.         int a,b;
    85.         cin>>a>>b;
    86.         p[i]={a,b};
    87.     }
    88.     rep2(i,1,m)leave[i]=0;
    89.     build(1,1,m);
    90.     sort(p+1,p+n+1);
    91.     pro_q,greater>q;
    92.     int ans=0;
    93.     rep2(i,1,n)
    94.     {
    95.         while(q.size()&&q.top().first<=p[i].start)
    96.         {
    97.             modify(1,q.top().second,-1);
    98.             q.pop();
    99.         }
    100.         int pos=query(1,1,m);
    101.         modify(1,pos,1);
    102.         leave[pos]=max(p[i].start,leave[pos])+p[i].len;
    103.         q.push({leave[pos],pos});
    104.         ans=max(leave[pos],ans);
    105.     }
    106.     dbug(ans);
    107. }
    108. signed main()
    109. {
    110.     quick_cin();
    111.     T_solve();
    112.     return 0;
    113. }

  • 相关阅读:
    redis的原理和源码-主从复制的原理介绍
    【kafka】十四、kafka生产者API
    【数据结构】排序3——交换排序（冒泡排序、快速排序）
    JavaScript (上篇)
    【UGUI】给美术的备忘录
    Cryptographic primitives（密码原语）
    SpringCloud无介绍快使用，gateway的基本使用（十六）
    数据异常值检测
    第二十一章 源代码文件 REST API 参考（三）
    Linux编译器gcc的使用
  • 原文地址：https://blog.csdn.net/aidaqiudeaichao/article/details/126140332