7
26
2018
0

恢复计划

一年多没写题了,暑假稍微恢复一下

现在大概是普及组水平

恢复一下

-------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int a,b;

int main(){
freopen("1000.in","r",stdin);
freopen("1000.out","w",stdout);
scanf("%d %d",&a,&b);
printf("%d\n",a+b);
return 0;
}
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;

int n;
long long ans;
set<long long> St;
set<long long>::iterator I;

long long Abs(long long x){return x>0?x:-x;}
long long Min(long long x,long long y){return x<y?x:y;}

int main(){
freopen("1588.in","r",stdin);
freopen("1588.out","w",stdout);
scanf("%d",&n);
while(n--){
    long long sv,tp;
    scanf("%lld",&sv);
    if(St.empty()){St.insert(sv);ans=sv;}
    else {I=St.lower_bound(sv);tp=Abs(sv-*I);if(I!=St.begin())ans+=Min(tp,Abs(*--I-sv));else {ans+=tp;}St.insert(sv);}
}
printf("%lld\n",ans);
return 0;
}

正在恢复中...

Category: OI | Tags:
12
28
2016
0

WC2017去不了啦

有趣

Category: OI | Tags:
10
25
2016
0

NOIP2016考前乱写

留下一个坑

因为是NOIP,所以都是些非常简单的题呢

所以都是一句话题解

懒得放在博客里面了

看看到NOIP前能A掉多少道呢?

对了还有一个题单

都是目前没有AC的比较好的题,有些可能A掉忘了删掉了

反正都要做

-------------------------

10.25

1.[BZOJ3100] 排列

考虑选中的排列里面没有重复的数字然后和为一个定值随便扫描一下

时间复杂度$O(n)$

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1000005;

int n,m,a[N],nex[N],ne[N],ans;

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

inline void Prepare(){
memset(ne,0,sizeof(nex));
for(register int i=n;i>=1;i--){
	if(ne[a[i]]==0)nex[i]=n+1;
	else nex[i]=ne[a[i]];
	ne[a[i]]=i;
}
}

inline void Solve(){
Prepare();
m=0;
for(register int i=1;i<=n;i++)if(a[i]==1)ne[++m]=i;
if(m==0)return;
else ans=max(ans,1);
for(register int i=1;i<=m;i++){
	int mx=0,pos=ne[i],mn=nex[ne[i]];long long sum=0;
	for(register int j=ne[i]-1;j>ne[i-1];j--){
		mn=min(mn,nex[j]);
		sum+=a[j];
		if(a[j]<=mx){if(pos==j+mx+1)sum-=a[--pos];}
		else {mx=a[j];while(pos<mn && pos<=j+mx-1)sum+=a[pos++];}
		if(j+mx<=mn && sum==1ll*mx*(mx+1)/2)ans=max(mx,ans);
	}
}
}

int main(){
freopen("3100.in","r",stdin);
freopen("3100.out","w",stdout);
Read(n);
for(register int i=1;i<=n;i++)Read(a[i]);
Solve();
for(register int i=1;i<=n/2;i++)swap(a[i],a[n-i+1]);
Solve();
printf("%d\n",ans);
return 0;
}

2.[BZOJ1195] [HNOI2006]最短母串

把互相包含的串缩一下然后状压dp,注意使用string类型来压空间

时间复杂度$O(2^n*n^2*len)$,len表示比较的串的长度

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int N=14,M=52,INF=999999999;

int n;
char sr[M];

struct String{
string str;
int len;
String(){}
String(int lw){len=lw;}
friend inline bool operator<(const String &A,const String &B){
    int mn=min(A.len,B.len);
    for(register int i=1;i<=mn;i++){
		if(A.str[i-1]>B.str[i-1])return 0;
		if(A.str[i-1]<B.str[i-1])return 1;
    }
    return A.len<B.len;
}
friend inline String operator+(const String &A,const String &B){
String C=String(0);
if(A.len==INF){C.len=INF;return C;}
for(register int i=min(A.len,B.len);i>=0;i--){
	int diff=0;
	for(register int j=1;j<=i;j++){
		if(A.str[A.len-i+j-1]!=B.str[j-1]){diff=1;break;}
	}
	if(!diff){
		C.str=A.str;
		for(register int j=i+1;j<=B.len;j++)C.str+=B.str[j-1];
		C.len=A.len+B.len-i;
		//printf("%d\n",C.len);
		return C;
	}
}
return C;
}
}str[N],dp[1<<N][M],ans;

inline bool Cmp(const String &A,const String &B){
return A.len<B.len || (A.len==B.len && A<B);
}

int main(){
freopen("1195.in","r",stdin);
freopen("1195.out","w",stdout);
scanf("%d",&n);
for(register int i=1;i<=n;i++){scanf("%s",sr+1);str[i].str=sr+1;str[i].len=strlen(sr+1);}
sort(str+1,str+n+1);
for(register int i=1;i<n;i++){
	if(str[i].len<str[i+1].len){
		int diff=0;
        for(register int j=1;j<=str[i].len;j++){
			if(str[i].str[j-1]!=str[i+1].str[j-1]){diff=1;break;}
        }
        if(!diff){
			for(register int j=i;j<n;j++)str[j]=str[j+1];
			i--;n--;
        }
	}
}
for(register int i=1;i<=n;i++)dp[1<<(i-1)][i]=str[i];
for(register int i=1;i<(1<<n);i++){
    for(register int j=0;j<n;j++){
		if(dp[i][j+1].len)continue;
		if(((i>>j)&1)==0)continue;
		dp[i][j+1].len=INF;
		for(register int k=0;k<n;k++){
			if(j==k || ((i>>k)&1)==0)continue;
			if(Cmp(dp[i-(1<<j)][k+1]+str[j+1],dp[i][j+1]))dp[i][j+1]=dp[i-(1<<j)][k+1]+str[j+1];
		}
    }
}
ans=dp[(1<<n)-1][1];
for(register int i=2;i<=n;i++)ans=min(ans,dp[(1<<n)-1][i],Cmp);
for(register int i=0;i<ans.len;i++)putchar(ans.str[i]);
putchar('\n');
return 0;
}

3.[BZOJ3754] Tree之最小方差树

考虑平均数一定在已经排序好的边权中间的两数之间的某个区间,这样的话树的形态是不改变的。

因为边权只有100而且是整数,所以我们每0.25枚举一下就好了,一定满足要求

时间复杂度$O(400nlogn)$,其中$nlogn$是排序复杂度,$400$是枚举复杂度。

另:我一开始搞了一个最大最小生成树的优化但是显然没搞对,其实就是确定范围而已懒得改了反正不改也能过

想改的话就是把Solve先跑两遍一个输入是0一个输入是100然后把结果当作Mn Mx跑循环而已

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=105,M=2005;

struct Edge{
int a,b,u;
double v;
friend bool inline operator<(const Edge &A,const Edge &B){return A.v<B.v;}
}e[M];

int n,m,f[N];
double Mn,Mx,ans=9999999999.0;

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

