[关闭]
@jason-fan 2021-05-01T03:14:19.000000Z 字数 9039 阅读 260

省选联考 2021 A卷代码

CODE

D1T1 card

  1. #include <bits/stdc++.h>
  2. template<typename _Tp>
  3. inline void read(_Tp &x) {
  4.     x=0;bool fg=0;char ch=getchar();
  5.     while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
  6.     while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(_Tp)(ch^48),ch=getchar();
  7.     if(fg) x=-x;
  8. }
  9. template<typename _Tp,typename... Args>void read(_Tp &t,Args &... args){read(t);read(args...);}
  10. using namespace std;
  11. typedef long long ll;
  12. const int N = 1000010;
  14. int n,m,a[N],b[N];
  15. struct pp {
  16.     int ps,vl,fg;
  17.     bool operator<(const pp &a) const {
  18.         return vl<a.vl;
  19.     }
  20. }p[N*2];
  21. int sta[N*2];
  23. bool check(int gap) {
  24.     for(int i=1;i<=n;++i) sta[i]=0;
  25.     int used=0,cnt=0;
  27.     int l,r=0;
  28.     for(l=1;l<=2*n;++l) {
  29.         // erase l-1
  30.         if(l>1) {
  31.             pp t=p[l-1];
  32.             sta[t.ps]-=t.fg;
  33.             if(sta[t.ps]==0) --cnt;
  35.             if(t.fg==1) {
  36.                 if(sta[t.ps]) ++used;
  37.             }else {
  38.                 if(sta[t.ps]==0) --used;
  39.             }
  40.         }
  42.         while(r<2*n&&p[r+1].vl-p[l].vl<=gap) {
  43.             ++r;
  44.             // insert r
  45.             pp t=p[r];
  46.             if(sta[t.ps]==0) ++cnt; 
  47.             if(t.fg==1) {
  48.                 if(sta[t.ps]) --used;
  49.             }else {
  50.                 if(sta[t.ps]==0) ++used;
  51.             }
  52.             sta[t.ps]+=t.fg;
  53.         }
  55.         if(cnt==n&&used<=m) return true;
  56.     }
  57.     return false;
  59. }
  61. int main() {
  62.     read(n);read(m);
  63.     for(int i=1;i<=n;++i) read(a[i]);
  64.     for(int i=1;i<=n;++i) read(b[i]);
  66.     for(int i=1;i<=n;++i) {
  67.         p[i].ps=i;p[i].vl=a[i];p[i].fg=1;
  68.         p[i+n].ps=i;p[i+n].vl=b[i];p[i+n].fg=2;
  69.     }
  71.     sort(p+1,p+2*n+1);
  72.     int L=1,R=1e9,M,B;
  73.     while(L<=R) {
  74.         M=(L+R)>>1;
  75.         if(check(M)) B=M,R=M-1;
  76.         else L=M+1;
  77.     }
  78.     cout<<B<<endl;
  79.     return 0;
  80. }

