作者存档：edward_mj

[Vijos1083 小白逛公园] 【线段树维护最大子段和】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1756
【算法分析】
就是线段树动态维护最大子段和。实际易错较难的就只是update函数和找ans部分。
注意维护Lmax,Rmax,ans,Sum这4个域即可。
【其它】
1Y。
MS是oimaster大神出的题。。。但据说是动态树= =。。。貌似不是这题？好像还有小白逛公园加强版。。。不过不知道哪里有得交。。。
【CODE】
#include #include #include const int N=505555;
int n,m,res,Follow;
int w[N];
struct Node{int l,r,Lmax,Rmax,ans,Sum;}Tr[N*3];

void init(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&w[i]);
}

int max(int x,int y){return x>y?x:y;}

void update(int p){
Tr[p].Sum=Tr[p*2].Sum+Tr[p*2+1].Sum;
Tr[p].Lmax=max(Tr[p*2].Lmax,Tr[p*2].Sum+Tr[p*2+1].Lmax);
Tr[p].Rmax=max(Tr[p*2+1].Rmax,Tr[p*2+1].Sum+Tr[p*2].Rmax);
Tr[p].ans=max(Tr[p*2].ans,Tr[p*2+1].ans);
Tr[p].ans=max(Tr[p].ans,Tr[p*2].Rmax+Tr[p*2+1].Lmax);
}

void build(int p,int l,int r){
Tr[p].l=l; Tr[p].r=r;
if (l==r){
Tr[p].Lmax=Tr[p].Rmax=Tr[p].ans=Tr[p].Sum=w[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
update(p);
}

void Change(int p,int pos,int key){
if (Tr[p].l==Tr[p].r){
Tr[p].Lmax=Tr[p].Rmax=Tr[p].ans=Tr[p].Sum=key;
return;
}
int mid=(Tr[p].l+Tr[p].r)/2;
if (pos<=mid) Change(p*2,pos,key);
else Change(p*2+1,pos,key);
update(p);
}

void Get(int p,int l,int r){
if (l<=Tr[p].l && Tr[p].r<=r){
res=max(res,Tr[p].ans);
res=max(res,Tr[p].Lmax+Follow);
Follow=max(Tr[p].Rmax,Tr[p].Sum+Follow);
return;
}
int mid=(Tr[p].l+Tr[p].r)/2;
if (l<=mid) Get(p*2,l,r);
if (r> mid) Get(p*2+1,l,r);
}

void solve(){
int op,x,y,i;
for (i=1;i<=m;i++){
scanf("%d%d%d",&op,&x,&y);
if (op==1){
res=-0x7FFFFFFF; Follow=0;
if (x>y){x^=y; y^=x; x^=y;}
Get(1,x,y);
printf("%dn",res);
}
else Change(1,x,y);
}
}

int main(){
init();
build(1,1,n);
solve();
}

[Sdoi2010]魔法猪学院 【A*搜索】【堆】【K短路】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1975
【算法分析】
股价函数设为Dis(i,n)。
然后直接A*不用判重。
【其它】没有1Y。大家来BS我。。。第一次到CENA上测，90分。。。泪流满面。后来发现有个非常小的细节搞错了。。。然后这个细节如果不是刻意去搞的话，随即数据基本不可能出错，于是得了90分。
改了以后就Y了。
【CODE】
#include #include #include #include #define clr(a) memset(a,0,sizeof(a))
using namespace std;
const int N=5005;
const int E=200005;
const int MaxL=2000005;
const double INF=1e40;
struct edge{int x,y;double w;edge *next;}g[E],*ls[N];
int n,m,e,cnt;
int L[N],v[N];
double Limit,d[N];

void addedge(int x,int y,double w){
g[++e].x=x; g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=&g[e];
}

void init(){
int i,x,y;
double w;
e=cnt=0; clr(ls);
scanf("%d%d%lf",&n,&m,&Limit);
for (i=0;i scanf("%d%d%lf",&x,&y,&w);
addedge(y,x,w);
}
}

void spfa(){
int head=0,tail=1;
for (int i=1;i<=n;i++) d[i]=INF;
clr(v);
d[n]=0; v[n]=1;
L[1]=n;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=ls[L[head]];t;t=t->next)
if (d[t->x]+t->w d[t->y]=d[t->x]+t->w;
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
L[tail]=t->y;
}
}
v[L[head]]=0;
}
}