inline void Clear(){for(register int i=1;i<=n;i++)f[i]=i;}
int Find(int x){return f[x]==x?x:f[x]=Find(f[x]);}
inline void Union(int sa,int sb){if(sa>sb)f[sa]=sb;else f[sb]=sa;}
inline bool Mi(const Edge &A,const Edge &B){return A.u<B.u;}
inline bool Ma(const Edge &A,const Edge &B){return A.u>B.u;}
/*
inline void Mini(){
Clear();
double fx=0.0,fy=0.0;
sort(e+1,e+m+1,Mi);
for(register int i=1;i<=m;i++){
	if(Find(e[i].a)!=Find(e[i].b)){
		Union(Find(e[i].a),Find(e[i].b));
		fx+=e[i].u;
	}
}
fx/=n-1;
Clear();
for(register int i=1;i<=m;i++){
	if(Find(e[i].a)!=Find(e[i].b)){
		Union(Find(e[i].a),Find(e[i].b));
		fy+=(e[i].u-fx)*(e[i].u-fx);
	}
}
fy/=n-1;
Mn=sqrt(fy);
}

inline void Maxi(){
Clear();
double fx=0.0,fy=0.0;
sort(e+1,e+m+1,Ma);
for(register int i=1;i<=m;i++){
	if(Find(e[i].a)!=Find(e[i].b)){
		Union(Find(e[i].a),Find(e[i].b));
		fx+=e[i].u;
	}
}
fx/=n-1;
Clear();
for(register int i=1;i<=m;i++){
	if(Find(e[i].a)!=Find(e[i].b)){
		Union(Find(e[i].a),Find(e[i].b));
		fy+=(e[i].u-fx)*(e[i].u-fx);
	}
}
fy/=n-1;
Mx=sqrt(fy);
}
*/
inline void Solve(double x){
for(register int i=1;i<=m;i++)e[i].v=(x-e[i].u)*(x-e[i].u);
Clear();
double fx=0.0,fy=0.0;
sort(e+1,e+m+1);
for(register int i=1;i<=m;i++){
	if(Find(e[i].a)!=Find(e[i].b)){
		Union(Find(e[i].a),Find(e[i].b));
		fx+=e[i].u;
	}
}
fx/=n-1;
Clear();
for(register int i=1;i<=m;i++){
	if(Find(e[i].a)!=Find(e[i].b)){
		Union(Find(e[i].a),Find(e[i].b));
		fy+=(e[i].u-fx)*(e[i].u-fx);
	}
}
fy/=n-1;
ans=min(ans,sqrt(fy));
}

int main(){
freopen("3754.in","r",stdin);
freopen("3754.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=m;i++){
	Read(e[i].a);Read(e[i].b);Read(e[i].u);
}
//Mini();Maxi();
//if(Mn>Mx)swap(Mn,Mx);
Mn=0.0;Mx=100.0;
for(double i=Mn;i<=Mx;i+=0.25)Solve(i);
printf("%.4f\n",ans);
return 0;
}

4.[BZOJ3110] [Zjoi2013]K大数查询

差点忘了怎么做了……不过树套树的整体思想是清晰的

显然一个树是权值线段树,一个树是区间线段树

这题的新颖之处在于是权值套区间

以前写了爆int了没过,今天改了下unsigned int就过了

#include<cstdio>
#include<algorithm>
using namespace std;
  
int n,m,cnt,root[500005];
  
struct SegTree{
int nl,nr,l,r;
unsigned int sum,tag;
}tree[20000005];
  
void Pushdown(int rt){
if(tree[rt].tag && tree[rt].l!=tree[rt].r){
    int mid=tree[rt].l+tree[rt].r>>1;
    if(!tree[rt].nl){tree[rt].nl=++cnt;tree[tree[rt].nl].l=tree[rt].l;tree[tree[rt].nl].r=mid;}
    if(!tree[rt].nr){tree[rt].nr=++cnt;tree[tree[rt].nr].l=mid+1;tree[tree[rt].nr].r=tree[rt].r;}
    tree[tree[rt].nl].tag+=tree[rt].tag;
    tree[tree[rt].nr].tag+=tree[rt].tag;
    tree[tree[rt].nl].sum+=(tree[tree[rt].nl].r-tree[tree[rt].nl].l+1)*tree[rt].tag;
    tree[tree[rt].nr].sum+=(tree[tree[rt].nr].r-tree[tree[rt].nr].l+1)*tree[rt].tag;
    tree[rt].tag=0;
}
}
  
void Pushup(int rt){
tree[rt].sum=tree[tree[rt].nl].sum+tree[tree[rt].nr].sum;
}
  
void Modify(int &rt,int l,int r,int L,int R){
if(!rt){rt=++cnt;tree[rt].l=l;tree[rt].r=r;}
Pushdown(rt);
if(L<=tree[rt].l && tree[rt].r<=R){
    tree[rt].sum+=tree[rt].r-tree[rt].l+1;
    tree[rt].tag++;
    return;
}
int mid=tree[rt].l+tree[rt].r>>1;
if(L<=mid)Modify(tree[rt].nl,l,mid,L,R);
if(R>mid)Modify(tree[rt].nr,mid+1,r,L,R);
Pushup(rt);
}
  
unsigned int Query(int rt,int l,int r){
if(!rt)return 0;
Pushdown(rt);
if(l<=tree[rt].l && tree[rt].r<=r){return tree[rt].sum;}
int mid=tree[rt].l+tree[rt].r>>1;
unsigned int ans=0;
if(l<=mid)ans+=Query(tree[rt].nl,l,r);
if(r>mid)ans+=Query(tree[rt].nr,l,r);
Pushup(rt);
return ans;
}
  
void Insert(int l,int r,int v){
int L=1,R=n,rt=1;
while(L!=R){
    int mid=L+R>>1;
    Modify(root[rt],1,n,l,r);
    if(v<=mid){R=mid;rt*=2;}
    else {L=mid+1;rt=rt*2+1;}
}
Modify(root[rt],1,n,l,r);
}
  
int Ask(int l,int r,int k){
int L=1,R=n,rt=1;
while(L!=R){
    int mid=L+R>>1;
    unsigned int ans=Query(root[rt*2],l,r);
    if(ans>=k){R=mid;rt*=2;}
    else {L=mid+1;rt=rt*2+1;k-=ans;}
}
return L;
}
  
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
  
int main(){
freopen("3110.in","r",stdin);
freopen("3110.out","w",stdout);
n=read();m=read();
for(int i=1;i<=m;i++){
    int opt,a,b,c;
    opt=read();a=read();b=read();c=read();
    if(opt==1)Insert(a,b,n-c+1);
    if(opt==2)printf("%d\n",n-Ask(a,b,c)+1);
}
return 0;
}

小结:今天一共做了5题,修改了1题,包括一道不能放上来的题目,UER7B,和上面这4题。

1:考察了对于题目的审题能力以及观察题目性质的能力,比如我在一开始没有想到排列的和这个性质导致无从下手。

2:直接做困难的dp应考虑怎么简化状态表示和选择合适的状态表示。

3:观察题目数据范围发现问题和性质。

4:注意极限情况下的数据值可能会爆int

UER7B:考虑划分答案。蒟蒻我表示很难想到啊

不能放上来的题:考虑正负号对答案的影响或许是相同的,所以要特判。

总的来说收获还是挺多的,希望在接下来的一段时间内能够总结更多的知识,不然复赛退役可不是闹着玩的(毕竟我已经高二了)

-------------------------

10.26

考了试然后瞬间爆炸

3题只有几十分

NOIP拿不到1=咯

-------------------------

10.27

休息一天?(其实我忘了我在干啥)

-------------------------

10.28