D1T2 matrix

  1. #include <bits/stdc++.h>
  2. #define re register
  3. template<typename _Tp>
  4. inline void read(_Tp &x) {
  5.     x=0;bool fg=0;char ch=getchar();
  6.     while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
  7.     while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(_Tp)(ch^48),ch=getchar();
  8.     if(fg) x=-x;
  9. }
  10. using namespace std;
  11. typedef long long ll;
  12. const int N = 305;
  13. const int Max = 1000000;
  15. ll a[N][N],b[N][N];
  16. int n,m,T;
  18. ll c[N][N];
  20. namespace QAQ {  // 差分约束
  21.     const int N = 610;
  22.     const int M = 370010;
  23.     ll w[N][N];
  24.     ll dis[N];
  25.     bool vis[N];
  26.     int ct[N];
  27.     // Xv-Xu<=w
  28.     void adde(int u,int v,int _w) {
  29.         w[u][v]=_w;
  30.     }
  31.     void init() { memset(w,0x3f,sizeof(w));}
  32.     bool BF() { // Bellman-Ford
  33.         memset(dis,0,sizeof(dis));
  34.         for(int ts=0;ts<=n+m;++ts) {
  35.             bool fg=0;
  36.             for(int u=1;u<=n+m;++u) {
  37.                 for(int v=(u<=n)?n+1:1,ed=(u<=n)?n+m:n;v<=ed;++v) {
  38.                     if(dis[v]>dis[u]+w[u][v]) {
  39.                         dis[v]=dis[u]+w[u][v];
  40.                         fg=1;
  41.                     }
  42.                 }
  43.             }
  44.             if(!fg) return true;
  45.         }
  46.         return false;
  47.     }
  48. }
  49. namespace checker {
  50.     void check() {
  51.         for(int i=1;i<=n;++i) {
  52.             for(int j=1;j<=n;++j) {
  53.                 if(a[i][j]<0||a[i][j]>Max) {
  54.                     cerr<<"out of bound"<<endl;
  55.                     exit(-1);
  56.                 }
  57.             }
  58.         }
  59.         for(int i=1;i<n;++i){
  60.             for(int j=1;j<m;++j) {
  61.                 if(b[i][j]!=a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1]) {
  62.                     cerr<<"don't match"<<endl;
  63.                     exit(-2);
  64.                 }
  65.             }
  66.         }
  67.     }
  68. }
  70. void solve() {
  71.     for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) a[i][j]=0;
  73.     #define idR(x) (x)
  74.     #define idC(x) (n+x)
  77.     for(re int i=n-1;i>=1;--i) {
  78.         for(re int j=m-1;j>=1;--j) {
  79.             a[i][j]=b[i][j]-a[i+1][j]-a[i][j+1]-a[i+1][j+1];
  80.         }
  81.     }
  82.     QAQ::init();
  83.     for(re int i=1;i<=n;++i) {
  84.         for(re int j=1;j<=m;++j) {
  85.             if((i+j)&1) {
  86.                 // 行＋ 列- 
  87.                 // 0 <= idR(i)-idC(j)+a[i][j] <= 1e6
  88.                 QAQ::adde(idC(j),idR(i),Max-a[i][j]);
  89.                 QAQ::adde(idR(i),idC(j),a[i][j]);
  90.             }else {
  91.                 // 行- 列+
  92.                 // 0 <= -idR(i)+idC(j)+a[i][j] <= 1e6
  93.                 QAQ::adde(idR(i),idC(j),Max-a[i][j]);
  94.                 QAQ::adde(idC(j),idR(i),a[i][j]);
  95.             }      
  96.         }
  97.     }
  98.     bool fg=QAQ::BF();
  99.     if(!fg) {puts("NO");return ;}
  100.     for(re int i=1;i<=n;++i) for(re int j=1;j<=m;++j) {
  101.         if((i+j)&1) a[i][j]=a[i][j]-QAQ::dis[idC(j)]+QAQ::dis[idR(i)];
  102.         else a[i][j]=a[i][j]+QAQ::dis[idC(j)]-QAQ::dis[idR(i)];
  103.     }
  104.     puts("YES");
  105.     // checker::check();   
  106.     for(int i=1;i<=n;++i) {
  107.         for(int j=1;j<=m;++j) printf("%lld ",a[i][j]);
  108.         printf("\n");
  109.     }
  110. }
  111. int rmain() {
  112.     read(n);read(m);
  113.     for(int i=1;i<n;++i) for(int j=1;j<m;++j) read(b[i][j]);
  114.     solve();
  115.     return 0;
  116. }
  117. int main() {
  118.     read(T);
  119.     while(T--) rmain();
  120.     return 0;
  121. }

