[关闭]
@shixinyi 2018-01-04T12:46:34.000000Z 字数 30368 阅读 637

每日bug

OI

2017.12

03 test 1203 T1 数字

相当于%9，但是余0的是9。

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. #define ll long long
  10. ll T,l,r;
  12. ll aa;char cc;
  13. ll read() {
  14.     aa=0;cc=getchar();
  15.     while(cc<'0'||cc>'9') cc=getchar();
  16.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  17.     return aa;
  18. }
  20. ll cnt[20];
  21. ll get_ans(ll x) {
  22.     if(x<=0) return x+1;
  23.     ll rs=1;//0
  24.     for(ll i=1;i<=9;++i) rs+=(cnt[i]=(x-i*i+i*9)/(i*9));//用循环简单一些
  25.     rs-=cnt[1]/8;
  26.     rs-=cnt[2]/7;
  27.     rs-=cnt[3]/2;
  28.     rs-=cnt[4]/5;
  29.     return rs;
  30. }
  32. int main() {
  33.     T=read();
  34.     while(T--) {
  35.         l=read();r=read();
  36.         printf("%lld\n",get_ans(r)-get_ans(l-1));
  37.     }
  38.     return 0;
  39. }

03 test 1203 T2 探险

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. const int maxn=1e4+10,maxm=4e5+10,INF=0x3f3f3f3f;//maxm开小了
  10. int n,m,ans=INF;
  12. int aa;char cc;
  13. int read() {
  14.     aa=0;cc=getchar();
  15.     while(cc<'0'||cc>'9') cc=getchar();
  16.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  17.     return aa;
  18. }
  20. int fir[maxn],nxt[maxm],to[maxm],v[maxm],e=0;
  21. void add(int x,int y,int z) {
  22.     to[++e]=y;nxt[e]=fir[x];fir[x]=e;v[e]=z;
  23. }
  25. int dis[maxn],zz[maxn];
  26. bool vis[maxn];
  27. int spfa(int st) {
  28.     int s=1,t=0,x,y,z,tot=1;
  29.     memset(dis,0x3f3f3f3f,sizeof(dis));
  30.     dis[st]=0;vis[st]=1;zz[++t]=st;
  31.     while(tot--) {
  32.         x=zz[s];s=(s+1)%maxn;vis[x]=0;
  33.         for(y=fir[x];y;y=nxt[y]) {
  34.             if(dis[z=to[y]]<=dis[x]+v[y]||(x==st&&z==1)) continue;
  35.             dis[z]=dis[x]+v[y];
  36.             if(!vis[z]) {
  37.                 vis[z]=1;tot++;
  38.                 if(dis[z]<=dis[zz[s]]) {
  39.                     s=(s-1+maxn)%maxn;
  40.                     zz[s]=z;
  41.                 }
  42.                 else {
  43.                     t=(t+1)%maxn;
  44.                     zz[t]=z;
  45.                 }
  46.             }
  47.         }
  48.     }
  49.     return dis[1];
  50. }
  52. int main() {
  53.     n=read(); m=read();
  54.     int x,y,z1,z2;
  55.     for(int i=1;i<=m;++i) {
  56.         x=read();y=read();
  57.         z1=read();z2=read();
  58.         if(x>y) swap(x,y),swap(z1,z2);
  59.         add(x,y,z1); add(y,x,z2);
  60.     }
  61.     for(y=fir[1];y;y=nxt[y]) ans=min(ans,spfa(to[y])+v[y]);
  62.     printf("%d",ans);
  63.     return 0;
  64. }

05 test 1205 T1 safe