休息一天?(其实我忘了我在干啥)

-------------------------

10.29

考了一天试只有190拿不到1=咯

-------------------------

10.30

考了一天试只有180拿不到1=咯

-------------------------

10.31

被黑了一整天于是休息一天?(其实我忘了我在干啥)

好吧还是在bzoj上交了一个题

1.[BZOJ3304] [Shoi2005]带限制的最长公共子序列

状态加一维表示匹配到z串的哪个地方直接转移即可

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=505;

int dp[2][N][N],n1,n2,n3;
char s1[N],s2[N],s3[N];

int main(){
freopen("3304.in","r",stdin);
freopen("3304.out","w",stdout);
scanf("%s",s1+1);n1=strlen(s1+1);
scanf("%s",s2+1);n2=strlen(s2+1);
scanf("%s",s3);n3=strlen(s3);
for(register int i=1;i<=n1;i++){
	int now=i&1,pre=now^1;
	memset(dp[now],0,sizeof(dp[now]));
	for(register int j=1;j<=n2;j++){
        for(register int k=0;k<=n3;k++){
			dp[now][j][k]=max(dp[now][j][k],max(dp[pre][j][k],dp[now][j-1][k]));
			if(s1[i]==s2[j] && (k==0 || dp[pre][j-1][k])){
				if(s1[i]==s3[k])dp[now][j][k+1]=max(dp[now][j][k+1],dp[pre][j-1][k]+1);
				else dp[now][j][k]=max(dp[now][j][k],dp[pre][j-1][k]+1);
			}
			//printf("%d\n",dp[now][j][k]);
        }
	}
}
if(dp[n1&1][n2][n3]==0)puts("NO SOLUTION");
else printf("%d\n",dp[n1&1][n2][n3]);
return 0;
}

嗯,bzoj1009很有趣得在几天内A掉

-------------------------

11.1

睡觉睡掉了,最近需要好好休息一下

对了rky小号也上紫名了……这让大号还没紫的我情何以堪……

-------------------------

11.2

考试

爆炸

看着一个个神犇越来越强我却越来越弱的现实,却懒得去改变……难道真的要在NOIP2016直接退役吗

ZOJ挂了刷不了题目

只好做点简单题了

1.[BZOJ4326] NOIP2015 运输计划

我本来想用树链剖分,后来想了想还是看了下线性的神奇方法

好吧二分还是要二分的,只是判断线性

最近思维越来越差了

我的思路:二分答案$ans$,把所有大于$ans$的路径利用树链剖分实现路径加和路径取最大值

打标记实现,线段树节点保存当前最大次数和当前最大次数情况下的最大值

合并先比较次数,次数一样再取最大值

然后查询整棵树即可

但是这样单次判断是$O(mlogn)$的,总时间复杂度为$O(logmx\_len*mlogn)$

在CCF老爷机上就别想跑过去了

所以学习了一下树上前缀和

其实就是sum[u]++,sum[v]++,sum[lca]-=2;

然后dfs扫描一下就行

时间复杂度$O(logmx\_len*(logm+m+n))$

1A,总算缓解了一下考砸后糟糕的心情

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=300005;

int n,m,h[N],en,fa[N][20],sum[N],dfn[N],cnt,mx_len,dis[N][20],dep[N];

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

struct Queries{
int l,r,v,lca;
friend inline bool operator<(const Queries &A,const Queries &B){return A.v<B.v;}
}que[N];

struct Edge{
int b,v,next;
}e[N<<1];

inline void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

void dfs(int u){
dfn[u]=++cnt;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v==fa[u][0])continue;
	fa[v][0]=u;
	dis[v][0]=e[i].v;
	dep[v]=dep[u]+1;
	dfs(v);
}
}

inline void prepare(){
for(register int i=1;i<=19;i++){
    for(register int j=1;j<=n;j++){
		fa[j][i]=fa[fa[j][i-1]][i-1];
        dis[j][i]=dis[j][i-1]+dis[fa[j][i-1]][i-1];
    }
}
}

inline pair<int,int> dist(int u,int v){
int ans=0;
if(dep[u]<dep[v])swap(u,v);
int deep=dep[u]-dep[v];
for(int i=0;i<=19;i++)if((deep>>i)&1){ans+=dis[u][i];u=fa[u][i];}
for(int i=19;i>=0;i--){
	if(fa[u][i]!=fa[v][i]){
		ans+=dis[u][i]+dis[v][i];
		u=fa[u][i];
		v=fa[v][i];
	}
}
return u==v?make_pair(u,ans):make_pair(fa[u][0],ans+dis[u][0]+dis[v][0]);
}

int update(int u){
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fa[u][0])continue;
    sum[u]+=update(v);
}
//printf("Smu:%d\n",sum[u]);
return sum[u];
}

inline bool solve(int x){
int l=1,r=m,mt=0,aw=0;
while(l<=r){
	int mid=l+r>>1;
	if(que[mid].v>x)r=mid-1;
	else l=mid+1;
}
//printf("L:%d %d\n",l,x);
for(register int i=1;i<=n;i++)sum[i]=0;
for(register int i=l;i<=m;i++){
	sum[que[i].l]++;
	sum[que[i].r]++;
	sum[que[i].lca]-=2;
	mt=max(mt,que[i].v-x);
}
update(1);
for(register int i=1;i<=n;i++)if(sum[i]==(m-l+1))aw=max(aw,dis[i][0]);
//printf("mt:%d %d\n",mt,aw);
return mt<=aw;
}

void div2(){
int l=0,r=mx_len;
while(l<=r){
	int mid=l+r>>1;
    if(solve(mid))r=mid-1;
    else l=mid+1;
}
printf("%d\n",l);
}

int main(){
freopen("4326.in","r",stdin);
freopen("4326.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<n;i++){
    static int u,v,w;
    Read(u);Read(v);Read(w);
    AddEdge(u,v,w);AddEdge(v,u,w);
}
for(register int i=1;i<=m;i++){Read(que[i].l);Read(que[i].r);}
dfs(1);
prepare();
for(register int i=1;i<=m;i++){
	pair<int,int> Pr=dist(que[i].l,que[i].r);
	que[i].v=Pr.second;
	que[i].lca=Pr.first;
	mx_len=max(mx_len,que[i].v);
}
sort(que+1,que+m+1);
div2();
return 0;
}

-------------------------

11.3

日常颓废

1.[BZOJ4066] 简单题

啊……为了调试方便把x^=lastans注释掉了……然后提交时一直忘了加上去

最后就创下了单题提交12次的记录……最后一次才发现……

本身是裸KD树

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200005,INF=2100000000;

int n,sort_tag,cnt,root;
long long lastans;

struct KDTree{
int l,r,d[2],mx[2],mn[2];
long long sum,v;
KDTree(){l=r=d[0]=d[1]=mx[0]=mn[0]=mx[1]=mn[1]=sum=v=0;}
friend inline bool operator<(const KDTree &A,const KDTree &B){return A.d[sort_tag]<B.d[sort_tag];}
}tree[N];

inline void Pushup(int rt){
tree[rt].mx[0]=tree[rt].mn[0]=tree[rt].d[0];
tree[rt].mx[1]=tree[rt].mn[1]=tree[rt].d[1];
tree[rt].sum=tree[rt].v;
if(tree[rt].l){
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].l].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].l].mx[1]);
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].l].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].l].mn[1]);
    tree[rt].sum+=tree[tree[rt].l].sum;
}
if(tree[rt].r){
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].r].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].r].mx[1]);
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].r].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].r].mn[1]);
    tree[rt].sum+=tree[tree[rt].r].sum;
}
}

