UPD:我真不是想骗访问量TAT。。一开始没注意总长度写着写着网页崩了王仓（其实中午的时候就时常开始卡了= =）。。。。损失了2h(幸好长一点的都单独开了一篇)。。。。吓得赶紧分成两坨。。。。TAT。。。。。。。。。。。。。。
——————————————————————————————————————————————————————————————————————————————
写（被虐）了整整一个月b站上usaco的金组题。。。然而到现在总共只写了100道上下TAT（当然是按AC人数降序排列的了）（另外，是用云神的号写的= =毕竟三百大洋）
大概不到1\3是自己写的，一半是有大概方向后跑去看题解，剩下的就是毫无思路就去看题解作死的了= =
感觉金组题还是比较适合自己当前水平的QAQ。。。所以大致的写下题解加深下印象吧。。。对于比较经典而自己又不熟的题打算专门另写题解（瞬间就挖了一个大坑）
这里贴出50道。。。
bzoj 1597:[Usaco2008 Mar]土地购买
斜率优化入门题。f[i]表示买前i块土地的最小费用
f[i]=min{
f[j]+max_w(j+1,i)*max_l(j+1,i)，（ 0<=j<i ）
}// max_w(j+1,i)和max_l(j+1,i)分别表示第j+1块土地到第i块土地中宽度和长度的最大值
首先去掉那些被别的土地完全覆盖的土地（因为不会对答案有任何影响），剩下的按宽度排序。宽度升序排序的话，长度一定是降序的（被完全覆盖的都被去掉了）
方程就变成 f[i]=min{ f[j]+wid[i]*len[j+1] }，（0<=j<i）
剩下的就是斜率优化了。。。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define d double
#define ll long long
using namespace std;
const int maxn=;
struct zs{
int x,y;
}a[maxn];
bool cant[maxn];
ll f[maxn];
int l,r,dl[maxn];
int i,j,k,n,m;
char rx;int ra; bool cmp(zs a,zs b){return a.x<b.x||(a.x==b.x&&a.y>b.y);
}
bool smaller(int aa,int b,int c){
return (ll)(f[c]-f[b])*(ll)(a[aa+].y-a[b+].y) <= (ll)(f[b]-f[aa])*(ll)(a[b+].y-a[c+].y);
/*return (d)(f[i]-f[dlr])/(d)(a[dlr+1].y-a[i+1].y)
<
(d)(f[dlr]-f[pre])/(d)(a[pre+1].y-a[dlr+1].y);*/
}
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();
for(i=;i<=n;i++)a[i].x=read(),a[i].y=read();
sort(a+,a++n,cmp);int tmp=a[n].y;
for(i=n-;i;i--)
if(a[i].y<=tmp)cant[i]=;else tmp=a[i].y; tmp=;
for(i=;i<=n;i++)if(!cant[i])a[++tmp].x=a[i].x,a[tmp].y=a[i].y; n=tmp;
for(i=;i<=n;i++){
while(l<r&& (ll)(f[dl[l+]]-f[dl[l]]) < (ll)a[i].x*(ll)(a[dl[l]+].y-a[dl[l+]+].y) )l++;
f[i]=f[dl[l]]+(ll)a[i].x*a[dl[l]+].y;
while(l<r&& smaller(dl[r-],dl[r],i))r--;dl[++r]=i;
}
printf("%lld\n",f[n]);
return ;
}
bzoj 1699：[Usaco2007 Jan]Balanced Lineup排队
rmq裸题。。。因为不涉及区间修改的操作所以可以用线段树的点树写法（建成一个堆）来写。。。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=;
int mx[maxn<<],mn[maxn<<],a[maxn];
int i,j,k,n,m,len,L,R,ansmax,ansmin;
char s[];
inline void outx(int x){//len=0;
while(x||!len)s[len++]=x%,x/=;
while(len)len--,putchar(s[len]+'');putchar('\n');
}
inline void inx(int &x){
int ch;x=;
for(ch=getchar();ch<''||ch>'';ch=getchar());
for(;ch>=''&&ch<='';x=x*+ch-'',ch=getchar());;
}
int main(){
scanf("%d%d",&n,&m);int dep=;
while(<<dep<n)dep++;int stnum=(<<dep)-;dep++;
for(i=;i<=n;i++)inx(a[i]),mx[stnum+i]=mn[stnum+i]=a[i];
for(i=stnum;i;i--){
if(mx[i<<]>mx[(i<<)|])mx[i]=mx[i<<];else mx[i]=mx[(i<<)|];
if(mn[i<<]<mn[(i<<)|])mn[i]=mn[i<<];else mn[i]=mn[(i<<)|];
}
for(i=;i<=m;i++){
inx(L);inx(R);ansmax=max(a[L],a[R]);ansmin=min(a[L],a[R]);
L+=stnum;R+=stnum;if(L==R)outx();else{
for(;(L^R)!=;L>>=,R>>=){
if(R&){if(mx[R^]>ansmax)ansmax=mx[R^];if(mn[R^]<ansmin)ansmin=mn[R^];}
if(!(L&)){if(mx[L^]>ansmax)ansmax=mx[L^];if(mn[L^]<ansmin)ansmin=mn[L^];}
};outx(ansmax-ansmin);} }
return ;
}
bzoj 1230：[Usaco2008 Nov]lites 开关灯
线段树区间修改。。。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
int num[][maxn<<],a[maxn<<],b[maxn<<],l[maxn<<],r[maxn<<],mid[maxn<<];
bool rev[maxn<<];
int i,j,k,n,m,L,R,id,tot; char rx;int ra;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline void pushdown(int now,int l,int r){
rev[l]^=;rev[r]^=;
swap(num[][l],num[][l]);swap(num[][r],num[][r]);
rev[now]=;
}
void change(int now,int a,int b){
if(L<=a&&R>=b){rev[now]^=;swap(num[][now],num[][now]);return;}
if(rev[now])pushdown(now,l[now],r[now]);
if(L<=mid[now])change(l[now],a,mid[now]);
if(R>mid[now])change(r[now],mid[now]+,b);
num[][now]=num[][l[now]]+num[][r[now]];
num[][now]=num[][l[now]]+num[][r[now]];
}
int query(int now,int a,int b){
if(L<=a&&R>=b)
return num[][now];
if(rev[now])pushdown(now,l[now],r[now]);
if(R<=mid[now])return query(l[now],a,mid[now]);
else if(L>mid[now])return query(r[now],mid[now]+,b);
else return query(l[now],a,mid[now])+query(r[now],mid[now]+,b);
}
void build(int a,int b){
int now=++tot;
num[][now]=b-a+;mid[now]=(a+b)>>;
if(a<b){
l[now]=tot+;
build(a,mid[now]);r[now]=tot+;
build(mid[now]+,b);
}
}
int main(){
n=read();m=read();
build(,n);
for(i=;i<=m;i++){
id=read();L=read();R=read();
if(id)printf("%d\n",query(,,n));else change(,,n);
}
return ;
}
bzoj 1666：[Usaco2006 Oct]Another Cow Number Game 奶牛的数字游戏
代码长度知一切系列。。直接模拟即可
#include<cstdio>
int n,ans;
int main(){
for(scanf("%d",&n);n>;ans++)if(n&)n=n*+;else n>>=;printf("%d\n",ans);
}
bzoj 1724：[Usaco2006 Nov]Fence Repair 切割木板
反过来看就是合并果子。。维护小根堆，每次把最短的两段木板并起来，直到变成一段
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#define ll long long
using namespace std;
priority_queue <ll>q;
int i,j,k,n,m;
ll ans,tmp; char rx;int ra;
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();
for(i=;i<=n;i++)m=read(),q.push(-m);
for(i=;i<n;i++){
tmp=q.top();q.pop();tmp+=q.top();q.pop();
ans-=tmp;q.push(tmp);
}
printf("%lld\n",ans);
return ;
}
bzoj 1726：[Usaco2006 Nov]Roadblocks第二短路
求严格次短路。。。最短路改一下。。同时记录到达某个点的最短距离和严格次短距离
为了压常数把本来的代码长度改长了不少（反正本来也就毫无可读性= =）。。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
const int maxm=;
int dis[][maxn],last[maxn];
struct zs{
int too,dis;
int pre;
}e[maxm<<];
short dl[];
bool u[maxn];
int i,j,k,n,m,a,b,c,tot; inline void insert(short a,short b,short 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;
}
char rx;int ra;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
void spfa(){
int l=,r=,now,i,a,b;
for(i=;i<;i++)memset(dis[i],,(n+)*);
dl[]=;u[]=;dis[][]=;short j;
while(l<r){
now=dl[++l];u[now]=;
if(dis[][now]<dis[][n])
for(i=last[now],j=e[i].too,a=dis[][now]+e[i].dis,b=dis[][now]+e[i].dis;i;i=e[i].pre,j=e[i].too,a=dis[][now]+e[i].dis,b=dis[][now]+e[i].dis)
if(dis[][j]>a){
if(dis[][j]<b)dis[][j]=dis[][j];else dis[][j]=b;
dis[][j]=a;
if(!u[j])u[j]=,dl[++r]=j;
}else if(dis[][j]<a)
if(a<dis[][j]){
dis[][j]=a;
if(!u[j])u[j]=,dl[++r]=j;
}else;
else if(dis[][j]==a&&b<dis[][j]){
dis[][j]=b;
if(!u[j])u[j]=,dl[++r]=j;
}
}
}
int main(){
n=read();m=read();
for(i=;i<=m;i++)a=read(),b=read(),c=read(),insert(a,b,c);
spfa();
printf("%d\n",dis[][n]);
return ;
}
bzoj 1231：[Usaco2008 Nov]mixup2 混乱的奶牛
题目是要求能使排列混乱的方案数。语死早。。数据范围显然状压。。
f[i][j]表示当前已选入列奶牛的状态为i，最后一头牛编号为j的混乱方案数，(0<i<2^n，1<=j<=n)
f[0][0]=1;f[i][j]=sum{f[i-2^j][k]}，（S[k]-S[j]的绝对值>K，j存在于状态i中）
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=;
ll f[][(<<maxn)+],ans;
int pos[(<<maxn)+];
int two[];
short a[];
int x,y,x1,yy,j,K;
int mx;
int i,k,n;
bool can[][];
int main(){
scanf("%d%d",&n,&K);for(i=;i<=n;i++)scanf("%d",&a[i]);
f[][]=;mx=<<n;
for(i=;i<n;i++)for(j=i+;j<=n;j++)if(max(a[i]-a[j],a[j]-a[i])>K)can[i-][j-]=can[j-][i-]=;
for(i=;i<=n;i++)two[i]=<<(i-),pos[two[i]]=i-,f[i-][two[i]]=;
for(j=;j<=mx&&j>;j++)
for(x=j,y=x&(-x),i=pos[y];x;x-=y,y=x&(-x),i=pos[y])
for(x1=j,yy=x1&(-x1),k=pos[yy];x1;x1-=yy,yy=x1&(-x1),k=pos[yy])if(i!=k&&can[i][k])
f[k][j]+=f[i][j^yy];
for(i=;i<n;i++)ans+=f[i][mx-];
printf("%lld\n",ans);
return ;
}
bzoj 1572: [Usaco2009 Open]工作安排Job
按截止时间降序排序。也就是时间从大到小枚举，每个时间点安排价值最大、且截止时间在当前时间点之前的工作
具体实现就不能一个一个时间点枚举了。。在相邻工作的截止时间之间的时间点，可以完成的工作都是不变的
单调队列优化一下。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
const int maxn=;
struct zs{
int tim,val;
}a[maxn];
priority_queue<int>q;
int i,j,k,n,m,top;
ll ans;
int ra,size;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.tim<b.tim;
}
int main(){
n=read();
for(i=;i<=n;i++)a[i].tim=read(),a[i].val=read();
sort(a+,a++n,cmp); for(i=n;i;i--){
q.push(a[i].val);size++;
if(a[i].tim-a[i-].tim>size)j=size;else j=a[i].tim-a[i-].tim;
while(j--)ans+=q.top(),q.pop(),size--;
}
printf("%lld\n",ans);
return ;
}
bzoj 1579： [Usaco2009 Feb]Revamping Trails 道路升级
分层图最短路。。。dis[i][j]表示到i点，共更新了j条边的最短路径长度。
按照更新的边数建K+1层图，第i层表示当前更新了（i-1）条边。除了在本层内扩展外，第1~K层的点还可以向更高的一层扩展（更新当前边为0）
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int maxn=;
const int maxm=;
const int mx=;
struct poi{
short pos;int dis;short int x;
}tmp;
priority_queue<poi>q;
struct zs{
short too;
int dis,pre;
}e[maxm<<];
int last[maxn],dis[][maxn];
ll dist[][maxn],ans;
int i,j,k,n,m,K,tot,a,b;
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;
}
bool operator <(poi a,poi b){return a.dis>b.dis;}
void spfa(){
int l=,r=,i;short now;short int nowx;
for(i=;i<=K;i++)memset(dist[i],,(n+)<<);
ans=dist[][n];
u[][]=;dist[][]=;
tmp.dis=;tmp.pos=;tmp.x=;q.push(tmp) ;
while(!q.empty()){
tmp=q.top();q.pop();
now=tmp.pos;nowx=tmp.x;u[nowx][now]=;
if(dist[nowx][now]<ans)
for(i=last[now];i;i=e[i].pre){
if(dist[nowx][e[i].too]>dist[nowx][now]+e[i].dis){
dist[nowx][e[i].too]=dist[nowx][now]+e[i].dis;
if(e[i].too==n)ans=min(ans,dist[nowx][e[i].too]);
if(!u[nowx][e[i].too]){
u[nowx][e[i].too]=;
tmp.pos=e[i].too;tmp.x=nowx;tmp.dis=dist[nowx][e[i].too];
q.push(tmp);
}
}
if(nowx<K&&dist[nowx+][e[i].too]>dist[nowx][now]){
dist[nowx+][e[i].too]=dist[nowx][now];
if(e[i].too==n)ans=min(ans,dist[nowx+][e[i].too]);
if(!u[nowx+][e[i].too]){
u[nowx+][e[i].too]=;
tmp.pos=e[i].too;tmp.x=nowx+;tmp.dis=dist[nowx+][e[i].too];
q.push(tmp);
}
}
}
}
}
int main(){
n=read();m=read();K=read();
for(i=;i<=m;i++){
a=read();b=read();
e[++tot].dis=e[tot+].dis=read();
e[tot].too=b;e[tot].pre=last[a];last[a]=tot++;
e[tot].too=a;e[tot].pre=last[b];last[b]=tot;
}
spfa();
printf("%lld\n",ans);
return ;
}
bzoj 1708： [Usaco2007 Oct]Money奶牛的硬币
完全背包。。。一开始竟然没看出来王仓
bzoj 1690： [Usaco2007 Dec]奶牛的旅行
01分数规划。。。二分答案为mid，将原图的边(u,v,time)重建为(u,v,fun[v]-time*mid)，如果新图中有负环那么当前答案可行
#include<cstdio>
#include<cstring>
#include<iostream>
#define d double
using namespace std;
const int maxn=;
const int maxm=;
const d eps=1e-;
struct zs{
int too,pre,t;
d dis;
}e[maxm];
int i,j,k,n,m,tot,a,b,c;
d dist[maxn],l,r,mid;
int val[maxn],last[maxn];
bool u[maxn],uu[maxn],flag; inline int read(){
char x;int ans=;
for(x=getchar();x<''||x>'';x=getchar());
for(;x>=''&&x<='';x=getchar())ans*=,ans+=x-;
return ans;
}
inline void insert(int a,int b,int c){
e[++tot].too=b;e[tot].pre=last[a];e[tot].t=c;last[a]=tot;
}
bool spfa(int x){
u[x]=;uu[x]=;
for(int i=last[x];i;i=e[i].pre)if(dist[e[i].too]>dist[x]+e[i].dis){
dist[e[i].too]=dist[x]+e[i].dis;
if(u[e[i].too]){flag=;return ;}
if(spfa(e[i].too))return ;
}
u[x]=;
return ;
}
bool check(d mid){
memset(uu,,n+);
memset(u,,n+);
memset(dist,,*(n+));
flag=;
for(int i=;i<=n;i++)if(!uu[i])if(spfa(i))return ;
return ;
}
int main(){
n=read();m=read();
for(i=;i<=n;i++)val[i]=read();
for(i=;i<=m;i++)a=read(),b=read(),c=read(),insert(a,b,c),r=max(r,(d)val[b]/(d)c);
l=0.0;
while(l+eps<=r){
mid=(l+r)/2.0;
for(i=;i<=m;i++)e[i].dis=(d)(-val[e[i].too])+mid*e[i].t;
if(check(mid))l=mid;else r=mid-eps;
}
printf("%.2lf\n",l);
return ;
}
bzoj 1717： [Usaco2006 Dec]Milk Patterns 产奶的模式
字符串http://www.cnblogs.com/czllgzmzl/p/4989723.html
bzoj 1692： [Usaco2007 Dec]队列变换
贪心。。。当前剩下的队伍为[l,r]，每次比较 l到r 这段字符串和 r到l 这段字符串，哪段小选哪段
比较字符串大小的时候可以用hash+二分求出最长公共前缀的长度，再比较下一位的大小
hash用unsigned int不会被卡。。。感人。。明显优势#1
然而O(n^2)暴力可过TAT
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ull unsigned int
using namespace std;
const int maxn=;
char s[maxn];
ull pre[maxn],jc[maxn],val1,val2,pre1[maxn];
short i,j,k,n,m,l,r,mid,len,L,R; inline short getlen(){
if(s[L]!=s[R])return ;
l=;r=R-L+;
if(pre[L+r-]-pre[L-]*jc[r]==pre1[R-r+]-pre1[R+]*jc[r])return r;r--;
while(l<r){
mid=(l+r+)>>;//return mid;
val1=pre[L+mid-]-pre[L-]*jc[mid];
val2=pre1[R-mid+]-pre1[R+]*jc[mid];
if(val1!=val2)r=mid-;else l=mid;
if(s[L+l]!=s[R-l])return l;
}
return l;
}
inline bool bigger(){
if(s[L]!=s[R])return s[L]>s[R];
len=getlen();
if(len==R-L+)return ;
else return s[L+len]>s[R-len];
}
int main(){
scanf("%d",&n);
for(i=;i<=n;i++)for(s[i]=getchar();s[i]<'A'||s[i]>'Z';s[i]=getchar());
jc[]=;for(i=;i<=n;i++)jc[i]=jc[i-]*;
for(i=;i<=n;i++)pre[i]=pre[i-]*+(ull)s[i]-'A';
for(i=n;i;i--)pre1[i]=pre1[i+]*+(ull)s[i]-'A';
L=;R=n;
for(i=;i<=n;i++)if(bigger()){
putchar(s[R--]);
if(i%==)putchar('\n');
}else {putchar(s[L++]);if(i%==)putchar('\n');}
return ;
}
bzoj 1782： [Usaco2010 Feb]slowdown 慢慢游
dfs序，一头牛走到点i，相当于将点i所在子树的权值都+1，查询的时候查询牛要走到的点的权值
也可以差分，变成点修改+区间查询，用树状数组就行了。。。
太傻逼用线段树然后被常数感动哭了
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
struct zs{
int too,pre;
}e[];
int pos[],last[],size[];
int l[maxn<<],r[maxn<<],add[maxn<<],A[maxn<<],B[maxn<<],mid[maxn<<];
int i,j,k,n,m,a,b,c,tim,tot,tott;
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;
e[++tot].too=a;e[tot].pre=last[b];last[b]=tot;
}
void dfs(int x,int pre){
size[x]=;pos[x]=++tim;
for(int i=last[x];i;i=e[i].pre)if(e[i].too!=pre){
dfs(e[i].too,x);size[x]+=size[e[i].too];
}
}
void build(int a,int b){
int now=++tott;
A[now]=a;B[now]=b;mid[now]=(a+b)>>;
if(a<b){
l[now]=tott+;build(a,mid[now]);
r[now]=tott+;build(mid[now]+,b);
}
}
inline void pushdown(int now){
add[l[now]]+=add[now];add[r[now]]+=add[now];
add[now]=;
}
void insert(int now,int c,int d){
if(c<=A[now]&&B[now]<=d){add[now]++;return;}
if(add[now])pushdown(now);
if(c<=mid[now])insert(l[now],c,d);
if(d>mid[now])insert(r[now],c,d);
}
int query(int now,int c){
if(A[now]==B[now])return add[now];
if(add[now])pushdown(now);
if(c<=mid[now])return query(l[now],c);else return query(r[now],c);
}
int main(){
n=read();
for(i=;i<n;i++)a=read(),b=read(),insert(a,b);
dfs(,);
build(,n);
for(i=;i<=n;i++){
a=read();printf("%d\n",query(,pos[a]));
insert(,pos[a],pos[a]+size[a]-);
}
}
bzoj 1827： [Usaco2010 Mar]gather 奶牛大集会
O(n^2)的暴力就是对每个点都把整棵树遍历一遍
考虑一下，假设求出了到当前点i的不方便值为fasum，如何快速计算i的儿子的不方便值
先预处理出每个点的子树内奶牛总数存在size[]，那么对于i的某个儿子j，所有不在j的子树里的奶牛都得多走从i->j这段路，而j子树里的奶牛都可以少走i->j这段路
nowsum=fasum+(cownum-size[j])*dis(i,j)-size[j]*dis(i,j);
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn=;
struct zs{
int too,pre;
ll dis;
}e[maxn<<];
int size[maxn],last[maxn],tot,fa[maxn];
int i,j,k,n,m,a,b,poinum;
int ra;char rx;
ll nowsum,ans; inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
void dfs(int x,ll fasum){
for(int i=last[x];i;i=e[i].pre)if(e[i].too!=fa[x]&&size[e[i].too]<<>poinum){
nowsum=fasum+(ll)(poinum-size[e[i].too]*)*e[i].dis;
if(nowsum<ans)ans=nowsum;
dfs(e[i].too,nowsum);
}
}
void dfs1(int x){
for(int i=last[x];i;i=e[i].pre)if(e[i].too!=fa[x])
fa[e[i].too]=x,dfs1(e[i].too),size[x]+=size[e[i].too],nowsum+=(ll)size[e[i].too]*e[i].dis;
}
int main(){
n=read();
for(i=;i<=n;i++)size[i]=read(),poinum+=size[i];
for(i=;i<n;i++){
a=read();b=read();e[++tot].dis=e[tot+].dis=read();
e[tot].too=b;e[tot].pre=last[a];last[a]=tot;
e[++tot].too=a;e[tot].pre=last[b];last[b]=tot;
}
dfs1();ans=nowsum;
dfs(,nowsum);
printf("%lld\n",ans);
return ;
}
bzoj 1592: [Usaco2008 Feb]Making the Grade 路面修整
显然（看题解才知道的TAT）一段路修整后，高度一定和原来那些路中的某一段相等。。。。所以把高度离散化一下就变成O(n^2)的dp了。。。
不下降的情况：f[i][j]表示前i段路，第i段高度修整为j的最小支出
f[i][j]=min{ f[i-1][k]+abs(h[i]-h[j]) }，（k<=j）转移的过程中顺便记录一下k就行了
不上升就倒过来做一遍
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define uint unsigned int
#define ll long long
using namespace std;
const int maxn=;
ll f[maxn][maxn],mn,ans;
int a[maxn],b[maxn];
int ra;char rx;
int i,j,k,n,m,nn;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline short getpos(int x){
short l=,r=nn,mid;
while(l<r){
mid=(l+r+)>>;
if(b[mid]<=x)l=mid;else r=mid-;
}return l;
}
int main(){
n=read();for(i=;i<=n;i++)a[i]=read();memcpy(b,a,(n+)<<);
sort(b+,b++n);
nn=unique(b+,b++n)-b-;
for(i=;i<=n;i++)a[i]=getpos(a[i]);
for(i=;i<=n;i++)memset(f[i],,(nn+)<<);ans=f[][];
for(i=;i<=n;i++){mn=f[i-][];
for(j=;j<a[i];j++){
if(f[i-][j]<mn)mn=f[i-][j];
f[i][j]=mn+b[a[i]]-b[j];
}
for(j=a[i];j<=nn;j++)mn=min(mn,f[i-][j]),f[i][j]=mn+b[j]-b[a[i]];
}
for(i=;i<=nn;i++)if(f[n][i]<ans)ans=f[n][i]; for(i=;i<=n;i++)memset(f[i],,(nn+)<<);
for(i=;i<=n;i++){mn=f[i-][nn];
for(j=nn;j>a[i];j--){
if(f[i-][j]<mn)mn=f[i-][j];
f[i][j]=mn+b[j]-b[a[i]];
}
for(j=a[i];j;j--)mn=min(mn,f[i-][j]),f[i][j]=mn+b[a[i]]-b[j];
}
for(i=;i<=nn;i++)if(f[n][i]<ans)ans=f[n][i];
printf("%lld\n",ans);
return ;
}
bzoj 1725：[Usaco2006 Nov]Corn Fields牧场的安排
数据范围就是状压了。。
f[i][j]表示前i行，第i行种草状态为j的总方案数。
f[i][j]=sum{ f[i-1][k] }，j状态和k状态是合法的（没种到那一行贫瘠的土地，且没有草相邻），且j&k==0（没有上下两行没有草在同一列）
预处理了各种非法情况结果比直接枚举慢= =
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const short maxn=;
const int modd=;
short two[maxn],mapl[maxn],mx;
short map[(<<)+][];
short i,j,k,n,m,tmp,now,pre;
int f[][(<<)+],ans;
char x;
int main(){
scanf("%d%d",&n,&m);
mx=<<m;two[]=;
for(i=;i<=m;i++)two[i]=two[i-]<<;
for(i=;i<mx;i++){
bool flag=;
for(j=;j<m&&!flag;j++)if(i&two[j]&&i&two[j+])flag=;
if(!flag)map[][++map[][]]=i;
}
for(i=;i<mx;i++){
tmp=i-(i&(-i));
for(j=map[tmp][];j;j--)if(!(map[tmp][j]&i))map[i][++map[i][]]=map[tmp][j];
}
now=;pre=;
f[][]=;
for(i=;i<=n;i++){
now=i;pre=i-;
for(j=;j<=m;j++){for(x=getchar();x<''||x>'';x=getchar());mapl[i]+=(x=='')*two[j];}
for(j=map[][],tmp=map[][j];j;j--,tmp=map[][j])if(!(tmp&mapl[i-])&&f[pre][tmp])
for(k=map[tmp][];k;k--)if(!(map[tmp][k]&mapl[i]))
f[now][map[tmp][k]]+=f[pre][tmp],f[now][map[tmp][k]]-=(f[now][map[tmp][k]]>=modd)?modd:;
}
for(i=;i<mx;i++)ans+=f[n][i],ans-=(ans>=modd)?modd:;
printf("%d\n",ans);
return ;
}
bzoj 1711：[Usaco2007 Open]Dingin吃饭
二分图最大匹配。。s连奶牛，饮料和食品连t，每头牛往它要吃的东西连边。。。用dinic比匈牙利算法慢了点
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
struct zs{
short too,flow;
int pre;
}e[];
short dis[],dl[];
short l,r,now;
int last[],tot,s,t,n,m1,m2,num1,num2,a,i,j,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(short a,short 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;
}
bool bfs(){
memset(dis,,(t+)<<);
l=;r=;dl[]=s;dis[s]=;
short now;int i;
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]!=-;
}
short dfs(short x,short mx){
if(!mx||x==t)return mx;
short w,used=;int i;
for(i=last[x];i;i=e[i].pre)if(e[i].flow&&dis[e[i].too]==dis[x]+){
w=dfs(e[i].too,min(mx-used,(int)e[i].flow));if(w){
e[i].flow-=w;e[((i-)^)+].flow+=w;
used+=w;if(used==mx)return used;
}
}
dis[x]=-;return used;
}
int main(){
n=read();m1=read();m2=read();s=;t=n*+m1+m2+;
for(i=;i<=n;i++){
insert(i+m1,i+m1+n);
num1=read();num2=read();
for(j=;j<=num1;j++)a=read(),insert(a,i+m1);
for(j=;j<=num2;j++)a=read(),insert(i+m1+n,a+m1+n*);
}
for(i=;i<=m1;i++)insert(,i);
for(i=;i<=m2;i++)insert(n*+m1+i,t);
while(bfs())ans+=dfs(s,);
printf("%d\n",ans);
return ;
}
bzoj 1668： [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富
裸dp。f[i][j]表示走到第i列，第j行最大财富，
f[1][1]=map[1][j];f[i][j]=max{f[i-1][j-1],f[i-1][j],f[i-1][j+1]}
注意边界。。。。第0、n+1行和第1列初始化成负无穷QAQ
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxh=;
int map[maxh][maxh];
int i,j,k,n,m,now,pre;
int f[][maxh];
char x;
inline void read(int &ans){
x=getchar();int fh=;
while((x<''||x>'')&&x!='-')x=getchar();
if(x=='-')fh=-,x=getchar();
while(x>=''&&x<='')ans*=,ans+=x-,x=getchar();ans*=fh;
}
int main(){
read(n);read(m);
for(i=;i<=n;i++)for(j=;j<=m;j++)read(map[i][j]);
f[][]=map[][];for(i=;i<=n;i++)f[][i]=-;
for(i=;i<=m;i++){
pre=i&;now=pre^;f[pre][]=f[pre][n+]=-;
for(j=;j<=n;j++)f[now][j]=max(f[pre][j],max(f[pre][j-],f[pre][j+]))+map[j][i];
}
printf("%d\n",f[now][n]);
return ;
}
bzoj 1571： [Usaco2009 Open]滑雪课Ski
dp，f[i][j]表示前i时间过后，能力值为j的最大滑雪次数
f[i][j]=max{
f[i-1][j]，//开颓
f[ i-Dmin[j] ][ j ]+1，//先把斜坡按所需能力排序，Dmin[j]表示 所需能力值<=j的斜坡中 所需最小时长
g[ i-L[k] ]，//上第k节课（前提是有课= =），g[i]表示f[i][1..100]中的最大值
}
代码丑得不忍直视。。。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=;
struct lesson{
short st,l,val;
}a[];
struct poi{
short need,cost;
}b[maxn];
short f[maxn][],g[maxn],ans;
short cost[maxn],need[maxn],M[maxn],L[maxn],aa[];
bool can[];
int i,j,k,n,m,maxt,nn;
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(lesson a,lesson b){
return a.st<b.st;
}
bool cmp1(poi a,poi b){
return a.need<b.need;
}
bool cmp2(poi a,poi b){
return a.cost<b.cost;
}
inline short getpos(int x){
short l=,r=nn,mid;
while(l<r){
mid=(l+r+)>>;
if(aa[mid]<=x)l=mid;else r=mid-;
}
return l;
}
int main(){
maxt=read();n=read();m=read();
for(i=;i<=n;i++)a[i].st=read(),a[i].l=read(),a[i].val=aa[i]=read();
sort(a+,a++n,cmp);aa[n+]=;sort(aa,aa++n);nn=unique(aa+,aa++n)-aa-;//printf(" %d\n",nn);
for(i=;i<=n;i++)a[i].val=getpos(a[i].val);
for(i=;i<=m;i++)b[i].need=read(),b[i].cost=read();
sort(b+,b++m,cmp1);int tmp=,tmp1=b[].cost;
for(i=;i<=m;i++)if(b[i].cost<tmp1)tmp1=b[i].cost,b[++tmp].cost=b[i].cost,b[tmp].need=b[i].need;
m=tmp;
sort(b+,b++m,cmp2);
int nowlesson=,nowpoi=;
memset(f[],,sizeof(f[]));f[][]=;can[]=;
for(i=;i<=maxt;i++){
memcpy(f[i],f[i-],(nn+)<<);
while(nowpoi<m&&b[nowpoi+].cost<=i)nowpoi++;
while(nowlesson<n&&a[nowlesson+].st+a[nowlesson+].l==i)nowlesson++,f[i][a[nowlesson].val]=g[a[nowlesson].st],can[a[nowlesson].val]=;
for(j=;j<=nn;j++)if(can[j]){
for(k=;k<=nowpoi;k++)if(aa[j]>=b[k].need&&f[i-b[k].cost][j]>=f[i][j])f[i][j]=f[i-b[k].cost][j]+;
// printf("%d %d %d\n",i,j,f[i][j]);
if(f[i][j]>g[i])g[i]=f[i][j];
}//printf(" gi:%d\n",g[i]);
}
for(i=;i<=nn;i++)ans=max(ans,f[maxt][i]);
printf("%d\n",ans);
return ;
}
bzoj 1715： [Usaco2006 Dec]Wormholes 虫洞
询问图中有没有负环。。。（回到过去必须是回到起点并且时间比出发时还早）
dfs版的spfa判负环。。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
const int maxm=;
struct zs{
short too,pre,dis;
}e[maxm];
short i,j,k,n,m,tot,T,w,a,b;
short last[maxn];
int dis[maxn];
bool u[maxn],uu[maxn];
short ra;char rx;
inline short read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
bool dfs(short x){
short i,j;
uu[x]=u[x]=;
for(i=last[x];i;i=e[i].pre)if(dis[e[i].too]>dis[x]+e[i].dis){
dis[e[i].too]=e[i].dis+dis[x];
if(u[e[i].too]||dfs(e[i].too)){u[x]=;return ;}
}u[x]=;
return ;
}
bool spfa(){
short j;
for(j=;j<=n;j++)if(!uu[j]&&dfs(j))return ;
return ;
}
int main(){
T=read();
for(int ii=;ii<=T;ii++){
n=read();m=read();w=read();
if(ii>)memset(last,,(n+)<<),memset(uu,,n+),tot=;
for(i=;i<=m;i++){
e[++tot+].too=a=read();e[tot].too=b=read();e[tot].dis=e[tot+].dis=read();
e[tot].pre=last[a];last[a]=tot++;
e[tot].pre=last[b];last[b]=tot;
}
for(i=;i<=w;i++)a=read(),e[++tot].too=read(),e[tot].dis=-read(),e[tot].pre=last[a],last[a]=tot;
bool flag=spfa();
if(flag)printf("YES\n");else printf("NO\n");
}
return ;
}
bzoj 1596： [Usaco2008 Jan]电话网络
树形dp。。http://www.cnblogs.com/czllgzmzl/p/5064626.html
bzoj 2442： [Usaco2011 Open]修剪草坪
单调队列。。
最大效率==总效率-最小损失效率。f[i]表示前i头奶牛，因为不能有连续K只奶牛而损失的效率的最小值（第i头牛不安排）。
f[i]=min{ f[j] } +E[i]，（i-j<=K）
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=;
int dl[maxn];
ll f[maxn],sum;
int i,j,k,n,m,l,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;
}
int main(){
n=read();k=read()+;
l=r=;dl[]=;
for(i=;i<=n+;i++){
while(l<r&&i-dl[l]>k)l++;
if(i<=n)j=read();else j=;
f[i]=f[dl[l]]+j;sum+=j;
while(l<=r&&f[dl[r]]>=f[i])r--;
dl[++r]=i;
}
printf("%lld\n",sum-f[dl[l]]);
return ;
}
bzoj 1233: [Usaco2009Open]干草堆tower
斜率优化。。。
看了别人（似乎是wshjzaa？）题解才明白TAT http://www.cnblogs.com/sagitta/p/4650681.html
注：题解最后似乎有个地方<和>打反了？（或者是我语文不好。。）
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=;
int f[maxn],pre[maxn],g[maxn];
int i,j,k,n,m,l,r;
int dl[maxn]; short ra;char rx;
inline short read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
int main(){
scanf("%d",&n);
for(i=;i<=n;i++)pre[i]=read()+pre[i-];
l=r=;dl[r]=n+;
for(i=n;i;i--){
while(l<=r&&f[dl[l]]<=pre[dl[l]-]-pre[i-])l++;l--;
f[i]=pre[dl[l]-]-pre[i-];
g[i]=g[dl[l]]+;
while(l<=r&&pre[dl[r]-]-f[dl[r]]<=pre[i-]-f[i])r--;
dl[++r]=i;
}
printf("%d\n",g[]);
return ;
}
bzoj 1707: [Usaco2007 Nov]tanning分配防晒霜
贪心。。http://www.cnblogs.com/czllgzmzl/p/5064620.html
bzoj 1709： [Usaco2007 Oct]Super Paintball超级弹珠
难得的傻逼题。。可以O(n^3)无脑暴力。。。
或者是先预处理一下，读入时处理出 每一行、每一列、每一条对角线的对手数量。。。当然还有每一个点上的对手数
某个射击位置(x,y)能打到的对手数就是 第x行的对手数+第y行的对手数+所在两条对角线的对手数-3*（(x,y)这个点上的对手数）
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=;
int h[maxn],l[maxn],dj1[maxn<<],dj2[maxn<<],map[maxn][maxn];
int i,j,k,n,m,ans,a,b;
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<=m;i++)a=read(),b=read(),h[a]++,l[b]++,dj1[a+b-]++,dj2[a-b+n]++,map[a][b]++;
for(i=;i<=n;i++)for(j=;j<=n;j++)
if(h[i]+l[j]+dj1[i+j-]+dj2[i-j+n]-map[i][j]*==m)ans++;
printf("%d\n",ans);
return ;
}
bzoj 1576： [Usaco2009 Jan]安全路经Travel
并查集正确姿势。。http://www.cnblogs.com/czllgzmzl/p/5064758.html
bzoj 1593： [Usaco2008 Feb]Hotel 旅馆
比较正常的线段树题目。。。维护一段只有0和1的区间里面，最长的0的长度，从左边开始、从右边开始的最长的0的长度
每次查找区间位置的时候，如果左子树里的够长就去左子树找，不然试试跨过左右子树的那段，最后才去右子树里找。（无解直接输出0）
区间修改的话就维护一个标记，表示当前区间被覆盖的情况（客人订满、客人退空、已下传）
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=;
const int inf=;
int mx[maxn<<],l[maxn<<],r[maxn<<],lmx[maxn<<],rmx[maxn<<],size[maxn<<],mid[maxn<<],mxpos[maxn<<];
short cov[maxn<<];//0：全可用，1：全不可，2：其他或已下传
int ra;char rx;
int i,j,k,n,m,ans,tot,L,R,id,pos;
inline void pushup(int now,int l,int r){
lmx[now]=lmx[l];if(lmx[l]==size[l])lmx[now]+=lmx[r];
rmx[now]=rmx[r];if(rmx[r]==size[r])rmx[now]+=rmx[l];
mx[now]=rmx[l]+lmx[r];mxpos[now]=mid[now]-rmx[l]+;if(mx[l]>mx[now])mx[now]=mx[l],mxpos[now]=mxpos[l];if(mx[r]>mx[now])mx[now]=mx[r],mxpos[now]=mxpos[r];
}
void build(int a,int b){
int now=++tot;mid[now]=(a+b)>>;
mx[now]=lmx[now]=rmx[now]=size[now]=b-a+;mxpos[now]=a;cov[now]=;
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){
if(cov[now]){
lmx[l]=lmx[r]=rmx[l]=rmx[r]=mx[l]=mx[r]=mxpos[r]=mxpos[l]=;
cov[l]=cov[r]=;
}else{
lmx[l]=rmx[l]=mx[l]=size[l];mxpos[l]=mid[now]-size[l]+;
lmx[r]=rmx[r]=mx[r]=size[r];mxpos[r]=mid[now]+;
cov[l]=cov[r]=;
}
cov[now]=;
}
void update(int now,int a,int b,int c,int d,int col){
if(c<=a&&d>=b){
cov[now]=col;
if(col)lmx[now]=rmx[now]=mx[now]=mxpos[now]=;
else lmx[now]=rmx[now]=mx[now]=size[now],mxpos[now]=a;
return;
}
if(cov[now]!=)pushdown(now,l[now],r[now]);
if(c<=mid[now])update(l[now],a,mid[now],c,d,col);
if(d>mid[now])update(r[now],mid[now]+,b,c,d,col);
pushup(now,l[now],r[now]);
}
int getpos(int now,int a,int b,int len){
int L=l[now],R=r[now];
if(cov[now]!=)pushdown(now,L,R);
if(mx[L]>=len)return getpos(L,a,mid[now],len);
else if(rmx[L]+lmx[R]>=len)return mid[now]-rmx[L]+;
else return getpos(R,mid[now]+,b,len);
}
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();
build(,n);
for(i=;i<=m;i++){
id=read();L=read();
if(id==){
if(mx[]>=L){
pos=getpos(,,n,L);
printf("%d\n",pos);
update(,,n,pos,pos+L-,);
}else printf("0\n");
}else{
R=read();
update(,,n,L,L+R-,);
}
}
return ;
}
1A感人TAT
bzoj 1697： [Usaco2007 Feb]Cow Sorting牛排序
置换群。。现在还是不会置换群QAQ。。。不过至少这题的题解看得懂QAQ。。。
题解网上一坨。。因为poj里也有= =
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=;
struct zs{
short pos;
int val;
}a[maxn];
short i,j,pos,n;
ll mn,ans,nowmn,nowsum,len;
bool u[maxn]; bool cmp(zs a,zs b){
return a.val<b.val;
}
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();
for(i=;i<=n;i++)a[i].val=read(),a[i].pos=i;
sort(a+,a++n,cmp);mn=a[].val;
for(i=;i<=n;i++)if(!u[i]){
u[i]=;nowmn=nowsum=a[i].val;len=;
for(pos=a[i].pos;!u[pos];pos=a[pos].pos){
len++,nowsum+=(ll)a[pos].val,u[pos]=;
if(a[pos].val<nowmn)nowmn=a[pos].val;
}
ans+=nowsum+min((len-)*nowmn,nowmn+(len+)*mn);
}
printf("%lld\n",ans);
return ;
}
bzoj 1828： [Usaco2010 Mar]balloc 农场分配
把各个请求按右端点从小到大排序。。然后直接依次能满足的就满足。。。这样就行了。。。。至于为什么这样子贪心是对的。。TAT
设区间左右端点为l[],r[]...
因为是按r排序的：如果当前区间插入后会影响到后面的某个区间的话，那么相比于那个被影响的区间，插入当前区间更优。
并且在插入当前区间前我们已经尽量满足了r更小的区间，所以当前区间对之前的区间无影响。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
struct zs{
int l,r;
}a[maxn];
int mn[maxn<<],l[maxn<<],r[maxn<<],mid[maxn<<],tag[maxn<<];
int ra;char rx;
int i,j,k,n,m,ans,tot; 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;
mid[now]=(a+b)>>;
if(a<b){
l[now]=tot+;build(a,mid[now]);
r[now]=tot+;build(mid[now]+,b);
if(mn[l[now]]<mn[r[now]])mn[now]=mn[l[now]];else mn[now]=mn[r[now]];
}else mn[now]=read();
}
bool cmp(zs a,zs b){
return a.r<b.r;
}
inline void pushdown(int now,int t){
tag[l[now]]+=t;tag[r[now]]+=t;
mn[l[now]]-=t;mn[r[now]]-=t;
tag[now]=;
}
int query(int now,int a,int b,int c,int d){
if(c<=a&&d>=b)return mn[now];
if(tag[now])pushdown(now,tag[now]);
if(d<=mid[now])return query(l[now],a,mid[now],c,d);
else if(c>mid[now])return query(r[now],mid[now]+,b,c,d);
else return min(query(l[now],a,mid[now],c,d),query(r[now],mid[now]+,b,c,d));
}
void insert(int now,int a,int b,int c,int d){
if(c<=a&&d>=b){tag[now]++;mn[now]--;return;}
if(tag[now])pushdown(now,tag[now]);
if(c<=mid[now])insert(l[now],a,mid[now],c,d);
if(d>mid[now])insert(r[now],mid[now]+,b,c,d);
mn[now]=min(mn[l[now]],mn[r[now]]);
}
int main(){
n=read();m=read();
build(,n);
for(i=;i<=m;i++)a[i].l=read(),a[i].r=read();
sort(a+,a++m,cmp);
for(i=;i<=m;i++)if(query(,,n,a[i].l,a[i].r)>)ans++,insert(,,n,a[i].l,a[i].r);
printf("%d\n",ans);
return ;
}
bzoj 1589： [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果
就是求后继节点的总数。。。因为整张图是由若干个基环内向树组成，所以可以用tarjan缩点后做。。。
不过因为是基环内向树（同今年noipD1T2）。。从某个点开始一直走就会把它所连向的环走遍，也就起到了缩点的效果。。
具体就开个栈记录一下当前路径，记录一个点是否在栈中。注意已经求出后继节点数的点就不用再走了.
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=;
int to[maxn],ans[maxn],st[maxn];
bool ins[maxn];
int i,j,n,m,top,ed,len,tmp;
char s[];
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 outx(int x){
for(tmp=;x;x/=)s[tmp++]=x%;
for(register int i=tmp-;i>=;i--)putchar(s[i]+);putchar('\n');
}
int main(){
n=read();
for(i=;i<=n;i++)to[i]=read();
for(i=;i<=n;i++)if(!ans[i]){
ins[i]=ans[i]=;st[top=]=i;
for(j=to[i];!ans[j]&&!ins[j];j=to[j])st[++top]=j,ins[j]=;
if(ins[j]){
for(ed=j,j=top,len=;st[j]!=ed;j--)len++;
for(;top>=j;top--)ans[st[top]]=len,ins[st[top]]=;
}
while(top)ans[st[top]]=+ans[to[st[top]]],ins[st[top--]]=;
}
for(i=;i<=n;i++)outx(ans[i]);
return ;
}
//之前弄了半天依然被踩在#2。。。。知道刚刚才想到一个布尔数组不用开才弄到200ms。。。再加了个输出优化瞬间就176ms了= =感人肺腑
//为什么我每次用register int都更慢
bzoj 1754： [Usaco2005 qua]Bull Math
高精度乘法。。。。。。。。。。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int modd=;
int a[],b[],ans[],len;
char s[];
short i,j;
int main(){
scanf("%s",s);a[]=;
for(i=strlen(s),len=;i;i--){
a[a[]]+=(s[i-]-'')*len;
len*=;if(len>=modd&&i>)len=,a[]++;
}
scanf("%s",s);b[]=;
for(i=strlen(s),len=;i;i--){
b[b[]]+=(s[i-]-'')*len;
len*=;if(len>=modd&&i>)len=,b[]++;
}
len=a[]+b[];
for(i=;i<=a[];i++)for(j=;j<=b[];j++){
ans[i+j-]+=a[i]*b[j];
if(ans[i+j-]>=modd)ans[i+j]+=ans[i+j-]/modd,ans[i+j-]%=modd;
}
while(!ans[len]&&len>)len--;
printf("%d",ans[len]);
for(i=len-;i;i--){
for(j=;j<modd;j*=)if(ans[i]<j)putchar('');
printf("%d",ans[i]);
}printf("\n");
return ;
}
bzoj 1770： [Usaco2009 Nov]lights 燈
高斯消元解异或方程组。。。。*元就暴力枚举+最优性剪枝= =。。。
话说*元啊什么的一直不懂。。。数学方面以后再慢慢补吧（已经无数次这么说了TAT
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
short f[][],ans[];
int i,j,k,n,m,mn,a,b;
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 gauss(){
short i,j,k;
for(i=;i<=n;i++){
for(j=i;j<=n&&!f[j][i];j++);if(j>n)continue;
if(i!=j)for(k=;k<=n+;k++)swap(f[i][k],f[j][k]);
for(j=;j<=n;j++)if(i!=j&&f[j][i])
for(k=;k<=n+;k++)f[j][k]^=f[i][k];
}
}
void dfs(short now,int tot){
if(tot>=mn)return;
if(!now){
mn=tot;return;
}
if(f[now][now]){
short i;
ans[now]=f[now][n+];
for(i=now+;i<=n;i++)if(f[now][i])ans[now]^=ans[i];
dfs(now-,tot+ans[now]);
}else{
ans[now]=;dfs(now-,tot);
ans[now]=;dfs(now-,tot+);
}
}
int main(){
n=read();m=read();
for(i=;i<=n;i++)f[i][i]=f[i][n+]=;
for(i=;i<=m;i++)a=read(),b=read(),f[a][b]=f[b][a]=;
gauss();
mn=;
dfs(n,);
printf("%d\n",mn);
return ;
}
抄了黄学长代码。。捂脸
bzoj 1691： [Usaco2007 Dec]挑剔的美食家
有点像bzoj1828。。。都是两个限定条件，虽然具体有点不同= =
把奶牛按要求最低价升序排序，牧草按价格升序排序。
枚举牧草，每种牧草让可接受它的奶牛中，对新鲜度要求最高的奶牛吃。
具体就是用平衡树维护可接受当前价格的奶牛（会越来越多）的要求新鲜度。。每种牧草按新鲜度在树中找一下前驱。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=;
const int inf=;
struct gc{
int c,v;
}g[maxn],c[maxn]; int t[maxn],l[maxn],r[maxn],rnd[maxn],sz[maxn];
int i,j,k,n,m,tot,rt,num;
ll ans; inline void lturn(int &x){
int R=r[x];r[x]=l[R];l[R]=x;x=R;
}
inline void rturn(int &x){
int L=l[x];l[x]=r[L];r[L]=x;x=L;
}
void insert(int &x,int val){
if(!x){x=++tot;t[x]=val;rnd[x]=rand();sz[x]=;//printf("! cow v:%d in\n",val);
return;
}
if(val==t[x])sz[x]++;
else if(val<t[x])
{insert(l[x],val);
if(rnd[l[x]]<rnd[x])rturn(x);
}else{insert(r[x],val);
if(rnd[r[x]]<rnd[x])lturn(x);
}
}
void del(int &x,int val){
if(t[x]==val){
//printf("! deleting %d v:%d\n",x,t[x]);
if(sz[x]>)sz[x]--;
else if(!(l[x]&&r[x]))x=l[x]+r[x];//,printf("---->%d\n",x);
else if(rnd[l[x]]<rnd[r[x]]){rturn(x);del(x,val);}else {lturn(x);del(x,val);}
}else if(val<t[x])del(l[x],val);else del(r[x],val);
}
int find(int x,int val){if(!x)return ;
if(t[x]>val)return find(l[x],val);else{
int tmp=find(r[x],val);
if(tmp)return tmp;else return t[x];
}
}
inline void read(int &ans){
char x=getchar();
while(x<''||x>'')x=getchar();
while(x>=''&&x<='')ans*=,ans+=x-,x=getchar();
}
bool cmp(gc a,gc b){return a.c<b.c;}
int main(){
read(n);read(m);
if(m<n){printf("-1\n");return ;};
for(i=;i<=n;i++)read(c[i].c),read(c[i].v);
for(i=;i<=m;i++)read(g[i].c),read(g[i].v);
sort(c+,c++n,cmp);sort(g+,g++m,cmp);j=rt=;
for(i=;i<=m&&m-i+>=n-num&&num<n;i++){
while(j<n&&c[j+].c<=g[i].c)j++,insert(rt,c[j].v);
int val=find(rt,g[i].v);
//printf("grass%d(%d %d) be eaten by cow v:%d(%d %d)\n",i,g[i].c,g[i].v,val,,c[pos].v);
if(val)
num++,ans+=(ll)g[i].c,del(rt,val);
//,printf("%d(%d %d) eats %d(%d %d)\n",pos,c[pos].c,c[pos].v,i,g[i].c,g[i].v);
}
if(num==n)
printf("%lld\n",ans);else printf("-1\n");
return ;
}
手打treap比调stl的慢= =
bzoj 1753： [Usaco2005 qua]Who's in the Middle
如题。。。。。。。。。。。。。。。。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int a[maxn],n,i; 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();for(i=;i<=n;i++)a[i]=read();
sort(a+,a++n);
printf("%d\n",a[(n+)>>]);
return ;
}
加了快速读入比没加的慢是什么情况= =
bzoj 1574： [Usaco2009 Jan]地震损坏Damage
就是说对于报告的每个点，都要找到一圈点把它围起来（与1点阻断）。。显然（又是看题解才知道的QAQ）这一圈点就是那个点相邻的所有点（当然相邻点也可能是被报告的点，但总之这些点都无法到达了）。。
因为圈内的点都无法到达，我们要使得圈上及圈内的点最少。。所以圈越小越好。。
把每个报告的点的相邻节点都设为不可通过，最后统计下还能到达的点的数目就好。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
struct zs{
short too;
int pre;
}e[];
int last[],dl[];
bool dead[];
int i,j,k,n,m,a,b,p,l,r,now,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;
}
inline void insert(short a,short 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;
}
int main(){
n=read();m=read();p=read();
for(i=;i<=m;i++)a=read(),b=read(),insert(a,b);
for(i=;i<=p;i++){
a=read();dead[a]=;
for(j=last[a];j;j=e[j].pre)dead[e[j].too]=;
}
l=;if(!dead[])r=;dl[]=;dead[]=;
while(l<r){
now=dl[++l];
for(i=last[now];i;i=e[i].pre)if(!dead[e[i].too])dead[e[i].too]=,dl[++r]=e[i].too;
}
printf("%d\n",n-r);
return ;
}
bzoj 1584： [Usaco2009 Mar]Cleaning Up 打扫卫生
DPhttp://www.cnblogs.com/czllgzmzl/p/5066443.html
bzoj 1710： [Usaco2007 Open]Cheappal 廉价回文
因为最后要形成回文串。。。对于回文串来说删一个字母和 在对应位置添加一个同样的字母是等价的= =
所以把一个字母和谐掉的代价是min(删除该字母费用，添加该字母费用)。。（记为cost[]）
接下来就是区间dp了。。。f[i][j]表示把原字符串中第i个~第j个字母变成回文串的最小代价。。原字符串为s
f[i][j]=min{
f[i][j-1]+cost[s[j]]，f[i+1][j]+cost[s[i]]，
f[i+1][j-1]，（s[i]==s[j]）
}最后答案就是f[1][m]
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
char s[maxn],c[];
short cost[],tmp;
int f[maxn][maxn];
short i,j,k,n,m,len;
short ra;char rx,trx;
inline short 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(s[]=getchar();s[]<'a'||s[]>'z';s[]=getchar());
for(i=;i<=m;i++)s[i]=getchar();
for(i=;i<=n;i++){
for(trx=getchar();trx<'a'||trx>'z';trx=getchar());
tmp=read();cost[trx]=read();
if(tmp<cost[trx])cost[trx]=tmp;
}
for(len=;len<=m;len++)for(i=m-len+,j=m;i;i--,j--)
if(s[i]==s[j])f[i][j]=f[i+][j-];
else if(cost[s[j]]+f[i][j-]<cost[s[i]]+f[i+][j])f[i][j]=cost[s[j]]+f[i][j-];
else f[i][j]=cost[s[i]]+f[i+][j];
printf("%d\n",f[][m]);
return ;
}
bzoj 1703： [Usaco2007 Mar]Ranking the Cows 奶牛排名
善用stl。。。善调bitset。。。
按给出的大小关系建图。。求出每头牛i能确定的比它小的奶牛的数量num[i]，答案就是 总对数-已知的关系对数。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<bitset>
using namespace std;
short too[][];
bool u[],map[][];
bitset<>a[];
int i,j,k,n,m;
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 dfs(int x){
u[x]=;
for(short i=too[x][];i;i--)if(!u[too[x][i]])dfs(too[x][i]),a[x]|=a[too[x][i]];
else a[x]|=a[too[x][i]];
}
int main(){
n=read();m=read();
for(i=;i<=m;i++){
j=read(),k=read();
if(!map[j][k])map[j][k]=,too[j][++too[j][]]=k;
}
for(i=;i<=n;i++)a[i][i]=;
for(i=;i<=n;i++)if(!u[i])dfs(i);
for(j=(n-)*n/+n,i=;i<=n;i++)j-=a[i].count();
printf("%d\n",j);
return ;
}
为啥同样是调bitset我就慢了这么多TAT
bzoj 1578： [Usaco2009 Feb]Stock Market 股票市场
看了老司机的题解。。。http://www.cnblogs.com/JSZX11556/p/4664348.html
引用：“我们假设每天买完第二天就卖掉( 不卖出也可以看作是卖出后再买入 ), 这样就是变成了一个完全背包问题了, 股票价格为体积, 第二天的股票价格 - 今天股票价格为价值.... 然后就一天一天dp...”。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxt=;
int map[][],val,cost;
int f[maxt];
int i,j,k,n,m,T,nowt; 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();T=read();m=read();
for(i=;i<n;i++)for(j=;j<T;j++)map[j][i]=read();
for(nowt=;nowt<T;nowt++){
if(nowt>)memset(f,,(m+)<<);
for(i=;i<n;i++){
val=map[nowt][i]-map[nowt-][i];cost=map[nowt-][i];
if(val<=)continue;
for(j=cost;j<=m;j++)if(f[j-cost]+val>f[j])f[j]=f[j-cost]+val;
}
m+=f[m];
}
printf("%d\n",m);
return ;
}
bzoj 1598: [Usaco2008 Mar]牛跑步
求第k短路。。看了kpm大爷的代码才知道可以懒出新境界。。。
用优先队列维护spfa的队列（其实就变成了堆优化的dij）。。一个点出队k次时我们就得出了k短路。。。。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=;
struct zs{
int dis,pos;
};
struct edge{
int too,pre,dis;
}e[];
int dis[maxn],last[maxn],sumk[maxn];
int i,j,k,n,m,size,K,a;
priority_queue<zs>q;
bool operator <(zs a,zs 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(){
n=read();m=read();K=read();
for(i=;i<=m;i++){
a=read();e[i].too=read();e[i].dis=read();
e[i].pre=last[a];last[a]=i;
}zs tmp;
size=;tmp.pos=n;tmp.dis=;q.push(tmp);
while(size&&sumk[]<K){
i=q.top().pos;j=q.top().dis;size--;q.pop();
if(sumk[i]>=K)continue;
sumk[i]++;if(i==){printf("%d\n",j);}
for(i=last[i];i;i=e[i].pre)tmp.pos=e[i].too,tmp.dis=j+e[i].dis,q.push(tmp),size++;
}
for(i=K-sumk[];i;i--)puts("-1\n");
return ;
}
bzoj 2060: [Usaco2010 Nov]Visiting Cows 拜访奶牛
终于是傻逼题了。。。没有上司的舞会。树形dp，f[i][0]表示以i为根节点，i不选，能选的最多点数，f[i][1]表示以i为根节点，i选，能选的最多点数。
f[i][0]=sum{ max(f[j][0],f[j][1]) }，（j是i的儿子）；f[i][1]=sum{ f[j][0] }，（j是i的儿子）
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
struct zs{
int too,pre;
}e[maxn<<];
int last[maxn],f[maxn][];
int i,j,n,m,tot,a,b;
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 dfs(int x,int fa){
f[x][]=;
for(int i=last[x];i;i=e[i].pre)if(e[i].too!=fa){
dfs(e[i].too,x);
if(f[e[i].too][]>f[e[i].too][])f[x][]+=f[e[i].too][];else f[x][]+=f[e[i].too][];
f[x][]+=f[e[i].too][];
}
}
int main(){
n=read();
for(i=;i<n;i++){
a=read();b=read();e[++tot].too=b;e[tot].pre=last[a];last[a]=tot;
e[++tot].too=a;e[tot].pre=last[b];last[b]=tot;
}
dfs(,);
printf("%d\n",max(f[][],f[][]));
return ;
}
bzoj 1702: [Usaco2007 Mar]Gold Balanced Lineup 平衡的队列
和bzoj4236那题思路一样。。。求得各种颜色数的前缀和，并差分。。如果两不同位置上差分后的结果相等，就说明这两个位置之间各种颜色数量相等。
可以上hash。。。然而卡常无力被稳稳地踩了TAT
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=;
struct zs{
int pos;
unsigned int v;
}a[maxn];
int nownum[],two[];
bool u[maxn];
int i,j,k,n,m,kk,x,ans;
bool same;
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||(a.v==b.v&&a.pos<b.pos);
}
int main(){
n=read();k=read();two[]=;
for(i=;i<k;i++)two[i+]=two[i]<<;
for(i=;i<=n;i++){
x=read();
for(j=;j<=k;j++)if(x&two[j])nownum[j]++;
for(j=;j<k;j++)//a[i].num[j]=nownum[j]-nownum[j+1],
a[i].v*=,a[i].v+=nownum[j]-nownum[j+];
a[i].pos=i;
}
n++;
sort(a+,a++n,cmp);
for(i=;i<=n;){
for(j=i+;j<=n&&a[i].v==a[j].v;j++);
j--;
if(a[j].pos-a[i].pos>ans)ans=a[j].pos-a[i].pos;
i=j+;
}
printf("%d\n",ans);
return ;
}
bzoj 1704： [Usaco2007 Mar]Face The Right Way 自动转身机
如果K已经确定的话，可以O(n)求出最小判断次数M：从前往后扫一遍，如果一个点i上奶牛朝后站着，就把i~i+k-1头奶牛都转过来。因为此时不转的话以后就转不了了。。。
注意无解的判定。。。如果第i头奶牛朝后站着且i+k>n（就是没有k头奶牛可以转了）就无解。。。
区间修改，单点查询。。。这个可以用差分。。因为只有朝前和朝后两种，就直接异或一下就好了。时间复杂度O(n*k)
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
bool now[maxn],nowsum;
int i,j,k,n,m,nowans,ans;
bool mp[maxn];
char rx;
int main(){
scanf("%d",&n);
for(i=;i<=n;i++){
for(rx=getchar();rx!='F'&&rx!='B';rx=getchar());
mp[i]^=(rx=='B');
if(rx=='B')mp[i+]^=,ans++;
}
k=;
for(i=;i<=n;i++){
memcpy(now,mp,(n+));nowans=nowsum=;
for(j=;j<=n&&nowans<ans;j++){
nowsum^=now[j];
if(nowsum&&j+i>n+){nowans=;break;}
if(nowsum)nowsum^=,now[j+i]^=,nowans++;
}
if(nowans<ans)ans=nowans,k=i;
}
printf("%d %d\n",k,ans);
return ;
}
bzoj 1776： [Usaco2010 Hol]cowpol 奶牛政坛
由题解可得（TAT）结论：某政党内部的最长路径一定有一个端点是政党内最深的一个点。。毕竟树的直径也有一个端点在叶子节点上？
先一遍dfs求出每个政党最深的点，然后求它和所在政党其他点的距离的最大值。。树上两点间的距离dis(i,j)=depth[i]+depth[j]-depth[lca(i,j)]*2。。
总时间复杂度O(nlogn)...求lca部分试了倍增和链剖两种。。。。代码长度差不多但是倍增慢多了QAQ
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
const int maxdep=;
struct zs{
int too,pre;
}e[maxn<<],map[maxn];
int last[maxn],dep[maxn],last1[maxn],mxpos[maxn],mxdep[maxn],bel[maxn],belong[maxn],size[maxn],fa[maxn];
int i,j,k,n,m,tot1,a,tot,K,b,ans,rt; 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){
map[++tot1].too=b;map[tot1].pre=last1[a];last1[a]=tot1;
}
void dfs(int x,int pre){
int i;size[x]=;dep[x]=dep[pre]+;fa[x]=pre;
if(dep[x]>mxdep[bel[x]])mxdep[bel[x]]=dep[x],mxpos[bel[x]]=x;
insert(bel[x],x);
for(i=last[x];i;i=e[i].pre)if(e[i].too!=pre)
dfs(e[i].too,x),size[x]+=size[e[i].too];
}
void dfs2(int x,int chain){
int i,k=;belong[x]=chain;
for(i=last[x];i;i=e[i].pre)if(e[i].too!=fa[x]&&size[e[i].too]>size[k])k=e[i].too;
if(!k)return;
dfs2(k,chain);
for(i=last[x];i;i=e[i].pre)if(e[i].too!=fa[x]&&e[i].too!=k)dfs2(e[i].too,e[i].too);
}
inline int getlcadep(int a,int b){
for(;belong[a]!=belong[b];a=fa[belong[a]])if(dep[belong[a]]<dep[belong[b]])swap(a,b);
if(dep[a]<dep[b])return dep[a];else return dep[b];
}
int main(){
n=read();K=read();
for(i=;i<=n;i++){
bel[i]=read();a=read();if(!a){rt=i;continue;}
e[++tot].too=i;e[tot].pre=last[a];last[a]=tot;
e[++tot].too=a;e[tot].pre=last[i];last[i]=tot;
}rt=n<?n>>:n>>;
dfs(rt,);dfs2(rt,rt);
for(i=;i<=K;i++){
ans=;
for(k=mxpos[i],j=last1[i];j;j=map[j].pre)ans=max(ans,dep[k]+dep[map[j].too]-(getlcadep(k,map[j].too)<<));
printf("%d\n",ans);
}
return ;
}
//链剖
链剖
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
const int maxdep=;
struct zs{
int too,pre;
}e[maxn<<],map[maxn];
int last[maxn],depth[maxn],fa[maxn][maxdep],dep[maxn],last1[maxn],mxpos[maxn],mxdep[maxn],bel[maxn];
int i,j,k,n,m,tot1,a,tot,K,b,ans,rt; 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){
map[++tot1].too=b;map[tot1].pre=last1[a];last1[a]=tot1;
}
void dfs(int x,int pre){
int i;
dep[x]=dep[pre]+;depth[x]=depth[pre];
if((dep[x]&(-dep[x]))==dep[x])depth[x]++;
if(dep[x]>mxdep[bel[x]])mxdep[bel[x]]=dep[x],mxpos[bel[x]]=x;
insert(bel[x],x);//printf("%d %d %d %d\n",x,bel[x],dep[x],depth[x]); for(i=;i<=depth[x];i++)fa[x][i]=fa[fa[x][i-]][i-];
for(i=last[x];i;i=e[i].pre)if(e[i].too!=pre)
fa[e[i].too][]=x,dfs(e[i].too,x);
}
inline int getlca(int a,int b){
int i;
if(dep[a]<dep[b])swap(a,b);
for(i=depth[a];i>=;i--)if(dep[fa[a][i]]>=dep[b])a=fa[a][i];
if(a!=b){
for(i=depth[a];i>=;i--)if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];
a=fa[a][];
}
return a;
}
int main(){
n=read();K=read();
for(i=;i<=n;i++){
bel[i]=read();a=read();if(!a){rt=i;continue;}
e[++tot].too=b=i;e[tot].pre=last[a];last[a]=tot;
e[++tot].too=a;e[tot].pre=last[b];last[b]=tot;
}depth[]=-;
dfs(rt,);
for(i=;i<=K;i++){
ans=;
for(k=mxpos[i],j=last1[i];j;j=map[j].pre)ans=max(ans,dep[k]+dep[map[j].too]-(dep[getlca(k,map[j].too)]<<));
printf("%d\n",ans);
}
return ;
}
//倍增
bzoj 1700： [Usaco2007 Jan]Problem Solving 解题
DP。。http://www.cnblogs.com/czllgzmzl/p/5068024.html
bzoj 1734： [Usaco2005 feb]Aggressive cows 愤怒的牛
傻逼题。。二分答案+判定。。。。每次二分出一个答案mid后，贪心的划分，看一下能不能划出C段
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int a[maxn];
int i,num,n,m,l,r,mid,pre;
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();
sort(a+,a++n);
if(m==){printf("%d\n",a[n]-a[]);return ;}
if(m==n){
for(l=a[n]-a[],i=;i<n;i++)if(a[i+]-a[i]<l)l=a[i+]-a[i];
printf("%d\n",l);return ;
}
l=;r=(a[n]-a[])/(m-);
while(l<r){
mid=(l+r+)>>;num=;pre=a[];
for(i=;i<=n;i++)if(a[i]-pre>=mid)pre=a[i],num++;
if(num>=m)l=mid;else r=mid-;
}
printf("%d\n",l);
return ;
}
bzoj 1741： [Usaco2005 nov]Asteroids 穿越小行星群
二分图最大匹配。。。存在小行星(i,j),连一条i到j+n的边。
dinic比匈牙利还是略慢。。
#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 1705： [Usaco2007 Nov]Telephone Wire 架设电话线
DPhttp://www.cnblogs.com/czllgzmzl/p/5068259.html
bzoj 1783： [Usaco2010 Jan]Taking Turns