你们啊，我感觉你们AHOI还要学习，你们非常熟悉NOIP的这一套难度。
你们毕竟TOO YOUNG，你明白我的意思吗？我告诉你们，我是身经百战了，见得多啊。NOIP的哪一个考试我没有做过？你们要知道强省的OI比你们不知要高到哪里去了，哎，我也被他们虐。
OI啊，还是要提高自己的知识水平，晓得不晓得啊？唉，我也替你们着急啊，真的。你们有一个好，NOIP跑到什么地方，比其他的强省OI跑得还快，但是问来问去的问题啊，都TOO SIMPLE，SOMETIMES NAIVE。懂了没有？懂不懂得？
SDOI比AHOI不知要高到哪里去了。
排序：
顺序无关，爆搜大法吼
#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
const int N=1<<12;
int w[N],n;
LL fac[N],Ans;
void Up(int x,int y,int t)
{
while(t--)
swap(w[x],w[y]),
x++,y++;
}
void dfs(int Now,int s)
{
if(Now==n)
{
Ans+=fac[s];
return;
}
int num=0,pos[5]={};
for(int i=0;i<(1<<n)&&num<=2;i+=1<<Now+1)
if(w[i+(1<<Now)-1]+1!=w[i+(1<<Now)])
pos[++num]=i;
if(num>2)
return;
if(num==0)
dfs(Now+1,s);
else if(num==1)
{
int p=pos[1];
if(w[p+(1<<Now+1)-1]+1==w[p])
Up(p,p+(1<<Now),1<<Now),
dfs(Now+1,s+1),
Up(p,p+(1<<Now),1<<Now);
}
else
{
int p1=pos[1],p2=pos[2];
if(w[p1+(1<<Now)-1]+1==w[p2+(1<<Now)]&&w[p2+(1<<Now)-1]+1==w[p1+(1<<Now)])
Up(p1,p2,1<<Now),
dfs(Now+1,s+1),
Up(p1,p2,1<<Now),
Up(p1+(1<<Now),p2+(1<<Now),1<<Now),
dfs(Now+1,s+1),
Up(p1+(1<<Now),p2+(1<<Now),1<<Now);
if(w[p2+(1<<Now)-1]+1==w[p1]&&w[p2+(1<<Now+1)-1]+1==w[p1+(1<<Now)])
Up(p1,p2+(1<<Now),1<<Now),
dfs(Now+1,s+1),
Up(p1,p2+(1<<Now),1<<Now);
if(w[p1+(1<<Now)-1]+1==w[p2]&&w[p1+(1<<Now+1)-1]+1==w[p2+(1<<Now)])
Up(p2,p1+(1<<Now),1<<Now),
dfs(Now+1,s+1),
Up(p2,p1+(1<<Now),1<<Now);
}
}
int main()
{
scanf("%d",&n);
fac[0]=1;
for(int i=1;i<=n;i++)
fac[i]=fac[i-1]*i;
for(int i=0;i<1<<n;i++)
scanf("%d",&w[i]);
dfs(0,0);
cout<<Ans<<endl;
return 0;
}
寻宝游戏：
很像虚树啊，显然按dfs序跑是最优的= =set大法吼
#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
set<int> T;
typedef set<int>::iterator Lzz;
typedef long long LL;
const int N=300005;
int pos[N],dfn[N],lg[N],Index,e[N],next[N],G[N],Len[N],tot,n,m;
LL Ans,dis[N],Min[N][20];
bool flag[N];
void adde(int u,int v,int l)
{
e[++tot]=v;next[tot]=G[u];G[u]=tot;Len[tot]=l;
}
void dfs(int u,int p)
{
pos[u]=++Index;
dfn[Index]=u;
Min[Index][0]=dis[u];
for(int v,i=G[u];i;i=next[i])
if((v=e[i])!=p)
dis[v]=dis[u]+Len[i],
dfs(v,u),
Min[++Index][0]=dis[u];
}
void Prepare()
{
for(int i=2;i<=Index;i++)
lg[i]=lg[i>>1]+1;
for(int j=1;j<=lg[Index];j++)
for(int i=1;i+(1<<j)-1<=Index;i++)
Min[i][j]=min(Min[i][j-1],Min[i+(1<<j-1)][j-1]);
}
LL dist(int u,int v)
{
int x=pos[u],y=pos[v];
if(x>y)
swap(x,y);
int l=lg[y-x+1];
return dis[u]+dis[v]-2*min(Min[x][l],Min[y-(1<<l)+1][l]);
}
void Update(int u)
{
flag[u]^=1;
if(flag[u]==1)
{
if(T.size())
{
Lzz it=T.insert(pos[u]).first;
Lzz A,B;
if(it==T.begin())
A=T.end(),A--;
else
A=it,A--;
it++;
if(it==T.end())
B=T.begin();
else
B=it;
Ans+=dist(u,dfn[*A])+dist(u,dfn[*B])-dist(dfn[*A],dfn[*B]);
}
else
T.insert(pos[u]);
}
else
{
if(T.size()>1)
{
Lzz it=T.find(pos[u]);
Lzz A,B;
if(it==T.begin())
A=T.end(),A--;
else
A=it,A--;
it++;
if(it==T.end())
B=T.begin();
else
B=it;
Ans-=dist(u,dfn[*A])+dist(u,dfn[*B])-dist(dfn[*A],dfn[*B]);
T.erase(pos[u]);
}
else
T.erase(pos[u]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,u,v,l;i<n;i++)
scanf("%d%d%d",&u,&v,&l),
adde(u,v,l),
adde(v,u,l);
dfs(1,0);
Prepare();
while(m--)
{
int u;
scanf("%d",&u);
Update(u);
printf("%lld\n",Ans);
}
return 0;
}
序列统计：
原根= =想到原根之后就好办了= =NTT快速幂（模数太显眼了）
程序见http://wuzuofan.is-programmer.com/posts/88375.html NTT模板
星际战争：
二分+网络流判定。。。
程序见http://wuzuofan.is-programmer.com/posts/88375.html DINIC模板
约数和个数：
莫比乌斯反演。。。
程序见http://wuzuofan.is-programmer.com/posts/88375.html MobiusInversion模板
道路修建：
堵塞的交通即视感= =线段树乱搞。。。
#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
const int N=100005;
int Li[N][2],Ro[N],n,m;
struct status
{
int Max_Li,l,r,Len,lmax,rmax,lpos,rpos,Num;
status(){}
status(int pos)
{
l=r=lpos=rpos=pos;
lmax=rmax=Len=Ro[pos];
Max_Li=0;
Num=1;
}
}T[N<<2];
status operator+(const status& Lc,const status& Rc)
{
status x;
int W=max(Li[Lc.r][0],Li[Lc.r][1]),Max=max(W,max(Lc.rmax,Rc.lmax));
x.Max_Li=max(max(Lc.Max_Li,Rc.Max_Li),W);
x.l=Lc.l;
x.r=Rc.r;
x.Len=Lc.Len+Rc.Len+Li[Lc.r][0]+Li[Lc.r][1]-Max;
x.Num=Lc.Num+Rc.Num;
x.lpos=Lc.lpos;
x.lmax=Lc.lmax;
x.rpos=Rc.rpos;
x.rmax=Rc.rmax;
if(Ro[Lc.rpos]==Max)
{
x.Num--;
if(Lc.Num==1)
x.lpos=Rc.lpos,
x.lmax=max(max(Lc.Max_Li,Rc.lmax),W);
}
else if(Ro[Rc.lpos]==Max)
{
x.Num--;
if(Rc.Num==1)
x.rpos=Lc.rpos,
x.rmax=max(max(Rc.Max_Li,Lc.rmax),W);
}
return x;
}
#define Lc (x<<1)
#define Rc (x<<1|1)
#define Mid (l+r>>1)
void Build(int x,int l,int r)
{
if(l==r)
T[x]=status(l);
else
Build(Lc,l,Mid),
Build(Rc,Mid+1,r),
T[x]=T[Lc]+T[Rc];
}
void Change_Ro(int x,int l,int r,int p)
{
if(l==r)
T[x]=status(l);
else
{
if(p<=Mid)
Change_Ro(Lc,l,Mid,p);
else
Change_Ro(Rc,Mid+1,r,p);
T[x]=T[Lc]+T[Rc];
}
}
void Change_Li(int x,int l,int r,int p)
{
if(p<Mid)
Change_Li(Lc,l,Mid,p);
else if(p>Mid)
Change_Li(Rc,Mid+1,r,p);
T[x]=T[Lc]+T[Rc];
}
status Ask(int x,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
return T[x];
if(R<=Mid)
return Ask(Lc,l,Mid,L,R);
else if(L>Mid)
return Ask(Rc,Mid+1,r,L,R);
return Ask(Lc,l,Mid,L,R)+Ask(Rc,Mid+1,r,L,R);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
scanf("%d",&Li[i][0]);
for(int i=1;i<n;i++)
scanf("%d",&Li[i][1]);
for(int i=1;i<=n;i++)
scanf("%d",&Ro[i]);
Build(1,1,n);
while(m--)
{
char op[10];
scanf("%s",op);
if(op[0]=='C')
{
int x1,y1,x2,y2,w;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&w);
if(y1==y2)
Ro[y1]=w,
Change_Ro(1,1,n,y1);
else
{
if(y1>y2)
swap(y1,y2);
Li[y1][x1-1]=w,
Change_Li(1,1,n,y1);
}
}
else
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",Ask(1,1,n,x,y).Len);
}
}
return 0;
}
评论 (0)