正向跑一次，反向跑一次，求交点。

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. #include<set>
  9. using namespace std;
  10. #define ll long long
  11. const int maxn=8e5+10,INF=1e7;
  12. int n,m,cse,tot1,tot2,p[maxn],tt,S,T,ok;
  13. bool vis[2*maxn];
  15. int aa;char cc;
  16. int read() {
  17.     aa=0;cc=getchar();
  18.     while(cc<'0'||cc>'9') cc=getchar();
  19.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  20.     return aa;
  21. }
  23. struct Node{
  24.     int x,y,p;
  25. }node[2*maxn];
  27. bool cmp1(int a,int b) {
  28.     return node[a].x==node[b].x? node[a].y<node[b].y : node[a].x<node[b].x;
  29. }
  30. bool cmp2(int a,int b) {
  31.     return node[a].y==node[b].y? node[a].x<node[b].x : node[a].y<node[b].y;
  32. }
  34. int fir[4*maxn],nxt[4*maxn],to[4*maxn],e;
  35. void add(int x,int y) {
  36. //  printf("add: %d %d\n",x,y);
  37.     to[++e]=y;nxt[e]=fir[x];fir[x]=e;
  38.     to[++e]=x;nxt[e]=fir[y];fir[y]=e;
  39. }
  41. void init() {
  42.     tot1=read();tot2=read();tt=tot1+tot2;
  43.     S=tt*2+1;T=S+1;
  44.     for(int i=1;i<=tot1;++i) {
  45.         node[i].x=read();
  46.         node[i].y=read();
  47.         node[i].p=0;
  48.     } 
  49.     for(int i=1;i<=tot2;++i) {
  50.         node[i+tot1].x=read();
  51.         node[i+tot1].y=read();
  52.         node[i+tot1].p=1;
  53.     }
  54.     node[S].x=1;node[S].y=0;
  55.     node[T].x=n;node[T].y=m+1;
  56. }
  58. void get_edge() {
  59.     for(int i=1;i<=tt;++i) p[i]=i;
  60.     sort(p+1,p+tt+1,cmp1);
  61.     for(int i=2;i<=tt;++i) if(node[p[i-1]].x==node[p[i]].x) add(p[i-1]+tt,p[i]);
  62.     if(node[p[1]].x==1) add(S,p[1]);
  63.     if(node[p[tt]].x==n) add(p[tt]+tt,T);
  64.     for(int i=1;i<=tt;++i) p[i]=i;
  65.     sort(p+1,p+tt+1,cmp2);
  66.     for(int i=2;i<=tt;++i) if(node[p[i-1]].y==node[p[i]].y) 
  67.         add(p[i-1]+tt*(int)(node[p[i-1]].p==0),p[i]+tt*(int)(node[p[i]].p==1));
  68. }
  70. int get_d(int tox,int x) {
  71.     if(!x) return (tox+1)%4+1;
  72.     return 5-tox;
  73. }
  75. struct Line{
  76.     int x,y,z;
  77. }li[5][2*maxn];
  78. int tot[5];
  79. //0~3
  80. bool cmp3(const Line& a,const Line& b) {
  81.     return a.z==b.z? a.x<b.x:a.z<b.z;//写反了
  82. }
  84. void bld1(int x,int y,int p) {
  85.     p=(p-1)<<1;
  86.     if(x<S&&x>tt) x-=tt;
  87.     int ff=(node[x].y==node[y].y);
  88.     int s=(++tot[p+=ff]);
  89.     if(!ff) li[p][s].x=node[x].y,li[p][s].y=node[y].y,li[p][s].z=node[x].x;
  90.     else li[p][s].x=node[x].x,li[p][s].y=node[y].x,li[p][s].z=node[x].y;
  91. }
  92. void bld2(int x,int tox,int p) {
  93.     p=(p-1)<<1;
  94.     if(x<S&&x>tt) x-=tt;
  95.     int ff=tox/3;
  96.     int s=(++tot[p+=ff]);
  97.     if(!ff) li[p][s].z=node[x].x;
  98.     else li[p][s].z=node[x].y;
  99.     if(tox==1) li[p][s].x=node[x].y,li[p][s].y=m+1;
  100.     else if(tox==2) li[p][s].y=node[x].y,li[p][s].x=0;
  101.     else if(tox==3) li[p][s].y=node[x].x,li[p][s].x=0;
  102.     else li[p][s].x=node[x].x,li[p][s].y=n+1;
  103. }
  105. bool dfs(int pos,int tox,int p) {
  106.     vis[pos]=1;
  107.     int y,z,g,d,ok=0;
  108.     for(y=fir[pos];y;y=nxt[y]) {
  109.         if(vis[z=to[y]]) continue;
  110.         if((z==T&&p==1)||(z==S&&p==2)) return 1;
  111.         else if(z==T||z==S) {
  112.             ok=0; break;
  113.         } 
  114.         ok=1; g=(z-1)%tt+1;d=get_d(tox,node[g].p);
  115.         bld1(pos,g,p);
  116.         if(dfs(z,d,p)) return 1;
  117.     }
  118.     vis[pos]=0;
  119.     if(!ok) bld2(pos,tox,p);
  120.     return 0;
  121. }
  123. set<ll> Gpl[2],Gmi[2];
  124. set<ll>::iterator it1,it2;
  126. int sz[3*maxn];
  127. int q(int pos) {
  128.     int rs=0;
  129.     while(pos) {
  130.         rs+=sz[pos];
  131.         pos-=(pos&-pos);
  132.     }
  133.     return rs;
  134. }
  135. void chge(int pos,int x) {
  136.     while(pos<=m) {
  137.         sz[pos]+=x;
  138.         pos+=(pos&-pos);
  139.     }
  140. }
  142. int ans,ansx,ansy;
  143. void rn(int x,int l,int r) {
  144.     int lx=l-1,rx=r,t=q(l-1),mid;
  145.     while(lx<rx-1) {
  146.         mid=(lx+rx)>>1;
  147.         if(q(mid)>t) rx=mid;
  148.         else lx=mid;
  149.     }
  150.     if(x<ansx||(x==ansx&&rx<ansy)) {
  151.         ansx=x;ansy=rx;
  152.     }
  153.     ok=1;
  154. }
  156. void get_ans() {
  157.     for(int i=0;i<4;++i) {
  158.         for(int j=1;j<=tot[i];++j) {
  159.             if(li[i][j].x>li[i][j].y) swap(li[i][j].x,li[i][j].y);
  160.             ++li[i][j].x;--li[i][j].y;
  161.             if(li[i][j].x>li[i][j].y) li[i][j].z=INF;//z写的x
  162.         }
  163.     }
  164.     ans=0;
  165.     sort(li[0]+1,li[0]+tot[0]+1,cmp3);
  166.     sort(li[2]+1,li[2]+tot[2]+1,cmp3);
  167.     while(tot[0]&&li[0][tot[0]].z==INF) tot[0]--;
  168.     while(tot[2]&&li[2][tot[2]].z==INF) tot[2]--;
  169.     Gpl[0].clear();Gmi[0].clear();
  170.     Gpl[1].clear();Gmi[1].clear();//忘记clear
  171.     for(int i=1;i<4;i+=2) {
  172.         for(int j=1;j<=tot[i];++j) {
  173.             if(li[i][j].z==INF) continue;
  174.             Gpl[i>2].insert((ll)li[i][j].z+(ll)li[i][j].x*INF);
  175.             Gmi[i>2].insert((ll)li[i][j].z+(ll)(li[i][j].y+1)*INF);//应该以x或y为第一关键字
  176.         }
  177.     }
  178.     memset(sz,0,sizeof(sz));
  179.     int pos=1;it1=Gpl[1].begin();it2=Gmi[1].begin();
  180.     int l,r,now;ok=0;
  181.     for(int i=1;i<=n&&pos<=tot[0];++i) {
  182.         while(it1!=Gpl[1].end()&&(*it1)/(ll)INF==i) chge((*it1)%(ll)INF,1),it1++;
  183.         while(it2!=Gmi[1].end()&&(*it2)/(ll)INF==i) chge((*it2)%(ll)INF,-1),it2++;//ll
  184.         l=0;r=0;
  185.         while(pos<=tot[0]&&li[0][pos].z==i) {
  186.             l=max(l,li[0][pos].x);r=max(l-1,li[0][pos].y);
  187.             if(l<=r) {
  188.                 ans+=(now=q(r)-q(l-1));
  189.                 if(!ok&&now) rn(i,l,r);
  190.             }
  191.             l=r+1; pos++;
  192.         } 
  193.     }
  194.     memset(sz,0,sizeof(sz));
  195.     pos=1;it1=Gpl[0].begin();it2=Gmi[0].begin(); ok=0;
  196.     for(int i=1;i<=n&&pos<=tot[2];++i) {
  197.         while(it1!=Gpl[0].end()&&(*it1)/(ll)INF==i) chge((*it1)%(ll)INF,1),it1++;
  198.         while(it2!=Gmi[0].end()&&(*it2)/(ll)INF==i) chge((*it2)%(ll)INF,-1),it2++;
  199.         l=0;r=0;
  200.         while(pos<=tot[2]&&li[2][pos].z==i) {
  201.             l=max(l,li[2][pos].x);r=max(l-1,li[2][pos].y);
  202.             if(l<=r) {
  203.                 ans+=(now=q(r)-q(l-1));
  204.                 if(!ok&&now) rn(i,l,r);
  205.             }
  206.             l=r+1; pos++;
  207.         } 
  208.     }
  209. }
  212. void clear() {
  213.     memset(fir,0,sizeof(fir));
  214.     memset(nxt,0,sizeof(nxt));
  215.     memset(vis,0,sizeof(vis));
  216.     e=0;ansx=n+1;ansy=m+1;
  217.     tot[0]=tot[1]=tot[2]=tot[3]=0;
  218. }
  220. int main() {
  221.     while(scanf("%d%d",&n,&m)==2) {
  222.         printf("Case %d: ",++cse);
  223.         clear(); init();
  224.         get_edge();
  225.         if(dfs(S,1,1)||dfs(T,2,2)||(n==1&&!tot1&&!tot2)) printf("0");//n==1的情况直接射出去
  226.         else if(n==1) printf("impossible");
  227.         else {
  228.             get_ans();
  229.             if(ans) printf("%d %d %d",ans,ansx,ansy);
  230.             else printf("impossible");
  231.         }
  232.         printf("\n");
  233.     }
  234.     return 0;
  235. }

06 test 1206 T2 minflow