int Rebuild(int l,int r,int D){
sort_tag=D;
int mid=l+r>>1;
nth_element(tree+l,tree+mid,tree+r+1);
tree[mid].mx[0]=tree[mid].mn[0]=tree[mid].d[0];
tree[mid].mx[1]=tree[mid].mn[1]=tree[mid].d[1];
tree[mid].l=tree[mid].r=0;
if(l<mid)tree[mid].l=Rebuild(l,mid-1,!D);
if(r>mid)tree[mid].r=Rebuild(mid+1,r,!D);
Pushup(mid);
return mid;
}

template<typename T>inline void ReadO(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

template<typename T>inline void Read(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
x^=lastans;
}

inline int AddKDNode(int x,int y,int z){
tree[++cnt].d[0]=x;
tree[cnt].d[1]=y;
tree[cnt].v=z;
Pushup(cnt);
return cnt;
}

int Add(int rt,int d0,int d1,int val,bool D){
if(!rt)return AddKDNode(d0,d1,val);
if(tree[rt].d[0]==d0 && tree[rt].d[1]==d1){tree[rt].v+=val;tree[rt].sum+=val;return rt;}
if(D){
    if(d1<tree[rt].d[D])tree[rt].l=Add(tree[rt].l,d0,d1,val,!D);
    else tree[rt].r=Add(tree[rt].r,d0,d1,val,!D);
}
else {
	if(d0<tree[rt].d[D])tree[rt].l=Add(tree[rt].l,d0,d1,val,!D);
    else tree[rt].r=Add(tree[rt].r,d0,d1,val,!D);
}
Pushup(rt);
return rt;
}

long long Sum(int rt,int x1,int y1,int x2,int y2,int D){
if(!rt)return 0ll;
long long ans=0;
if(y1>tree[rt].mx[1] || y2<tree[rt].mn[1] || x1>tree[rt].mx[0] || x2<tree[rt].mn[0])return 0ll;
if(y1<=tree[rt].mn[1] && tree[rt].mx[1]<=y2 && x1<=tree[rt].mn[0] && tree[rt].mx[0]<=x2)return tree[rt].sum;
if(y1<=tree[rt].d[1] && tree[rt].d[1]<=y2 && x1<=tree[rt].d[0] && tree[rt].d[0]<=x2)ans+=tree[rt].v;
ans+=Sum(tree[rt].l,x1,y1,x2,y2,!D)+Sum(tree[rt].r,x1,y1,x2,y2,!D);
return ans;
}

int main(){
freopen("4066.in","r",stdin);
freopen("4066.out","w",stdout);
ReadO(n);tree[0].d[0]=tree[0].d[1]=INF;
while(1){
	static int opt,x1,y1,x2,y2;
    ReadO(opt);
    if(opt==1){Read(x1);Read(y1);Read(x2);root=Add(root,x1,y1,x2,0);if(cnt%10000==0)root=Rebuild(1,cnt,0);}
    if(opt==2){Read(x1);Read(y1);Read(x2);Read(y2);printf("%lld\n",lastans=Sum(root,x1,y1,x2,y2,0));}
    if(opt==3)return 0;
}
return 0;
}

2.[BZOJ1013] [JSOI2008]球形空间产生器sphere

画一下式子发现拆开来就是一堆方程,半径什么的都可以消掉

直接高斯消元解方程即可

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=15;
const double eps=1e-9;

int n;
double px[N];

struct Equa{
double p[N];
Equa(){for(register int i=0;i<N;i++)p[i]=0.0;}
}poi[N];

inline double Abs(const double &x){return x>0?x:-x;}

inline void Gauss(){
int j;
for(register int i=1;i<=n;i++){
	for(j=i;j<=n;j++)if(Abs(poi[j].p[i])>eps)break;
	if(i!=j)for(register int k=1;k<=n+1;k++)swap(poi[i].p[k],poi[j].p[k]);
	double w=poi[i].p[i];
	for(register int k=1;k<=n+1;k++)poi[i].p[k]/=w;
    for(register int k=1;k<=n;k++){
		if(k==i)continue;
		w=poi[k].p[i];
		for(register int l=1;l<=n+1;l++)poi[k].p[l]-=w*poi[i].p[l];
    }
}
}

int main(){
freopen("1013.in","r",stdin);
freopen("1013.out","w",stdout);
scanf("%d",&n);
for(register int i=1;i<=n;i++)scanf("%lf",&px[i]);
for(register int i=1;i<=n;i++){
    for(register int j=1;j<=n;j++){
		static double x;
        scanf("%lf",&x);
        poi[i].p[j]=2.0*(x-px[j]);
        poi[i].p[n+1]+=x*x-px[j]*px[j];
    }
}
Gauss();
for(register int i=1;i<n;i++)printf("%.3lf ",poi[i].p[n+1]);
printf("%.3lf\n",poi[n].p[n+1]);
return 0;
}

3.[BZOJ1831] [AHOI2008]逆序对

难得的看出来的题目……

总之选择的数成一个不下降序列

所以直接dp就行

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int N=10005,K=105;

int n,k,a[N],pos[N],pcnt;
long long dp[N][K],g[N][K],f[N][K],ans;

int main(){
freopen("1831.in","r",stdin);
freopen("1831.out","w",stdout);
scanf("%d %d",&n,&k);
for(register int i=1;i<=n;i++)scanf("%d",&a[i]);
for(register int i=1;i<=n;i++){
	if(a[i]==-1)pos[++pcnt]=i;
	else for(register int j=1;j<a[i];j++)g[i][j]++;
	for(register int j=1;j<=k;j++)g[i][j]+=g[i-1][j];
	if(a[i]!=-1)ans+=g[i][a[i]];
}
for(register int i=n;i>=1;i--){
	if(a[i]!=-1)for(register int j=a[i]+1;j<=k;j++)f[i][j]++;
	for(register int j=1;j<=k;j++)f[i][j]+=f[i+1][j];
}
for(register int i=1;i<=pcnt;i++){
	long long d=1ll<<62;
    for(register int j=1;j<=k;j++){
		d=min(d,dp[i-1][j]);
		dp[i][j]=d+f[pos[i]][j]+g[pos[i]][j];
    }
}
long long d=1ll<<62;
for(register int i=1;i<=k;i++)d=min(d,dp[pcnt][i]);
printf("%lld\n",d+ans);
return 0;
}

11.4-11.9

复习以及准备期中考试,暂不更新

-------------------------

Category: OI | Tags: OI
6
19
2016
3

简易FFT教程

这是一篇简易的FFT教程,作者水平奇低无比,这篇博文仅仅是用于分享体会

已经学会FFT的神犇们可以直接无视这篇文章

推荐几个学习FFT的很好的博客地址:Picks大神的博客 Miskcoo大神的博客 FFT算法学习笔记 (对于想要进阶的来说去第一个,基础去第二个,入门去第三个)

我觉得学FFT先要去看上面三个博客,实在一点看不懂在看我的口胡……

而且我的口胡非常模糊(半夜三点在写这东西),难免会出错,敬请指正~

嗯,蒟蒻Lvat_s开始口胡了

首先你需要知道什么是FFT

其实我也不知道是啥,但是有个专业的名字叫做Fast Fourier Transform(快速傅立叶变换)

相信看这篇博文的神犇们都具有初中数学姿势:一个二次函数可以被三个点表示出来

而小学数学告诉我们一个一次函数可以用两个点表示出来

所以,我们类比一下,一个n次多项式$F(n)=a_n*x^n+......+a_1*x+a_0$可以用n+1个二维平面上的点来表示,这些点称为多项式的点值表示法

我们再来思考一下函数是怎么乘起来的

例如$F*G=......$(懒得写了)(总之就是对于x坐标相同的点,将两个函数的y坐标值相乘后就行了)

那么对于点值表达我们可以$O(n)$的实现乘法

所以离散傅立叶变换(DFT)就是暴力的将这些点分拆与合并,时间复杂度$O(n^2)$

为什么DFT复杂度这么高?

都是开始分拆多项式和后期合并的锅!

初中数学告诉我们由一个二次函数得到的三个点不具有唯一性,而由三个点合成的那个二次函数一定是唯一的

我们再来类比一下就知道了n次多项式$F(n)$也可以这么做

所以,FFT就是找一些合适的点用$O(nlog_2n)$得到点值表达,然后$O(n)$计算乘法,最后用$O(nlog_2n)$来重新得到这个多项式。

然而怎么降低复杂度呢?

我们选择单位复数根的倍数作为我们要找的这些点的x坐标。

看起来好像一点用没有……真的没有吗?

当然是有用的了。

(未完待续)

更新啦

我们需要知道关于复数的两个引理

设$w_n=e^{2\pi/n}$

消去引理:$w_{dk}^{dk}=w_k^k(n>=0,k>=0,d>=0)$证明很简单,带进去算下就行= =

折半引理:我不太会Mathjax语法怎么办……那就弄个图片吧

还有一个求和引理就不发了= =懒得截图了

这三个引理使我们可以证明FFT的正确性。

FFT的核心就是分组(按照奇数和偶数对多项式的指数进行分组)。

如果我们可以在单次$O(n)$时间内合并($n$为多项式的长度),那么多项式乘法就可以在$O(nlogn)$的时间内解决。

事实是确实可以这样

具体证明在我推荐的第三个博客地址里面就有,讲的还是很清晰的。

那么我们就可以递归FFT啦!

当然这样不优美。

我们可以改成非递归版的,这样节省时间。

写的好渣啊……主要是因为当初看了好多FFT方面的博客都看不懂,所以才决定事无巨细的写这篇文章。

====================分割线=======================

多项式求逆

这玩意要用到类似倍增的东西,我还没想太清楚……

过几天更新

orz rky大爷几个月前就会了

Category: OI | Tags: OI
4
30
2016
0

后缀数组练习

CTSC&APIO感觉自己水平太低,完全没法做……

所以打算利用在北京的这段时间提高一下自己的OI水平

后缀数组虽然会写,但是仅限于会敲模版。。

所以我打算把罗穗骞论文里面的所有题写一遍

----------------------------------------

POJ 2774

两个串连一起搞完后缀数组然后求height最大值判断一下前后是否分别属于两个不同的串就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200005;

int n1,n2,n,rank[N],sa[N],rank2[N],wa[N],ws[N],height[N];
char s1[N],s2[N],s[2*N];

int cmp(int *r,int a,int b,int l){return (r[a]==r[b])&(r[a+l]==r[b+l]);}

void GetSA(char *r,int *sa,int n,int m){
int i,j,p,*x=rank,*y=rank2,*t;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]=r[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;
for(j=p=1;p<n;j<<=1,m=p){
	for(p=0,i=n-j;i<n;i++)y[p++]=i;
	for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
	for(i=0;i<m;i++)ws[i]=0;
	for(i=0;i<n;i++)ws[wa[i]=x[y[i]]]++;
    for(i=1;i<m;i++)ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--)sa[--ws[wa[i]]]=y[i];
    for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}

void CalHeight(char *r,int *sa,int n){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k){
	for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
}

bool Diff(int x){return (sa[x]<n1 && sa[x-1]>=n1)||(sa[x]>=n1 && sa[x-1]<n1);}

int Solve(){
int MxHeight=0;
for(int i=2;i<=n;i++){
	if(height[i]>MxHeight && Diff(i))MxHeight=height[i];
}
return MxHeight;
}

int main(){
freopen("2774.in","r",stdin);
freopen("2774.out","w",stdout);
scanf("%s %s",s1,s2);
n1=strlen(s1);
n2=strlen(s2);
n=n1+n2;
for(int i=0;i<n1;i++)s[i]=s1[i];
for(int i=n1;i<n;i++)s[i]=s2[i-n1];
s[n]=0;
GetSA(s,sa,n+1,128);
CalHeight(s,sa,n);
printf("%d\n",Solve());
return 0;
}

----------------------------------------

POJ 1743

先差分,然后二分答案k,然后对于height分组(height[i]记录的是sa[i]和sa[i-1]的LCP),那么因为字典序相邻的后缀在sa里的顺序是连续的,那么我们对于判定答案k是否合法的方法就是找到连续的height,它们的值都不小于k(保证重复的串长大于等于k),然后如果组内最靠前和最靠后的位置差也大于等于k,那么这个方案就是合法的。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int N=200005,INF=2100000000;

int sa[N],rank[N],rank2[N],ws[N],s[N],wa[N],n,height[N];

int Abs(int x){return x>0?x:-x;}
int cmp(int *r,int a,int b,int l){return (r[a]==r[b])&(r[a+l]==r[b+l]);}

void GetSA(int *r,int *sa,int n,int m){
int i,j,p,*x=rank,*y=rank2,*t;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]=r[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;
for(j=p=1;p<n;j<<=1,m=p){
    for(p=0,i=n-j;i<n;i++)y[p++]=i;
    for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
    for(i=0;i<m;i++)ws[i]=0;
    for(i=0;i<n;i++)ws[wa[i]=x[y[i]]]++;
    for(i=1;i<m;i++)ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--)sa[--ws[wa[i]]]=y[i];
    for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}

void Calheight(int *r,int *sa,int n){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k){
    for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
}

int Solve(int k){
int i=2,Mx,Mn;
while(1){
    while(i<=n && height[i]<k)i++;
    if(i>n)break;
    Mx=sa[i-1];Mn=sa[i-1];
    while(i<=n && height[i]>=k){Mn=min(Mn,sa[i]);Mx=max(Mx,sa[i]);i++;}
    if(Mx-Mn>=k)return 1;
}
return 0;
}

int Div(){
int l=4,r=n*2,ans=0;
while(l<=r){
    int mid=l+r>>1;
    if(Solve(mid)){l=mid+1;ans=mid;}
    else r=mid-1;
}
ans++;
return ans<5?0:ans;
}

int main(){
freopen("1743.in","r",stdin);
freopen("1743.out","w",stdout);
while(scanf("%d",&n),n){
    for(int i=0;i<n;i++)scanf("%d",&s[i]);
    if(n<10){puts("0");continue;}
    n--;
    for(int i=0;i<n;i++)s[i]=s[i+1]-s[i]+89;
    s[n]=0;
    for(int i=0;i<N;i++)wa[i]=ws[i]=0;
    GetSA(s,sa,n+1,200);
    Calheight(s,sa,n);
    printf("%d\n",Div());
}
return 0;
}

----------------------------------------

Category: OI | Tags: OI
11
12
2015
0

模版

突然觉得应该攒一些模版了……这样以后就可以方便的抄了

#include<cstdio>
#include<algorithm>
using namespace std;

int en,pre[30005],segn,n,q,top[30005],id[30005],data[30005],fa[30005],son[30005],siz[30005],dep[30005],h[30005];
char ask[10];

struct Edge{
int b,next;
}e[60005];

struct SegTree{
int l,r,v,sum;
}tree[120005];

void add(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void Build(int root,int l,int r){
tree[root].l=l;
tree[root].r=r;
if(l==r){
    tree[root].v=data[pre[l]];
    tree[root].sum=data[pre[l]];
    return;
}
int mid=(l+r)/2;
Build(root*2,l,mid);
Build(root*2+1,mid+1,r);
tree[root].v=max(tree[root*2].v,tree[root*2+1].v);
tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}

void Update(int root,int pos,int val){
if(tree[root].l==tree[root].r){
    tree[root].v+=val;
    tree[root].sum+=val;
    return;
}
int mid=(tree[root].l+tree[root].r)/2;
if(pos<=mid)Update(root*2,pos,val);
if(pos>mid)Update(root*2+1,pos,val);
tree[root].v=max(tree[root*2].v,tree[root*2+1].v);
tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}

int QueryMax(int root,int l,int r){
if(tree[root].l>=l && tree[root].r<=r){
    return tree[root].v;
}
int mid=(tree[root].l+tree[root].r)/2,ans=-2147483647;
if(l<=mid)ans=max(ans,QueryMax(root*2,l,r));
if(r>mid)ans=max(ans,QueryMax(root*2+1,l,r));
return ans;
}

int QuerySum(int root,int l,int r){
if(tree[root].l>=l && tree[root].r<=r){
    return tree[root].sum;
}
int mid=(tree[root].l+tree[root].r)/2,ans=0;
if(l<=mid)ans+=QuerySum(root*2,l,r);
if(r>mid)ans+=QuerySum(root*2+1,l,r);
return ans;
}

void dfs1(int u,int father,int deep){
fa[u]=father;
dep[u]=deep;
siz[u]=1;
son[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==father)continue;
    dfs1(v,u,deep+1);
    siz[u]+=siz[v];
    if(siz[v]>siz[son[u]]){
        son[u]=v;
    }
}
}

void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
pre[segn]=u;
if(son[u])dfs2(son[u],ux);
else return;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=son[u] && v!=fa[u]){dfs2(v,v);}
}
}