D1T3 graph

  1. #include <bits/stdc++.h>
  2. template<typename _Tp>
  3. inline void read(_Tp &x) {
  4.     x=0;bool fg=0;char ch=getchar();
  5.     while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
  6.     while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(_Tp)(ch^48),ch=getchar();
  7.     if(fg) x=-x;
  8. }
  9. template<typename _Tp,typename... Args>void read(_Tp &t,Args &... args){read(t);read(args...);}
  10. using namespace std;
  11. typedef long long ll;
  12. const int N = 1010;
  13. const int M = 200010;
  14. struct edge {int u,v;}e[M];
  15. int n,m;
  16. vector<int> g[N],rg[N];
  18. int ans[M];
  19. bool vis[N],rvis[N];
  20. int cnt=0;
  21. void bfs(int s) {
  22.     queue<int> q;
  23.     q.push(s);vis[s]=1; if(rvis[s]) ++cnt;
  24.     while(!q.empty()) {
  25.         int u=q.front();q.pop();
  26.         for(int i=0;i<g[u].size();++i) {
  27.             int v=g[u][i];
  28.             if(!vis[v]) {
  29.                 vis[v]=1;
  30.                 if(rvis[v]) ++cnt;
  31.                 q.push(v);
  32.             }
  33.         }
  34.     }
  35. }
  37. void rbfs(int s) {
  38.     queue<int> q;
  39.     q.push(s);rvis[s]=1; if(vis[s]) ++cnt;
  40.     while(!q.empty()) {
  41.         int u=q.front();q.pop();
  42.         for(int i=0;i<rg[u].size();++i) {
  43.             int v=rg[u][i];
  44.             if(!rvis[v]) {
  45.                 rvis[v]=1;
  46.                 if(vis[v]) ++cnt;
  47.                 q.push(v);
  48.             }
  49.         }
  50.     }
  51. }
  53. int main() {
  54.     read(n);read(m);
  55.     for(int i=1;i<=m;++i) {
  56.         read(e[i].u);read(e[i].v);
  57.     }
  58.     for(int u=1;u<=n;++u) {
  59.         memset(vis,0,sizeof(vis));
  60.         memset(rvis,0,sizeof(rvis));
  61.         for(int i=1;i<=n;++i) g[i].clear(),rg[i].clear();
  63.         vis[u]=1;rvis[u]=1; ans[m+1]++;
  64.         cnt=1;
  65.         for(int i=m;i>=1;--i) {
  66.             if(e[i].u>=u&&e[i].v>=u) {
  67.                 // if() {
  68.                     g[e[i].u].push_back(e[i].v);
  69.                     rg[e[i].v].push_back(e[i].u);
  70.                 // }
  71.                 if(vis[e[i].u] && !vis[e[i].v]) bfs(e[i].v);
  72.                 if(rvis[e[i].v] && !rvis[e[i].u]) rbfs(e[i].u);
  74.             }
  75.             ans[i]+=cnt;           
  76.         }
  77.     }
  78.     for(int i=1;i<=m+1;++i) {
  79.         printf("%d ",ans[i]);
  80.     }
  81.     puts("");
  82.     return 0;
  83. }