直接枚举z，然后用并查集维护联通快，跑最短路。
因为中间有一些已经连好的边，所以不能直接只判断从S所在联通块直接到T所在联通块的最短距离

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. #include<queue>
  9. using namespace std;
  10. #define ll long long
  11. #define db double
  12. const int maxn=400+10,maxm=5e4+10;
  13. const db INF=1e17;
  14. ll n,m,S,T,p[maxn],fa[maxn],h,now;
  15. db d[maxn][maxn],ans=INF;
  16. bool vis[maxn];
  18. ll aa,ff;char cc;
  19. ll read() {
  20.     aa=0;cc=getchar();ff=1;
  21.     while(cc<'0'||cc>'9') {
  22.         if(cc=='-') ff=-1;
  23.         cc=getchar();
  24.     }
  25.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  26.     return aa*ff;
  27. }
  29. struct Node{
  30.     ll x,y,z,k;int id;
  31. }node[maxn];
  32. bool cmp(const Node& a,const Node& b) {
  33.     return a.z < b.z;
  34. }
  36. db pf(db x) {return x*x;}
  37. db get_dis(int a,int b) {
  38.     return sqrt(pf(node[a].x-node[b].x)+pf(node[a].y-node[b].y)+pf(node[a].z-node[b].z));
  39. }
  41. int fir[maxn],nxt[2*maxm],to[2*maxm],e=0;
  42. void add(int x,int y) {
  43.     to[++e]=y;nxt[e]=fir[x];fir[x]=e;
  44.     to[++e]=x;nxt[e]=fir[y];fir[y]=e;
  45. }
  47. int find(int x) {
  48.     return fa[x]==x? x:fa[x]=find(fa[x]);
  49. }
  51. struct Di{
  52.     int x,p;db d;
  53.     Di(){}
  54.     Di(int x,int p,db d):x(x),p(p),d(d){}
  55.     bool operator <(const Di& b) const{
  56.         return d > b.d;
  57.     }
  58. };
  59. priority_queue<Di> G;
  61. db dis[maxn][2];
  62. void get_ans(int pos) {
  63.     for(int i=1;i<=n;++i) dis[i][0]=dis[i][1]=INF;
  64.     dis[S][0]=0; G.push(Di(S,0,0));
  65.     int x,y,t; db rs=(db)now*0.5,ad,dx;//dx开成int
  66.     while(!G.empty()) {
  67.         x=G.top().x; t=G.top().p; dx=G.top().d; G.pop();//忘记pop
  68.         if(dx!=dis[x][t]) continue;
  69.         for(y=1;y<=pos;++y) {
  70.             if(find(y)!=find(S)&&find(y)!=find(T)) ad=(db)node[y].k*0.5;//忘记(db)
  71.             else ad=0;
  72.             if(d[x][y]==0) {
  73.                 if(dis[y][0]<=dx+ad) continue;
  74.                 dis[y][0]=dx+ad;
  75.                 G.push(Di(y,0,dis[y][0]));
  76.             } 
  77.             else if(node[y].k&&node[x].k>t&&dis[y][1]>dx+d[x][y]+ad-1) {//t与dx搞混
  78.                 dis[y][1]=dx+d[x][y]+ad-1;
  79.                 G.push(Di(y,1,dis[y][1]));
  80.             } 
  81.         }
  82.     }
  83.     ans=min(ans,min(dis[T][0],dis[T][1])+rs);
  84. }
  86. int main() {
  87.     n=read();m=read();
  88.     for(int i=1;i<=n;++i) {
  89.         node[i].x=read();
  90.         node[i].y=read();
  91.         node[i].z=read();
  92.         node[i].k=read();
  93.         node[i].id=i;
  94.     }
  95.     sort(node+1,node+n+1,cmp);
  96.     for(int i=1;i<=n;++i) p[node[i].id]=i;
  97.     S=p[1];T=p[n];
  98.     h=max(node[S].z,node[T].z);
  99.     for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) 
  100.         d[i][j]=d[j][i]=get_dis(i,j);
  101.     for(int i=1;i<=n;++i) fa[i]=i;
  102.     int x,y;
  103.     for(int i=1;i<=m;++i) {
  104.         x=p[read()]; y=p[read()];
  105.         d[x][y]=d[y][x]=0;
  106.         add(x,y);
  107.     }
  108.     for(int i=1;i<=n;++i) {
  109.         for(int j=fir[i];j;j=nxt[j]) 
  110.             if(to[j]<i) fa[find(to[j])]=find(i);
  111.         for(int j=1;j<=i;++j) if(!vis[j]) {//上面的联通可能会导致下面的有些点与S、T联通
  112.             x=find(j);  
  113.             if(x==find(S)||x==find(T)) {
  114.                 now+=node[j].k; vis[j]=1;//j打成i
  115.             }
  116.         }
  117.         if(node[i].z<h||(i!=n&&node[i].z==node[i+1].z)) continue;
  118.         get_ans(i);
  119.     }
  120.     if(ans!=INF) printf("Case 1: %.4f",ans);
  121.     else printf("Case 1: impossible");
  122.     return 0;
  123. }

08 test 1208 T1 A

计算几何题
求能够构成的的个数，暴力代码：

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. #define db double
  10. #define ll long long
  11. const int maxn=2333+10;
  12. const db eps=1e-11;
  13. int n;
  14. ll tot[3],ans;
  16. int aa,ff;char cc;
  17. int read() {
  18.     aa=0;ff=1;cc=getchar();
  19.     while(cc<'0'||cc>'9') {
  20.         if(cc=='-') ff=-1;//忘记判断负数情况
  21.         cc=getchar();
  22.     }
  23.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  24.     return aa*ff;
  25. }
  27. struct Node {
  28.     db x,y;
  29. }node[maxn];
  31. db xx,yy,x2,y2;
  32. db X_(int i,int j,int k) {
  33.     xx=node[j].x-node[i].x;x2=node[k].x-node[i].x;
  34.     yy=node[j].y-node[i].y;y2=node[k].y-node[i].y;
  35.     return xx*y2-yy*x2;
  36. }
  37. db D_(int i,int j,int k) {
  38.     xx=node[j].x-node[i].x;x2=node[k].x-node[i].x;
  39.     yy=node[j].y-node[i].y;y2=node[k].y-node[i].y;
  40.     return xx*x2+yy*y2;
  41. }
  43. int main() {
  44.     n=read();
  45.     for(int i=1;i<=n;++i) node[i].x=read(),node[i].y=read();
  46.     for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) {
  47.         tot[1]=tot[2]=0;
  48.         for(int k=1;k<=n;++k) if(k!=i&&k!=j) {
  49.             if(X_(i,j,k)+eps<0&&D_(i,j,k)+eps>=0) ++tot[1];
  50.             else if(X_(i,j,k)-eps>0&&D_(j,i,k)+eps>=0) ++tot[2];
  51.         }
  52.         ans+=tot[1]*tot[2];
  53.     }
  54.     printf("%lld",ans);
  55.     return 0;
  56. }

09 hdu 5126 star

cdq套cdq裸题

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. const int maxn=4e5+10;
  10. int T,n,tot,qtot,ans[maxn/6];
  11. int pz[maxn/4],tz;
  13. int aa;char cc;
  14. int read() {
  15.     aa=0;cc=getchar();
  16.     while(cc<'0'||cc>'9') cc=getchar();
  17.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  18.     return aa;
  19. }
  21. int ef(int x) {
  22.     int l=1,r=tz,mid;
  23.     while(l<=r) {
  24.         mid=(l+r)>>1;
  25.         if(pz[mid]==x) return mid;
  26.         if(pz[mid]<x) l=mid+1;
  27.         else r=mid-1;
  28.     }
  29. }
  30. int xx[maxn],yy[maxn],zz[maxn],fnum[maxn];
  31. struct Ask{
  32.     int qid,id;
  33. }ask[maxn],ask1[maxn],ask2[maxn];
  34. bool cmp(const Ask& a,const Ask& b) {
  35.     return xx[a.id]==xx[b.id]? a.id < b.id : xx[a.id] < xx[b.id];//相同时必须比较id否则会挂
  36. }
  37. bool cmp2(const Ask& a,const Ask& b) {
  38.     return yy[a.id]==yy[b.id]? a.id < b.id : yy[a.id] < yy[b.id];
  39. }
  41. void add(int x,int y,int z,int num) {
  42.     fnum[++tot]=num;ask[tot].id=tot;
  43.     xx[tot]=x;yy[tot]=y;zz[tot]=z;
  44.     if(num) ask[tot].qid=qtot;
  45. }
  47. int sz[maxn];
  48. int q(int pos) {
  49.     int rs=0;
  50.     while(pos) {
  51.         rs+=sz[pos];
  52.         pos-=pos&-pos;
  53.     }
  54.     return rs;
  55. }
  57. void chge(int pos,int x) {
  58.     while(pos<=tz) {
  59.         sz[pos]+=x;
  60.         pos+=pos&-pos;
  61.     }
  62. }
  64. void cdq2(int l,int r) {
  65.     if(l>=r) return;
  66.     int mid=(l+r)>>1,now=0;
  67.     cdq2(l,mid); cdq2(mid+1,r);
  68.     for(int i=l;i<=mid;++i) if(!fnum[ask1[i].id]) ask2[++now]=ask1[i];
  69.     for(int i=mid+1;i<=r;++i) if(fnum[ask1[i].id]) ask2[++now]=ask1[i];
  70.     sort(ask2+1,ask2+now+1,cmp2);
  71.     for(int i=1;i<=now;++i) {
  72.         if(!fnum[ask2[i].id]) chge(zz[ask2[i].id],1);
  73.         else ans[ask2[i].qid]+=fnum[ask2[i].id]*q(zz[ask2[i].id]);
  74.     }
  75.     for(int i=1;i<=now;++i) if(!fnum[ask2[i].id]) chge(zz[ask2[i].id],-1);
  76. }
  78. void cdq(int l,int r) {
  79.     if(l>=r) return;
  80.     int mid=(l+r)>>1,now=0;
  81.     cdq(l,mid); cdq(mid+1,r);
  82.     for(register int i=l;i<=mid;++i) if(!fnum[ask[i].id]) ask1[++now]=ask[i];
  83.     for(register int i=mid+1;i<=r;++i) if(fnum[ask[i].id]) ask1[++now]=ask[i];
  84.     sort(ask1+1,ask1+now+1,cmp);
  85.     cdq2(1,now);
  86. }
  88. void clear() {
  89.     memset(ans,0,sizeof(ans));
  90.     tz=tot=qtot=0;
  91. }
  93. int main() {//提交的时候忘记关freopen
  94.     T=read();
  95.     int op,x,y,z,x1,y1,z1;
  96.     while(T--) {
  97.         n=read(); clear();
  98.         for(int i=1;i<=n;++i) {
  99.             op=read(); x=read(); y=read(); z=read(); 
  100.             if(op==1) add(x,y,z,0),pz[++tz]=z;
  101.             else {
  102.                 x1=read();y1=read();z1=read();++qtot; pz[++tz]=z1; pz[++tz]=z-1;
  103.                 add(x-1,y-1,z-1,-1);  add(x1,y1,z1,1);
  104.                 add(x1,y-1,z-1,1);  add(x-1,y1,z-1,1);  add(x-1,y-1,z1,1);
  105.                 add(x-1,y1,z1,-1);  add(x1,y-1,z1,-1);  add(x1,y1,z-1,-1);//x、y、z需要-1
  106.             }
  107.         }
  108.         sort(pz+1,pz+tz+1);//忘记sort了
  109.         tz=unique(pz+1,pz+tz+1)-(pz+1);
  110.         for(int i=1;i<=tot;++i) zz[i]=ef(zz[i]);//提前离散化跑得更快
  111.         cdq(1,tot);
  112.         for(int i=1;i<=qtot;++i) printf("%d\n",ans[i]);
  113.     }
  114.     return 0;
  115. }

