分类存档：默认分类

[USACO2010 Mar Gold 【gather】]树形dp

【题目链接】http://ace.delos.com/ioiupload?init=1&a=uNRSh9JKRlk
【题目大意】
就是给一颗树，树上的点都有不同数目的奶牛。
然后边有边权。
让你选一个结点，使得所有牛到这个点走的路程之和最小。
【算法分析】
随便拿个点做根。
两次DFS。
第一次算出两个信息：
1、以该结点为根的子树上的牛的总数目。
2、该结点的子孙到该点的距离之和。
第二次算出另一个信息：
从父亲来的那部分需要的距离之和。
最后将两部分相加即可。
【其它】1Y。
【CODE】
/*
ID:jie22221
TASK:gather
LANG:C++
*/
#include #include #include #include using namespace std;
typedef long long lld;
const int N=105555;
struct edge{int x,y,w;edge *next;}*ls[N];
int n;
int c[N];
lld f[N],cow[N],From_Fa[N],ans=(lld)(1) << 60; void addedge(int x,int y,int w){
edge *t=(edge *)malloc(sizeof(edge));
t->x=x; t->y=y; t->w=w; t->next=ls[x]; ls[x]=t;
}

void init(){
ios::sync_with_stdio(false);
cin >> n;
for (int i=1;i<=n;i++) cin >> c[i];
for (int i=1,x,y,w;i cin >> x >> y >> w;
addedge(x,y,w);
addedge(y,x,w);
}
}

void predfs(int p,int fa){
cow[p]=c[p];
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa){
predfs(t->y,p);
f[p]+=cow[t->y]*t->w+f[t->y];
cow[p]+=cow[t->y];
}
}

void dfs(int p,int fa){
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa){
From_Fa[t->y]=From_Fa[p]+f[p]-f[t->y]-cow[t->y]*t->w+(cow[1]-cow[t->y])*t->w;
dfs(t->y,p);
}
ans=min(ans,From_Fa[p]+f[p]);
}

int main(){
freopen("gather.in","r",stdin);
freopen("gather.out","w",stdout);
init();
predfs(1,0);
dfs(1,0);
cout << ans << endl;
return 0;
}

[USACO2010 Feb Gold 【slowdown】]对树进行“序”的转化、树状数组

【题目链接】http://ace.delos.com/ioiupload?init=1&a=CKerK76g6Pn
or 八中
【题目大意】
给定以1为根的一棵树。点数<=10^5
然后每个点按输入顺序被染色。
每次染色前都输出，从根到该结点的路径上，有多少个点被染色过了？
【算法分析】
首先，假如一个点染色，会影响到哪些点呢？
没错，就是以他为根的子树上的所有点。
所以我们按DFS序遍历的话，会得出一张线性表，在这个表上，每一个点为根的子树就会连在一起~
进而可以用线段树或者树状数组解决。
当然，树状数组好些多了。
【其它】1Y
【CODE】
/*
ID:jie22221
TASK:slowdown
LANG:C++
*/
#include #include #include #include using namespace std;
const int N=105555;
struct edge{int y;edge *next;}*ls[N];
int n,times;
int St[N],Ed[N],w[N];

void addedge(int x,int y){
edge *t=(edge *)malloc(sizeof(edge));
t->y=y; t->next=ls[x]; ls[x]=t;
}

void init(){
memset(ls,0,sizeof(ls));
scanf("%d",&n);
for (int i=1,x,y;i scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
}

void dfs(int p,int fa){
St[p]=++times;
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa)
dfs(t->y,p);
Ed[p]=times;
}

int Get_Sum(int p){
int res=0;
for (int i=p;i;i-=i&-i)
res+=w[i];
return res;
}

void Add(int p,int x){
for (int i=p;i<=n;i+=i&-i)
w[i]+=x;
}

void solve(){
memset(w,0,sizeof(w));
for (int i=1,x;i<=n;i++){
scanf("%d",&x);
printf("%dn",Get_Sum(St[x]));
Add(St[x],1);
Add(Ed[x]+1,-1);
}
}

int main(){
freopen("slowdown.in","r",stdin);
freopen("slowdown.out","w",stdout);
init();
dfs(1,0);
solve();
return 0;
}

[USACO2010 Feb Gold 【ice】]hash+BFS+n多个二分