int AskMax(int u,int v){
int f1=top[u],f2=top[v],ans=-2147483647;
while(f1!=f2){
    if(dep[f1]<dep[f2]){
        swap(u,v);
        swap(f1,f2);
    }
    ans=max(ans,QueryMax(1,id[f1],id[u]));
    u=fa[f1];
    f1=top[u];
}
if(dep[u]>dep[v]){
    swap(u,v);
}
ans=max(ans,QueryMax(1,id[u],id[v]));
return ans;
}

int AskSum(int u,int v){
int f1=top[u],f2=top[v],ans=0;
while(f1!=f2){
    if(dep[f1]<dep[f2]){
        swap(u,v);
        swap(f1,f2);
    }
    ans+=QuerySum(1,id[f1],id[u]);
    u=fa[f1];
    f1=top[u];
}
if(dep[u]>dep[v]){
    swap(u,v);
}
ans+=QuerySum(1,id[u],id[v]);
return ans;
}

int main(){
freopen("1036.in","r",stdin);
freopen("1036.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    add(sa,sb);
    add(sb,sa);
}
for(int i=1;i<=n;i++){
    scanf("%d",&data[i]);
}
dfs1(1,0,1);
dfs2(1,1);
Build(1,1,n);
scanf("%d",&q);
while(q--){
    int sa,sb;
    scanf("%s %d %d",ask,&sa,&sb);
    if(ask[0]=='C'){Update(1,id[sa],sb-data[sa]);data[sa]=sb;}
    if(ask[1]=='M'){printf("%d\n",AskMax(sa,sb));}
    if(ask[1]=='S'){printf("%d\n",AskSum(sa,sb));}
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

struct AC_Trie{
int fail,next[26],key;
AC_Trie(){fail=0;key=0;}
}tree[500005];

int n,cnt=1;
char s[1000005];
queue<int> Q;

void Ins(){
int len=strlen(s),j=1;
for(int i=0;i<len;i++){
	int p=s[i]-'a';
	if(tree[j].next[p]==0)tree[j].next[p]=++cnt;
	j=tree[j].next[p];
}
tree[j].key++;
}

void BFS(){
Q.push(1);
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	for(int i=0;i<=25;i++){
        int v=tree[u].next[i];
		if(v==0)continue;
		Q.push(v);
		if(u==1){
			tree[v].fail=1;
			continue;
		}
		int p=tree[u].fail;
		while(p){
			if(tree[p].next[i]){
				tree[v].fail=tree[p].next[i];
				break;
			}
			p=tree[p].fail;
		}
		if(!p)tree[v].fail=1;
	}
}
}

int GetAns(){
int len=strlen(s),ans=0,j=1;
for(int i=0;i<len;i++){
	int p=s[i]-'a';
	while(tree[j].next[p]==0 && j!=1)j=tree[j].fail;
	j=tree[j].next[p];
	if(j==0)j=1;
	int q=j;
	while(q!=1 && tree[q].key!=-1){
		ans+=tree[q].key;
		tree[q].key=-1;
		q=tree[q].fail;
	}
}
return ans;
}

int main(){
freopen("2222.in","r",stdin);
freopen("2222.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
	scanf("%s",s);
	Ins();
}
BFS();
scanf("%s",s);
printf("%d\n",GetAns());
return 0;
}
#include<cstdio>
#include<algorithm>
using namespace std;

int n,a[1000005],m;

struct Node{
int v,mx,sum,lx,rx,siz,tag,rev;
Node *ch[2],*fa;
Node(int val,Node *fat);
void Pushdown();
void Pushup();
}*root,*Null;

Node::Node(int val=0,Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
v=sum=mx=val;
tag=rev=0;
siz=1;
if(v>=0)lx=rx=v;
else lx=rx=0;
}

void Node::Pushdown(){
if(tag){
	tag=rev=0;
	if(ch[0]!=Null){ch[0]->tag=1;ch[0]->sum=ch[0]->siz*v;ch[0]->v=v;}
	if(ch[1]!=Null){ch[1]->tag=1;ch[1]->sum=ch[1]->siz*v;ch[1]->v=v;}
	if(v>=0){
        if(ch[0]!=Null){ch[0]->lx=ch[0]->mx=ch[0]->rx=v*ch[0]->siz;}
        if(ch[1]!=Null){ch[1]->lx=ch[1]->mx=ch[1]->rx=v*ch[1]->siz;}
	}
	else {
		if(ch[0]!=Null){ch[0]->mx=v;ch[0]->lx=ch[0]->rx=0;}
        if(ch[1]!=Null){ch[1]->mx=v;ch[1]->lx=ch[1]->rx=0;}
	}
}
if(rev){
	rev=0;
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0]->ch[0],ch[0]->ch[1]);
	swap(ch[1]->ch[0],ch[1]->ch[1]);
	swap(ch[0]->lx,ch[0]->rx);
	swap(ch[1]->lx,ch[1]->rx);
}
}