11 test 1211 T3 C

一个裸的基环树+gcd
需要注意一些细节问题.

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. #define ll long long
  10. const int maxn=1e5+10;
  11. int n,m,hst;ll d;
  13. ll aa;char cc;
  14. ll read() {
  15.     aa=0;cc=getchar();
  16.     while(cc<'0'||cc>'9') cc=getchar();
  17.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  18.     return aa;
  19. }
  21. int fir[maxn],nxt[2*maxn],to[2*maxn],e=1;ll v[2*maxn];
  22. void add(int x,int y,ll z) {
  23.     to[++e]=y;nxt[e]=fir[x];fir[x]=e;v[e]=z;
  24.     to[++e]=x;nxt[e]=fir[y];fir[y]=e;v[e]=-z;
  25. }
  27. int zz[maxn],t,inh[maxn],vis[maxn];
  28. void dfs1(int pos,int p) {
  29.     if(vis[pos]) {
  30.         while(t&&zz[t]!=pos) inh[zz[t--]]=1;
  31.         hst=pos; inh[pos]=1;
  32.         return ;//忘了return直接段错误
  33.     }
  34.     vis[pos]=1; zz[++t]=pos;
  35.     for(int y=fir[pos];y;y=nxt[y]) {
  36.         if(y==p) continue;
  37.         dfs1(to[y],y^1);
  38.     }
  39. }
  41. ll dis[maxn],toth,fa[maxn];
  42. void dfs3(int pos,ll d,ll bel) {
  43.     dis[pos]=d;fa[pos]=bel;vis[pos]=1;
  44.     for(int y=fir[pos];y;y=nxt[y]) {
  45.         if(vis[to[y]]) continue;
  46.         dfs3(to[y],d+v[y],bel);
  47.     }
  48. }
  50. void dfs2(int pos,ll d,int p) {
  51.     dis[pos]=d;fa[pos]=pos;vis[pos]=1;
  52.     for(int y=fir[pos];y;y=nxt[y]) {
  53.         if(y==p) continue;
  54.         if(!inh[to[y]]) dfs3(to[y],v[y],pos);
  55.         else {
  56.             if(vis[to[y]]) {
  57.                 if(to[y]==hst) toth=d+v[y];
  58.                 continue;
  59.             }
  60.             inh[to[y]]=inh[pos]+1;
  61.             dfs2(to[y],d+v[y],y^1);
  62.         }
  63.     }
  64. }
  66. ll get_d(int x,int y) {
  67.     if(x==y) return 0;
  68.     if(inh[y]>inh[x]) return dis[y]-dis[x];
  69.     return -toth+(dis[y]-dis[x]);//正负号弄反
  70. }
  72. ll gcd(ll x,ll y) {
  73.     return y==0? x:gcd(y,x%y);
  74. }
  76. int main() {
  77.     n=read(); ll x,y,z,now;
  78.     for(int i=1;i<=n;++i) {
  79.         x=read(); y=read(); z=read();
  80.         add(x,y,z);
  81.     }
  82.     dfs1(1,0);
  83.     memset(vis,0,sizeof(vis));
  84.     dfs2(hst,0,0);
  85.     m=read();
  86.     for(int i=1;i<=m;++i) {
  87.         x=read();y=read();z=read();d=0;
  88.         if(fa[x]!=x) d-=dis[x];
  89.         if(fa[y]!=y) d+=dis[y];
  90.         d+=get_d(fa[x],fa[y]);
  91.         d%=z; now=toth%z;
  92.         if(d<=0) d+=z;
  93.         if(now<=0) now+=z;
  94.         now=gcd(now,z);
  95.         d%=now;if(!d) d+=now;
  96.         if((z-d)%now==0) printf("%lld\n",z-now);//必须特判否则挂
  97.         else printf("%lld\n",((z-d)/now)*now+d);
  98.     }
  99.     return 0;
  100. }

12 test 1212 T1 A

Meet in the middle模板题
因为是无向图,所以可以把从i点到其他点可以得到的二进制数的问题转化为从其他点到i点可以得到的二进制数,所以对于第二个dp就很好处理了.
改题的时候T了一发

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. #define ll long long
  10. const int maxn=97,maxm=2e4+7,maxt=(1<<10)|3;//maxm开小了,T
  11. int n,m,d,totans,sz1,sz2;
  12. bool dp1[2][maxn][maxt],dp2[2][maxn][maxt];
  14. int aa;char cc;
  15. int read() {
  16.     aa=0;cc=getchar();
  17.     while(cc<'0'||cc>'9') cc=getchar();
  18.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  19.     return aa;
  20. }
  22. int fir[maxn],nxt[maxm],to[maxm],v[maxm],e=1;
  23. void add(int x,int y,int z) {
  24.     to[++e]=y;nxt[e]=fir[x];fir[x]=e;v[e]=z;
  25.     to[++e]=x;nxt[e]=fir[y];fir[y]=e;v[e]=z;
  26. }
  28. bool vis[(1<<21)|5];int ans;
  29. void get_ans(int x) {
  30.     if(!vis[x]) ++ans,vis[x]=1;
  31. }
  33. int main() {
  34.     n=read(); m=read(); d=read();
  35.     int x,y,z;
  36.     for(int i=1;i<=m;++i) {
  37.         x=read(); y=read(); z=read();
  38.         add(x,y,z);
  39.     }
  40.     sz1=d/2; sz2=d-sz1;
  41.     int p1=0,p2=0;
  42.     dp1[0][1][0]=1;
  43.     for(int s=1;s<=sz1;++s) {
  44.         p1^=1;
  45.         memset(dp1[p1],0,sizeof(dp1[p1]));
  46.         for(int t=0;t<(1<<s-1);++t) for(int i=1;i<=n;++i) {
  47.             if(dp1[p1^1][i][t]) for(int j=fir[i];j;j=nxt[j]) dp1[p1][to[j]][(t<<1)|v[j]]=1;
  48.         }
  49.     }
  50.     for(int i=1;i<=n;++i) dp2[0][i][0]=1;
  51.     for(int s=1;s<=sz2;++s) {
  52.         p2^=1;
  53.         memset(dp2[p2],0,sizeof(dp2[p2]));
  54.         for(int t=0;t<(1<<s-1);++t) for(int i=1;i<=n;++i) {
  55.             if(dp2[p2^1][i][t]) for(int j=fir[i];j;j=nxt[j]) dp2[p2][to[j]][(t<<1)|v[j]]=1;
  56.         }
  57.     }
  58.     for(int i=1;i<=n;++i) for(int t=0;t<(1<<sz1);++t) if(dp1[p1][i][t]) {
  59.         for(int tt=0;tt<(1<<sz2);++tt) if(dp2[p2][i][tt]) get_ans(t<<sz2|tt);
  60.     }
  61.     printf("%d\n",ans);
  62.     return 0;
  63. }

