edward_mj

[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;
}

[Elite 2010 January Competition Gold 【hayturn】]博弈类动态规划★★

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1783
【吐槽】
唉唉唉唉。。。
看了解题报告才会。太水了= =。。。
一开始看错题，写了个dp，样例都不过，后来看了解题报告才理解了题意。。。
囧
【算法分析】
下面基本是对解题报告的翻译：
令Fa[i]表示当前到这只牛选，选的范围是[i,n]，然后这只牛到最后最多能得到多少分？
令Fb[i]表示当前到另外一只牛选，选的范围是[i,n]，然后到最后这只牛最多能得到多少分？
然后我们应当注意到，主动权在选的那只牛手里。
现在我们有两种决策。
1、选第i格这个权。
那么Fa[i]=Fb[i+1]+w[i];
同时Fb[i]=Fa[i+1];
2、不选第i格这个权。
那么Fa[i]=Fa[i+1];
同时Fb[i]=Fb[i+1];

注意到主动权在当前选那只牛的手里，那么我们以当前选这只牛为上帝进行决策。
就是要取最大的Fa[i]。
所以只要比较Fb[i+1]+w[i]和Fa[i+1]就可以了。。。
【其它】cin取消同步以后原来不是很慢！！！就是800+MS。我用scanf也就500+MS…
当然，要G++才可以。就像外挂一样。
【CODE】
#include using namespace std;
typedef long long lld;
const lld N=705555;
lld n,w[N],Fa[N],Fb[N];

void solve(){
Fa[n]=w[n];
Fb[n]=0;
int i;
for (i=n-1;i>=1;i–)
if (Fb[i+1]+w[i]>=Fa[i+1]){
Fa[i]=Fb[i+1]+w[i];
Fb[i]=Fa[i+1];
}
else{
Fa[i]=Fa[i+1];
Fb[i]=Fb[i+1];
}
cout << Fa[1] << " " << Fb[1] << endl;
}

int main(){
ios::sync_with_stdio(false);
cin >> n;
for (lld i=1;i<=n;i++) cin >> w[i];
solve();
return 0;
}

[Elite 2010 January Competition Gold 【telephone】]树形dp

【题目链接】http://ace.delos.com/ioigate
另外八中OJ的1785也是。不过八中的可能pascal会爆栈。。。
【算法分析】
首先建议看英文，八中的翻译有点歧义。
这个一颗无根树，于是我们可以选一个非叶结点出来当根，那么就可以搞了。
然后我们注意到，如果两个叶子搞在一块的话，那么必然是连到它们的LCA那里去搞了。
如果是这样的话，如果是从某一个结点搞上它父亲那里的话，无论是哪个都是一样的。
因为都是占用父亲的链。
而且显然是越早解决越好。
于是我们直接用一个rest数组记录剩下多少个需要用连向父亲这条边来解决。
然后，都算不上dp了，就是统计算一下就可以了。
【其它】1Y
【CODE】
/*
ID:jie22221
TASK:telephone
LANG:C++
*/
#include #include #include #include using namespace std;
const int N=105555;
struct edge{int x,y,next;}g[N*2];
int n,k,e,root,ans;
int ls[N],du[N],rest[N];

void add(int x,int y){
e++;
g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}

void init(){
memset(ls,0,sizeof(ls));
memset(du,0,sizeof(du));
e=0;
scanf("%d%d",&n,&k);
for (int x,y,i=1;i scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
du[x]++; du[y]++;
}
}

void dfs(int p,int fa){
if (du[p]==1){
rest[p]=1;
return;
}
for (int t=ls[p];t;t=g[t].next)
if (g[t].y!=fa){
dfs(g[t].y,p);
rest[p]+=rest[g[t].y];
}
if (rest[p]<=2*k && rest[p]%2){
ans+=rest[p]>>1;
rest[p]=1;
}
else{
if (rest[p]>2*k) ans+=k;
else ans+=rest[p]>>1;
rest[p]=0;
}
}

void solve(){
if (n<=2){
printf("%dn",n);
return;
}
for (int i=1;i<=n;i++)
if (du[i]>1){
root=i;
break;
}
memset(rest,0,sizeof(rest));
ans=0;
dfs(root,0);
}

int main(){
init();
solve();
cout << ans << endl;
return 0;
}