void Node::Pushup(){
siz=ch[0]->siz+ch[1]->siz+1;
sum=ch[0]->sum+ch[1]->sum+v;
mx=max(ch[0]->mx,ch[1]->mx);
mx=max(mx,ch[0]->rx+v+ch[1]->lx);
lx=max(ch[0]->lx,ch[0]->sum+v+ch[1]->lx);
rx=max(ch[1]->rx,ch[1]->sum+v+ch[0]->rx);
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x,Node *place){
while(x->fa!=place){
	Node *y=x->fa,*z=y->fa;
	if(z==Null || z==place)Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
if(place==Null)root=x;
}

Node *Find(Node *splay,int k){
splay->Pushdown();
if(splay->ch[0]->siz+1==k)return splay;
if(splay->ch[0]->siz>=k)return Find(splay->ch[0],k);
return Find(splay->ch[1],k-1-splay->ch[0]->siz);
}

Node *Split(int pos,int tot){
Node *x=Find(root,pos);
Splay(x,Null);
Node *y=Find(root,pos+tot+1);
Splay(y,root);
return y->ch[0];
}

Node *Build(int l,int r){
if(l>r)return Null;
int mid=l+r>>1;
Node *splay=new Node(a[mid],Null);
splay->ch[0]=Build(l,mid-1);
if(splay->ch[0]!=Null)splay->ch[0]->fa=splay;
splay->ch[1]=Build(mid+1,r);
if(splay->ch[1]!=Null)splay->ch[1]->fa=splay;
splay->Pushup();
return splay;
}

void Insert(int pos,int tot){
Node *x=Find(root,pos+1),*y=Find(root,pos+2);
Splay(x,Null);Splay(y,root);
y->ch[0]=Build(1,tot);
if(y->ch[0]!=Null)y->ch[0]->fa=y;
y->Pushup();
x->Pushup();
}

Node *GetNull(){
Node *p=new Node(0,Null);
p->fa=p->ch[0]=p->ch[1]=p;
p->mx=p->v=-1000000000;
p->rev=p->tag=p->siz=p->sum=p->lx=p->rx=0;
return p;
}

void Build_First(){
Null=GetNull();
a[1]=-1000000000;
a[n+2]=-1000000000;
root=Build(1,n+2);
}

void Del_Tree(Node *splay){
if(splay==Null)return;
splay->Pushdown();
Del_Tree(splay->ch[0]);
Del_Tree(splay->ch[1]);
if(splay->ch[0]!=Null)delete splay->ch[0];
if(splay->ch[1]!=Null)delete splay->ch[1];
splay->ch[0]=Null;
splay->ch[1]=Null;
splay->Pushup();
}

void Delete(int pos,int val){
Node *seq=Split(pos,val),*fat=seq->fa;
Del_Tree(seq);
if(seq!=Null)delete seq;
fat->ch[0]=Null;
fat->Pushup();
fat->fa->Pushup();
}

void MakeSame(int pos,int tot,int val){
Node *seq=Split(pos,tot),*fat=seq->fa;
seq->tag=1;
seq->sum=seq->siz*val;
seq->v=val;
if(val>=0)seq->lx=seq->rx=seq->mx=seq->siz*val;
else seq->lx=seq->rx=0,seq->mx=val;
fat->Pushup();
fat->fa->Pushup();
}

void Reverse(int pos,int tot){
Node *seq=Split(pos,tot),*fat=seq->fa;
if(!seq->tag){
	seq->rev^=1;
	swap(seq->ch[0],seq->ch[1]);
	swap(seq->lx,seq->rx);
	fat->Pushup();
	fat->fa->Pushup();
}
}

int GetSum(int pos,int tot){
Node *seq=Split(pos,tot);
return seq->sum;
}

int main(){
freopen("1500.in","r",stdin);
freopen("1500.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=2;i<=n+1;i++)scanf("%d",&a[i]);
Build_First();
for(int i=1;i<=m;i++){
	char s[10];
    scanf("%s",s);
    if(s[0]=='I'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		for(int i=1;i<=tot;i++)scanf("%d",&a[i]);
		Insert(pos,tot);
	}
	if(s[0]=='D'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		Delete(pos,tot);
	}
	if(s[0]=='M' && s[2]=='K'){
		int pos,tot,val;
		scanf("%d %d %d",&pos,&tot,&val);
        MakeSame(pos,tot,val);
	}
	if(s[0]=='M' && s[2]=='X'){
		printf("%d\n",root->mx);
	}
	if(s[0]=='R'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		Reverse(pos,tot);
	}
	if(s[0]=='G'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		printf("%d\n",GetSum(pos,tot));
	}
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

char s[500005];
int n,rank[500005],rank2[500005],height[500005],sa[500005],rmq[500005][20],ws[500005],wv[500005],er[20],log2[500005];

int cmp(int *r,int a,int b,int l){return (r[a]==r[b])&(r[a+l]==r[b+l]);}

void GetSA(char *r,int *sa,int n,int m){
int i,j,p,*x=rank,*y=rank2,*t;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]=r[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;
for(j=p=1;p<n;j*=2,m=p){
	for(p=0,i=n-j;i<n;i++)y[p++]=i;
	for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
	for(i=0;i<m;i++)ws[i]=0;
	for(i=0;i<n;i++)ws[wv[i]=x[y[i]]]++;
	for(i=1;i<m;i++)ws[i]+=ws[i-1];
	for(i=n-1;i>=0;i--)sa[--ws[wv[i]]]=y[i];
	for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}

void CalHeight(char *r,int *sa,int n){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k)for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}

void RMQ(){
int i,j;
er[0]=1;
for(i=1;i<20;i++)er[i]=er[i-1]<<1;
log2[0]=-1;
for(i=1;i<=n;i++)log2[i]=(i&(i-1))?log2[i-1]:log2[i-1]+1;
for(i=1;i<=n;i++)rmq[i][0]=height[i];
for(j=1;j<20;j++)for(i=1;i+er[j-1]-1<=n;i++)rmq[i][j]=min(rmq[i][j-1],rmq[i+er[j-1]][j-1]);
}

int LCP(int a,int b){
int x=rank[a],y=rank[b],t;
if(x>y)t=x,x=y,y=t;
x++;
int k=log2[y-x+1];
return min(rmq[x][k],rmq[y-er[k]+1][k]);
}

int main(){
freopen("suffix.in","r",stdin);
freopen("suffix.out","w",stdout);
scanf("%s",s);
n=strlen(s);
s[n]=0;
GetSA(s,sa,n+1,128);
CalHeight(s,sa,n);
RMQ();
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    printf("%d\n",LCP(sa,sb));
}
return 0;
}
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;

const double Pi=2*asin(1);
const int NUM_SIZE=100005;

int An,Bn,Cn,Rev[NUM_SIZE*3],Step,n;

struct Complex{
double a,b;
Complex(double as=0.0,double bs=0.0){a=as;b=bs;}
friend Complex operator+(Complex a,Complex b){return Complex(a.a+b.a,a.b+b.b);}
friend Complex operator-(Complex a,Complex b){return Complex(a.a-b.a,a.b-b.b);}
friend Complex operator*(Complex a,Complex b){return Complex(a.a*b.a-a.b*b.b,b.a*a.b+a.a*b.b);}
friend Complex operator/(Complex a,Complex b){return Complex((a.a*b.a+a.b*b.b)/(b.a*b.a+b.b*b.b),(b.a*a.b-a.a*b.b)/(b.a*b.a+b.b*b.b));}
double Mod(){return sqrt(a*a+b*b);}
}A[NUM_SIZE*3],B[NUM_SIZE*3],C[NUM_SIZE*3];

template<typename T>void Read(T &x){
int flag=1;
char ch;
while((ch=getchar())<'0' || ch>'9')if(ch=='-')flag=-1;
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
x*=flag;
}

void FFT(Complex *x,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);
for(int k=1;k<n;k<<=1){
    Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
    for(int i=0;i<n;i+=k<<1){
		Complex wkj=Complex(1.0,0.0);
		for(int j=0;j<k;j++){
			Complex a=x[i+j],b=x[i+j+k]*wkj;
			x[i+j]=a+b;
			x[i+j+k]=a-b;
			wkj=wkj*wk;
		}
    }
}
if(flag==-1){for(int i=0;i<n;i++)x[i].a/=n;}
}

int main(){
freopen("34.in","r",stdin);
freopen("34.out","w",stdout);
Read(An);Read(Bn);
An++;Bn++;
Cn=An+Bn-1;
for(int i=0;i<An;i++)Read(A[i].a);
for(int i=0;i<Bn;i++)Read(B[i].a);
for(n=1,Step=0;n<Cn;Step++,n<<=1);
for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
FFT(A,1);
FFT(B,1);
for(int i=0;i<n;i++)C[i]=A[i]*B[i];
FFT(C,-1);
for(int i=0;i<Cn;i++)printf("%d ",(int)(C[i].a+0.5));
putchar('\n');
return 0;
}
Category: OI | Tags: OI
10
25
2015
0

KMP+Manacher学习笔记

KMP是一种可以在最坏O(n+m)的时间内完成匹配的字符串匹配算法。学了这个也有一些时间了,也是时候写一点学习笔记了。

KMP需要处理一个next数组,也就是当匹配失败后应该跳转到的匹配位置。

算法如下(懒癌晚期,简直啥也没说)

UPD:代码里面有一个明显的错误今天才发现……我水平怎么这么低……为被坑到的同学们道个歉……555 ——2016.6.21

char s1[1000005],s2[105];
int next[105];
//s1表示需要匹配的串,s2表示模式串

void Fill(){
memset(next,0,sizeof(next));
int len=strlen(s2);
for(int i=0;i<len2;i++){
    int j=next[i];
    while(j && s[i]!=s[j])j=next[j];
    next[j+1]=(s[i]==s[j])?j+1:0;
}
}

//以下Find函数的mode意思是:当mode=0时,输出匹配成功的位置;mode=1时,输出出现的次数.

int Find(int mode){
Fill();
int ans=0,len1=strlen(s1),len2=strlen(s2),j=0;
for(int i=0;i<len1;i++){
    while(j && s1[i]!=s2[j])j=next[j];
    if(s1[i]==s2[j])j++;
    if(j==len2){
        if(mode)ans++;
        else return i-len2+1;
    }
}
return ans;
}

接下来是Manacher算法。

这是一种可以O(n)解决回文子串的算法。详见这里

你萌不觉得我的代码简直就是背模版么233

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int p[240005],len;
char s[240005];

int main(){
freopen("3068.in","r",stdin);
freopen("3068.out","w",stdout);
while(scanf("%s",s)!=EOF){
    int len=strlen(s),id=0,maxlen=0;
    for(int i=len;i>=0;i--){
        s[i*2+1]='#';
        s[i*2+2]=s[i];
    }
    s[0]='*';
    s[len*2+3]='\0';
    for(int i=2;i<2*len+1;i++){
        if(p[id]+id>i){
            p[i]=min(p[id*2-i],p[id]+id-i);
        }
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]])p[i]++;
        if(id+p[id]<i+p[i])id=i;
        if(p[i]>maxlen)maxlen=p[i];
    }
    printf("%d\n",maxlen-1);
}
return 0;
}
Category: OI | Tags: OI
10
16
2015
0