12 test 1212 T2 B

一道sb题,但是场上sb了.
改题的时候发现题解所说的单调队列并不需要.
然后就自己随便搞了搞,跑得飞快(比std快3倍).
写了两个版本的代码,分别debug,特别难受,后来,,,
随便放一个跑得快的.

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. #define ll long long
  10. const int maxn=2000+7;
  11. int n,m,k,up[maxn][maxn],down[maxn][maxn],ans,nowans[maxn][maxn],p[maxn];
  12. bool ok[maxn][maxn];
  14. ll aa;char cc;
  15. ll read() {
  16.     aa=0;cc=getchar();
  17.     while(cc<'0'||cc>'9') cc=getchar();
  18.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  19.     return aa;
  20. }
  22. struct Ask{
  23.     int x,y;
  24. }ask[maxn];
  26. int f[maxn][maxn],g[maxn][maxn];
  27. bool check(int x,int y,int t) {
  28.     if(t>m||t>n) return 0;
  29.     int l=y,r=y,pos1,pos2,now1,now2;
  30.     f[x][y]=up[x][y];g[x][y]=down[x][y];//一开始g也用的up赋值
  31.     now1=up[x][y];  now2=down[x][y];
  32.     while(now1+now2-1>=t&&l) {
  33.         l--;
  34.         now1=min(now1,up[x][l]);
  35.         now2=min(now2,down[x][l]);
  36.         f[x][l]=now1;g[x][l]=now2;
  37.     }
  38.     l++;
  39.     now1=up[x][y];  now2=down[x][y];
  40.     while(now1+now2-1>=t&&r<=m) {
  41.         r++;
  42.         now1=min(now1,up[x][r]);
  43.         now2=min(now2,down[x][r]);
  44.         f[x][r]=now1;g[x][r]=now2;
  45.     }
  46.     r--;
  47.     if(r-l+1<t) return 0;
  48.     pos1=l;
  49.     for(pos2=y;pos2<=r&&f[x][pos2]+g[x][pos2]-1>=t;++pos2) {
  50.         while(min(f[x][pos1],f[x][pos2])+min(g[x][pos1],g[x][pos2])-1<t) pos1++;
  51.         if(pos2-pos1+1>=t) return 1;
  52.     }
  53.     pos2=r;
  54.     for(pos1=y;pos1>=l&&f[x][pos1]+g[x][pos1]-1>=t;--pos1) {
  55.         while(min(f[x][pos1],f[x][pos2])+min(g[x][pos1],g[x][pos2])-1<t) pos2--;
  56.         if(pos2-pos1+1>=t) return 1;
  57.     }
  58.     return 0;
  59. }
  61. int main() {
  62.     n=read(); m=read(); k=read();
  63.     for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
  64.         do cc=getchar();while(cc!='X'&&cc!='.');
  65.         if(cc=='X') ok[i][j]=1;
  66.     }
  67.     for(int i=1;i<=k;++i) {
  68.         ask[i].x=read(); ask[i].y=read();
  69.         ok[ask[i].x][ask[i].y]=1;
  70.     }
  71.     for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) up[i][j]= ok[i][j]? 0 : up[i-1][j]+1;
  72.     for(int i=n;i;--i) for(int j=1;j<=m;++j) down[i][j]= ok[i][j]? 0 : down[i+1][j]+1;
  73.     for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
  74.         if(ok[i][j]) nowans[i][j]=0;
  75.         else nowans[i][j]=min(nowans[i-1][j-1],min(nowans[i-1][j],nowans[i][j-1]))+1;
  76.         ans=max(ans,nowans[i][j]);
  77.     }
  78.     p[k]=ans;
  79.     int x,y,l,r,len1,len2;
  80.     for(int qaq=k;qaq>1;--qaq) {
  81.         x=ask[qaq].x;y=ask[qaq].y;
  82.         ok[x][y]=0;
  83.         for(int i=x;i<=n&&!ok[i][y];++i) up[i][y]=up[i-1][y]+1;
  84.         for(int i=x;i&&!ok[i][y];--i) down[i][y]=down[i+1][y]+1;//曾把x和y弄错
  85.         while(check(x,y,ans+1)) ++ans;
  86.         p[qaq-1]=ans;
  87.     }
  88.     for(int i=1;i<=k;++i) printf("%d\n",p[i]);
  89.     return 0;
  90. }

12 test 1212night T1 A

一道网络流解决可行流的问题,场上连了负边特别难受.

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. #define ll long long
  10. const ll maxn=200+10,maxm=1000+10,INF=1e9;//数组开小了
  11. ll n,m,S,T,ind[maxn];
  12. ll ans;
  14. ll aa;char cc;
  15. ll read() {
  16.     aa=0;cc=getchar();
  17.     while(cc<'0'||cc>'9') cc=getchar();
  18.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  19.     return aa;
  20. }
  22. struct Node{
  23.     int x,y;ll cap,flow,w;
  24.     Node(){}
  25.     Node(int x,int y,ll cap,ll w):x(x),y(y),cap(cap),w(w){flow=0;}
  26. }node[2*maxm];
  28. int fir[maxn],nxt[2*maxm],e=1;
  29. void add(int x,int y,ll z,ll w) {
  30.     node[++e]=Node(x,y,z,w); nxt[e]=fir[x]; fir[x]=e;
  31.     node[++e]=Node(y,x,0,-w); nxt[e]=fir[y];fir[y]=e;
  32. }
  34. ll zz[maxn],dis[maxn],from[maxn];
  35. bool vis[maxn];
  36. bool spfa() {
  37.     for(int i=1;i<=n+2;++i) dis[i]=INF,from[i]=0;//写成了i<=n
  38.     int s=1,t=0,x,y,z,o;
  39.     dis[S]=0; zz[++t]=S;vis[S]=1;
  40.     while(s<=t) {
  41.         x=zz[s%maxn];s++; vis[x]=0;
  42.         for(y=fir[x];y;y=nxt[y]) {
  43.             z=node[y].y;
  44.             if(node[y].flow>=node[y].cap||dis[z]<=dis[x]+node[y].w) continue;
  45.             dis[z]=dis[x]+node[y].w;
  46.             from[z]=y;
  47.             if(!vis[z]) {
  48.                 vis[z]=1; t++;
  49.                 zz[t%maxn]=z;
  50.             }
  51.         }
  52.     }
  53.     return dis[T]<INF;//一开始建负边的时候写的<0后来忘了改回来
  54. }
  56. ll MCMF() {
  57.     ll rs=0,now;
  58.     while(spfa()) {
  59.         now=INF;
  60.         for(int x=T;x!=S;x=node[from[x]].x) now=min(now,node[from[x]].cap-node[from[x]].flow);
  61.         for(int x=T;x!=S;x=node[from[x]].x) {
  62.             rs+=now*node[from[x]].w;
  63.             node[from[x]].flow+=now;
  64.             node[from[x]^1].flow-=now;
  65.         }
  66.     }
  67.     return rs;
  68. }
  70. int main() {
  71.     n=read(); m=read();
  72.     int x,y,f,c; S=n+1;T=n+2;
  73.     for(int i=1;i<=m;++i) {
  74.         x=read(); y=read(); c=read(); f=read();
  75.         ind[y]+=f; ind[x]-=f;
  76.         if(f<=c) {
  77.             add(y,x,f,1);
  78.             if(f!=c) add(x,y,c-f,1);
  79.             add(x,y,INF,2);
  80.         }
  81.         else { 
  82.             ans+=f-c;
  83.             add(y,x,f-c,0);
  84.             add(y,x,c,1);
  85.             add(x,y,INF,2);
  86.         }
  87.     }
  88.     for(int i=1;i<=n;++i) {
  89.         if(ind[i]<0) add(i,T,-ind[i],0);
  90.         else if(ind[i]>0) add(S,i,ind[i],0);
  91.     }
  92.     add(n,1,INF,0);
  93.     ans+=MCMF();
  94.     printf("%lld",ans);
  95.     return 0;
  96. }