void Graph_op(){
int tmp=e;
e=0; clr(ls);
for (int i=1;i<=tmp;i++)
addedge(g[i].y,g[i].x,g[i].w);
}

struct Node{double w;int p;};
struct Heap_t{
Node a[MaxL];
int tot;
void up(int k){
while (k>1 && a[k].w swap(a[k],a[k>>1]);
k>>=1;
}
}

void down(int k){
int p;
while ((k<<1)<=tot){
p=k<<1;
p+=(p if (a[p].w swap(a[p],a[k]);
k=p;
}else break;
}
}

void Insert(int p,double w){
if (w>Limit) return;
tot++;
a[tot].p=p;
a[tot].w=w;
up(tot);
}

void Del(int p){
swap(a[p],a[tot]);
tot–;
down(p);
up(p);
}
}Heap;

void A_star(){
Heap.tot=0;
Heap.Insert(1,d[1]);
Node T;
while (Heap.tot && Heap.a[1].w<=Limit){
T=Heap.a[1];
Heap.Del(1);
if (T.p==n){
cnt++;
Limit-=T.w;
}
else
for (edge *t=ls[T.p];t;t=t->next)
Heap.Insert(t->y,T.w-d[T.p]+t->w+d[t->y]);
}
printf("%dn",cnt);
}

int main(){
init();
spfa();
Graph_op();
A_star();
}

[NOI2009]植物大战僵尸 【拓扑排序】【最大权闭合图】【网络流】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1565
【算法分析】
恩，就是比较裸的最大权闭合图，但是要知道如果形成环的话，网络流是处理不了的。
于是拓扑排序去环，然后最大权闭合图。
【其它】
今天见到NOI2009那里居然有一题未A= =，于是写一个练练手。
1Y。
NOI2009里的送分题。
【CODE】
#include #include const int N=1000;
const int E=1005555;
struct edge{int x,y,c;edge *next,*op;};
struct Node{int x,y;Node *next;};
struct Lint_t{
Node *ls[N],g[E];
int e;
void addedge(int x,int y){
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=&g[e];
}
}Link;
struct Network_t{
int Flow,e,S,T;
edge *ls[N],*fa[N],*cur[N],g[E];
int num[N],d[N];
void addedge(int x,int y,int c){
g[++e].x=x; g[e].y=y; g[e].c=c; 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].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
}

void relabel(int k){
cur[k]=ls[k];
int mm=T;
for (edge *t=ls[k];t;t=t->next)
if (t->c && d[t->y] mm=d[t->y];
d[k]=mm+1;
}

void change(){
int nf=0x7FFFFFFF;
for (int i=T;i!=S;i=fa[i]->x)
if (fa[i]->c for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
Flow+=nf;
}

void sap(){
int i;
Flow=0;
for (i=S;i<=T;i++) {
num[i]=0;
d[i]=0;
cur[i]=ls[i];
}
i=S;
while (d[S]<=T){
edge *&t=cur[i];
for (;t;t=t->next)
if (t->c && d[t->y]+1==d[t->x]) break;
if (t){
fa[t->y]=t;
i=t->y;
if (i==T){
change();
i=S;
}
}
else{
if (! –num[d[i]]) break;
relabel(i);
++num[d[i]];
if (i!=S) i=fa[i]->x;
}
}
}
}Network;

int n,m,Sum;
int W[N],pos[50][50],L[N],du[N],v[N];

void init(){
scanf("%d%d",&m,&n);
int cnt=0,i,j,k,x,y;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
pos[i][j]=++cnt;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++){
scanf("%d%d",&W[pos[i][j]],&cnt);
for (k=0;k scanf("%d%d",&x,&y);
x++; y++;
Link.addedge(pos[i][j],pos[x][y]);
du[pos[x][y]]++;
}
if (j>1){
Link.addedge(pos[i][j],pos[i][j-1]);
du[pos[i][j-1]]++;
}
}
}

void topsort(){
int head=0,tail=0,i;
n*=m;
for (i=1;i<=n;i++)
if (!du[i]) L[++tail]=i;
while (head!=tail){
head++;
for (Node *t=Link.ls[L[head]];t;t=t->next){
du[t->y]–;
if (!du[t->y]) L[++tail]=t->y;
}
}
memset(v,0,sizeof(v));
for (int i=1;i<=tail;i++)
v[L[i]]=1;
}

void build(){
Network.S=0; Network.T=n+1;
Sum=0;
for (int i=1;i<=n;i++) if (v[i]){
for (Node *t=Link.ls[i];t;t=t->next)
if (v[t->y])
Network.addedge(t->y,i,0x7FFFFFFF);
if (W[i]>0){
Network.addedge(0,i,W[i]);
Sum+=W[i];
}
else Network.addedge(i,n+1,-W[i]);
}
}

int main(){
Link.e=Network.e=0;
memset(Link.ls,0,sizeof(Link.ls));
memset(Network.ls,0,sizeof(Network.ls));
init();
topsort();
build();
Network.sap();
printf("%dn",Sum-Network.Flow);
}

[POI2009]石子游戏Kam 【博弈】【分组】★★

【题目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1115
【算法分析】
先假设n为偶数，然后对于任意偶数i<=n，都满足a[i]=a[i-1]。
那么显然先手只能取奇数位置a[j]的石头。然后后手必然可以取同样数量的a[j+1]。那么最后必然是后手的取完石头。所以先手必败。

对于n为偶数时的一般情况，依然是连续的每两个分组。
我们可以将这个模型分成两部分，一部分是a[i-1]=a[i]的，另一部分是a[i]-a[i-1]。（i为偶数）
然后一部分用前面那个解决，后者，将两堆合成一个整体看，就变成一般的NIM游戏了！
于是利用SG函数那个xor定理就可以解决了。。
【CODE】
#include int Tc,n,i,ans,a[1005];
int main(){
scanf("%d",&Tc);
for (;Tc;Tc–){
scanf("%d",&n);
for (i=0;i if (n%2) ans=a[0]; else ans=0;
for (i=n-1;i>0;i-=2) ans^=(a[i]-a[i-1]);
if (ans) puts("TAK");
else puts("NIE");
}
}

[JSOI2008]星球大战starwar 【并差集】【逆序处理】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1015
【算法分析】
就是逆过来，把拆分变成合并，用并差集即可。
【其它】= =1RE。n<=2m我还以为是他搞错了压在一起。。。
【CODE】
#include #include #include using namespace std;
const int N=405555;
struct edge{int y;edge *next;}g[405555],*ls[N];
int n,m,ans,e,Qn;
int F[N],Num[N],Q[N],v[N],reply[N];

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

int GF(int k){
int res,i,tmp;
for (i=k;F[i]!=i;i=F[i]);
res=i;
for (i=k;F[i]!=i;tmp=F[i],F[i]=res,i=tmp);
return res;
}

int main(){
e=0;
memset(ls,0,sizeof(ls));
memset(v,0,sizeof(v));
int x,y,i;
scanf("%d%d",&n,&m);
for (i=0;i scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for (i=0;i F[i]=i;
Num[i]=1;
}
scanf("%d",&Qn);
ans=n;
for (i=0;i scanf("%d",&Q[i]);
if (!v[Q[i]]) ans–;
v[Q[i]]++;
}
for (i=0;i for (edge *t=ls[i];t;t=t->next)
if (!v[t->y] && GF(i)!=GF(t->y)){
ans–;
x=F[i]; y=F[t->y];
if (Num[x]>Num[y]) swap(x,y);
F[x]=y;
Num[y]+=Num[x];
}
reply[Qn]=ans;
for (i=Qn-1;i>=0;i–){
v[Q[i]]–;
if (!v[Q[i]]){
ans++;
for (edge *t=ls[Q[i]];t;t=t->next)
if (!v[t->y] && GF(Q[i])!=GF(t->y)){
ans–;
x=F[Q[i]]; y=F[t->y];
if (Num[x]>Num[y]) swap(x,y);
F[x]=y;
Num[y]+=Num[x];
}
}
reply[i]=ans;
}
for (int i=0;i<=Qn;i++) printf("%dn",reply[i]);
}