NOI题乱做
HJWJBSR
posted @ 2015年6月15日 11:50
in 题解
, 346 阅读
RT，放些最近写的NOI老题。
BZOJ3668起床困难综合症
直接爆搞
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100050
#define INF 0x7f7f7f7f
#define ll long long
ll a[N][2],n,m,ans=0,ss,t=0;
inline ll aa(int x)
{
ll i,j,k,l,q,w,e=x;
for (i=1;i<=n;i++)
if (a[i][0]==1)
e=e&(a[i][1]&ss);else
e=a[i][0]==2?e^(a[i][1]&ss):e|(a[i][1]&ss);
return e;
}
int main()
{
ll i,j,k,l,q,w,e;
char b[20];
memset(a,0,sizeof(a));
scanf("%lld%lld",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%s%lld",b,&a[i][1]);
if (b[0]=='A'&&b[1]=='N')
a[i][0]=1;else
a[i][0]=b[0]=='X'&&b[1]=='O'?2:3;
}
for (ss=1 << 29;ss;ss >>= 1)
{
i=aa(0);
j=t+ss>m?-1:aa(ss);
if (i>=j)
ans+=i;else
ans+=j,t+=ss;
}
cout <<ans<<endl;
return 0;
}
BZOJ3669魔法森林：LCT
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define INF 0x7f7f7f7f
struct Line
{
int s,v,a1,b1;
} a[N];
int c[N][2],t[N],fa[N],rf[N],ft[N],ma[N];
int n,m,ans=INF,ss;
bool fz[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=(x << 3)+(x << 1)+y-'0',y=getchar();
while (y>='0'&&y<='9');
return x;
}
inline bool cmp(Line x,Line y)
{
return x.a1<y.a1;
}
inline void Update(int x)
{
ma[x]=max(ma[c[x][0]],max(ma[c[x][1]],x>n?t[x]:-INF));
return;
}
inline void fzj(int x)
{
if (!x||!fz[x])
return;
fz[c[x][0]]=!fz[c[x][0]];fz[c[x][1]]=!fz[c[x][1]];
swap(c[x][0],c[x][1]);
fz[0]=fz[x]=0;
return;
}
inline void Rotate(int x)
{
int i=fa[x],j=fa[fa[x]],k=x==c[i][0];
if (j)
c[j][c[j][1]==i]=x;else
rf[x]=rf[i],rf[i]=0;
fa[c[x][k]]=c[x][k]?i:0;
c[i][1-k]=c[x][k];fa[i]=x;
c[x][k]=i;fa[x]=j;
Update(i);
return;
}
inline void DFS(int x)
{
if (fa[x])
DFS(fa[x]);
fzj(x);fzj(c[x][0]);fzj(c[x][1]);
return;
}
inline void Splay(int x)
{
DFS(x);
while (fa[x])
{
if (fa[fa[x]])
Rotate(c[fa[fa[x]]][0]==fa[x]^c[fa[x]][0]==x?x:fa[x]);
Rotate(x);
}
Update(x);
return;
}
inline void Access(int x)
{
int i=0;
while (x)
{
Splay(x);
rf[c[x][1]]=fa[i]=x;
fa[c[x][1]]=rf[i]=0;
c[x][1]=i;Update(x);
i=x;x=rf[x];
}
rf[0]=fa[0]=0;
return;
}
inline void Cg_rt(int x)
{
Access(x);Splay(x);
fz[x]=1;fzj(x);
return;
}
inline void Line(int x,int y)
{
Cg_rt(x);rf[x]=y;
return;
}
inline void Delete(int x)
{
Splay(x);fa[c[x][0]]=fa[c[x][1]]=0;
c[x][0]=c[x][1]=0;
return;
}
inline int Lma(int x)
{
if (ma[x]==t[x])
return x;else
return ma[c[x][0]]==ma[x]?Lma(c[x][0]):Lma(c[x][1]);
}
inline int Find(int x)
{
if (x==ft[x])
return x;
ft[x]=Find(ft[x]);
return ft[x];
}
int main()
{
int i,j,k,l,q,w,e;
memset(t,0,sizeof(t));memset(c,0,sizeof(c));
memset(fa,0,sizeof(fa));memset(rf,0,sizeof(rf));
memset(ft,0,sizeof(ft));memset(ma,0,sizeof(ma));
memset(fz,0,sizeof(fz));
scanf("%d%d",&n,&m);
ma[0]=-INF;
for (i=1;i<=n;i++)
ft[i]=i;
ss=n;
for (i=1;i<=m;i++)
scanf("%d%d%d%d",&a[i].s,&a[i].v,&a[i].a1,&a[i].b1);
sort(a+1,a+m+1,cmp);
for (i=1;i<=m;i++)
if (a[i].s!=a[i].v)
{
k=Find(a[i].s);l=Find(a[i].v);
if (k!=l)
{
ft[k]=l;t[++ss]=ma[ss]=a[i].b1;
Line(a[i].s,ss);Line(a[i].v,ss);
}else
{
Cg_rt(a[i].s);Access(a[i].v);Splay(a[i].v);
k=Lma(a[i].v);
if (t[k]>a[i].b1)
{
Delete(k);ma[k]=t[k]=a[i].b1;
Line(a[i].s,k);Line(a[i].v,k);
}
}
if (Find(1)==Find(n))
{
Cg_rt(1);Access(n);Splay(n);
ans=min(ans,a[i].a1+t[Lma(n)]);
}
}
ans=ans==INF?-1:ans;
cout <<ans<<endl;
return 0;
}
BZOJ3670动物园：建一棵Fail树（貌似也有的叫KMP自动机？），然后我写了个倍增，但是怎么调都只有60分（明明在本机上用同一组数据是答案正确的但是uoj上怎么都会错是smg？）。感觉最近都是的，未免对这种复杂度太有自信了吧= =，结果好几次都没去想正解就直接贴这种挂的代码。然后想线性的做法，en，没想出来，orzei了hzwer的（wulala说这个还算不难想吧，我思维弱已经成了常态了么= =），然后发现它确实是有性质的（还是看代码吧= =），然后可以搞到线性的。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1000050
#define M 1000000007
#define ll long long
ll ans;
int la[N],h[N],n,m,t;
char b[N];
int main()
{
int i,j,k,l,q,w,e;
memset(la,0,sizeof(la));memset(h,0,sizeof(h));
scanf("%d ",&t);
while (t--)
{
gets(b);n=strlen(b);h[1]=ans=1;
for (i=2;i<=n;i++)
{
k=la[i-1];
while (k&&b[k]!=b[i-1]) k=la[k];
if (b[k]==b[i-1]) la[i]=k+1;else la[i]=0;
h[i]=h[la[i]]+1;
}
k=0;
for (i=2;i<=n;i++)
{
while (k&&b[k]!=b[i-1]) k=la[k];
if (b[k]==b[i-1]) k++;
while (k>(i>>1)) k=la[k];
ans=(ans*(h[k]+1))%M;
}
printf("%lld\n",ans);
}
return 0;
}
BZOJ3671随机数生成器：感觉题目一大串其实还不就是暴力，但是各种时间空间卡常数卡的丧心病狂，一开始用函数递归打标记MLE，然后用queue也是挂，然后换成了数组，最后把快读的变量都考虑进去了，都过不了= =，后来知道了还是要对于每一行维护左右边界，虽然复杂度一样，但是比起我这种常数还是要小些。
#include <iostream>
#include <string.h>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define N 5050
#define ll long long
struct Point
{
int a1,a2;
};
ll a,b,c,d,x0;
int n,m,nm,wz[N*N],t[N*N],le[N],ri[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void Sign(int x,int y)
{
for (int i=1;i<=n;i++)
if (i<x) ri[i]=min(ri[i],y);else
if (i>x) le[i]=max(le[i],y);
return;
}
int main()
{
ll i,j,k,l,q,w,e;
cin >>x0>>a>>b>>c>>d>>n>>m>>nm;k=n*m;e=n+m-1;
for (i=1;i<=k;i++) t[i]=i;
for (i=1;i<=k;i++)
x0=((a*x0+b)*x0+c)%d,swap(t[x0%i+1],t[i]);
for (i=1;i<=nm;i++)
swap(t[q=Read()],t[l=Read()]);
for (i=1;i<=n;i++)
le[i]=1,ri[i]=m;
for (i=1;i<=k;i++)
wz[t[i]]=i;
for (i=1;i<=k;i++)
{
q=(wz[i]-1)%m+1;w=(wz[i]-1)/m+1;
if (q>=le[w]&&q<=ri[w])
{
if (--e)
printf("%d ",i);else
{printf("%d\n",i);break;}
Sign(w,q);
}
}
return 0;
}
BZOJ3240矩阵游戏：总记得之前分析过复杂度，总觉得是可以过的= =后来猜结论发现可以套费马小定理上去，然后就高精度都不用就水过了。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 1000000007
#define ll long long
#define ld long double
struct Point
{
ll a1,a2;
};
Point Read()
{
ll x=0,z=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=(x*10+y-'0')%(M-1),z=(z*10+y-'0')%M,
y=getchar(); while (y>='0'&&y<='9');
return (Point){x,z};
}
inline ll Quick_Multi(ll x,ll y)
{
ll i=x*y-(ll)((ld)x/M*y+1e-9)*M;
return i<0?i+M:i;
}
inline Point Multi(Point x,Point y)
{
return (Point){Quick_Multi(x.a1,y.a1),
(Quick_Multi(x.a2,y.a1)+y.a2)%M};
}
Point Quick_Mi(Point x,ll y)
{
Point z;z.a1=1;z.a2=0;
while (y)
{
if (y&1) z=Multi(z,x);
x=Multi(x,x);
y >>= 1;
}
return z;
}
int main()
{
int i,j;Point k,l,q,w,e,n,m;
n=Read();m=Read();k.a1=(e=Read(),e.a1);k.a2=(e=Read(),e.a1);
l.a1=(e=Read(),e.a1);l.a2=(e=Read(),e.a1);
q=k.a1!=1?Quick_Mi(k,(m.a1+M-2)%(M-1)):
(Point){1,((m.a2-1)*k.a2)%M};
w=Multi(q,l);
w=w.a1!=1?Quick_Mi(w,(n.a1+M-2)%(M-1)):
(Point){1,((n.a2-1)*w.a2)%M};
w=Multi(w,q);
cout <<(w.a1+w.a2)%M<<endl;
return 0;
}
BZOJ2875随机数生成器：裸矩乘
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long
struct Point
{
ll a1,a2;
};
ll n,m,s;
inline ll Multi(ll x,ll y)
{
ll z=0;
while (y)
{
if (y&1) z=(z+x)%m;
x=(x+x)%m;
y >>= 1;
}
return z;
}
inline Point Mult(Point x,Point y)
{
return (Point){Multi(x.a1,y.a1),(Multi(x.a2,y.a1)+y.a2)%m};
}
inline Point Quick_mi(Point x,ll y)
{
Point z;z.a1=1;z.a2=0;
while (y)
{
if (y&1) z=Mult(z,x);
x=Mult(x,x);
y >>= 1;
}
return z;
}
int main()
{
int i,j;ll k,l;Point q,w,e;
cin >>m>>q.a1>>q.a2>>k>>n>>s;
q=Quick_mi(q,n);
k=((Multi(q.a1,k)+q.a2)%m)%s;
cout <<k<<endl;
}
BZOJ2878迷失游乐园：如果是树就是树形DP，否则环上情况特殊考虑，由于环很小甚至环上可以有k^2级别的处理。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100050
#define ld long double
double h[N],s[N],ans,v[N];
int fi[N],c[N*2][3],ss=1,n,m,cl[N],d[N],le,ri,li[N];
bool b[N],f[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
d[x]++;d[y]++;
return;
}
double DF1(int x,int y)
{
int l=0;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=y&&!b[c[i][0]])
h[x]+=c[i][2]+DF1(c[i][0],x),l++;
return l?(h[x]/=l):0;
}
void DS1(int x,int y,int z)
{
int i;double j=h[x];
h[x]=0;
for (i=fi[x];i;i=c[i][1])
if (c[i][0]!=y) h[x]+=h[c[i][0]]+c[i][2];
if (y)
h[x]+=z+(d[y]>1?(h[y]-j-z)/(d[y]-1):0);
ans+=h[x]/d[x];
for (i=fi[x];i;i=c[i][1])
if (c[i][0]!=y)
DS1(c[i][0],x,c[i][2]);
return;
}
void So1()
{
DF1(n,0);
DS1(n,0,0);
printf("%.8lf\n",ans/n);
return;
}
bool Find(int x,int y,int z)
{
b[li[y]=x]=1;
for (int i=fi[x];i;i=c[i][1])
if (b[c[i][0]]&&(i^1)!=z)
{
le=c[i][0];li[ri=y]=i;return 1;
}else
if (!b[c[i][0]]&&(li[y]=i,Find(c[i][0],y+1,i))) return 1;
return 0;
}
double DF2(int x)
{
int i,j,k,l=0;double q,w,e=0;
f[x]=1;
for (i=fi[x];i;i=c[i][1])
if (b[c[i][0]]&&!f[c[i][0]])
e+=c[i][2]+DF2(c[i][0]),l++;else
if (!b[c[i][0]])
e+=h[c[i][0]]+c[i][2],l++;
if (!l) l=1;
f[x]=0;v[x]=e;
return e/l;
}
void So2()
{
int i,j,k,l,q,w,e;
Find(1,1,0);
for (i=ri;i&&c[li[i-1]][0]!=le;i--);
if (!i) i++;
memset(b,0,sizeof(b));
for (j=i;j<=ri;j++) b[li[j-i+1]=c[li[j]][0]]=1;
for (j=1,ri=ri-i+1;j<=ri;j++)
DF1(li[j],0);
for (i=1;i<=ri;i++)
h[li[i]]=DF2(li[i]),ans+=h[li[i]],h[li[i]]=v[li[i]];
for (i=1;i<=ri;i++)
for (j=fi[li[i]];j;j=c[j][1])
if (!b[c[j][0]])
DS1(c[j][0],li[i],c[j][2]);
printf("%.8lf\n",ans/n);
return;
}
int main()
{
int i,j,k,l,q,w,e;
scanf("%d%d",&n,&m);ans=0;
for (i=1;i<=m;i++)
q=Read(),w=Read(),e=Read(),Line(q,w,e);
if (m<n)
So1();else
So2();
return 0;
}
BZOJ2877魔幻棋盘：
没看出来，感觉二维差分是很神啊，具体题解移步这里，然后就是写一个二维线段树了= =
然而中间有一个地方写挂了一直没调出来wa了几次真是羞耻= =不过感觉还是很容易写挂啊
而且40+个if真是sxbk。也不知道网上有的人写400+是怎么做到的（以前我好像写裸的splay也写过400+现在感觉真是厉害）
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 500050
#define ll long long
ll t,n,m,X,Y,st=0,ss=0,d[N*5],s=0,INF=100000000151234567;
struct Seg_Tree
{
ll v;Seg_Tree* c[2];
} b[N*10];
struct Ment_Tree
{
Seg_Tree* t;Ment_Tree* c[2];
} a[N*4];
inline ll Read()
{
ll x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);}
inline ll Num(int x,int y)
{return d[(x-1)*m+y];}
inline ll Abs(ll x)
{return x<0?-x:x;}
inline ll Calc(int x,int y)
{
if (x<X&&y<Y) return Num(x,y)-Num(x+1,y)-Num(x,y+1)+Num(x+1,y+1);
if (x>X&&y<Y) return Num(x,y)-Num(x-1,y)-Num(x,y+1)+Num(x-1,y+1);
if (x<X&&y>Y) return Num(x,y)-Num(x+1,y)-Num(x,y-1)+Num(x+1,y-1);
if (x>X&&y>Y) return Num(x,y)-Num(x-1,y)-Num(x,y-1)+Num(x-1,y-1);
if (x==X&&y==Y) return Num(x,y);
if (x==X&&y<Y) return Num(x,y)-Num(x,y+1);
if (x==X&&y>Y) return Num(x,y)-Num(x,y-1);
if (x<X&&y==Y) return Num(x,y)-Num(x+1,y);
return Num(x,y)-Num(x-1,y);
}
Seg_Tree* DSF(int x,int y,int z)
{
int i=(x+y)/2,j=++st;
if (x==y) b[j].v=Calc(z,x),b[j].c[0]=b[j].c[1]=NULL;else
b[j].c[0]=DSF(x,i,z),b[j].c[1]=DSF(i+1,y,z),
b[j].v=gcd(b[j].c[0]->v,b[j].c[1]->v);
return &b[j];
}
Seg_Tree* Merge(int x,int y,Seg_Tree* z,Seg_Tree* o)
{
int i=(x+y)/2,j=++st;
b[j].v=gcd(z->v,o->v);
if (x==y) b[j].c[0]=b[j].c[1]=NULL;else
b[j].c[0]=Merge(x,i,z->c[0],o->c[0]),
b[j].c[1]=Merge(i+1,y,z->c[1],o->c[1]);
return &b[j];
}
Ment_Tree* DFS(int x,int y)
{
int i=(x+y)/2,j=++ss;
if (x==y)
a[j].t=DSF(1,m,x);else
a[j].c[0]=DFS(x,i),a[j].c[1]=DFS(i+1,y),
a[j].t=Merge(1,m,a[j].c[1]->t,a[j].c[0]->t);
return &a[j];
}
ll QueSeg(int x,int y,Seg_Tree* z,int o,int p)
{
int i=(x+y)/2;ll j=-INF,k=-INF;
if (x==o&&y==p) return z->v;
if (o<=i) j=QueSeg(x,i,z->c[0],o,min(p,i));
if (p>i) k=QueSeg(i+1,y,z->c[1],max(o,i+1),p);
if (j==-INF) return k;else
return k==-INF?j:Abs(gcd(k,j));
}
ll QueMent(int x,int y,Ment_Tree* z,int o,int p,int u,int v)
{
int i=(x+y)/2;ll j=-INF,k=-INF;
if (x==o&&y==p) return QueSeg(1,m,z->t,u,v);
if (o<=i) j=QueMent(x,i,z->c[0],o,min(p,i),u,v);
if (p>i) k=QueMent(i+1,y,z->c[1],max(o,i+1),p,u,v);
if (j==-INF) return k;else
return k==-INF?j:Abs(gcd(k,j));
}
void ModiSeg(int x,int y,Seg_Tree* z,int o,ll p)
{
int i=(x+y)/2;
if (x==y) {z->v+=p;return;}
if (o<=i) ModiSeg(x,i,z->c[0],o,p);else
ModiSeg(i+1,y,z->c[1],o,p);
z->v=gcd(z->c[0]->v,z->c[1]->v);
return;
}
void Modify(int x,int y,Seg_Tree* z,Seg_Tree* o,Seg_Tree* p,ll u)
{
int i=(x+y)/2;
z->v=gcd(o->v,p->v);
if (x==y) return;
if (u<=i) Modify(x,i,z->c[0],o->c[0],p->c[0],u);else
Modify(i+1,y,z->c[1],o->c[1],p->c[1],u);
return;
}
void ModiMent(int x,int y,Ment_Tree* z,int o,int p,ll u)
{
int i=(x+y)/2;
if (x==y) {ModiSeg(1,m,z->t,p,u);return;}
if (o<=i) ModiMent(x,i,z->c[0],o,p,u);else
ModiMent(i+1,y,z->c[1],o,p,u);
Modify(1,m,z->t,z->c[0]->t,z->c[1]->t,p);
return;
}
void Revise()
{
ll i,j,k=Read(),q=Read(),l=Read(),w=Read(),e=Read();
if (k<=X&&l>=X&&q<=Y&&w>=Y) ModiMent(1,n,&a[1],X,Y,e);
if (k<=X&&l>=X&&q<=Y&&q-1) ModiMent(1,n,&a[1],X,q-1,-e);
if (k<=X&&l>=X&&w>=Y&&w!=m) ModiMent(1,n,&a[1],X,w+1,-e);
if (k<=X&&l>=X&&q>Y) ModiMent(1,n,&a[1],X,q,e);
if (k<=X&&l>=X&&w<Y) ModiMent(1,n,&a[1],X,w,e);
if (q<=Y&&w>=Y&&k<=X&&k-1) ModiMent(1,n,&a[1],k-1,Y,-e);
if (q<=Y&&w>=Y&&l>=X&&l!=n) ModiMent(1,n,&a[1],l+1,Y,-e);
if (q<=Y&&w>=Y&&k>X) ModiMent(1,n,&a[1],k,Y,e);
if (q<=Y&&w>=Y&&l<X) ModiMent(1,n,&a[1],l,Y,e);
if (k<=X&&q<=Y&&k-1&&q-1) ModiMent(1,n,&a[1],k-1,q-1,e);
if (k<=X&&q>Y&&k-1) ModiMent(1,n,&a[1],k-1,q,-e);
if (k>X&&q<=Y&&q-1) ModiMent(1,n,&a[1],k,q-1,-e);
if (k>X&&q>Y) ModiMent(1,n,&a[1],k,q,e);
if (k<=X&&w>=Y&&k-1&&w!=m) ModiMent(1,n,&a[1],k-1,w+1,e);
if (k<=X&&w<Y&&k-1) ModiMent(1,n,&a[1],k-1,w,-e);
if (k>X&&w>=Y&&w!=m) ModiMent(1,n,&a[1],k,w+1,-e);
if (k>X&&w<Y) ModiMent(1,n,&a[1],k,w,e);
if (l>=X&&q<=Y&&l!=n&&q-1) ModiMent(1,n,&a[1],l+1,q-1,e);
if (l>=X&&q>Y&&l!=n) ModiMent(1,n,&a[1],l+1,q,-e);
if (l<X&&q<=Y&&q-1) ModiMent(1,n,&a[1],l,q-1,-e);
if (l<X&&q>Y) ModiMent(1,n,&a[1],l,q,e);
if (l>=X&&w>=Y&&l!=n&&w!=m) ModiMent(1,n,&a[1],l+1,w+1,e);
if (l>=X&&w<Y&&l!=n) ModiMent(1,n,&a[1],l+1,w,-e);
if (l<X&&w>=Y&&w!=m) ModiMent(1,n,&a[1],l,w+1,-e);
if (l<X&&w<Y) ModiMent(1,n,&a[1],l,w,e);
return;
}
int main()
{
ll i,j,k,l,q,w,e;
n=Read();m=Read();X=Read();Y=Read();t=Read();
for (i=1;i<=n*m;i++) d[i]=Read();
DFS(1,n);
for (i=1;i<=t;i++)
if (!Read())
{
k=Read(),l=Read(),q=Read(),w=Read(),s++,
printf("%lld\n",QueMent(1,n,&a[1],X-k,X+q,Y-l,Y+w));
}else
Revise();
return 0;
}
BZOJ2435道路修建：
做法一眼，但是之前一直不知道递归层数5w+就会爆炸的【捂脸贼】，所以搞成DFS序再搞
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1000050
#define ll long long
ll ans=0;
int c[N*2][3],b[N],fa[N],fi[N],s[N],a[N],n,m,ss=1;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
return;
}
void BFS()
{
int i,j,k,l,q,w,e,ri=1;
b[1]=1;fa[1]=-1;
for (i=1;i<=n;i++)
{
for (j=fi[b[i]];j;j=c[j][1])
if (!fa[c[j][0]])
fa[c[j][0]]=b[i],b[++ri]=c[j][0],
a[c[j][0]]=c[j][2];
s[i]=1;
}
for (i=n;i>=1;i--)
for (j=fi[b[i]];j;j=c[j][1])
if (c[j][0]!=fa[b[i]])
s[b[i]]+=s[c[j][0]];
for (i=2;i<=n;i++)
ans+=(ll)(a[i])*abs(n-s[i]*2);
return;
}
int main()
{
int i,j,k,l,q,w,e;
n=Read();
for (i=1;i<n;i++)
q=Read(),w=Read(),e=Read(),Line(q,w,e);
BFS();
cout <<ans<<endl;
return 0;
}
BZOJ2434阿狸的打字机：
首先AC自动机是肯定的，但是爆力kmp会挂。所以考虑优化，首先询问可以变成y串上面有多少个i使得yi可以通过fail指针转移到x串的末尾，所以考虑建fail树，然后维护关于DFS序的线段树，初始权值全部为0，在AC自动机上DFS，每经过一个点就使其权值加1，遇到询问就查询x串末尾所对应的子树和，离开时也要权值-1。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define N 100050
#define ll long long
int n,m,ss=0,qu[N][3],fi[N],li[N],s=0,sg[N][2];char d[N];
int fr[N],nr[N];
queue <int> list;
struct Trie
{
int fa[N],ne[N],fi[N],v[N];
} a;
struct Fail
{
int fa[N],ne[N],fi[N];
} b;
struct Segment_Tree
{
int c[N*3][2],s[N];
} c;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
/*
void DFF(int x)
{
cout <<x<<' '<<b.fa[x]<<' '<<b.ne[x]<<' '<<b.fi[x]<<endl;
if (b.fi[x]) DFF(b.fi[x]);
if (b.ne[x]) DFF(b.ne[x]);
return;
}*/
inline void Get(int x,int y)
{
b.fa[x]=y;b.ne[x]=b.fi[y];b.fi[y]=x;return;
}
void Set_Up()
{
int i,j,k,l,q,w,e;
list.push(0);
while (!list.empty())
{
k=list.front();list.pop();
for (i=a.fi[k];i;i=a.ne[i])
{
list.push(i);q=b.fa[k];
while (q)
{
for (j=a.fi[q];j;j=a.ne[j])
if (a.v[j]==a.v[i])
{Get(i,j);break;}
if (b.fa[i]) break;
q=b.fa[q];
}
if (!q&&!b.fa[i])
{
for (j=a.fi[0];j;j=a.ne[j])
if (a.v[j]==a.v[i]&&i!=j)
{Get(i,j);break;}
if (!b.fa[i]) Get(i,0);
}
}
}
return;
}
void Set_up()
{
int i,j,k,l,q,w,e=0;
for (i=0;i<n;i++)
if (d[i]=='B') e=a.fa[e];else
if (d[i]=='P')
li[++s]=e,nr[s]=fr[e],fr[e]=s;else
{
k=0;
for (j=a.fi[e];j;j=a.ne[j])
if (a.v[j]==d[i])
{k=e=j;break;}
if (k==0)
{
a.v[++ss]=d[i];a.fa[ss]=e;
a.ne[ss]=a.fi[e];a.fi[e]=ss;e=ss;
}
}
ss=0;
Set_Up();
return;
}
void Sign(int x)
{
sg[x][0]=++ss;
for (int i=b.fi[x];i;i=b.ne[i])
Sign(i);
sg[x][1]=ss;
return;
}
void Insert(int x,int y,int z,int o,int p)
{
int i=(x+y)/2,j=z*2;
c.s[z]+=p;
if (x==y) return;
if (o>i)
Insert(i+1,y,j+1,o,p);else
Insert(x,i,j,o,p);
return;
}
int Query(int x,int y,int z,int o,int p)
{
int i=(x+y)/2,j=z*2,k=0;
if (x==o&&y==p) return c.s[z];
if (o<=i) k=Query(x,i,j,o,min(i,p));
if (p>i) k+=Query(i+1,y,j+1,max(o,i+1),p);
return k;
}
void DFS(int x)
{
Insert(1,ss,1,sg[x][0],1);
for (int i=fr[x];i;i=nr[i])
for (int j=fi[i];j;j=qu[j][1])
qu[j][2]=Query(1,ss,1,sg[li[qu[j][0]]][0],sg[li[qu[j][0]]][1]);
for (int i=a.fi[x];i;i=a.ne[i])
DFS(i);
Insert(1,ss,1,sg[x][0],-1);
return;
}
int main()
{
scanf("%s",d);n=strlen(d);
Set_up();Sign(0);m=Read();
for (int i=1,k;i<=m;i++)
qu[i][0]=Read(),qu[i][1]=fi[k=Read()],fi[k]=i;
DFS(0);
for (int i=1;i<=m;i++)
printf("%d\n",qu[i][2]);
return 0;
}
BZOJ2007海拔：
可以自行YY到一个性质：这些数要不就是0要不就是1（话说题目下面那个提示：海拔也有可能是小数也是sxbk），因为最优方案中最大的数如果调整到旁边的数的大小是可以使答案更优的，最小的也是这样。所以最优方案中最大的数一定是1、最小的一定是0，同理通过调整不存在小数，而且不存在不包含左上角的0连通块和不包含右下角的1连通块，因为这些连通块全部取反之后是会更优的。所以最后就变成了求一个最小割了，由于是平面图，而且点数艹蛋，所以转成对偶图用最短路问题做。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define N 550
#define M 1500000
#define INF 0x7f7f7f7f
int h[M],fi[M],c[M][3],n,m,S=M-1,T=M-2,sg[N][N],ss=1,st=0;
int a[N][N][4];
bool b[M];
queue <int> li;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z,int o)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=o;fi[y]=ss;
return;
}
void Set_up()
{
int i,j,k,l,q,w,e;
for (i=1;i<=n;i++)
sg[0][i]=sg[i][n+1]=S,sg[n+1][i]=sg[i][0]=T;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) sg[i][j]=++st;
for (i=0;i<=n;i++)
for (j=1;j<=n;j++)
a[i][j][3]=Read();
for (i=1;i<=n;i++)
for (j=0;j<=n;j++)
a[i][j+1][4]=Read();
for (i=0;i<=n;i++)
for (j=1;j<=n;j++)
a[i+1][j][1]=Read();
for (i=1;i<=n;i++)
for (j=0;j<=n;j++)
a[i][j][2]=Read();
for (int i=1;i<=n;i++)
for (int j=0;j<=n;j++)
Line(sg[i][j],sg[i][j+1],a[i][j][2],a[i][j+1][4]);
for (int i=0;i<=n;i++)
for (int j=1;j<=n;j++)
Line(sg[i][j],sg[i+1][j],a[i][j][3],a[i+1][j][1]);
return;
}
void SPFA()
{
int i,j,k,l,q,w,e;
li.push(S);b[S]=1;h[T]=INF;h[S]=0;
for (i=1;i<=st;i++) h[i]=INF;
while (!li.empty())
{
q=li.front();li.pop();b[q]=0;
for (i=fi[q];i;i=c[i][1])
if (h[q]+c[i][2]<h[c[i][0]])
{
h[c[i][0]]=h[q]+c[i][2];
if (!b[c[i][0]])
li.push(c[i][0]),b[c[i][0]]=1;
}
}
return;
}
int main()
{
int i,j,k,l,q,w,e;
n=Read();Set_up();
SPFA();
printf("%d\n",h[T]);
return 0;
}
评论 (0)
