续。。。。。TAT这回不到50题编辑器就崩了。。
这里塞40道吧= =
bzoj 1585： [Usaco2009 Mar]Earthquake Damage 2 地震伤害
比较经典的最小割？。。然而一开始还是不会QAQ
和地震伤害1的区别在于这题求的是最少的损坏牧场数目。把牧场拆点，因为要让1和被报告的点不联通，把1归到S集，被报告的点归到T集，就变成求最小割了。
具体建图：
假设点拆成x和x’，x和x‘间连边（就是等下要割的）。被报告的点和1点：容量无穷大（不能割）；其他点容量为1。
原图中相连的边就按照二分图正常姿势，出点连到入点，容量无穷大（路没坏）。
最后就是s连1，被报告的点连t，容量都无穷大
dinic大法好。。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
const int inf=;
struct zs{
int too,pre,flow;
}e[];
int last[maxn<<],dl[maxn<<],l,r,now,tot=;
short dis[maxn<<];
bool u[maxn];
int i,j,k,n,m,a,b,s,t,p,ans; int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline void insert(int a,int b,int c){
// printf(" %d-->%d %d\n",a,b,c==1?1:233);
e[++tot].too=b;e[tot].flow=c;e[tot].pre=last[a];last[a]=tot;
e[++tot].too=a;e[tot].flow=;e[tot].pre=last[b];last[b]=tot;
}
inline bool bfs(){
memset(dis,,(t+)<<);
l=;r=;dl[]=s;dis[s]=;
while(l<r&&dis[t]==-)for(now=dl[++l],i=last[now];i;i=e[i].pre)if(e[i].flow&&dis[e[i].too]==-)
dis[e[i].too]=dis[now]+,dl[++r]=e[i].too;
// for(i=1;i<=t;i++)printf(" %d %d\n",i,dis[i]);
return dis[t]!=-;
}
int dfs(int x,int mx){
if(x==t||!mx)return mx;
int used=,i,w;
for(i=last[x];i;i=e[i].pre)if(dis[e[i].too]==dis[x]+&&e[i].flow){
w=dfs(e[i].too,min(mx-used,e[i].flow));if(w){
e[i].flow-=w;e[i^].flow+=w;
used+=w;if(used==mx)return mx;
}
}
dis[x]=-;return used;
}
int main(){
n=read();m=read();p=read();s=;t=n+n+;
for(i=;i<=m;i++)a=read(),b=read(),insert(a+n,b,inf),insert(b+n,a,inf);
for(i=;i<=p;i++)a=read(),u[a]=,insert(a,a+n,inf),insert(a+n,t,inf);
for(i=;i<=n;i++)if(!u[i])insert(i,i+n,);if(!u[])insert(,+n,inf);
insert(s,,inf);
while(bfs())ans+=dfs(s,inf);
printf("%d\n",ans);
return ;
} View
bzoj 2200： [Usaco2011 Jan]道路和航线
正解：根据题目，一条航线就是图的一条割边。。 所以先把图中各个联通块单独拿出来，在联通块里跑最短路（这时联通块里没有负权边，就用Dijkstra+堆去求）。再按联通块之间的拓扑顺序把整张图的最短路求出来。
又wa又T一时爽。。一开始是没注意负权边直接上dij，然后是spfa被卡。。。。spfa+slf就可过了= =巧妙的避开了正解（逃。。。
话说spfa好像并不难卡？。。。以后得小心了QAQ
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
const int mx=;
struct zs{
int too,pre,dis;
}e[];
int dl[mx+];
int i,j,k,n,m,m1,s,tot,a,b,c;
int dis[maxn],last[maxn];
bool u[maxn];
int ra,fh;char rx;
inline int getnext(int x){
x++;if(x>=mx)return ;
return x;
}
inline int getpre(int x){
x--;if(x<)return mx-;
return x;
}
inline int read(){
rx=getchar();ra=;fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')fh=-,rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
}
inline void insert(int a,int b,int c){
e[++tot].too=b;e[tot].dis=c;e[tot].pre=last[a];last[a]=tot;
} inline void spfa(){
int size=,i,now,to,l,r;//,tt=0;
memset(dis,,(n+)<<);
dis[s]=;dl[]=s;l=;r=;
while(size){
l=getnext(l);size--;
now=dl[l];u[now]=;
for(i=last[now],to=e[i].too;i;i=e[i].pre,to=e[i].too)if(dis[to]>dis[now]+e[i].dis){
dis[to]=dis[now]+e[i].dis;
if(!u[to])
if(size&&dis[to]<dis[dl[getnext(l)]])dl[l]=to,l=getpre(l),size++,u[to]=;
else r=getnext(r),dl[r]=to,size++,u[to]=;
}
}
}
int main(){
n=read();m=read();m1=read();s=read();
for(i=;i<=m;i++)a=read(),b=read(),c=read(),insert(a,b,c),insert(b,a,c);
for(i=;i<=m1;i++)a=read(),b=read(),c=read(),insert(a,b,c);
spfa();
for(i=;i<=n;i++)if(dis[i]<)printf("%d\n",dis[i]);else puts("NO PATH");
return ;
}
bzoj 1575： [Usaco2009 Jan]气象牛Baric
正常dp。。。先预处理出sum[i][j]表示s集中选了第i天和第j天时，原序列中第i+1~j-1天的误差值之和。pre[i]表示s集中第一个选了i的话，1~i-1天的误差和。aft[i]表示s集中最后一个是第i天的话i+1~n天的误差和。
f[i][j]表示最后选第i天，总共选了j天的第1~i天的最小误差。初始化f[i][1]=pre[i];
f[i][j]=min{f[k][j-1]+sum[k][i]}，（1<=k<i，2<=j<=n）。如果min{ f[i][j]+aft[i] }<=E的话就可以了
总复杂度O(n^3)。
#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;
const int maxn=;
int i,j,k,n,m,l,r,mid,ans,tmp;
int a[maxn],sum[maxn][maxn],aftsum[maxn],befsum[maxn];
int f[maxn][maxn];
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
int main(){
n=read();m=read();
for(i=;i<=n;i++)a[i]=read();
for(i=;i<n;i++)for(j=i+;j<=n;j++)
for(k=i+;k<j;k++)sum[i][j]+=abs((a[k]<<)-a[i]-a[j]);
for(i=n;i;i--){
for(j=n;j>i;j--)aftsum[i]+=abs(a[j]-a[i])<<;
for(j=;j<i;j++)befsum[i]+=abs(a[j]-a[i])<<;
}
for(i=;i<=n;i++)f[i][]=befsum[i];
ans=;
for(j=;j<=n&&ans>m;j++){
for(i=j;i<=n;i++){
if(j>)
for(f[i][j]=f[][j-]+sum[][i],k=;k<i;k++)if(f[k][j-]+sum[k][i]<f[i][j])f[i][j]=f[k][j-]+sum[k][i];
if(f[i][j]+aftsum[i]<ans)ans=f[i][j]+aftsum[i];
}
}
printf("%d %d\n",j-,ans);
return ;
}
bzoj 1755： [Usaco2005 qua]Bank Interest
如题。。就是求算存钱若干年后的本息之和
#include<cstdio>
#include<iostream>
#include<cstring>
#define d double
using namespace std;
int i,j,k,n,m,r,y;
d ans;
int main(){
scanf("%d%d%d",&r,&m,&y);
ans=(d)(+r)/(d)100.0;
for(i=;i<=y;i++)ans=ans*(d)(+r)/(d)100.0;
printf("%d\n",y?(int)(ans*m):m);
return ;
}
bzoj 1774： [Usaco2009 Dec]Toll 过路费
floyd。。http://www.cnblogs.com/czllgzmzl/p/5070943.html
bzoj 1775： [Usaco2009 Dec]Vidgame 电视游戏问题
一开始以为是状压。。。结果发现数据范围是给01背包的= =
ans[i]表示指出i元的最多产出，f[i]表示当前游戏平台内，花i元买游戏的最大产出。初始化f[i]=ans[i-P]（买游戏得先买平台），（P是当前游戏平台的价格）f[i]就是个01背包。
ans[i]=max(ans[i],f[i])。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int cost,val;
int need,num;
int f[],g[];
int i,j,k,n,m,maxv,tmp,ans;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
int main(){
n=read();maxv=read();
for(i=;i<=n;i++){
need=read();num=read();
memset(g,,need<<);
for(j=need;j<=maxv;j++)g[j]=f[j-need];
for(j=;j<num;j++)
for(cost=read(),val=read(),k=maxv,tmp=k-cost;tmp>=;k--,tmp--)
if(g[tmp]+val>g[k])g[k]=g[tmp]+val;
for(j=maxv;j>=need;j--)if(f[j]<g[j])f[j]=g[j];
}
for(i=maxv;i>=;i--)if(f[i]>ans)ans=f[i];
printf("%d\n",ans);
return ;
}
bzoj 1696: [Usaco2007 Feb]Building A New Barn新牛舍
中位数。。好吧是平面上的。设奶牛吃草位置为x[],y[]，理想情况下(ansx,ansy)分别是x数组、y数组排序后的中位数。
n为奇数时，最理想的点是唯一的。但如果那个地方已经有奶牛吃草了的话，就尝试下它相邻4个点（这是仅有的可能次优的几个）。
n为偶数时，点(x[n/2],y[n/2])与点(x[n/2+1],y[n/2+1])组成的矩形内的点都是最优的。（x、y已排序）最优点的个数要减去在矩形里吃草的牛的数量。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=;
struct zs{
int x,y;
}a[maxn];
int xx[]={,,,-},yy[]={,-,,};
int i,j,k,n,m,maxv,tmp,ans,x,y,nowx,nowy,x1,y1,sum;
bool cant;
int ra,fh;char rx;
inline int read(){
rx=getchar();ra=;fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')rx=getchar(),fh=-;
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
}
bool cmp1(zs a,zs b){
return a.x<b.x;
}
bool cmp2(zs a,zs b){
return a.y<b.y;
}
inline int get(int x,int y){
int ans=,i;
for(i=;i<=n;i++)ans+=abs(x-a[i].x)+abs(y-a[i].y);return ans;
}
int main(){
n=read();
for(i=;i<=n;i++)a[i].x=read(),a[i].y=read();
ans=;
if(n&){
sort(a+,a++n,cmp1);x=a[(n+)>>].x;
sort(a+,a++n,cmp2);y=a[(n+)>>].y;
for(i=;i<=n;i++)if(a[i].x==x&&a[i].y==y){cant=;break;}
if(!cant)ans=get(x,y),sum=;
else for(i=;i<;i++){
nowx=x+xx[i];nowy=y+yy[i];
tmp=get(nowx,nowy);if(tmp<ans)ans=tmp,sum=;else if(tmp==ans)sum++;
}
}else{
sort(a+,a++n,cmp1);x=a[n>>].x;x1=a[n/+].x;
sort(a+,a++n,cmp2);y=a[n>>].y;y1=a[n/+].y;
ans=get(x,y);sum=(x1-x+)*(y1-y+);
for(i=;i<=n;i++)if(a[i].x>=x&&a[i].x<=x1&&a[i].y>=y&&a[i].y<=y1)sum--;
}
printf("%d %d\n",ans,sum);
return ;
}
bzoj 1916： [Usaco2010 Open]冲浪
dp。按照拓扑顺序来。。f[i][j]表示从i点到n点，途中j次失误的最大愉悦值，val(i,j)表示i到j这条边的愉悦值。
f[i][j]=min{ max{ f[k][j]+val(i,k) }（没失误），min{ f[k][j-1]+val(i,k) }（失误了= =） }，（存在边i-->k）。
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=;
struct zs{
int dis,too,pre;
}e[],E[];
int last[maxn],cd[maxn],las[maxn];
ll f[maxn][];
int dl[maxn],l,r,now,to;
int i,j,k,K,n,m,a,b,c;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline void ins(int a,int b,int c){
E[i].too=b;E[i].dis=c;E[i].pre=las[a];las[a]=i;
}
int main(){
n=read();m=read();K=read();
for(i=;i<=m;i++)
a=read(),b=read(),e[i].dis=read(),e[i].too=a,e[i].pre=last[b],last[b]=i,cd[a]++,ins(a,b,e[i].dis);
//memset(f,255,sizeof(f));
r=;dl[]=n;f[n][]=;
while(l<r){
now=dl[++l];
for(i=last[now],to=e[i].too;i;i=e[i].pre,to=e[i].too){
cd[to]--;if(!cd[to])dl[++r]=to;
if(f[now][]+e[i].dis>f[to][])f[to][]=f[now][]+e[i].dis;
}
}
// for(i=1;i<=n;i++)printf(" %d %lld\n",dl[i],f[dl[i]][0]);
for(i=,now=dl[i];i<=n;now=dl[++i]){
for(j=las[now],to=E[j].too;j;j=E[j].pre,to=E[j].too)
for(k=;k<=K;k++)if(f[to][k]+E[j].dis>f[now][k])f[now][k]=f[to][k]+E[j].dis;
for(j=las[now],to=E[j].too;j;j=E[j].pre,to=E[j].too)
for(k=;k<=K;k++)if(f[to][k-]+E[j].dis<f[now][k])f[now][k]=f[to][k-]+E[j].dis;
// for(j=0;j<=K;j++)printf(" %d %d: %lld\n",now,j,f[now][j]);
}
printf("%lld\n",f[][K]);
return ;
}
bzoj 1751： [Usaco2005 qua]Lake Counting
如题。。联通块计数。。注意是八连通= =
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
int map[maxn*maxn];
int xx[]={,,,,,-,-,-},yy[]={-,,,-,,-,,};
int fa[maxn*maxn];
int i,j,k,n,m,x,y,nowx,nowy,tmpx,tmpy,tmp,now,ans;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
int getfa(int x){
if(fa[x]!=x)fa[x]=getfa(fa[x]);
return fa[x];
}
int main(){
n=read();m=read();
for(i=;i<=n;i++)for(j=;j<=m;j++){
for(rx=getchar();rx!='.'&&rx!='W';rx=getchar());
map[(i-)*m+j]=(rx=='W')?:;
fa[(i-)*m+j]=(i-)*m+j;
}
for(i=;i<=n;i++)for(j=;j<=m;j++){
tmp=(i-)*m+j;
if(map[tmp]!=)continue;
for(k=;k<;k++){
nowx=i+xx[k];nowy=j+yy[k];
if(nowx<||nowy<||nowx>n||nowy>m)continue;
now=(nowx-)*m+nowy;
if(map[now]!=)continue;
x=getfa(tmp);y=getfa(now);
if(x!=y)fa[y]=x;
}
}
for(i=n*m;i;i--)if(map[i]==&&fa[i]==i)ans++;
printf("%d\n",ans);
return ;
}
bzoj 1914： [Usaco2010 OPen]Triangle Counting 数三角形
极角排序一下。。http://www.cnblogs.com/czllgzmzl/p/5071114.html
bzoj 1590： [Usaco2008 Dec]Secret Message 秘密信息
好久没写trie了。。。注意在trie树上得记录两个信息：在当前节点结束的信息数量；在当前节点还没结束的信息数量。。
每次查找的答案就是 路径上已经结束的数量+最后那个节点上还没结束的信息数量。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=;
int map[maxn][],len,tot,tmp;
int i,j,k,n,m,now,ans;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
int main(){
n=read();m=read();
for(i=;i<=n;map[now][]++,i++)
for(now=,len=read();len;len--){
for(rx=getchar();rx!=''&&rx!='';rx=getchar());tmp=rx-;
if(!map[now][tmp])map[now][tmp]=++tot,now=tot;else now=map[now][tmp];
if(len>)map[now][]++;
}
for(i=;i<=m;printf("%d\n",ans+map[now][]),i++)
for(now=ans=,len=read();len;len--){
for(rx=getchar();rx!=''&&rx!='';rx=getchar());tmp=rx-;
now=map[now][tmp];ans+=map[now][];
if(!now){while(--len)for(rx=getchar();rx!=''&&rx!='';rx=getchar());break;}
}
return ;
}
bzoj 1718： [Usaco2006 Jan] Redundant Paths 分离的路径
边双联通分量。。先把边双连通分量缩点，就变成如何使一棵树上两两节点间有多条路可走。。。答案就是（叶子节点数量+1）/2。
求边双连通分量时，记录一下当前点的父亲边，如果low[x]==dfn[x]，那么点x的父亲边就是桥。把桥都从原图中去掉，剩下的就是一坨边双联通分量了。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
struct zs{
int too,pre;
}e[];
int last[maxn],tot=;
bool isbridge[];
int dfn[maxn],low[maxn],tim;
int degree[maxn],bel[maxn],blocknum;
int i,j,k,n,m,a,b,ans; int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
void tarjan(int x,int preedge){
int i,to;dfn[x]=low[x]=++tim;
for(i=last[x],to=e[i].too;i;i=e[i].pre,to=e[i].too)if((i^)!=preedge)
if(!dfn[to])tarjan(to,i),low[x]=low[x]>low[to]?low[to]:low[x];
else low[x]=low[x]>dfn[to]?dfn[to]:low[x];
if(preedge&&low[x]==dfn[x])isbridge[preedge]=isbridge[preedge^]=;
}
inline void insert(int a,int b){
e[++tot].too=b;e[tot].pre=last[a];last[a]=tot;
e[++tot].too=a;e[tot].pre=last[b];last[b]=tot;
}
void rebuild(int x,int num){
bel[x]=num;
for(int i=last[x];i;i=e[i].pre)if(!isbridge[i]&&!bel[e[i].too])rebuild(e[i].too,num);
}
int main(){
n=read();m=read();
for(i=;i<=m;i++)a=read(),b=read(),insert(a,b);
for(i=;i<=n;i++)if(!dfn[i])tarjan(i,);
for(i=;i<=n;i++)if(!bel[i])rebuild(i,++blocknum);
for(i=;i<=tot;i+=)if(isbridge[i])degree[bel[e[i].too]]++,degree[bel[e[i^].too]]++;
for(i=;i<=blocknum;i++)if(degree[i]==)ans++;
printf("%d\n",(ans+)>>);
return ;
}
bzoj 1693： [Usaco2007 Demo]Asteroids
盯了半天英文题面。。。结果发现双倍经验。同bzoj1741。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
struct zs{
int too,pre;
bool flow;
}e[];
int last[maxn<<],u[maxn<<],dl[maxn<<];
short dis[maxn<<];
int i,j,k,n,m,tot,s,t,a,b,ans;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline void insert(int a,int b){
e[++tot].too=b;e[tot].flow=;e[tot].pre=last[a];last[a]=tot;
e[++tot].too=a;e[tot].flow=;e[tot].pre=last[b];last[b]=tot;
}
inline bool bfs(){
memset(dis,,(t+)<<);
int l=,r=,now,i;dl[]=s;dis[s]=;
while(l<r){
now=dl[++l];
for(i=last[now];i;i=e[i].pre)if(dis[e[i].too]==-&&e[i].flow)
dis[e[i].too]=dis[now]+,dl[++r]=e[i].too;
}
return dis[t]!=-;
}
int dfs(int x,int mx){
if(x==t)return mx;
int i,used=,w;
for(i=last[x];i;i=e[i].pre)if(e[i].flow&&dis[e[i].too]==dis[x]+){
w=dfs(e[i].too,);if(w){
e[i].flow=;;e[i^].flow=;
used++;if(used==mx)return mx;
}
}
dis[x]=-;return used;
}
int main(){tot=;
n=read();m=read();s=;t=n+n+;
for(i=;i<=n;i++)insert(s,i),insert(i+n,t);
for(i=;i<=m;i++)
a=read(),b=read(),insert(a,b+n);
while(bfs())ans+=dfs(s,);
printf("%d\n",ans);
return ;
}
bzoj 1716： [Usaco2006 Dec]The Fewest Coins 找零钱
搜题解的话应该连题目名字一起搜。。因为也是poj3260。
店家找钱一定不超过v_max^2。。。因为这就意味着John多给店主硬币超过了v_max个。。想要让这些硬币无法用v_max的硬币替代掉一部分，则它们不同组合的价值和对v_max取模后都各不相同。。。。总之根据抽屉原理这是不可能的。。。
所以对店家跑个无限背包，对john跑个有限背包就行了。
UPD：。。。。。。。。。。。。。。。。。。。论傻逼不好好想题就跑去看题解的危害性。
根据KPM代码可得。。店家找钱一定不超过v_max。。。其实这也是很显然的？（捂脸。。然而为何我想不到）。。找钱超过v_max肯定有硬币是脑残多给的啊。。。
不过更加不科学的是。。。我数组开大反而快了不少。。。。而且是多次试验确定不是测评姬看脸= =。。。。导演这和说好的不一样。。。
数组开2w+就#1了。。。开1w+就慢了快一倍TAT。。。感人肺腑
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=<<;
const int inf=;
struct zs{
int c,v;
}a[maxn];
int f[],owner[];
int c[],v[];
int i,j,k,n,m,ans,mx,N;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
bool cmp(zs a,zs b){
return a.v<b.v;
}
int main(){
n=read();m=read();
for(i=;i<=n;i++)v[i]=read(),mx=max(mx,v[i]);
for(i=;i<=n;i++)c[i]=read();
// mx*=mx;
for(i=;i<=n;i++){
for(j=;j<=c[i];j<<=)a[++N].c=j,a[N].v=j*v[i],c[i]-=j;
if(c[i])j=c[i],a[++N].c=j,a[N].v=j*v[i];
}
sort(a+,a++N,cmp);
while(N&&a[N].v>mx+m)N--;
// for(i=1;i<=N;i++)printf(" %d %d\n",a[i].c,a[i].v);
memset(owner,,(mx+)<<);
memset(f,,(mx++m)<<);owner[]=f[]=;
for(i=;i<=n;i++)for(j=v[i];j<=mx;j++)if(owner[j]>owner[j-v[i]]+)owner[j]=owner[j-v[i]]+;
// for(i=1;i<=20;i++)printf(" %d %d\n",i,owner[i]);
for(i=;i<=N;i++)for(j=mx+m;j>=a[i].v;j--)
if(f[j]>f[j-a[i].v]+a[i].c)f[j]=f[j-a[i].v]+a[i].c;
ans=inf;
for(j=mx+m;j>=m;j--)if(f[j]+owner[j-m]<ans)ans=f[j]+owner[j-m];
if(ans==inf)printf("-1\n");else printf("%d\n",ans);
return ;
}
bzoj 2199： [Usaco2011 Jan]奶牛议会
2-SAT问题。。。这类问题似乎没法怎么包装。。。对于每头奶牛，如果它的某票没实现的话，另一票一定要实现。。。
因为有的议案结局未定。。而且数据范围不大。。直接暴力上。。。时间复杂度O(nm)
不知道如果缩点后搞的话怎么处理那些未定的议案TAT
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
struct zs{
int too,pre;
}e[];
int last[maxn<<],a,b;
bool must[maxn<<];
int i,j,k,n,m,tot;
char ans[maxn];
int ra;char rx,x1,x2;
bool can0,can1;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline void insert(int a,int b){
e[++tot].too=b;e[tot].pre=last[a];last[a]=tot;
}
void dfs(int x){
must[x]=;if(must[x>n?x-n:x+n])return;
for(int i=last[x];i;i=e[i].pre)if(!must[e[i].too])dfs(e[i].too);
}
inline bool judge(int x){
memset(must,,(n+n+));
dfs(x);
for(int i=n;i;i--)if(must[i]&&must[i+n])return ;
return ;
}
int main(){
n=read();m=read();
for(i=;i<=m;i++){
a=read();for(x1=getchar();x1!='Y'&&x1!='N';x1=getchar());
if(x1=='N')a+=n;
b=read();for(x2=getchar();x2!='Y'&&x2!='N';x2=getchar());
if(x2=='N')b+=n;
insert(a>n?a-n:a+n,b);insert(b>n?b-n:b+n,a);
}
for(i=;i<=n;i++){
can0=judge(i);
can1=judge(i+n);
if(can0&&can1)ans[i]='?';
else if(can0)ans[i]='Y';
else if(can1)ans[i]='N';
else {puts("IMPOSSIBLE");return ;}
}
for(i=;i<=n;i++)putchar(ans[i]);printf("\n");
return ;
}
bzoj 1712： [Usaco2007 China]Summing Sums 加密
矩阵乘法。。。由题目得出，Ci'=sum-Ci，（sum表示前一轮中奶牛数字和）。本轮结束后sum'=sum*n-sum。
构造矩阵。。一个n行2列的矩阵A，第i行第一列为Ci，第二列为sum。
第二个矩阵B为2*2的矩阵，第一行为-1,0；第二行为1,(n-1)。
为啥卡了半天常数还是那么慢TAT
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
const ll modd=;
const int maxn=;
ll pow[][],b[][],a[maxn][];
int i,j,k,n,m,T;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline void mul1(ll a[][],ll b[][]){
ll c[][];int i,j,k;
for(i=;i<;i++)for(j=;j<;j++)
for(c[i][j]=,k=;k<;k++){c[i][j]+=a[i][k]*b[k][j];if(c[i][j]>=modd)c[i][j]%=modd;}
for(i=;i<;i++)for(j=;j<;j++)a[i][j]=c[i][j];
}
inline void mul2(ll a[maxn][],ll b[][]){
ll c[maxn][];i,j,k;
for(i=;i<n;i++)for(j=;j<;j++)
for(c[i][j]=,k=;k<;k++){c[i][j]+=a[i][k]*b[k][j];if(c[i][j]>=modd)c[i][j]%=modd;}
for(i=;i<n;i++)for(j=;j<;j++)a[i][j]=c[i][j];
}
int main(){
n=read();T=read();
for(i=;i<n;i++)a[i][]=read(),a[][]+=a[i][],a[][]-=a[][]>=modd?modd:;
for(i=;i<n;i++)a[i][]=a[][];
pow[][]=pow[][]=;
b[][]=-;b[][]=;b[][]=;b[][]=n-;
while(T){
if(T&)
mul1(pow,b);
T>>=;if(T)mul1(b,b);
}
mul2(a,pow);
for(i=;i<n;i++)printf("%lld\n",(a[i][]+modd)%modd);
return ;
}
bzoj 1583： [Usaco2009 Mar]Moon Mooing 哞哞叫
首先根据题目给出的式子，两种方式叫声时长都是递增的。。就变成了在两个递增的数列中取出前n小的。。
可以无脑的分别求出两种叫法的前n项再合并。。。。也可以只记录当前两种叫法分别叫到了多长时间，每次选下一次叫时间短的加入答案（因为可以当前项算出后一项时长）。
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=;
int i,j,k,n,m,l1,l2,r;
ll c,a1,a2,c1,c2,b1,b2;
ll now,tmp1,tmp2,dl[maxn];
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
int main(){
c=read();n=read();
a1=read();b1=read();c1=read();
a2=read();b2=read();c2=read();
l1=l2=;r=;dl[]=c;tmp1=c*a1/c1+b1;tmp2=c*a2/c2+b2;
while(r<n){
if(tmp1<tmp2){
if(tmp1!=dl[r])dl[++r]=tmp1;
tmp1=dl[++l1]*a1/c1+b1;
}else{
if(tmp2!=dl[r])dl[++r]=tmp2;
tmp2=dl[++l2]*a2/c2+b2;
}
}
printf("%lld\n",dl[r]);
return ;
}
bzoj 1731： [Usaco2005 dec]Layout 排队布局
差分约束。。http://www.cnblogs.com/czllgzmzl/p/5072819.html
bzoj 2099： [Usaco2010 Dec]Letter 恐吓信
字符串。因为原信件里同一段内容可以多次截取。。所以每次剪出最长公共前缀就可以使总的剪裁次数最小。
求出后缀数组后，每次二分找lcp。。。时间复杂度（nlogn+mlogn*比较字符串大小的时间复杂度）(实际复杂度远低于最坏情况。。。比较字符串大小可以直接暴力)
注意一下二分的左边界（取决于具体写法= =）
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll modd=;
const int maxn=;
int i,j,k,n,m,l,r,mid,now,pos,ans,samelen,L,R,MID;
ll pre[maxn],pre1[maxn],jc[maxn],val1,val2;
int sa[maxn];
char s[maxn],s1[maxn];
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline int getlen(int s1,int s2){
if(s[s1]!=s[s2])return ;
l=;r=n-(s1<s2?s2:s1)+;
val1=pre[s1+r-]-pre[s1-]*jc[r]%modd;if(val1<)val1+=modd;
val2=pre[s2+r-]-pre[s2-]*jc[r]%modd;if(val2<)val2+=modd;
if(val1==val2)return r;r--;
while(l<r){
mid=(l+r+)>>;
val1=pre[s1+mid-]-pre[s1-]*jc[mid]%modd;if(val1<)val1+=modd;
val2=pre[s2+mid-]-pre[s2-]*jc[mid]%modd;if(val2<)val2+=modd;
if(val1!=val2)r=mid-;else l=mid;
}
return l;
}
bool cmp(int a,int b){
now=getlen(a,b);
return s[a+now]<s[b+now];
}
inline int get1(int l1,int l2){
if(s[l1]!=s1[l2])return ;
l=;r=min(n-l1,m-l2)+;
val1=pre[l1+r-] -pre[l1-] *jc[r]%modd;if(val1<)val1+=modd;
val2=pre1[l2+r-]-pre1[l2-]*jc[r]%modd;if(val2<)val2+=modd;
if(val1==val2)return r;r--;
while(l<r){
mid=(l+r+)>>;
val1=pre[l1+mid-] -pre[l1-] *jc[mid]%modd;if(val1<)val1+=modd;
val2=pre1[l2+mid-]-pre1[l2-]*jc[mid]%modd;if(val2<)val2+=modd;
if(val1!=val2)r=mid-;else l=mid;
// printf("%d %d-%d %lld %d-%d %lld\n",mid,l1,l1+mid-1,val1,l2,l2+mid-1,val2);
}
return l;
}
inline bool bigger(int l1,int l2){
now=get1(l1,l2);
if(now>samelen)samelen=now;
// for(int i=l1;i<=n;i++)putchar(s[i]);putchar('|');for(int i=l2;i<=m;i++)putchar(s1[i]);printf(" %d\n",now);
return s[l1+now]>s1[l2+now];
}
int main(){
n=read();m=read();s[n+]=;s1[m+]=;
for(jc[]=,i=;i<=n;pre[i]=(pre[i-]*(ll)+(ll)s[i])%modd,jc[i]=jc[i-]*%modd,i++)for(s[i]=getchar();s[i]<'A'||s[i]>'Z';s[i]=getchar());
for(i=;i<=m;pre1[i]=(pre1[i-]*(ll)+(ll)s1[i])%modd,i++)for(s1[i]=getchar();s1[i]<'A'||s1[i]>'Z';s1[i]=getchar());
// for(i=1;i<=n;i++)printf("%lld ",pre[i]);printf("\n");
// for(i=1;i<=m;i++)printf("%lld ",pre1[i]);printf("\n"); for(i=;i<=n;i++)sa[i]=i;
sort(sa+,sa++n,cmp);
// for(i=1;i<=n;i++)printf("%d\n",sa[i]);
// for(i=1;i<=n;i++)printf(" %d\n",sa[i]);
for(pos=;pos<=m;now=samelen=){
L=;R=n;
while(L<=R){
MID=(L+R)>>;
if(bigger(sa[MID],pos))R=MID-;else L=MID+;
}
// for(i=sa[L];i<=n;i++)putchar(s[i]);printf("\n");
if(samelen<m-pos+&&L<n)samelen=max(samelen,get1(sa[L+],pos));
ans++;pos+=samelen;//printf(" %d\n",pos);
}
printf("%d\n",ans);
return ;
}
bzoj 1577： [Usaco2009 Feb]庙会捷运Fair Shuttle
把奶牛按目的地升序排序，然后直接依次尽量满足。。正确性同bzoj1828.。。。
具体用线段树实现（区间加&&查询区间最小值）
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=;
struct zs{
int t,s,num;
}a[];
int l[maxn<<],r[maxn<<],mn[maxn<<],mid[maxn<<],del[maxn<<];
int i,j,k,n,m,c,num,ans,tot;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
void build(int a,int b){
int now=++tot;mn[now]=c;
mid[now]=(a+b)>>;
if(a<b){
l[now]=tot+;build(a,mid[now]);
r[now]=tot+;build(mid[now]+,b);
}
}
inline void pushdown(int now,int l,int r){
del[l]+=del[now];del[r]+=del[now];
mn[l]-=del[now];mn[r]-=del[now];del[now]=;
}
void insert(int now,int a,int b,int c,int d,int num){
if(c<=a&&d>=b){del[now]+=num,mn[now]-=num;return;}
if(del[now])pushdown(now,l[now],r[now]);
if(c<=mid[now])insert(l[now],a,mid[now],c,d,num);
if(d>mid[now])insert(r[now],mid[now]+,b,c,d,num);
mn[now]=mn[l[now]]<mn[r[now]]?mn[l[now]]:mn[r[now]];
}
int query(int now,int a,int b,int c,int d){
if(c<=a&&d>=b)return mn[now];
if(del[now])pushdown(now,l[now],r[now]);
int tmp=;
if(c<=mid[now])tmp=query(l[now],a,mid[now],c,d);
if(d>mid[now])tmp=min(tmp,query(r[now],mid[now]+,b,c,d));
return tmp;
}
bool cmp(zs a,zs b){return a.t<b.t;}
int main(){
m=read();n=read();c=read();
for(i=;i<=m;i++)a[i].s=read(),a[i].t=read()-,a[i].num=read();
build(,n);
sort(a+,a++m,cmp);
for(i=;i<=m;i++)num=min(a[i].num,query(,,n,a[i].s,a[i].t)),insert(,,n,a[i].s,a[i].t,num),ans+=num;
printf("%d\n",ans);
return ;
}
bzoj 2274： [Usaco2011 Feb]Generic Cow Protests
dp优化。。f[i]表示划分前i个数的方案总数。。f[0]=1;f[i]=sum{ f[j] }，（j<i且presum[i]>=presum[j]）（presum表示前缀和）
所以把presum排序后，按原顺序算。。就是求排序后的前缀和。树状数组还是线段树什么的随意啦。。结果写的sgt比kpm的树状数组慢了三分之一= =
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
const int modd=;
int sum[maxn<<],rk[],pos[],pre[],a[],f[];
int i,j,k,n,m,x,size,tot;
int ra,fh;char rx;
inline int read(){
rx=getchar();ra=;fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')fh=-,rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
}
bool cmp(int aa,int b){return pre[aa]<pre[b];}
int main(){
n=read();
for(i=;i<=n;rk[i]=i,pre[i]=pre[i-]+a[i],i++)a[i]=read();
sort(rk+,rk++n,cmp);for(i=;i<=n;i++)tot+=(pre[rk[i]]!=pre[rk[i-]])||i==,pos[rk[i]]=tot;
size=;while(size<tot)size<<=;size--;
for(i=;i<=n;i++){
for(x=pos[i]+size,f[i]=sum[x]+(pre[i]>=);(x&(-x))!=x;x>>=)if(x&){f[i]+=sum[x^];if(f[i]>=modd)f[i]-=modd;}
for(x=pos[i]+size;x;x>>=){sum[x]+=f[i];if(sum[x]>=modd)sum[x]-=modd;}
}
printf("%d\n",f[n]);
return ;
}
bzoj 1594： [Usaco2008 Jan]猜数游戏
二分答案+并查集判定 http://www.cnblogs.com/czllgzmzl/p/5074066.html
bzoj 1744： [Usaco2005 oct]Skiing 奶牛滑雪
最短路。。看了kpm代码才发现倒着跑会方便一些。。速度的变化就好弄了。。就是把后面的路径（耗时）长度都乘上速度的变化。。。
假设初始速度为1，最后把时间除以真正的初始速度就好了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=;
int xx[]={,,,-},yy[]={,-,,};
int dlx[],dly[];
int map[][];
double tmpdis,v0,dis[][],nowdis;
double two[];
bool u[][];
int i,j,k,n,m,c,ans,l,r,x,y,nowx,nowy;
int ra,fh;char rx;
inline int read(){
rx=getchar();ra=;fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')fh=-,rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
}
inline double get(double x,int delta){
if(delta>=)return x*two[delta];
return x/two[-delta];
}
int main(){
for(two[]=1.0,i=;i<=;i++)two[i]=two[i-]*2.0;
double inf=<<;inf*=inf;
v0=read();n=read();m=read();
for(i=;i<=n;i++)for(j=;j<=m;j++)map[i][j]=read(),dis[i][j]=inf;
dis[n][m]=0.0;
dlx[]=n;dly[]=m;l=;r=;u[n][m]=;
while(l<r){
nowx=dlx[++l];nowy=dly[l];nowdis=dis[nowx][nowy];
for(i=;i<;i++){
x=nowx+xx[i];y=nowy+yy[i];
if(x<||x>n||y<||y>m)continue;
tmpdis=get(nowdis,map[nowx][nowy]-map[x][y])+1.0;
if(tmpdis<dis[x][y])
if(!u[x][y])dis[x][y]=tmpdis,dlx[++r]=x,dly[r]=y,u[x][y]=;
else dis[x][y]=tmpdis;
}
u[nowx][nowy]=;
}
printf("%.2lf\n",dis[][]/v0);
return ;
}
bzoj 1663： [Usaco2006 Open]赶集
最长路。。如果接完一个点的礼物后还来得及去另外的一个点接礼物，就在这两点间连条单向边。
因为出发时不一定要等点1的礼物，所以新建一个点0，与出发时能赶去接礼物的点连边 。最后答案就是最长路长度了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=;
struct zs{
int too,pre;
}e[];
int last[maxn],dis[maxn],dl[],tim[maxn];
int i,j,k,n,m,ans,l,r,tot,b,s,now,to;
bool u[maxn];
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline void insert(int a,int b){
e[++tot].too=b;e[tot].pre=last[a];last[a]=tot;
}
int main(){
n=read();
for(i=;i<=n;i++)tim[i]=read();
for(i=;i<=n;i++)for(j=;j<=n;j++){
b=read();
if(i!=j&&tim[j]-tim[i]>=b)insert(i,j);
if(i==&&tim[j]>=b)insert(,j);
}
s=;u[s]=;l=;r=;dl[]=s;dis[s]=;
while(l<r){
now=dl[++l];
for(i=last[now],to=e[i].too;i;i=e[i].pre,to=e[i].too)if(dis[to]<dis[now]+)
if(!u[to])u[to]=,dl[++r]=to,dis[to]=dis[now]+;
else dis[to]=dis[now]+;
u[now]=;
}
for(i=;i<=n;i++)if(dis[i]>ans)ans=dis[i];
printf("%d\n",ans);
return ;
}
bzoj 1735： [Usaco2005 jan]Muddy Fields 泥泞的牧场
二分图最大匹配。类似1741小行星那题。。不同的是多了个约束条件，木板只能在泥地里放。
先按行处理出各泥地的编号（同一行且联通的泥地算同个点），列的时候同理
对于每个泥泞的点，把它所在的行编号和所在的列编号这两点间连边。。最后求二分图最大匹配
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=**+;
struct zs{
int too,pre;
bool flow;
}e[];
int last[maxn],dis[maxn],s,t,tot=;
int dl[maxn];
int bell[][],belh[][],lnum,hnum;
int i,j,k,n,m,ans;
char map[][];
bool u[maxn];
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline bool bfs(){
int l=,r=,now,i;
memset(dis,,(t+)<<);dis[s]=;dl[]=s;
while(l<r){
now=dl[++l];
for(i=last[now];i;i=e[i].pre)if(dis[e[i].too]==-&&e[i].flow)
dl[++r]=e[i].too,dis[e[i].too]=dis[now]+;
}
return dis[t]!=-;
}
int dfs(int x,int mx){
if(x==t)return mx;
int used=,i,w,to;
for(i=last[x],to=e[i].too;i;i=e[i].pre,to=e[i].too)if(e[i].flow&&dis[to]==dis[x]+){
w=dfs(e[i].too,);if(w){
e[i].flow=;e[i^].flow=;
used++;
if(used==mx)return mx;
}
}
dis[x]=-;return used;
}
inline void insert(int a,int b){
e[++tot].too=b;e[tot].flow=;e[tot].pre=last[a];last[a]=tot;
e[++tot].too=a;e[tot].flow=;e[tot].pre=last[b];last[b]=tot;
}
int main(){
n=read();m=read();
for(i=;i<=n;i++)for(j=;j<=m;j++)for(map[i][j]=getchar();map[i][j]!='*'&&map[i][j]!='.';map[i][j]=getchar());
for(i=;i<=n;i++)
for(j=;j<=m;j++)if(map[i][j]=='*'){
if(map[i][j-]!='*')hnum++;
belh[i][j]=hnum;
}lnum=hnum;
for(j=;j<=m;j++)for(i=;i<=n;i++)if(map[i][j]=='*'){
if(map[i-][j]!='*')lnum++;
bell[i][j]=lnum;
}
for(i=;i<=n;i++)for(j=;j<=m;j++)if(map[i][j]=='*')insert(belh[i][j],bell[i][j]);
s=;t=lnum+;
for(i=;i<=hnum;i++)insert(s,i);for(i=hnum+;i<=lnum;i++)insert(i,t);
while(bfs())ans+=dfs(s,);
printf("%d\n",ans);
return ;
}
bzoj 2196： [Usaco2011 Mar]Brownie Slicing
二分答案+判定。。。。
JSZX11556：我随手写的怎么就#1了。。。。不过后来kpm压常抢了#1.。%%%
二分答案设为mid。。判定就是看是否能分出A段连续的行，每一段里面竖着分成B份，使得每一份都>=mid。划分的时候都贪心地试就行了。。。。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
int map[maxn][maxn],a[maxn];
int i,j,k,n,m,sum,A,B,l,r,mid;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline bool can(int h,int x){
register int i;int sum=,num=;
for(i=;i<=m;i++)a[i]+=map[h][i];
for(i=;i<=m&&sum<B;i++){
num+=a[i];
if(num>=x)num=,sum++;
}
return sum>=B;
}
inline bool judge(int x){
sum=;
memset(a,,(m+)<<);
for(i=;i<=n&&sum<A;i++)if(can(i,x))sum++,memset(a,,(m+)<<);
return sum>=A;
}
int main(){
n=read();m=read();A=read();B=read();
for(i=;i<=n;i++)for(j=;j<=m;j++)map[i][j]=read(),r+=map[i][j];
l=;r/=(A*B);
while(l<r){
mid=(l+r+)>>;
if(judge(mid))l=mid;else r=mid-;
}
printf("%d\n",l);
return ;
}
bzoj 2059： [Usaco2010 Nov]Buying Feed 购买饲料
数据范围是n<=500，k<=10000。。dp+单调队列优化
f[i][j]表示到第i个商店后，车上有j吨饲料的最小花费。
f[i][j]=min{ f[i-1][k]+dis(i-1,i)*k^2+cost[i]*(j-k) }，（k<=j，dis表示两点间距离，cost[i]表示商店i的饲料价格）
也就是f[i][j]=cost[i]*j + min{ f[i-1][k]+dis(i-1,i)*k^2-cost[i]*k }。后面那个就可以用单调队列优化了。。
偷懒调了优先队列。。多了个log果然慢成狗= =。。一开始脑残wa了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
const int maxn=;
const int maxk=;
ll f[maxk];
struct zs{
int k;ll val;
};
struct poi{
int pos,rest,cost;
}a[maxn];
int i,j;
ll n,m,K,ed; int ra,fh;char rx;
inline int read(){
rx=getchar();ra=;fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')rx=getchar(),fh=-;
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
} bool cmp(poi a,poi b){return a.pos<b.pos;}
bool operator <(zs a,zs b){
return a.val>b.val;
}
int main(){
K=read();ed=read();n=read();
for(i=;i<=n;i++)a[i].pos=read(),a[i].rest=read(),a[i].cost=read();
sort(a+,a++n,cmp);
memset(f,,(K+)<<);f[]=;
for(i=;i<=n;i++){
priority_queue<zs>q;
while(!q.empty())q.pop();
ll dis=a[i].pos-a[i-].pos;
q.push((zs){,});
for(j=;j<=K;j++){
q.push((zs){j,f[j]-(ll)j*a[i].cost+dis*j*j});
while(!q.empty()&&q.top().k<j-a[i].rest)q.pop();
f[j]=q.top().val+(ll)j*a[i].cost;
}
}
printf("%lld\n",f[K]+(ll)(ed-a[n].pos)*K*K);
return ;
}
bzoj 1777： [Usaco2010 Hol]rocks 石头木头
博弈论。。。求当前局面的sg值
如果不考虑每次取的数量的限制的话这题就是个阶梯nim（以深度为阶梯）。。。只考虑把石头从奇数深度挪到偶数深度。（根节点深度为0）
但是有L的限制。。对每个奇数深度的节点就变成俩人轮流取，一次最多取L个。。。sg值就是石头数量对（L+1）取模后的值。。。偶数深度的节点sg值为0.
把各个节点的sg值异或起来就是整个局面的sg值了（节点间互不影响）。修改操作的时候，就把总的sg值和 修改的节点原来的sg值 异或一下，在异或下新的sg值。
总的sg值为0的话先手必败。。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
struct zs{
int too,pre;
}e[];
int last[maxn],dep[maxn],tot;
int num[maxn];
int i,j,k,n,m,t,r,ans,a,b;
inline void insert(int a,int b){
e[++tot].too=b;e[tot].pre=last[a];last[a]=tot;
}
void dfs(int x,int depth){
dep[x]=depth;
for(int i=last[x];i;i=e[i].pre)dfs(e[i].too,depth^);
}
int ra,fh;char rx;
inline int read(){
rx=getchar();ra=;fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')rx=getchar(),fh=-;
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
}
inline int getsg(int x){
if(dep[x])return num[x]%(r+);
else return ;
}
int main(){
n=read();t=read();r=read();
for(i=;i<=n;i++)
a=read(),num[i]=read(),insert(a,i);
dfs(,);
t--;
a=read();b=read();num[a]=b;
for(i=;i<=n;i++)ans^=getsg(i);
printf("%s\n",ans?"Yes":"No");
while(t--){
a=read();b=read();
ans^=getsg(a);
num[a]=b;
ans^=getsg(a);
printf("%s\n",ans?"Yes":"No");
}
return ;
}
bzoj 1733： [Usaco2005 feb]Secret Milking Machine 神秘的挤奶机
二分答案为mid，s连1，n连t，把长度不超过mid的边加进新图中，容量为1，看新图中最大流是否>=T。
二分前可以先按边的长度离散化一下。。。反正最后的答案一定等于某条边的长度
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
struct zs{
int too,pre;
bool flow;
}e[];
int last[maxn],dis[maxn],cur[maxn],x[],y[],dist[],tmp[];
int dl[maxn];
int i,j,k,n,m,s,t,a,b,c,tot,T,mx,l,r,mid,ans;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline void insert(int a,int b){
e[++tot].too=b;e[tot].flow=;e[tot].pre=last[a];last[a]=tot;
e[++tot].too=a;e[tot].flow=;e[tot].pre=last[b];last[b]=tot;
}
inline bool bfs(){
memset(dis,,(t+)<<);
int to,l=,r=,i,now;dl[]=s;dis[s]=;
while(l<r){
now=dl[++l];
for(i=last[now],to=e[i].too;i;i=e[i].pre,to=e[i].too)if(e[i].flow&&dis[to]==-)
dis[to]=dis[now]+,dl[++r]=to;
}
return dis[t]!=-;
}
int dfs(int x,int mx){
if(x==t)return mx;
int used=,w;register int i,to;
for(i=cur[x],to=e[i].too;i;cur[x]=i,i=e[i].pre,to=e[i].too)if(e[i].flow&&dis[to]==dis[x]+){
w=dfs(to,);if(w){
e[i].flow=;e[i^].flow=;
used++;if(used==mx)return mx;
}
}
dis[x]=-;return used;
}
int main(){
n=read();m=read();T=read();s=;t=n;
for(i=;i<=m;i++)x[i]=read(),y[i]=read(),dist[i]=tmp[i]=read();
sort(tmp+,tmp++m);
l=;r=m;
while(l<r){
mid=(l+r)>>;
tot=;memset(last,,(t+)<<);
for(i=;i<=m;i++)if(dist[i]<=tmp[mid])insert(x[i],y[i]),insert(y[i],x[i]);
ans=;
while(bfs()&&ans<T)memcpy(cur,last,(t+)<<),ans+=dfs(s,);
if(ans>=T)r=mid;else l=mid+;
}
printf("%d\n",tmp[l]);
return ;
}
bzoj 1740: [Usaco2005 mar]Yogurt factory 奶酪工厂
傻逼题。。没错我是连傻逼题都不会写的傻逼。
记录一下到当前，单位奶酪的最小代价就好了。
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
int S,n;
int ra;char rx;
inline ll read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
int main(){
n=read();S=read();
register int now,i,low=;register ll ans=;
for(i=n;i;low+=S,i--){
now=read();if(now<low)low=now;
ans+=read()*low;
}
printf("%lld\n",ans);
return ;
}
bzoj 1742： [Usaco2005 nov]Grazing on the Run 边跑边吃草
区间dp（因为走到哪里吃到哪里。。吃了的范围肯定是一段区间）。中英文数据范围不一致= =其实数据范围只有n<=1000.。。
f[i][j][0]表示吃完[i,j]这段区间里的草后站在左端点（i点）的最少腐败值。f[i][1]表示吃完[i,j]后站在右端点的最少腐败值。dis(i,j)表示点i与点j间的距离
初始化f[i][i][0]=f[i][i][1]=dis(i,p)*n。
f[i][j][0]=min{ f[i+1][j][0]+dis(i,i+1)*( n-(j-i) )，f[i+1][j][1]+dis(i,j)*( n-(j-i) ) }...f[i][j][1]类似，就是从f[i][j-1][0..1]转移过来。。
行走距离乘上(n-(j-i))是因为走这段路时，会使还没吃的(n-(j-i))棵草的腐败值都加上所花的时间。
如果用f[i][j][0..1]表示吃了的区间长度为i，区间以j结尾，吃完站在左右端点的最小腐败值，就可以省掉一维= =
压了下常数然后#1了。。。。然而代码更丑了TAT。。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=;
int f[maxn][];
int len,s,mxj,n;
int a[maxn],b[maxn];
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
int main(){
int i,j,mxj,tmp;
n=read();s=read();
for(i=;i<=n;i++)a[i]=read();sort(a+,a++n);
for(i=;i<=n;b[i]=a[i+]-a[i],i++)f[i][]=f[i][]=abs(s-a[i])*n;
for(i=,mxj=n-;i<n;mxj--,i++)for(j=;j<=mxj;j++)
tmp=f[j][],f[j][]=min(f[j+][]+mxj*b[j],f[j+][]+mxj*(a[j+i]-a[j])),
f[j][]=min(tmp+mxj*(a[j+i]-a[j]),f[j][]+mxj*b[j+i-]);
printf("%d\n",min(f[][],f[][]));
return ;
}
bzoj 3126: [Usaco2013 Open]Photo
dp....先把区间按右端点排序。。设题目给出的区间为l[],r[]
f[i]表示点1~第i个区间的右端点 中可能的点的最大数目。。
f[i]=max{ f[j]+1 }，（不存在任意一段区间满足j<L[k]，R[k]<i，也不存在任意一段区间满足L[k]<=j，R[k]>=i）。。。。
所以可以预处理一下。。。不清楚如何用单调队列写TAT。。只好写个线段树了。。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=;
struct zs{
int l,r;
}a[maxn],b[maxn];
int minl[maxn],maxl[maxn],mp[maxn],f[maxn];
int mx[maxn<<];
int i,j,n,m,tmpl,top,tmp,ans,size;
bool can[maxn];
struct poi{
int pos,val;
};
priority_queue<poi>q;
bool operator <(poi a,poi b){return a.val<b.val;}
bool cmp1(zs a,zs b){return a.r<b.r;}
bool cmp2(zs a,zs b){return a.r>b.r;}
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline void update(int x,int val){
for(x+=size;x&&mx[x]<val;x>>=)mx[x]=val;
}
inline int getmax(int l,int r){
// printf(" %d--%d:",l,r);
l+=size;r+=size;int ans=max(mx[l],mx[r]);
if(l<=size){
if(r>=size)ans=max(ans,);
l=size+;
}
if(l>=r)return ans;
ans=max(ans,mx[l]);
// printf(" %d--%d:",l-size,r-size);
while((l^)!=r){
if((!(l&))&&mx[l^]>ans)ans=mx[l^];
if((r&)&&mx[r^]>ans)ans=mx[r^];
l>>=;r>>=;
}
// printf("%d\n",ans);
return ans;
}
int main(){
m=read();n=read();
for(i=;i<=n;i++)a[i].l=read(),a[i].r=read(),mp[a[i].l]++,mp[a[i].r+]--;
for(i=,tmp=;i<=m;i++)tmp+=mp[i],can[i]=(tmp>);
memcpy(b,a,(n+)<<);
sort(b+,b++n,cmp1);top=n;tmpl=m+;
for(i=m;i;i--){
while(top&&b[top].r>=i)tmpl=min(tmpl,b[top--].l);
minl[i]=min(i,tmpl);
if(!can[i])minl[i]=m+;
}tmpl=-;
for(i=top=;i<=m;i++){
while(top<=n&&b[top].r<i)tmpl=max(tmpl,b[top++].l);
maxl[i]=tmpl-;
if(!can[i])maxl[i]=-;
}
// for(i=1;i<=m;i++)printf(" %d %d\n",maxl[i]+1,minl[i]-1);
memset(f,,(m+)<<);f[]=;
for(size=;size<m;size<<=);size--;
memset(mx,,(size*+)<<);
for(i=;i<=m;i++){
if(maxl[i]+<minl[i])f[i]=getmax(maxl[i]+,minl[i]-)+,update(i,f[i]);//,printf(" %d %d\n",i,f[i]);
ans=max(ans,f[i]);
// printf(" %d %d\n",i,f[i]);
}
for(i=;i<=n;i++)if(getmax(b[i].l,b[i].r)<=){puts("-1");return ;}
printf("%d\n",ans);
return ;
}
bzoj 1722: [Usaco2006 Mar] Milk Team Select 产奶比赛
树形dp。。f[i][j][0]表示在以i为根的子树中（不取i），有j对血缘关系，产出牛奶的最大值。f[i][j][1]同理，但要取i。。
求f[i][j][0]的时候，就是对各个孩子跑一遍01背包= =
f[i][j][1]类似，但是注意血缘关系= =。。。。太蛋疼具体就不写了TAT
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
struct zs{
int too,pre;
}e[];
int last[maxn],tot;
int f[maxn][maxn][];//f[i][j][2]=max(f[i][j][0],f[i][j][1])...
int pre[maxn],size[maxn];
int val[maxn];
int i,j,k,n,m,x,a,sum;
int ra,fh;char rx;
inline int read(){
rx=getchar();ra=;fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')rx=getchar(),fh=-;
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
}
inline void insert(int a,int b){
e[++tot].too=b;e[tot].pre=last[a];last[a]=tot;
}
void dfs(int x){
int i,j,to,k,mx,k1;size[x]=;
memset(f[x],,sizeof(f[x]));
f[x][][]=;f[x][][]=val[x];f[x][][]=max(,val[x]);
for(i=last[x];i;i=e[i].pre)dfs(e[i].too),size[x]+=size[e[i].too];
if(size[x]==)return;
if(x!=)
for(i=last[x],to=e[i].too;i;i=e[i].pre,to=e[i].too){
mx=size[to];while(mx&&f[to][mx][]<=-)mx--;
for(j=;j<size[x];j++)pre[j]=f[x][j][];
for(j=size[x]-;j>=;j--){
for(k=;k<=mx;k++)f[x][j][]=max(f[x][j][],f[x][j-k][]+f[to][k][]);
if(pre[]+f[to][j][]>f[x][j][])f[x][j][]=pre[]+f[to][j][]; if(mx>=j)mx=j-;
for(k=,k1=j-k;k<=mx&&k<j;k++,k1--){
if(pre[k1]+f[to][k][]>f[x][j][])f[x][j][]=pre[k1]+f[to][k][];
if(pre[k1-]+f[to][k][]>f[x][j][])f[x][j][]=pre[k1-]+f[to][k][];
}
}
}else
for(i=last[x],to=e[i].too;i;i=e[i].pre,to=e[i].too)
for(j=n-;j>=;j--)for(k=;k<=j;k++)f[x][j][]=max(f[x][j][],f[x][j-k][]+f[to][k][]);
for(i=;i<n;i++)f[x][i][]=f[x][i][]>f[x][i][]?f[x][i][]:f[x][i][];
}
int main(){
n=read();x=read();
for(i=;i<=n;i++){
val[i]=read(),a=read(),insert(a,i);
if(val[i]>=)sum+=val[i];
}
if(sum<x){puts("-1");return ;}
dfs();
for(i=n-;f[][i][]<x;i--);
printf("%d\n",i);
return ;
}
bzoj 1779: [Usaco2010 Hol]Cowwar 奶牛战争
比较简单的最大流。。。四分图233。。每个点拆成四个点。。假设图画起来是四列，每列n个点的。。
1、第一列中John的奶牛与S相连；
2、第一列John的每头奶牛与第二列中的可达位置（原地或相邻，且没有Tom的牛）相连；
3、第二列中的每个可达位置与第三列中的自己连一条边。（一个点上只能站一只牛）
4、第三列每个位置与它第四列中相邻的（能攻击到的）、有Tom的牛的位置相连。最后第四列的Tom的牛连一条到T的边。。。
各边容量都为1。。。求出来的最大流就是答案。。。可以把图中一些没用的点去掉= =
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
struct zs{
int too,pre;
bool flow;
}e[];
struct edge{
int too,pre;
}E[];
int last[maxn],tot=,LAST[],TOT,ans;
int jim[],tom[],id[],cow[];
short dis[maxn];
int dl[maxn]; int s,t,i,j,a,b,n,m,to;
bool istom[];
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline void insert(int a,int b){
// printf(" %d-->%d\n",a,b);
e[++tot].too=b;e[tot].flow=;e[tot].pre=last[a];last[a]=tot;
e[++tot].too=a;e[tot].flow=;e[tot].pre=last[b];last[b]=tot;
}
inline void insmap(int a,int b){
E[++TOT].too=b;E[TOT].pre=LAST[a];LAST[a]=TOT;
E[++TOT].too=a;E[TOT].pre=LAST[b];LAST[b]=TOT;
}
inline bool bfs(){
int l=,r=,i,now;
memset(dis,,(t+)<<);
dl[]=s;dis[s]=;
while(l<r)
for(now=dl[++l],i=last[now];i;i=e[i].pre)
if(e[i].flow&&dis[e[i].too]==-)
dl[++r]=e[i].too,dis[e[i].too]=dis[now]+;
return dis[t]!=-;
}
int dfs(int x,int mx){
if(x==t)return mx;
int used=,i,to,w;dis[x]++;
for(i=last[x],to=e[i].too;i;i=e[i].pre,to=e[i].too)if(e[i].flow&&dis[to]==dis[x]){
w=dfs(to,);if(w){
e[i].flow=;e[i^].flow=;
used++;if(used==mx){dis[x]--;return mx;}
}
}
dis[x]=-;return used;
}
int main(){
n=read();m=read();s=;int numj=,numt=;
for(i=;i<=n;i++){
for(rx=getchar();rx!='T'&&rx!='E'&&rx!='J';rx=getchar());
if(rx=='J')insert(s,++numj),jim[i]=numj,cow[numj]=i;
else if(rx=='T')tom[i]=++numt,istom[i]=;
}int tmp=;
for(i=;i<=n;i++)if(!istom[i])id[i]=++tmp;
t=numj+(n-numt)*+numt+;
for(i=;i<=m;i++)a=read(),b=read(),insmap(a,b);
for(i=last[];i;i=e[i].pre){
to=cow[e[i].too];insert(jim[to],numj+id[to]);
for(j=LAST[to];j;j=E[j].pre)if(!istom[E[j].too])
insert(jim[to],numj+id[E[j].too]);
}
for(i=;i<=n;i++)if(!istom[i]){
insert(numj+id[i],numj+id[i]+(n-numt));
for(j=LAST[i];j;j=E[j].pre)if(istom[E[j].too])
insert(numj+id[i]+(n-numt),numj+(n-numt)*+tom[E[j].too]);
}else insert(numj+(n-numt)*+tom[i],t);
while(bfs())ans+=dfs(s,);
printf("%d\n",ans);
return ;
}
bzoj 1739： [Usaco2005 mar]Space Elevator 太空电梯
背包dp。。因为最大高度才4w。。。所以直接用f[i]表示能否堆到i这个高度。
把方块按最大高度升序排序，按顺序对每种方块i跑多重背包。。。似乎也可以sxbk把f数组换成bitset。。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
struct zs{
int mx,c,h;
}a[maxn];
bool f[];
int i,j,n,m,ans,k,nowc,nowh,nowmx;
int ra,fh;char rx;
inline int read(){
rx=getchar();ra=;fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')rx=getchar(),fh=-;
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
}
bool cmp(zs a,zs b){return a.mx<b.mx;}
int main(){
n=read();f[]=;
for(i=;i<=n;i++)a[i].h=read(),a[i].mx=read(),a[i].c=read(),ans=max(ans,a[i].mx);
sort(a+,a++n,cmp);
for(i=;i<=n;i++){nowc=a[i].c;nowh=a[i].h;nowmx=a[i].mx;
for(j=;j<=nowc;j++)
for(k=nowmx;k>=nowh;k--)f[k]|=f[k-nowh];
}
while(!f[ans]&&ans)ans--;
printf("%d\n",ans);
return ;
}
bzoj 2272： [Usaco2011 Feb]Cowlphabet 奶牛文字
dp。。。f[i][j][k]表示长度为(i+j)的单词中，有i个大写字母，j个小写字母，最后一个字母为k的方案数。
f[i][j][k]=sum{ f[i-1][j][k1] }，（存在词素(k1,k)，k为大写字母时）
或f[i][j][k]=sum{ f[i][j-1][k1] }，（存在词素(k1,k)，k为小写字母时）
大概是题目太水没人压常数嗯。。一开始卡常太sxbk连样例都过不了。。实在不敢调就重新写了个正常点的。。
取余的时候用减法，先把词素的俩字母连边就可以#1了= =
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
const int modd=;
int f[maxn][maxn][];
int mp[][],map[],num[];
bool used[];
char x1,x2;int tmp1,tmp2,tot,upnum,lownum,tmp,to,ans;
int i,j,k,n,m,l,p,u;
bool up,low;
int main(){
scanf("%d%d%d",&u,&l,&p);
for(i=;i<=p;i++){
for(x1=getchar();!isupper(x1)&&!islower(x1);x1=getchar());
for(x2=getchar();!isupper(x2)&&!islower(x2);x2=getchar());
if(x1>='a')tmp1=x1-'a'+;else tmp1=x1-'A';
if(x2>='a')tmp2=x2-'a'+;else tmp2=x2-'A';
if(!used[tmp1])map[++map[]]=tmp1,used[tmp1]=;
if(!used[tmp2])map[++map[]]=tmp2,used[tmp2]=;
mp[tmp1][++num[tmp1]]=tmp2;
}
sort(map+,map++map[]);for(i=;i<=map[];i++)if(map[i]>=)break;upnum=i-;
for(i=;i<=upnum;i++)f[][][map[i]]=;for(i=upnum+;i<=map[];i++)f[][][map[i]]=;
// for(i=1;i<=upnum;i++)printf("%d ",map[i]);printf("\n");
// for(i=upnum+1;i<=map[0];i++)printf("%d ",map[i]);printf("\n");
for(i=;i<=u;i++)for(j=;j<=l;j++)if(i+j>=){
up=i>;low=j>;
if(up)for(tmp=,k=map[];tmp<=upnum;f[i][j][k]=ans,ans=,k=map[++tmp])
for(tmp1=,to=mp[k][tmp1];tmp1<=num[k];to=mp[k][++tmp1])
ans+=f[i-][j][to],ans-=ans>=modd?modd:;
if(low)for(tmp=upnum+,k=map[tmp];tmp<=map[];f[i][j][k]=ans,ans=,k=map[++tmp])
for(tmp1=,to=mp[k][tmp1];tmp1<=num[k];to=mp[k][++tmp1])
ans+=f[i][j-][to],ans-=ans>=modd?modd:;
}
for(i=;i<;i++)ans+=f[u][l][i],ans-=ans>=modd?modd:;
printf("%d\n",ans);
return ;
}
bzoj 1752： [Usaco2005 qua]Til the Cows Come Home
为何一道最短路的AC人数和AC率这么低= =
为何我spfa调优先队列和普通版的一样慢TAT
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=;
struct zs{
int too,pre,dis;
}e[];
struct poi{
int pos,dis;
};
int i,j,n,m,a,b,tot,c,size;
int last[maxn],dis[maxn];
bool used[maxn];
priority_queue<poi>q;
inline void insert(int a,int b,int c){
e[++tot].too=b;e[tot].dis=c;e[tot].pre=last[a];last[a]=tot;
e[++tot].too=a;e[tot].dis=c;e[tot].pre=last[b];last[b]=tot;
}
bool operator <(poi a,poi b){return a.dis>b.dis;}
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
int main(){
m=read();n=read();memset(dis,,(n+)<<);
for(i=;i<=m;i++)a=read(),b=read(),c=read(),insert(a,b,c);
dis[n]=;size=;q.push((poi){n,});int pos,dist,to;
while(size&&!used[]){
while(size&&used[q.top().pos])q.pop(),size--;
pos=q.top().pos;dist=q.top().dis;used[pos]=;if(pos==)break;
for(i=last[pos],to=e[i].too;i;i=e[i].pre,to=e[i].too)if(dis[to]>dist+e[i].dis)
dis[to]=dist+e[i].dis,q.push((poi){to,dis[to]}),size++;
}
printf("%d\n",dis[]);
return ;
}
bzoj 1738： [Usaco2005 mar]Ombrophobic Bovines 发抖的牛
一开始看成总时间最小以为是费用流。。。结果发现是二分答案+最大流判定
先用floyd把两两之间的最短路求出来，然后二分答案为mid，
建个二分图，S连每个点x，容量为开始前牛的数量，x'连T，容量为雨棚容量。两个点间的最短路径长如果<=mid的话就在新图中加条边，容量无穷。
检验新图中最大流是否为牛的总数。
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=;
struct zs{
int too,pre,flow;
}e[];
int last[maxn],dis[maxn],dl[maxn],num[maxn],mx[maxn];
ll map[][];
int i,j,k,n,m,a,b,c,s,t,sumnum,summx,tot;
ll l,r,mid;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline bool bfs(){
int l=,r=,i,now;
memset(dis,,(t+)<<);dl[]=s;dis[s]=;
while(l<r){
now=dl[++l];
for(i=last[now];i;i=e[i].pre)if(e[i].flow&&dis[e[i].too]==-)
dl[++r]=e[i].too,dis[e[i].too]=dis[now]+;
}
return dis[t]!=-;
}
int dfs(int x,int mx){
if(x==t)return mx;
int i,used=,w,to;
for(i=last[x],to=e[i].too;i;i=e[i].pre,to=e[i].too)if(e[i].flow&&dis[to]==dis[x]+){
w=dfs(to,min(mx-used,e[i].flow));if(w){
e[i].flow-=w;e[i^].flow+=w;
used+=w;if(used==mx)return mx;
}
}
dis[x]=-;return used;
}
inline void insert(int a,int b,int c){
// printf("%d-->%d:%d\n",a,b,c);
e[++tot].too=b;e[tot].flow=c;e[tot].pre=last[a];last[a]=tot;
e[++tot].too=a;e[tot].flow=;e[tot].pre=last[b];last[b]=tot;
}
inline bool can(ll x){
int i,j;//printf("! %lld\n",x);
for(i=;i<=n;i++)insert(s,i,num[i]),insert(i+n,t,mx[i]);
for(i=;i<=n;i++)for(j=;j<=n;j++)if(map[i][j]<=x)insert(i,j+n,);
int ans=;
while(bfs())ans+=dfs(s,);
return ans==sumnum;
}
int main(){
n=read();m=read();
for(i=;i<=n;i++)memset(map[i],,(n+)<<);
for(i=;i<=n;i++)num[i]=read(),mx[i]=read(),map[i][i]=,summx+=mx[i],sumnum+=num[i];
if(summx<sumnum){puts("-1");return ;}
for(i=;i<=m;i++){
a=read();b=read();c=read();
if(c<map[a][b])map[a][b]=map[b][a]=c;
}
for(k=;k<=n;k++)for(i=;i<=n;i++)for(j=;j<=n;j++)if(map[i][k]+map[k][j]<map[i][j])map[i][j]=map[i][k]+map[k][j]; for(i=;i<=n;i++)for(j=;j<=n;j++)if(map[i][j]<map[][]&&map[i][j]>r)r=map[i][j];ll mxl=r;
l=;r++;s=;t=n+n+;tot=;
while(l<r){
mid=(l+r)>>;
if(can(mid))r=mid;else l=mid+;
if(l<r)memset(last,,(t+)<<),tot=;
}
printf("%lld\n",l<=mxl?l:-);
return ;
}
bzoj 1986： [USACO2004 Dec] Dividing the Path 划区灌溉
dp+单调队列优化。。f[i]表示灌溉了1~i（全体右移一位从1开始。。）的最小喷灌器总数。设各草区左右端点为l[],r[]
f[i]=min{ f[j] }+1，（1、i和j为偶数，2*A<=i-j<=2*B；2、不存在k,使l[k]<=j，r[k]>j）
第二个转移条件也就是i和j都不存在于任意[ l[i],r[i]-1 ]中。
调个优先队列就行了。。每次算f[i]前把f[i-A*2]入队。时间复杂度O(n)
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=;
int dl[maxn],f[maxn];
int map[maxn];
int i,j,n,m,len,a,b,l,r,A,B,now;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
int main(){
n=read();len=read();A=read();B=read();
memset(f,,(min(len,A*)+)<<);
for(i=;i<=n;i++)
a=read(),b=read(),map[min(a+,b)]++,map[b]--;
int inf=;
l=;r=;
f[]=;
a=A*-B*;b=;for(i=;i<A*;i++)now+=map[i];
for(i=A<<;i<=len;i+=,a+=,b+=){
while(l<=r&&f[dl[r]]>=f[b])r--;dl[++r]=b;if(f[dl[r]]>=inf)r--;
now+=map[i]+map[i-];if(now){f[i]=inf;continue;}
while(l<=r&&dl[l]<a)l++;
f[i]=(l<=r&&f[dl[l]]<inf)?(f[dl[l]]+):inf;
}
printf("%d\n",f[len]<inf?f[len]:-);
return ;
}
bzoj 1605： [Usaco2008 Open]Crisis on the Farm 牧场危机
DP。。先预处理出val[i][j]，表示使各牛群横纵坐标分别增加了i和j后能救几头牛（只算最后一次吹哨救的）。。
f[i][j][k]表示吹了k次哨子，使各牛群横纵坐标分别增加了i和j能救的最多奶牛数。
f[i][j][k]=max{ f[i1][j1][k-1] }+val[i][j]。（点(i1,j1)与点(i,j)相邻）。
觉得直接dp的话冗余状态略蛋疼就借（chao）鉴（xi）题解代码写了记忆化搜索= =输出方案的话记录下f[i][j][k]是从哪里转移来的
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=;
const int maxstep=;
const int xx[]={,,,,-},yy[]={,,,-,};
int next[maxn][maxn][maxstep],f[maxn][maxn][maxstep],val[maxn][maxn];
int x[],y[],gx[],gy[];
int i,j,k,n,m,a,b,deltax,deltay;
char map[]={,'E','N','S','W'};
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
//f[i][j][k]表示横纵坐标增加了i和j，剩k次吹哨机会时的最大值。
int dfs(int dx,int dy,int rest){
if(rest<=)return val[dx][dy];
if(next[dx][dy][rest])return f[dx][dy][rest];
next[dx][dy][rest]=;f[dx][dy][rest]=dfs(dx+xx[],dy+yy[],rest-);
for(int i=;i<=;i++)
if(dfs(dx+xx[i],dy+yy[i],rest-)>f[dx][dy][rest])
f[dx][dy][rest]=dfs(dx+xx[i],dy+yy[i],rest-),next[dx][dy][rest]=i;
f[dx][dy][rest]+=val[dx][dy];//printf("%d %d %d %d %d\n",dx,dy,rest,f[dx][dy][rest],next[dx][dy][rest]);
return f[dx][dy][rest];
}
int main(){
n=read();m=read();k=read();
for(i=;i<=n;i++)x[i]=read(),y[i]=read();
for(i=;i<=m;i++){
a=read();b=read();
for(j=,deltax=abs(x[j]-a),deltay=abs(y[j]-b);j<=n;deltax=abs(x[++j]-a),deltay=abs(y[j]-b))
if(deltax+deltay<=k)val[a-x[j]+][b-y[j]+]++;
}
printf("%d\n",dfs(,,k)-val[][]);
int nowx=,nowy=;
for(;k;k--){
putchar(map[next[nowx][nowy][k]]);
if(next[nowx][nowy][k]<||next[nowx][nowy][k]>)nowx+=xx[next[nowx][nowy][k]];else nowy+=yy[next[nowx][nowy][k]];
}
putchar('\n');
return ;
}
bzoj usaco 金组水题题解（2）的更多相关文章
-
bzoj usaco 金组水题题解（1）
UPD:我真不是想骗访问量TAT..一开始没注意总长度写着写着网页崩了王仓(其实中午的时候就时常开始卡了= =)....损失了2h(幸好长一点的都单独开了一篇)....吓得赶紧分成两坨....TAT. ...
-
bzoj usaco 金组水题题解（2.5）
bzoj 2197: [Usaco2011 Mar]Tree Decoration 树形dp..f[i]表示处理完以i为根的子树的最小时间. 因为一个点上可以挂无数个,所以在点i上挂东西的单位花费就是 ...
-
BZOJ USACO 银组 水题集锦
最近刷银组刷得好欢快，好像都是水题，在这里吧他们都记录一下吧（都是水题大家一定是道道都虐的把= =）几道比较神奇的题到时再列出来单独讲一下吧= =（其实我会说是BZOJ蹦了无聊再来写的么 = =） [ ...
-
NOIP2018初赛普及组原题&;题解
NOIP2018初赛普及组原题&题解 目录 NOIP2018初赛普及组原题&题解 原题&答案 题解 单项选择题 第$1$题 第$2$题 第$3$题 第$4$题 第$5$题 第$ ...
-
World Finals 2017 (水题题解)
看大佬做2017-WF,我这种菜鸡,只能刷刷水题,勉强维持生活. 赛后补补水题. 题目pdf链接,中文的,tls翻译的,链接在这里 个人喜欢在vjudge上面刷题. E Need for Speed ...
-
noip2008普及组3题题解-rLq
(第一次写题解,随意喷) (只是前一天的作业哈) (先凑个数) 题目描述 上体育课的时候,小蛮的老师经常带着同学们一起做游戏.这次,老师带着同学们一起做传球游戏.游戏规则是这样的:n个同学站成一个圆圈 ...
-
2006-2007 ACM-ICPC | POJ3380 POJ3384 POJ3385 水题题解
// CF比赛链接:http://codeforces.com/gym/101650 // POJ链接:http://poj.org/searchproblem?field=source&ke ...
-
noip2008普及组4题题解-rLq
(啊啊啊终于补到了今天的作业了) 本题地址:http://www.luogu.org/problem/show?pid=1058 题目描述 小渊是个聪明的孩子,他经常会给周围的小朋友们将写自己认为有趣 ...
-
Cmd2001的毒瘤水题题解
怕不是我再不写题解这题就该成没人做也没人会的千古谜题了...... T1: 仔细分析题面,发现相同就是广义SAM上节点相同,相似就是广义SAM上为从根到某个点路径的前缀..直接SAM上跑从根开始,每个 ...
随机推荐
-
不要遍历dom
function selectProvince() { $.ajax( { type: "post", url: "/province/getStrType", ...
-
IOS监听屏幕状态
一.定义两个宏 //锁屏通知 #define NotificationOff CFSTR("com.apple.springboard.lockcomplete") //解 ...
-
sublimetext 使用正则表达式匹配中文
[\x{4e00}-\x{9fa5}] ============================================= 参考资料 1.在javascript下正确的\x4e00-\x9fa ...
-
YII 框架使用之——创建应用
linux环境为UBUNTU14.04,YII框架的版本是1.1.17 将下载的YII解压缩,压缩后会有三个文件夹,”demos,requirements,framework”,demos 当然就是演 ...
-
CentOS6.9-zabbix3.2启动失败原因及页面没有mysql选择项
环境内核信息: [root@zabbix- ~]# uname -a Linux lodboyedu- -.el6.x86_64 # SMP Tue Mar :: UTC x86_64 x86_64 ...
-
支持向量机-完整Platt-SMO算法加速优化
完整版SMO算法与简单的SMO算法: 实现alpha的更改和代数运算的优化环节一模一样,唯一的不同就是选择alpha的方式.完整版应用了一些能够提速的方法. 同样使用Jupyter实现,后面不在赘述 ...
-
WDA-BOPF业务对象处理框架
SAP中的BOPF(Business Object Processing Framework) 正文 希望简化你的业务应用开发过程?业务对象处理框架(Business Object Processin ...
-
c# 异步和同步问题（转载）
[C#] 谈谈异步编程async await 为什么需要异步,异步对可能起阻止作用的活动(例如,应用程序访问 Web 时)至关重要. 对 Web 资源的访问有时很慢或会延迟. 如果此类活动在同步过 ...
-
typedef struct bit0 : 1
这句话定义了一个位域,bit0是该位域的域名,而且bit0只占用一个位.位域是指信息在存储时,并不需要占用一个完整的字节, 而只需占几个或一个二进制位.为了节省存储空间,并使处理简便,C语言提供了一种 ...
-
软件工程：java实现wordcount基本功能
github链接:https://github.com/Nancy0611/wc 一:项目相关要求 该项目能统计文本文件的字符数.单词数和行数.这个项目要求写一个命令行程序,模仿已有wc.exe 的功 ...