19 test 1219 T3 澳洲稻草人

逐渐明白样例是多么水的东西，对拍是多么优秀的东西

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. #define ll long long
  10. const int maxn=2e5+10;
  11. int n,p1[maxn],p2[maxn],t1,t2;ll ans;
  13. int aa;char cc;
  14. int read() {
  15.     aa=0;cc=getchar();
  16.     while(cc<'0'||cc>'9') cc=getchar();
  17.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  18.     return aa;
  19. }
  21. int now[maxn];
  22. struct Node{
  23.     int x,y,id;
  24. }node[maxn];
  25. bool cmp(const Node& a,const Node& b) {
  26.     return a.x < b.x;
  27. }
  28. bool cmp2(const Node& a,const Node& b) {
  29.     return now[a.y] < now[b.y];
  30. }
  32. int ef(int x,int *p,int r) {
  33.     int l=1,mid;
  34.     while(l<=r) {
  35.         mid=(l+r)>>1;
  36.         if(p[mid]==x) return mid;
  37.         if(p[mid]<x) l=mid+1;
  38.         else r=mid-1;
  39.     }
  40. }
  42. int zz[2][maxn];
  43. int ef2(int x) {
  44.     int l=0,r=t1,mid;
  45.     if(node[zz[0][r]].x<x) return r+1;//一开始写特判t1=0的情况写错了
  46.     while(l<r-1) {
  47.         mid=(l+r)>>1;
  48.         if(node[zz[0][mid]].x>x) r=mid;//栈里面放的是标号而不是直接的x
  49.         else l=mid;
  50.     }
  51.     return r;
  52. }
  54. void add(int p,int x) {
  55.     if(!p) {
  56.         while(t1&&node[zz[0][t1]].y<=node[x].y) --t1;//栈里面放标号，按照y递减
  57.         zz[0][++t1]=x;
  58.     }
  59.     else {
  60.         while(t2&&node[zz[1][t2]].y>=node[x].y) --t2;
  61.         zz[1][++t2]=x;//++写成--了
  62.         if(t2>1) ans+=(ll)t1-(ll)ef2(node[zz[1][t2-1]].x)+1;
  63.         else ans+=t1;
  64.     }
  65. }
  67. void cdq(int l,int r) {
  68.     if(l==r) return; t1=0; t2=0;
  69.     int mid=(l+r)>>1,pos1=l,pos2=mid+1;
  70.     for(int i=l;i<=r;++i) {
  71.         if(node[i].y<=mid) add(0,i),now[node[i].y]=++pos1;
  72.         else add(1,i),now[node[i].y]=++pos2;
  73.     }
  74.     sort(node+l,node+r+1,cmp2);
  75.     cdq(l,mid); cdq(mid+1,r);
  76. }
  78. int main() {
  79.     freopen("scarecrows.in","r",stdin);
  80.     freopen("scarecrows.out","w",stdout);
  81.     n=read(); 
  82.     for(int i=1;i<=n;++i) {
  83.         p1[++t1]=node[i].x=read(); 
  84.         p2[++t2]=node[i].y=read();
  85.     }
  86.     sort(p1+1,p1+t1+1);
  87.     sort(p2+1,p2+t2+1);
  88.     for(int i=1;i<=n;++i) {
  89.         node[i].x=ef(node[i].x,p1,t1);
  90.         node[i].y=ef(node[i].y,p2,t2);
  91.     }
  92.     sort(node+1,node+n+1,cmp);
  93.     cdq(1,n);
  94.     printf("%lld",ans);
  95.     return 0;
  96. }

28 test 1228 T1 可做题1

一道数学题
没什么好说的就是忘了取模，做题的时候一定要注意数据范围

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. #define ll long long
  10. ll T,p,n,m;
  11. ll f[3],g[3][3],f2[3],g2[3][3];
  13. ll aa;char cc;
  14. ll read() {
  15.     aa=0;cc=getchar();
  16.     while(cc<'0'||cc>'9') cc=getchar();
  17.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  18.     return aa;
  19. }
  21. ll gcd(ll x,ll y) {
  22.     return y==0? x:gcd(y,x%y);
  23. }
  25. void cf1() {
  26.     memcpy(f2,f,sizeof(f));
  27.     f[1]=f2[1]*g[1][1]%p+f2[2]*g[2][1]%p;
  28.     f[2]=f2[1]*g[1][2]%p+f2[2]*g[2][2]%p;
  29.     if(f[1]>=p) f[1]-=p;
  30.     if(f[2]>=p) f[2]-=p;
  31. }
  33. void cf2() {
  34.     memcpy(g2,g,sizeof(g));
  35.     memset(g,0,sizeof(g));
  36.     for(int i=1;i<=2;++i) for(int j=1;j<=2;++j) for(int k=1;k<=2;++k) {
  37.         g[i][j]+=g2[i][k]*g2[k][j]%p;
  38.         if(g[i][j]>=p) g[i][j]-=p;
  39.     }
  40. }
  42. void qpz(ll k) {
  43.     f[1]=f[2]=1; g[1][1]=0;
  44.     g[1][2]=g[2][1]=g[2][2]=1;
  45.     while(k) {
  46.         if(k&1) cf1();
  47.         cf2(); k>>=1;
  48.     }
  49. }
  51. ll qp(ll x,ll k) {
  52.     ll rs=1;
  53.     while(k) {
  54.         if(k&1) rs=rs*x%p;
  55.         k>>=1; x=x*x%p;
  56.     }
  57.     return rs;
  58. }
  60. void exgcd(ll a,ll b,ll &x,ll &y) {
  61.     if(!b) {
  62.         x=1; y=0;
  63.         return;
  64.     }
  65.     exgcd(b,a%b,y,x);
  66.     y-=(a/b)*x;
  67. }
  69. ll get_ans(ll r,ll x,ll b) {
  70.     if(r<0) return 0;
  71.     ll rs=r/b;
  72.     if(r%b>=x) rs++;
  73.     return rs;
  74. }
  76. int main() {
  77.     freopen("1.in","r",stdin);
  78.     freopen("test.out","w",stdout);
  79.     T=read();ll x,y,a,b,c,o,l,r,w;
  80.     while(T--) {
  81.         w=read(); l=read(); r=read();
  82.         n=read(); p=read(); m=read();
  83.         qpz(n-3);
  84.         a=f[2]; b=p; c=(m%p-w%p*f[1]%p+p)%p;//
  85.         if(c%(o=gcd(a,b))) {
  86.             printf("0\n"); continue;
  87.         }
  88.         a/=o; b/=o; c/=o;
  89.         exgcd(a,b,x,y); x*=c;
  90.         x%=b; if(x<0) x+=b;
  91.         printf("%lld\n",get_ans(r,x,b)-get_ans(l-1,x,b));
  92.     }
  93.     fclose(stdin);fclose(stdout);
  94.     return 0;
  95. }
  96. /*
  97. 1
  98. 692858490132927148 33 93 11 90 52
  99. */

28 test 1228 T3