单调队列训练

http://hzwer.com/?s=%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97

已经做了几题:

1

Category: OI | Tags: OI
10
15
2015
0

多重背包单调队列优化的理解

其实我早就会写多重背包了……只不过是写成做多次01背包而已……

看着大爷秒题,我心中感到自己好弱啊。

于是我就来理解一下多重背包的单调队列做法,并记录在这里。

对于一个物品有个数限制的背包,我们考虑状态转移方程:

f[now][j]=max(f[last][j],f[last][j-w[i]*k]+c[i]*k),其中w[i]为重量,c[i]为价值。

感觉要枚举i,j,k,然后时间复杂度就爆炸了……

怎么办?用单调队列!

因为当我们取到了最大的f[last][j-w[i]*k]+c[i]*k时,再往下取k就没有意义了(不可能大于这个值)

所以我们维护一个单调队列,使队首为最大值,每次把不符合的队首删去,同时把队尾小于我们枚举的f[last][j-w[i]*k]+c[i]*k删去。

队列中存的是k,也就是记录当前取了多少个该物品,即可。

下面是一道例题。

----------------------------------------------------------------

超市购物

Description

Bob家附近新开了一家超市。最近,超市开展了促销活动。
超 市共出售N种不同的商品,编号为1…N。不同的物品对Bob来说有不同的价值,第i种物品每一个的价值为Wi。而每种商品的售价也不相同,第i种物品的单 价为Ci元。同一种商品可以买多个。超市经理为了避免某些商品被一抢而光,决定每种商品每位顾客最多只能买Li个。现在,Bob共有M元,他想知道在花费 不超过M元的情况下,能买到的商品价值和最大为多少?

