Diary of March 28th

3
28
2016

今天做了三道看过题解就是SB题的题

ZJOI DAY1T2做了一晚上

不开森

Codeforces653D

二分每头熊带多少货物

然后把每条边都除去这个值

那么每条边的权值就变成了最多能通过多少头熊

跑网络流验证一下就可以了

二分80次

CF653D
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99	`#include<cstdio>` `#include<cstring>` `#include<algorithm>` `#include<cctype>` `#include<ctime>` `#include<cstdlib>` `#include<string>` `#include<queue>` `#include<cmath>` `#include<set>` `#include<map>` `#include<bitset>` `#define Rep(x,a,b) for (int x=a;x<=b;x++)` `#define Drp(x,a,b) for (int x=a;x>=b;x--)` `#define Cross(x,a) for (int x=head[a];~x;x=next[x])` `#define ll long long` `#define eps 1e-9` `#define oo (1<<29)` `#define mk(a,b) make_pair(a,b)` `#define fr first` `#define sc second` `using` `namespace` `std;` `inline` `ll IN(){` `ll x=0;int` `ch=getchar(),f=1;` `while` `(!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();` `if` `(ch=='-'){f=-1;ch=getchar();}` `while` `(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}` `return` `xf;` `}` `inline` `void` `OUT(ll x){` `if` `(x<0)` `putchar('-'),x=-x;` `if` `(x>=10) OUT(x/10),putchar(x%10+'0');` `else` `putchar(x+'0');` `}` `const` `int` `N=55,M=505;` `double` `L=0,R=0;` `int` `cnt,to[M<<1],next[M<<1],cap[M<<1],Cap[M<<1],head[N];` `void` `AddEdge(int` `u,int` `v,int` `w){` `to[cnt]=v;next[cnt]=head[u];Cap[cnt]=w;head[u]=cnt++;` `to[cnt]=u;next[cnt]=head[v];Cap[cnt]=0;head[v]=cnt++;` `}` `int` `n,m,x,Tm[N],De[N],T,q[N],h,t;` `bool` `BFS(){` `h=1,t=0;` `T++;` `Tm[1]=T,De[1]=1;` `q[++t]=1;` `while` `(h<=t){` `int` `u=q[h++];` `Cross(i,u)` `if` `(cap[i]!=0&&Tm[to[i]]<T){` `int` `v=to[i];` `Tm[v]=T;` `De[v]=De[u]+1;` `q[++t]=v;` `}` `}` `return` `Tm[n]==T;` `}` `int` `DFS(int` `u,int` `Flow){` `if` `(u==n\|\|!Flow)` `return` `Flow;` `int` `ret=0,F;` `Cross(i,u){` `int` `v=to[i];` `if` `(De[v]==De[u]+1&&(F=DFS(v,min(Flow,cap[i])))){` `ret+=F,Flow-=F;` `cap[i]-=F,cap[i^1]+=F;` `}` `}` `return` `ret;` `}` `int` `Dinic(){` `T=0;` `int` `Flow=0;` `while` `(BFS()){` `int` `F=0;` `while` `(F=DFS(1,oo)) Flow+=F;` `}` `return` `Flow;` `}` `double` `Solve(){` `double` `l=1e-5,r=1e6;` `Rep(it,1,80){` `double` `mid=(l+r)/2;` `memset(Tm,0,sizeof` `Tm);` `Rep(i,0,cnt-1) cap[i]=min((int)(Cap[i]/mid),1000000);` `int` `f=Dinic();` `if` `(f>=x) l=mid;else` `r=mid;` `}` `return` `l;` `}` `int` `main(){` `n=IN(),m=IN(),x=IN();` `memset(head,-1,sizeof` `head);` `Rep(i,1,m){` `int` `u=IN(),v=IN(),w=IN();` `AddEdge(u,v,w);` `}` `printf("%.10lf\n",Solve()x);` `}`

BZOJ2726

斜率优化DP

$DP_i$ 表示处理到第

$i$ 个为止，所有的任务的最小费用和

$T_i$ 和

$F_i$ 表示前缀和