D2T1 gem

  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. template<typename _Tp>
  5. inline void read(_Tp &x) {
  6.     x=0;bool fg=0;char ch=getchar();
  7.     while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
  8.     while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(_Tp)(ch^48),ch=getchar();
  9.     if(fg) x=-x;
  10. }
  11. using namespace std;
  12. typedef long long ll;
  13. typedef vector<int> vt;
  14. const int N = 200010;
  16. int head[N],pnt[N<<1],nxt[N<<1],E;
  17. int n,m,q,c,P[N],op[N],w[N];
  19. void adde(int u,int v) {
  20.     E++;pnt[E]=v;nxt[E]=head[u];head[u]=E;
  21. }
  23. namespace seg {
  24.     #define ls(p) t[p].l
  25.     #define rs(p) t[p].r
  26.     #define mid ((l+r)>>1)
  27.     struct node{
  28.         int l,r,x;
  29.     }t[N*23*2];
  30.     int root[2][N],tot;
  31.     int newnode() {
  32.         ++tot;t[tot].l=t[tot].r=t[tot].x=0;return tot;
  33.     }
  34.     void modify(int p,int q,int ps,int vl,int l=1,int r=c) {
  35.         if(l==r) {
  36.             t[q].x=vl;
  37.             return;
  38.         }
  39.         if(ps<=mid) {
  40.             modify(ls(p),ls(q)=newnode(),ps,vl,l,mid);
  41.             rs(q)=rs(p);
  42.         }else {
  43.             modify(rs(p),rs(q)=newnode(),ps,vl,mid+1,r);
  44.             ls(q)=ls(p);
  45.         }
  46.     }
  47.     int ask(int p,int ps,int l=1,int r=c) {
  48.         if(ps<1||ps>c) return 0;
  49.         if(!p) return 0;
  50.         if(l==r) return t[p].x;
  51.         if(ps<=mid) return ask(ls(p),ps,l,mid);
  52.         return ask(rs(p),ps,mid+1,r);
  53.     }
  54.     #undef ls
  55.     #undef rs
  56.     #undef mid
  57. }using seg::root;
  59. namespace STD {
  60.     const int M = 21;
  61.     int fa[N],siz[N],son[N],dep[N],top[N];
  62.     int dnxtp[M][N],unxtp[M][N];
  63.     vt bots;
  64.     void dfs1(int u,int f,int d) {
  65.         siz[u]=1;fa[u]=f;dep[u]=d;
  66.         for(int i=head[u];i;i=nxt[i]) {
  67.             int v=pnt[i];
  68.             if(v==f) continue;
  69.             dfs1(v,u,d+1);
  70.             siz[u]+=siz[v];
  71.             if(siz[v]>siz[son[u]]) son[u]=v;
  72.         }
  73.     }
  74.     void dfs2(int u,int topf) {
  75.         top[u]=topf;
  76.         if(son[u]) {
  77.             dfs2(son[u],topf);
  78.         }else bots.push_back(u);
  79.         for(int i=head[u];i;i=nxt[i]) {
  80.             int v=pnt[i];
  81.             if(v==fa[u]||v==son[u]) continue;
  82.             dfs2(v,v);
  83.         }
  84.     }
  86.     void init() {
  87.         dfs1(1,0,0);dfs2(1,1);    
  88.         for(int i=1;i<=n;++i) w[i]=op[w[i]];
  89.         root[0][0]=seg::newnode();
  90.         root[1][0]=seg::newnode();
  91.         static int t[N];
  92.         for(int _i=0;_i<(int)bots.size();++_i) {
  93.             int cnt=0,u=bots[_i];
  94.             while(true) {
  95.                 t[++cnt]=u;
  96.                 if(u==top[u]) break;
  97.                 u=fa[u];
  98.             }
  99.             t[0]=t[cnt+1]=0;
  100.             map<int,int> ext;
  101.             for(int i=1;i<=cnt;++i) {
  102.                 u=t[i];
  103.                 if(ext.find(w[u]+1)!=ext.end()) {
  104.                     dnxtp[0][u]=ext[w[u]+1];
  105.                 }
  106.                 seg::modify(root[0][t[i-1]],root[0][u]=seg::newnode(),w[u],u);
  107.                 ext[w[u]]=u;
  108.             }
  109.             for(int i=1;i<M;++i) {
  110.                 for(int j=1,u;j<=cnt;++j) {
  111.                     u=t[j];
  112.                     dnxtp[i][u]=dnxtp[i-1][dnxtp[i-1][u]];
  113.                 }
  114.             }
  115.             ext.clear();
  116.             for(int i=cnt;i>=1;--i) {
  117.                 u=t[i];
  118.                 if(ext.find(w[u]+1)!=ext.end()) {
  119.                     unxtp[0][u]=ext[w[u]+1];
  120.                 }
  121.                 seg::modify(root[1][t[i+1]],root[1][u]=seg::newnode(),w[u],u);
  122.                 ext[w[u]]=u;
  123.             }
  124.             for(int i=1;i<M;++i) {
  125.                 for(int j=1,u;j<=cnt;++j) {
  126.                     u=t[j];
  127.                     unxtp[i][u]=unxtp[i-1][unxtp[i-1][u]];
  128.                 }
  129.             }
  130.         }
  131.     }
  132.     vector<pair<int,int> > up,dn;
  133.     void LCA(int s,int t) {
  134.         up.clear();dn.clear();
  135.         int fs=top[s],ft=top[t];
  136.         while(fs!=ft) {
  137.             if(dep[fs]>dep[ft]) {
  138.                 up.push_back(make_pair(s,fs));
  139.                 s=fa[fs];fs=top[s];
  140.             }else {
  141.                 dn.push_back(make_pair(t,ft));
  142.                 t=fa[ft];ft=top[t];
  143.             }
  144.         }
  145.         if(dep[s]>dep[t]) {
  146.             up.push_back(make_pair(s,t));
  147.         }else {
  148.             dn.push_back(make_pair(t,s));
  149.         }
  150.     }
  151.     void query(int s,int t) {
  152.         LCA(s,t);
  153.         int x=0;
  154.         for(int _i=0;_i<(int)up.size();++_i) {
  155.             pair<int,int> cha=up[_i];
  156.             int u=seg::ask(root[1][cha.fi],w[x]+1);
  157.             if(u==0||dep[u]<dep[cha.se]) continue;
  158.             x=u;
  159.             for(int i=M-1;i>=0;--i) if(unxtp[i][x]&&dep[unxtp[i][x]]>=dep[cha.se]) {
  160.                 x=unxtp[i][x];
  161.             }
  162.         }
  164.         for(int _i=dn.size()-1;_i>=0;--_i) {
  165.             pair<int,int> cha=dn[_i];
  166.             int u=seg::ask(root[0][cha.se],w[x]+1);
  167.             if(u==0||dep[u]>dep[cha.fi]) continue;
  168.             x=u;
  169.             for(int i=M-1;i>=0;--i) if(dnxtp[i][x]&&dep[dnxtp[i][x]]<=dep[cha.fi]) {
  170.                 x=dnxtp[i][x];
  171.             }
  172.         }
  173.         printf("%d\n",w[x]);
  174.     }
  175.     void solve() {
  176.         init();
  177.         for(int ts=1;ts<=q;++ts) {
  178.             int s,t;read(s);read(t);
  179.             query(s,t);
  180.         }
  181.     }
  182. }
  183. int main() {
  184.     read(n);read(m);read(c);
  185.     for(int i=1;i<=c;++i) read(P[i]),op[P[i]]=i;
  186.     for(int i=1;i<=n;++i) read(w[i]);
  187.     for(int i=1;i<n;++i) {
  188.         int u,v;read(u);read(v);
  189.         adde(u,v);adde(v,u);
  190.     }
  191.     read(q);
  192.     STD::solve();
  193.     return 0;
  194. }