Input

第1行两个整数N和M,分别表示商品的种数与Bob现有的钱数。
接下来N行每行为三个整数Ci,Wi,Li,分别表示第i种商品的单价,单个的价值,最多可购买的件数。

Output

输出只有一行,为Bob能买到的商品最大价值和。

Sample Input

5 30
3 1 3
1 4 1
8 10 3
4 7 2
2 2 4

Sample Output

42

Hint

20%的数据:N≤30,M≤10000,Li≤500;
70%的数据:N≤50,M≤500000,Li≤2000;
100%的数据:N≤50,M≤500000,Li≤500000;
----------------------------------------------------------------
Code:
#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,l[55],c[55],w[55],f[2][500005],q[500005];

int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    scanf("%d %d %d",&c[i],&w[i],&l[i]);
}
for(int i=1;i<=n;i++){
    int now=i%2,last;
    last=now^1;
    for(int j=0;j<c[i];j++){
        int Rear=1,Front=1;
        q[1]=0;
        for(int k=0;k*c[i]+j<=m;k++){
            while(Front!=Rear && k-q[Front]>l[i])Front++;
            f[now][k*c[i]+j]=max(f[last][k*c[i]+j],f[last][q[Front]*c[i]+j]+w[i]*(k-q[Front]));
            while(Front<=Rear && f[last][q[Rear]*c[i]+j]+w[i]*(k-q[Rear])<=f[last][k*c[i]+j])Rear--;
            q[++Rear]=k;
        }
    }
}
printf("%d\n",f[n%2][m]);
return 0;
}

 

Category: OI | Tags: OI

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com