$DP_i=min\{DP_j+(S+T_i-T_j)*(F_n-F_j)$

把

$DP_j+(S-T_j)*(F_n-F_j)$ 当做

$y$

把

$F_j-F_n$ 当做

$x$ （没打错）

把

$T_i$ 当做

$k$ ，把

$DP_i$ 当做

$b$

$kx+b=y$ ，

$x$ 递增，

$k$ 不固定，

维护单调栈，每次二分就可以了

BZOJ2726
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70	`#include<cstdio>` `#include<cstring>` `#include<algorithm>` `#include<cctype>` `#include<ctime>` `#include<cstdlib>` `#include<string>` `#include<queue>` `#include<cmath>` `#include<set>` `#include<map>` `#include<bitset>` `#define Rep(x,a,b) for (int x=a;x<=b;x++)` `#define Drp(x,a,b) for (int x=a;x>=b;x--)` `#define Cross(x,a) for (int x=head[a];~x;x=next[x])` `#define ll long long` `#define oo (1<<29)` `#define mk(a,b) make_pair(a,b)` `#define fr first` `#define sc second` `using` `namespace` `std;` `inline` `ll IN(){` `ll x=0;int` `ch=getchar(),f=1;` `while` `(!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();` `if` `(ch=='-'){f=-1;ch=getchar();}` `while` `(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}` `return` `xf;` `}` `inline` `void` `OUT(ll x){` `if` `(x<0)` `putchar('-'),x=-x;` `if` `(x>=10) OUT(x/10),putchar(x%10+'0');` `else` `putchar(x+'0');` `}` `const` `int` `N=300005;` `int` `n,S;` `ll T[N],F[N],Dp[N],Y[N],X[N];` `long` `double` `GK(int` `a,int` `b){` `if` `(X[a]==X[b]){` `if` `(Y[a]>Y[b])` `return` `1e9;` `else` `return` `-1e9;` `}` `return` `(long` `double)(Y[a]-Y[b])/(X[a]-X[b]);` `}` `int` `Top,St[N];` `int` `GetAns(long` `double` `K){` `if` `(Top==1)` `return` `St[1];` `if` `(GK(St[Top],St[Top-1])<K)` `return` `St[Top];` `int` `l=1,r=Top-1;` `while` `(l<r){` `int` `mid=l+r>>1;` `if` `(GK(St[mid+1],St[mid])<K) l=mid+1;` `else` `r=mid;` `}` `return` `St[l];` `}` `int` `main(){` `n=IN(),S=IN();` `Rep(i,1,n) T[i]=T[i-1]+IN(),F[i]=F[i-1]+IN();` `X[0]=-F[n],Y[0]=SF[n];` `Top=0,St[++Top]=0;` `Rep(i,1,n){` `int` `Bt=GetAns(T[i]);` `Dp[i]=Y[Bt]-T[i]X[Bt];` `X[i]=F[i]-F[n];` `Y[i]=Dp[i]+(S-T[i])(F[n]-F[i]);` `while` `(Top>1&&GK(St[Top],St[Top-1])>=GK(i,St[Top])) Top--;` `St[++Top]=i;` `}` `OUT(Dp[n]);` `}`

BZOJ4456

分治

题解：某初三神牛的博客

讲道理这是我第一次写堆优化的dijkstra

一开始用系统的优先队列狂WA不止而且后面几个点又WA又T

然后就改成手写堆

然后卡卡常

一个晚上就过去了。。

BZOJ4456
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131	`#include<cstdio>` `#include<cstring>` `#include<algorithm>` `#include<cctype>` `#include<ctime>` `#include<cstdlib>` `#include<string>` `#include<queue>` `#include<cmath>` `#include<set>` `#include<map>` `#include<bitset>` `#define Rep(x,a,b) for (int x=a;x<=b;x++)` `#define Drp(x,a,b) for (int x=a;x>=b;x--)` `#define Cross(x,a) for (int x=head[a];~x;x=next[x])` `#define ll long long` `#define oo (1<<29)` `#define mk(a,b) make_pair(a,b)` `#define fr first` `#define sc second` `#define y1 sdjfklajsdlkfs` `#define y2 fsdafsdsdjfaskdls` `#define ID(a,b) ((a-1)m+b)` `using` `namespace` `std;` `#define S 100000` `char` `bf[S],p1=bf,p2=bf;` `#define nc() (p1==p2&&(p2=(p1=bf)+fread(bf,1,S,stdin),p2==p1)?-1:p1++)` `inline` `int` `IN(){` `int` `x=0;char` `ch=nc();for(;ch<'0'\|\|ch>'9';ch=nc());` `for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return` `x;` `}` `inline` `void` `OUT(ll x){` `if` `(x<0)` `putchar('-'),x=-x;` `if` `(x>=10) OUT(x/10),putchar(x%10+'0');` `else` `putchar(x+'0');` `}` `const` `int` `N=20005,Q=100005;` `int` `n,m,q;` `int` `Dt[N],Vs[N],Ans[Q],r[N],c[N];` `struct` `Query{` `int` `x1,y1,x2,y2,id;` `}a[Q],b[Q];` `int` `min(int` `a,int` `b){return` `a<b?a:b;}` `int` `H[N<<2],Ps[N],Nm;` `void` `PushDown(int` `Cur){` `int` `Zx=H[Cur],Ds=Dt[Zx];` `while` `((Cur<<1)<=Nm){` `int` `Nx=Cur<<1;` `if` `(Nx<Nm&&Dt[H[Nx\|1]]<Dt[H[Nx]]) Nx\|=1;` `if` `(Dt[H[Nx]]<Ds){` `H[Cur]=H[Nx];` `Ps[H[Cur]]=Cur;` `Cur=Nx;` `}` `else` `break;` `}` `H[Cur]=Zx,Ps[Zx]=Cur;` `}` `void` `PushUp(int` `Cur){` `int` `Zx=H[Cur],Ds=Dt[Zx];` `while` `(Cur!=1&&Dt[H[Cur>>1]]>Ds){` `H[Cur]=H[Cur>>1];` `Ps[H[Cur]]=Cur;` `Cur>>=1;` `}` `H[Cur]=Zx,Ps[Zx]=Cur;` `}` `void` `Dijkstra(int` `sx,int` `sy,int` `x1,int` `x2,int` `y1,int` `y2){` `int` `s=ID(sx,sy);` `H[1]=s,Ps[s]=1;` `Nm=1;` `Rep(i,x1,x2) Rep(j,y1,y2){` `int` `Lt=ID(i,j);` `Vs[Lt]=0,Dt[Lt]=oo;` `if` `(Lt!=s){H[++Nm]=Lt;Ps[Lt]=Nm;}` `}` `Dt[s]=0;` `Drp(i,Nm,1){` `int` `u=H[1];H[1]=H[Nm--];PushDown(1);` `Vs[u]=1;` `int` `tx=(u-1)/m+1,ty=(u-1)%m+1,It=ID(tx,ty);` `if` `(tx>x1&&Dt[It]+c[It-m]<Dt[It-m]) Dt[It-m]=Dt[It]+c[It-m],PushUp(Ps[It-m]);` `if` `(ty>y1&&Dt[It]+r[It-1]<Dt[It-1]) Dt[It-1]=Dt[It]+r[It-1],PushUp(Ps[It-1]);` `if` `(tx<x2&&Dt[It]+c[It]<Dt[It+m]) Dt[It+m]=Dt[It]+c[It],PushUp(Ps[It+m]);` `if` `(ty<y2&&Dt[It]+r[It]<Dt[It+1]) Dt[It+1]=Dt[It]+r[It],PushUp(Ps[It+1]);` `}` `}` `void` `Solve(int` `x1,int` `x2,int` `y1,int` `y2,int` `l,int` `r){` `if` `(l>r)` `return;` `if` `(x2-x1>y2-y1){` `int` `mid=x1+x2>>1;` `Rep(i,y1,y2){` `Dijkstra(mid,i,x1,x2,y1,y2);` `Rep(j,l,r) Ans[a[j].id]=min(Ans[a[j].id],Dt[ID(a[j].x1,a[j].y1)]+Dt[ID(a[j].x2,a[j].y2)]);` `}` `int` `L=l-1,R=r+1;` `Rep(i,l,r){` `if` `(a[i].x1<mid&&a[i].x2<mid) b[++L]=a[i];` `if` `(a[i].x1>mid&&a[i].x2>mid) b[--R]=a[i];` `}` `Rep(i,l,L) a[i]=b[i];Solve(x1,mid-1,y1,y2,l,L);` `Rep(i,R,r) a[i]=b[i];Solve(mid+1,x2,y1,y2,R,r);` `}` `else{` `int` `mid=y1+y2>>1;` `Rep(i,x1,x2){` `Dijkstra(i,mid,x1,x2,y1,y2);` `Rep(j,l,r) Ans[a[j].id]=min(Ans[a[j].id],Dt[ID(a[j].x1,a[j].y1)]+Dt[ID(a[j].x2,a[j].y2)]);` `}` `int` `L=l-1,R=r+1;` `Rep(i,l,r){` `if` `(a[i].y1<mid&&a[i].y2<mid) b[++L]=a[i];` `if` `(a[i].y1>mid&&a[i].y2>mid) b[--R]=a[i];` `}` `Rep(i,l,L) a[i]=b[i];Solve(x1,x2,y1,mid-1,l,L);` `Rep(i,R,r) a[i]=b[i];Solve(x1,x2,mid+1,y2,R,r);` `}` `}` `int` `main(){` `n=IN(),m=IN();` `Rep(i,1,n) Rep(j,1,m-1) r[ID(i,j)]=IN();` `Rep(i,1,n-1) Rep(j,1,m) c[ID(i,j)]=IN();` `q=IN();` `Rep(i,1,q){` `a[i].x1=IN(),a[i].y1=IN(),a[i].x2=IN(),a[i].y2=IN();` `a[i].id=i;` `}` `memset(Ans,127,sizeof` `Ans);` `Solve(1,n,1,m,1,q);` `Rep(i,1,q) OUT(Ans[i]),putchar('\n');` `}`

Category: Diary | Tags: 分治图论网络流 DP 凸包 | Read Count: 918

[回复]

KBPE Question Paper 说:
3 年前 SCERT Kerala Model Paper 2023 Pdf Download for Pareeksha Bhavan and Samagra Shiksha designed and suggested Model Question Bank or Question Pool for Theory, Objective (MCQ) and Bit Questions to 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (SSLC), 11 & 12 (+1 & +2) HSC Malayalam Medium & English Medium students. KBPE Question Paper New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.

WTRC's Memory

三世烟火沧笙踏歌