【题目链接】http://ace.delos.com/ioigate
八中也有
【题目大意】
给定一个无穷大的棋盘，和上面的n个石头，n<=20000。他们的坐标范围是-1e9<=x<=1e9
然后有一只牛在上面滑。
它每次可能选上下左右这4个方向滑，如果遇到石头，那么它就会停下来，并且它没办法在不遇到石头的情况下停下来。
当然了，它是不能穿越石头的。
给定起点和终点，为最少滑多少步能到达终点。
保证有解。
【算法分析】
呃，就是一最短路问题，而边权都为1，所以就只裸的BFS。
由于只能碰到石头才停下，所有最多有4*n个可达位置。
然后扩展就比较纠结。。。可能离散化比较好写，但是离散化的话还要对相隔的搞多一层。
也不是非常好处理。
我就是写了12个二分，泪流满面地1Y。
我的扩展是这样的：
开两个数组装那些石头，
第一个是x为第一关键字，y为第二关键字排序的。
第二个是y为第一关键字，x为第二关键字排序的。
然后走的时候就像前向星那样二分出x(y)相等的区间，然后再找一个y(x)刚好小于(大于)当前点的石头，扩展即可。最后利用hash判下重。。。
【其它】。。。之前代码贴错了。
【CODE】
/*
ID:jie22221
TASK:ice
LANG:C++
*/
#include #include #include #define AA (*((Node*)A))
#define BB (*((Node*)B))
using namespace std;
const int N=25555;
const int INF=0x7FFFFFFF;
const int Mod=200003;
struct Node{int x,y;}S,T,p[N],q[N],L[N*4];
struct edge{Node data;edge *next;}*ls[Mod];
int n,step[N*4],ans=INF,head,tail,fa[N*4];

void init(){
memset(ls,0,sizeof(ls));
cin >> n >> S.x >> S.y >> T.x >> T.y;
for (int i=1;i<=n;i++){
cin >> p[i].x >> p[i].y;
q[i]=p[i];
}
}

int cmp_p(const void *A,const void *B){
if (AA.x!=BB.x) return AA.x-BB.x;
return AA.y-BB.y;
}

int cmp_q(const void *A,const void *B){
if (AA.y!=BB.y) return AA.y-BB.y;
return AA.x-BB.x;
}