网络流题，给一些前缀和后缀，每个前缀或后缀都有一个代价，你需要用最小的代价覆盖所有的数字。
先对前缀和后缀各建一个字典树，然后直接在字典树上建图跑最大流(最小割)。

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. const int maxn=800+7,maxm=maxn*maxn,INF=0x3f3f3f3f;//
  10. int n,m,a[maxn],len,S,T;
  11. bool ok[maxn];
  12. char c[23],s[23];
  14. int aa;char cc;
  15. int read() {
  16.     aa=0;cc=getchar();
  17.     while(cc<'0'||cc>'9') cc=getchar();
  18.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  19.     return aa;
  20. }
  22. //////////////////////////////////////////////////////////////Dinic
  23. struct Node{
  24.     int x,y,flow,cap;
  25.     Node(){}
  26.     Node(int x,int y,int cap):x(x),y(y),cap(cap){flow=0;}
  27. }node[2*maxm];
  29. int cur[maxn],fir[maxn],nxt[2*maxm],e=1;
  30. int ind[maxn];
  31. void add(int x,int y,int z) {
  32. //  printf("add: %d -> %d cap:%d\n",x,y,z); 
  33.     node[++e]=Node(x,y,z); nxt[e]=fir[x];fir[x]=e;
  34.     node[++e]=Node(y,x,0); nxt[e]=fir[y];fir[y]=e;
  35. }
  37. int dis[maxn],zz[maxn];
  38. bool BFS() {
  39.     memset(dis,-1,sizeof(dis));
  40.     int x,y,z,s=1,t=0;
  41.     zz[++t]=S; dis[S]=1;
  42.     while(s<=t) {
  43.         x=zz[s++];
  44.         for(y=fir[x];y;y=nxt[y]) {
  45.             if(dis[z=node[y].y]!=-1||node[y].flow>=node[y].cap) continue;
  46.             dis[z]=dis[x]+1;
  47.             zz[++t]=z;
  48.         }
  49.     }
  50.     return dis[T]!=-1;
  51. }
  53. int DFS(int pos,int maxf) {
  54.     if(pos==T||!maxf) return maxf;
  55.     int z,now,rs=0;
  56.     for(int &y=cur[pos];y&&maxf;y=nxt[y]) {
  57.         if(dis[z=node[y].y]!=dis[pos]+1||node[y].flow>=node[y].cap) continue;
  58.         now=DFS(z,min(maxf,node[y].cap-node[y].flow));
  59.         node[y].flow+=now;
  60.         node[y^1].flow-=now;
  61.         rs+=now; maxf-=now;
  62.     }
  63.     if(!rs) dis[pos]=-1;
  64.     return rs;
  65. }
  67. int Dinic() {
  68.     int rs=0;
  69.     while(BFS()) {
  70.         memcpy(cur,fir,sizeof(fir));
  71.         rs+=DFS(S,INF);
  72.     }
  73.     return rs;
  74. }
  75. ////////////////////////////////////////////////////////////////
  77. bool check(int r,int x,int p,int len) {
  78.     if(p==0) return (r>>(8-len))==x;
  79.     else {
  80.         r&=((1<<len)-1);
  81.         return r==x;
  82.     }
  83. }
  85. int le[maxn],num[maxn],cost[maxn];
  86. int t[2]={1,1};
  87. struct G{
  88.     int num,son[2];
  89. }g[2][maxn*4];
  91. void insert(int p,int x,int len,int i) {
  92.     int now=1,r;
  93.     if(!p) {
  94.         int xx=x; x=0;
  95.         for(int i=1;i<=len;++i,xx>>=1) {
  96.             x<<=1;
  97.             x+=(xx&1);
  98.         }
  99.     }
  100.     while(len--) {
  101.         r=x&1; x>>=1;
  102.         if(!g[p][now].son[r]) g[p][now].son[r]=++t[p];
  103.         now=g[p][now].son[r];
  104.     }
  105.     if(!g[p][now].num) g[p][now].num=i;
  106.     else if(cost[g[p][now].num] > cost[i]) g[p][now].num=i;
  107. }
  109. void dfs1(int pos,int f) {
  110.     if(!pos) return;
  111.     int id=g[0][pos].num;
  112.     if(id) add(f,n+id,cost[id]),f=id+n;//
  113.     dfs1(g[0][pos].son[0],f);
  114.     dfs1(g[0][pos].son[1],f);
  115.     if(id) {
  116.         for(int j=1;j<=n;++j) if((!ok[j])&&check(a[j],num[id],0,le[id])) {
  117.             ok[j]=1; add(n+id,j,INF);
  118.         }
  119.     }
  120. }
  122. void dfs2(int pos,int f) {
  123.     if(!pos) return;
  124.     int id=g[1][pos].num;
  125.     if(id) add(n+id,f,cost[id]),f=id+n;
  126.     dfs2(g[1][pos].son[0],f);
  127.     dfs2(g[1][pos].son[1],f);
  128.     if(id) {
  129.         for(int j=1;j<=n;++j) if((!ok[j])&&check(a[j],num[id],1,le[id])) {
  130.             ok[j]=1; add(j,n+id,INF);
  131.         }
  132.     }
  133. }
  135. int main() {
  136.     freopen("C.in","r",stdin);
  137.     freopen("C.out","w",stdout);
  138.     n=read(); m=read(); int x,p;
  139.     S=n+m+1; T=S+1;
  140.     memset(g,0,sizeof(g));
  141.     for(int i=1;i<=n;++i) a[i]=read();
  142.     for(int i=1;i<=m;++i) {
  143.         scanf("%s%s",c+1,s+1);
  144.         cost[i]=read();
  145.         le[i]=len=strlen(s+1);
  146.         x=0; p= c[1]=='S';//0前缀 1后缀
  147.         for(int j=1;j<=len;++j) {
  148.             x<<=1;
  149.             x+=(s[j]-'0');
  150.         }
  151.         num[i]=x;
  152.         for(int j=1;j<=n;++j) if(check(a[j],x,p,len)) ok[j]=1;
  153.         insert(p,x,len,i);
  154.     }
  155.     for(int i=2;i<=n;++i) ok[1]&=ok[i];
  156.     if(!ok[1]) printf("-1");
  157.     else {
  158.         memset(ok,0,sizeof(ok));
  159.         dfs1(1,S); 
  160.         for(int i=1;i<=n;++i) if(!ok[i]) add(S,i,INF);//一开始没有考虑到
  161.         memset(ok,0,sizeof(ok));
  162.         dfs2(1,T);
  163.         for(int i=1;i<=n;++i) if(!ok[i]) add(i,T,INF);
  164.         printf("%d\n",Dinic());
  165.     }
  166.     fclose(stdin); fclose(stdout);
  167.     return 0;
  168. }
  169. /*
  170. 8 7
  171. 0 1 2 3 4 5 6 6
  172. P 000001 3
  173. P 0000000 2
  174. P 0000010 1
  175. P 0000000 1
  176. S 10 1
  177. S 11 1
  178. S 00 1
  179. S 01 1
  180. */

29 test 1208 T2 BG的保险箱

一个模意义下开根的模板题。第一次写，还是debug了一个小时。

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. #define ll long long
  10. ll T,n,p,ans;
  11. ll f[3],g[3][3],f2[3],g2[3][3];
  13. ll aa;char cc;
  14. ll read() {
  15.     aa=0;cc=getchar();
  16.     while(cc<'0'||cc>'9') cc=getchar();
  17.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  18.     return aa;
  19. }
  21. void cf1() {
  22.     memcpy(f2,f,sizeof(f));
  23.     f[1]=f2[1]*g[1][1]%p+f2[2]*g[2][1]%p;
  24.     f[2]=f2[1]*g[1][2]%p+f2[2]*g[2][2]%p;
  25.     if(f[1]>=p) f[1]-=p;
  26.     if(f[2]>=p) f[2]-=p;
  27. }
  29. void cf2() {
  30.     memcpy(g2,g,sizeof(g));
  31.     memset(g,0,sizeof(g));
  32.     for(int i=1;i<=2;++i) for(int j=1;j<=2;++j) for(int k=1;k<=2;++k) {
  33.         g[i][j]+=g2[i][k]*g2[k][j]%p;
  34.         if(g[i][j]>=p) g[i][j]-=p;
  35.     }
  36. }
  38. void qpz(ll k) {
  39.     f[1]=f[2]=1; g[1][1]=0;
  40.     g[1][2]=g[2][1]=g[2][2]=1;
  41.     while(k) {
  42.         if(k&1) cf1();
  43.         cf2(); k>>=1;
  44.     }
  45. }
  47. ll qp(ll x,ll k) {
  48.     ll rs=1;
  49.     while(k) {
  50.         if(k&1) rs=rs*x%p;
  51.         k>>=1; x=x*x%p;
  52.     }
  53.     return rs;
  54. }
  56. bool check(ll x) {
  57.     x%=p;
  58.     return qp(x,(p-1)>>1) == 1;
  59. }
  61. ll get_sq(ll x) {
  62.     ll a,wpf; x%=p;
  63.     do a=rand()%(2*p);while(!a||check(a*a-x));
  64.     wpf=(a*a-x)%p;
  65.     ll rs1=1,rs2=0,x1=a,x2=1,k=(p+1)>>1,aa,bb;//一开始x1写成了1 
  66.     while(k) {
  67.         if(k&1) {
  68.             aa=(rs1*x1%p+rs2*x2%p*wpf%p)%p;
  69.             bb=(rs1*x2%p+rs2*x1%p)%p;
  70.             rs1=aa; rs2=bb;
  71.         }
  72.         k>>=1;
  73.         aa=(x1*x1%p+x2*x2%p*wpf%p)%p;
  74.         bb=2*x1*x2%p;
  75.         x1=aa; x2=bb;
  76.     }
  77.     return rs1;
  78. }
  80. int main() {
  81.     srand(1031); ll a,b;
  82.     T=read();
  83.     while(T--) {
  84.         a=read(); b=read(); n=read(); p=read();
  85.         if((!check(a)||(!check(b)))) printf("0\n");
  86.         else {
  87.             a=get_sq(a);
  88.             b=get_sq(b);
  89.             p--; qpz(n-1); 
  90.             f[1]=f[1]*2%p; f[2]=f[2]*2%p;
  91.             p++; ans=(qp((a+b+p)%p,f[2])+qp((a-b+p)%p,f[2]))%p;
  92.             printf("%lld\n",ans*4%p);
  93.         }
  94.     }
  95.     return 0;
  96. }
  97. /*
  98. 4
  99. 2 3 1 10007
  100. 2 3 2 10007
  101. 2 3 3 10007
  102. 2 3 4 10007
  103. */