D2T2 ranklist

  1. #include <bits/stdc++.h>
  2. template<typename _Tp>
  3. inline void read(_Tp &x) {
  4.     x=0;bool fg=0;char ch=getchar();
  5.     while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
  6.     while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(_Tp)(ch^48),ch=getchar();
  7.     if(fg) x=-x;
  8. }
  9. template<typename _Tp,typename... Args>void read(_Tp &t,Args &... args){read(t);read(args...);}
  10. using namespace std;
  11. typedef long long ll;
  12. const int N = 13;
  13. const int M = 505;
  14. const int K = 1<<13;
  15. int a[N],n,m,ful;
  16. int ct[K];
  17. ll dp[K][N][M];
  18. int main() {
  19.     read(n);read(m);
  20.     int bst=0;
  21.     for(int i=0;i<n;++i) {
  22.         read(a[i]);
  23.         if(a[i]>a[bst]) bst=i;
  24.     }
  25.     ful=(1<<n)-1;
  26.     for(int mask=1;mask<=ful;++mask) ct[mask]=ct[mask-(mask&-mask)]+1;
  27.     for(int i=0;i<n;++i) {
  28.         int b=a[bst]-a[i];
  29.         if(i>bst) b++;
  30.         if(n*b<=m) dp[1<<i][i][n*b]=1;
  31.     }
  32.     for(int S=1;S<ful;++S) {
  33.         for(int _c=S;_c;_c-=_c&-_c) {
  34.             int c=log2(_c&-_c);
  35.             for(int r=0;r<=m;++r) if(dp[S][c][r]) {
  36.                 for(int _x=(S^ful);_x;_x-=_x&-_x) {
  37.                     int x=log2(_x&-_x);
  38.                     int dif=max(0,a[c]-a[x]);
  39.                     if(a[x]+dif==a[c]&&x>c) ++dif;
  40.                     if(r+dif*(n-ct[S])<=m) 
  41.                         dp[S|(1<<x)][x][r+dif*(n-ct[S])]+=dp[S][c][r];
  42.                 }
  43.             }
  44.         }
  45.     }
  46.     ll ans=0;
  47.     for(int c=0;c<n;++c) {
  48.         for(int r=0;r<=m;++r) {
  49.             ans+=dp[ful][c][r];
  50.         }
  51.     }
  52.     printf("%lld\n",ans);
  53.     return 0;
  54. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注