Node Findu(Node W){
Node res; res.x=INF;
int l,r,mid,St,Ed;
for (l=1,r=n,mid=(l+r)>>1;l if (W.y<=q[mid].y) r=mid;
else l=mid+1;
St=l;
for (l=1,r=n,mid=(l+r)>>1;l+1 if (W.y else l=mid;
if (q[r].y==W.y) l=r;
Ed=l;
if (q[l].y!=W.y || q[St].x>=W.x) return res;
for (l=St,r=Ed,mid=(l+r)>>1;l+1 if (q[mid].x else r=mid-1;
if (q[r].x res.x=q[l].x+1;
res.y=W.y;
return res;
}

Node Findd(Node W){
Node res; res.x=INF;
int l,r,mid,St,Ed;
for (l=1,r=n,mid=(l+r)>>1;l if (W.y<=q[mid].y) r=mid;
else l=mid+1;
St=l;
for (l=1,r=n,mid=(l+r)>>1;l+1 if (W.y else l=mid;
if (q[r].y==W.y) l=r;
Ed=l;
if (q[l].y!=W.y || q[Ed].x<=W.x) return res;
for (l=St,r=Ed,mid=(l+r)>>1;l if (q[mid].x>W.x) r=mid;
else l=mid+1;
res.x=q[l].x-1;
res.y=W.y;
return res;
}

Node Findl(Node W){
Node res; res.x=INF;
int l,r,mid,St,Ed;
for (l=1,r=n,mid=(l+r)>>1;l if (W.x<=p[mid].x) r=mid;
else l=mid+1;
St=l;
for (l=1,r=n,mid=(l+r)>>1;l+1 if (W.x else l=mid;
if (p[r].x==W.x) l=r;
Ed=l;
if (p[l].x!=W.x || p[St].y>=W.y) return res;
for (l=St,r=Ed,mid=(l+r)>>1;l+1 if (p[mid].y else r=mid-1;
if (p[r].y res.x=W.x;
res.y=p[l].y+1;
return res;
}

Node Findr(Node W){
Node res; res.x=INF;
int l,r,mid,St,Ed;
for (l=1,r=n,mid=(l+r)>>1;l if (W.x<=p[mid].x) r=mid;
else l=mid+1;
St=l;
for (l=1,r=n,mid=(l+r)>>1;l+1 if (W.x else l=mid;
if (p[r].x==W.x) l=r;
Ed=l;
if (p[l].x!=W.x || W.y>=p[Ed].y) return res;
for (l=St,r=Ed,mid=(l+r)>>1;l if (W.y else l=mid+1;
res.x=W.x;
res.y=p[l].y-1;
return res;
}

inline long long ABS(int x){
if (x<0) return -x;
return x;
}
inline int f(Node W){return (int)(((ABS(W.x)*17+ABS(W.y)*31)&INF)%Mod);}

bool Inhash(Node W){
for (edge *t=ls[f(W)];t;t=t->next)
if (t->data.x==W.x && t->data.y==W.y) return true;
return false;
}

void Insert(Node W){
edge *t=(edge *)malloc(sizeof(edge));
int h=f(W);
t->next=ls[h];
t->data=W;
ls[h]=t;
}

void expand(Node res){
if (res.x==INF || Inhash(res)) return;
Insert(res);
tail++;
L[tail]=res;
step[tail]=step[head]+1;
fa[tail]=head;
if (res.x==T.x && res.y==T.y)
ans=min(ans,step[tail]);
}

int solve(){
if (S.x==T.x && S.y==T.y) return 0;
L[0].x=S.x; L[0].y=S.y; step[0]=0; Insert(L[0]);
for (head=0,tail=0;head<=tail;head++){
expand(Findu(L[head]));
expand(Findd(L[head]));
expand(Findl(L[head]));
expand(Findr(L[head]));
if (ans }
return ans;
}

int main(){
freopen("ice.in","r",stdin);
freopen("ice.out","w",stdout);
ios::sync_with_stdio(false);
init();
qsort(p+1,n,sizeof(Node),cmp_p);
qsort(q+1,n,sizeof(Node),cmp_q);
cout << solve() << endl;
}

[POJ3762 The Bonus Salary!]费用流

【题目大意】
给N个时间段，每个时间段只能用一次，然后有k天供你用这些时间段。
同一天里，时间段不能有重叠。
问最多能用到多少费用？
【算法分析】
先对所有时刻进行离散化。
然后每个时刻向下一个时刻连容量为k，费用为0的边。
接着对于每个区间 [L,R]，对对应的时间连边L->R费用为区间费用，容量为1.
然后源点要退一个格子。
最后搞一个最大费用最大流就可以了。
【其它】
1CE，悲剧，POJ的iostream里不含sort函数。。。
【CODE】
#include #include #include #include #include using namespace std;
const int N=20000;
struct edge{int x,y,c,w;edge *op,*next;}g[N],*ls[N],*fa[N];
struct Node{int x,y,w;}p[N];
int n,k,tot,e,cost;
int lx[N],d[N],v[N],List[N];

void init(){
tot=0; e=0; memset(ls,0,sizeof(ls));
for (int i=1;i<=n;i++){
int h1,m1,s1,h2,m2,s2;
scanf("%d:%d:%d %d:%d:%d %d",&h1,&m1,&s1,&h2,&m2,&s2,&p[i].w);
p[i].x=h1*3600+m1*60+s1;
p[i].y=h2*3600+m2*60+s2;
lx[++tot]=p[i].x;
lx[++tot]=p[i].y;
}
}

void addedge(int x,int y,int c,int w){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].w=w; g[e].next=ls[x];
ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w; g[e].next=ls[y];
ls[y]=&g[e]; g[e].op=&g[e-1];
}

int Find(int x){
int l=1,r=tot,mid;
while (l mid=(l+r)/2;
if (x>lx[mid]) l=mid+1;
else r=mid;
}
return l;
}

void Lisan(){
sort(lx+1,lx+tot+1);
int tmp=tot,i; tot=0;
for (i=1;i<=tmp;i++)
if (!tot || lx[tot]!=lx[i]) lx[++tot]=lx[i];
for (i=1;i<=n;i++)
addedge(Find(p[i].x),Find(p[i].y),1,p[i].w);
for (i=1;i addedge(i,i+1,k,0);
addedge(0,1,k,0);
}

bool spfa(){
memset(d,200,sizeof(d));
memset(v,0,sizeof(v));
int head=0,tail=1;
List[1]=0; v[0]=1; d[0]=0;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=ls[List[head]];t;t=t->next)
if (t->c && d[t->x]+t->w>d[t->y]){
d[t->y]=d[t->x]+t->w;
fa[t->y]=t;
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
List[tail]=t->y;
}
}
v[List[head]]=0;
}
if (d[tot]<=0) return false;
return true;
}

void change(){
int nf=0x7FFFFFFF;
for (int i=tot;i;i=fa[i]->x)
if (fa[i]->c cost+=nf*d[tot];
for (int i=tot;i;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
}

void MCMF(){
cost=0;
while (spfa()) change();
}

int main(){
while (scanf("%d%d",&n,&k)!=EOF){
init();
Lisan();
MCMF();
printf("%dn",cost);
}
return 0;
}

[Elite 2010 February Competition Gold 【corral】]二进制步长分解、动态内存水过~★★

【题目链接】http://ace.delos.com/ioigate
八中也有。。。但是八中现在暂时爆了。等它好了的时候，搜索USACO2010就能很容易找到。
【算法分析】
原创傻×做法。。。
首先我们容易发现，假设对于两个围栏，如果一个包括另外一个的话，那么被包的就废了。
这样搞完以后呢，我们发现一个重要性质，假设用[l,r]来表示一个围栏，那么如果按l排序的话，那么r也是递增的！
我们先把数组复制多一次。这样就可以避免圈的情况。
题目转化成，在这个长度为2*c的长栏里，找一个长度为c的部分被完全覆盖。使之用的围栏最少。
我们很容易想到每次找下一个满足Lk<=Ri，且Lk最大的围栏来搞。
直到覆盖长度超过>=c。
那么我们设Right[i]表示对于当前这个栅栏i的下一个最优栅栏k。
然后我们解决问题时就可以枚举开头，然后一直Right下去统计就可以了。
但是会超时。
于是我们把Next[k][i]定义为i这个围栏，Right了2^k次以后到达哪一个围栏。
然后我们走的时候只要跟着这个跳着走就可以了。
于是问题可以在限定时间内水过。
【时间复杂度】O(n lg n)
【空间复杂度】O(n lg n)
【其它】
重要的是。。。USACO的内存少得可怜，我也不知道它到底有多少，反正就是会爆。。。
于是我百般无奈之下：malloc申请刚好大小的数组。
终于AC~
另外我依然不怕死地对10^5的读入用了cin。。
【时间与空间情况】
> Run 1: OK [0.011 secs, 4792 KB]
> Run 2: OK [0.022 secs, 4792 KB]
> Run 3: OK [0.011 secs, 4792 KB]
> Run 4: OK [0.011 secs, 4924 KB]
> Run 5: OK [0.000 secs, 4924 KB]
> Run 6: OK [0.011 secs, 5080 KB]
> Run 7: OK [0.032 secs, 5412 KB]
> Run 8: OK [0.130 secs, 7920 KB]
> Run 9: OK [0.248 secs, 11344 KB]
> Run 10: OK [0.248 secs, 11272 KB]
> Run 11: OK [0.259 secs, 16116 KB]
> Run 12: OK [0.238 secs, 11056 KB]
> Run 13: OK [0.248 secs, 8872 KB]
【CODE】
/*
ID:jie22221
TASK:corral
LANG:C++
*/
#include #include #include #include #include using namespace std;
const int N=105555*2;
struct Node{int p,l;}q[N];
bool del[N];
int n,c,mp;
int *Right,*next[20];

void input(){
cin >> c >> n;
for (int i=1;i<=n;i++)
cin >> q[i].p >> q[i].l;
}

bool cmp(Node A,Node B){
if (A.p!=B.p) return A.p return A.l>B.l;
}

void init(){
memset(del,false,sizeof(del));
for (int i=1;i<=n;i++){
q[i+n]=q[i];
q[i+n].p+=c;
}
for (int i=1,Max=-1;i<=2*n;i++)
if (q[i].p+q[i].l<=Max) del[i]=true;
else Max=q[i].p+q[i].l;
int tot=0;
for (int i=1;i<=2*n;i++)
if (!del[i]) q[++tot]=q[i];
n=tot;
}

void makenext(){
int i,j=1,k;
for (k=1;1< mp=k;
Right=(int*)malloc(sizeof(int)*(n+1));
for (i=0;i next[i]=(int*)malloc(sizeof(int)*(n+1));
for (i=1;i<=n;i++){
while (j Right[i]=j;
}
for (i=1;i<=n;i++)
next[0][i]=Right[i];
for (k=1;1< for (i=1;i<=n;i++)
next[k][i]=next[k-1][next[k-1][i]];
}
mp=k;
}

void work(){
int ans=0x7FFFFFFF,i,j,k,tmp,done;
for (k=1;q[k].p tmp=q[k].p+c;
done=1;
for (i=k,j=mp-1;j>=0;j–){
int &t=next[j][i];
if (q[t].p+q[t].l done+=1< i=t;
}
}
done++;
ans=min(ans,done);
}
cout << ans << endl;
}

int main(){
freopen("corral.in","r",stdin);
freopen("corral.out","w",stdout);
ios::sync_with_stdio(false);
input();
sort(q+1,q+n+1,cmp);
init();
makenext();
work();
return 0;
}