2018.01

0104 练习题palindrome

和去年省选D2T3很像，但不用本质不同，而且简单很多，用后缀数组和马拉车预处理lcp和以i为开头的回文串(放到树状数组里)bug弄了一晚上

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. #define ll long long
  10. const int maxn=16e5+10,INF=0x3f3f3f3f;
  11. int n,m,Q,ql,qr;ll totans;
  12. char A[maxn],B[maxn],S[2*maxn];
  13. int x[maxn],y[maxn],c[maxn],sa[maxn],h[maxn],rad[maxn];
  15. ll aa;char cc;
  16. ll read() {
  17.     aa=0;cc=getchar();
  18.     while(cc<'0'||cc>'9') cc=getchar();
  19.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  20.     return aa;
  21. }
  23. ll minnum[4*maxn];
  24. void bld(int pos,int l,int r) {
  25.     if(l==r) {
  26.         minnum[pos]=h[l];
  27.         return;
  28.     }
  29.     int mid=(l+r)>>1;
  30.     bld(pos<<1,l,mid); bld(pos<<1|1,mid+1,r);
  31.     minnum[pos]=min(minnum[pos<<1],minnum[pos<<1|1]);
  32. }
  34. ll qmin(int pos,int l,int r) {
  35.     if(l>=ql&&r<=qr) return minnum[pos];
  36.     int mid=(l+r)>>1;ll rs=INF;
  37.     if(ql<=mid) rs=min(rs,qmin(pos<<1,l,mid));
  38.     if(qr>mid) rs=min(rs,qmin(pos<<1|1,mid+1,r));
  39.     return rs;
  40. }
  42. ll tot[2][maxn],sum[2][maxn];
  43. ll q(int pos,ll *sz) {
  44.     ll rs=0;
  45.     while(pos) {
  46.         rs+=sz[pos];
  47.         pos-=pos&-pos;
  48.     }
  49.     return rs;
  50. }
  52. void chge(int pos,int x,ll *sz,int n) {
  53.     while(pos<=n) {
  54.         sz[pos]+=x;
  55.         pos+=pos&-pos;
  56.     }
  57. }
  59. void get_sa(char *s,int n) {
  60.     int m='z'+1,p;
  61.     for(int i=0;i<n;++i) c[x[i]=s[i]]++;
  62.     for(int i=1;i<m;++i) c[i]+=c[i-1];
  63.     for(int i=n-1;i>=0;--i) sa[--c[x[i]]]=i;
  64.     for(int k=1;k<=n;k<<=1) {
  65.         p=0;
  66.         for(int i=n-1;i>=n-k;--i) y[p++]=i;
  67.         for(int i=0;i<n;++i) if(sa[i]>=k) y[p++]=sa[i]-k;
  68.         for(int i=0;i<m;++i) c[i]=0;
  69.         for(int i=0;i<n;++i) c[x[y[i]]]++;
  70.         for(int i=1;i<m;++i) c[i]+=c[i-1];
  71.         for(int i=n-1;i>=0;--i) sa[--c[x[y[i]]]]=y[i];
  73.         swap(x,y);p=1;
  74.         x[sa[0]]=0;
  75.         for(int i=1;i<n;++i) 
  76.             x[sa[i]]= y[sa[i]]==y[sa[i-1]]&&
  77.             ((sa[i]+k<n&&sa[i-1]+k<n&&y[sa[i]+k]==y[sa[i-1]+k])||(sa[i]+k>=n&&sa[i-1]+k>=n))? p-1:p++;
  78.         if(p>=n) break; else m=p;
  79.     }
  80.     p=0;int u;
  81.     for(int i=0;i<n;++i) {
  82.         if(!x[i]) continue;
  83.         u=sa[x[i]-1];
  84.         if(p) p--;
  85.         while(s[u+p]==s[i+p]) p++;
  86.         h[x[i]]=p;
  87.     }
  88.     memset(minnum,0x3f3f3f3f,sizeof(minnum));
  89.     bld(1,1,n-1);
  90. }
  92. void manacher(char *s,ll *sz,int len,int o) {
  93.     int maxpos=0,p=0;
  94.     for(int i=len;i;--i) {//不是从0开始而是从1开始 
  95.         s[i<<1]=s[i];
  96.         s[i<<1|1]='#';
  97.     }
  98.     s[0]=s[1]='#';
  99.     for(int i=2;i<=2*len;++i) {
  100.         if(maxpos>i) rad[i]=min(maxpos-i,rad[2*p-i]);
  101.         else rad[i]=0;
  102.         while(i-rad[i]>0&&i+rad[i]<=2*len+1&&s[i-rad[i]]==s[i+rad[i]]) rad[i]++;
  103.         rad[i]--;
  104.         if(i+rad[i]>maxpos) p=i,maxpos=i+rad[i];
  105.     }
  106.     for(int i=2;i<=2*len;++i) {
  107.         chge((i-rad[i]+1)>>1,1,tot[o],len);
  108.         chge((i+2)>>1,-1,tot[o],len);
  109.     }
  110. }
  112. int main() {
  113.     freopen("palindrome.in","r",stdin);
  114.     freopen("palindrome.out","w",stdout);
  115.     scanf("%s",A+1);
  116.     scanf("%s%s",A+1,B+1);
  117.     n=strlen(A+1); m=strlen(B+1);
  118.     for(int i=1;i<=m/2;++i) swap(B[i],B[m-i+1]);
  119.     for(int i=1;i<=n;++i) S[i-1]=A[i]; S[n]='#';//n不是n+1 
  120.     for(int i=1;i<=m;++i) S[i+n]=B[i];
  121.     get_sa(S,n+m+1);
  122.     manacher(A,tot[0],n,0);
  123.     manacher(B,tot[1],m,1);
  124.     for(int i=1;i<=n;++i) chge(i,q(i,tot[0]),sum[0],n+1); 
  125.     for(int i=1;i<=m;++i) chge(i,q(i,tot[1]),sum[1],m+1);
  126.     //注意是n+1和m+1,因为可能询问到 
  128.     Q=read();int xx,yy,len;
  129.     for(int i=1;i<=Q;++i) {
  130.         xx=read(); yy=read();
  131.         ql=x[xx-1]; qr=x[yy+n];
  132.         if(qr<ql) swap(ql,qr);
  133.         ++ql;
  134.         len=qmin(1,1,n+m);
  135.         totans=len;
  136.         totans+=q(xx+len,sum[0])-q(xx,sum[0]);
  137.         totans+=q(yy+len,sum[1])-q(yy,sum[1]);//注意边界 
  138.         printf("%lld\n",totans);
  139.     }
  140.     fclose(stdin);fclose(stdout);
  141.     return 0;
  142. }
  143. /*
  144. orzAchen
  145. babaabbba
  146. baaabbb
  147. 1
  148. 9 6
  149. */
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注