BZOJ3881:[Coci2015]Divljak AC自动机+树链求并

思路:

AC自动机的Fail树有很多奇妙的性质.

例如串\(a\)是串\(b\)在Fail树上的祖先,那么\(a\)在\(b\)中应该出现\(dep[b]-dep[a]\)次.

(不过好像跟这题没什么关系)
 

把Alice的\(n\)个字符串插入AC自动机.

然后每插入一个修改串,都动态维护一下每个自动机中的节点,如果出现在修改串中,则该节点答案+1.

我们用修改串在自动机上走,每走到一个节点,我们都想要这个节点在Fail树上到根的路径上的答案均+1.

遗憾的是,这样有可能重复!

 

利用树链的并.

将所有要处理的节点按照dfs序排序,然后首先把它们到根的路径+1.

随后将相邻两个节点的LCA到根的路径-1.

非常科学.

 

怎么加?树链剖分?等TLE吧.

直接将标记累加在节点上,询问时就询问子树内的标记之和.

这样只需用树状数组维护DFS序即可.

 

可惜卡常数!

用倍增LCA会超时.

于是我们换用RMQlca,并用ZKW线段树维护.

估计ST表预处理也会超时.

 

反正总算还是水过去了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
  
#define N 2002010
int ch[N][26],fail[N],ins[N],cnt;
char s[N];
  
int head[N],next[N],end[N];
inline void addedge(int a,int b){
    static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;
}
  
int in[N],out[N],dep[N],tclock;
void dfs(int x){
    in[x]=++tclock;
    for(int j=head[x];j;j=next[j])
        dep[end[j]]=dep[x]+1,dfs(end[j]);
    out[x]=tclock;
}
 
namespace Lca_system{
    int Seq[N<<1],a[8383608],M,ins[N],cnt;
    inline void build_dfs(int x){
        ins[x]=++cnt;
        Seq[cnt]=x;
        for(int j=head[x];j;j=next[j]){
            build_dfs(end[j]);
            Seq[++cnt]=x;
        }
    }
    inline int Min(int x,int y){
        if(x==-1||y==-1)return x==-1?y:x;
        return dep[x]<dep[y]?x:y;
    }
    inline void init(){
        build_dfs(0);
        for(M=1;M<cnt+2;M<<=1);
        memset(a,-1,sizeof a);
        for(int i=1;i<=cnt;++i)a[M+i]=Seq[i];
        for(int i=M-1;i>=1;--i)a[i]=Min(a[2*i],a[2*i+1]);
    }
    inline int ask(int tl,int tr){
        int re=-1;
        for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
            if(~tl&1)re=Min(re,a[tl^1]);
            if(tr&1)re=Min(re,a[tr^1]);
        }
        return re;
    }
    inline int lca(int x,int y){
        x=ins[x],y=ins[y];
        if(x>y)swap(x,y);
        return ask(x,y);
    }
}
 
int seq[N],num;
  
int A[N];
inline void modify(int x,int c){
    for(;x<=cnt+1;x+=x&-x)A[x]+=c;
}
inline int ask(int x){
    int re=0;for(;x;x-=x&-x)re+=A[x];return re;
}
  
inline bool cmp(const int&x,const int&y){return in[x]<in[y];}
  
inline int git(){
    int c,re;
    while(!isdigit(c=getchar()));
    re=c-'0';
    while(isdigit(c=getchar()))re=(re<<1)+(re<<3)+c-'0';
    return re;
}
char buf[100010*6],*o=buf;
inline void print(int x){
    static int s[100];int top=0;
    if(!x)*o++=48;else{for(;x;x/=10)s[++top]=x%10;for(int i=top;i>=1;--i)*o++=48+s[i];}
    *o++='\n';
}
int main(){
    int n=git();
    register int i,j;
      
    int len,p;
    for(i=1;i<=n;++i){
        scanf("%s",s);
        len=strlen(s),p=0;
        for(j=0;j<len;++j){
            if(!ch[p][s[j]-'a'])ch[p][s[j]-'a']=++cnt;
            p=ch[p][s[j]-'a'];
        }
        ins[i]=p;
    }
      
    queue<int>q;
    for(i=0;i<26;++i)if(ch[0][i])q.push(ch[0][i]);
    int u,v,r;
    while(!q.empty()){
        u=q.front(),q.pop();
        for(i=0;i<26;++i)if((v=ch[u][i])){
            q.push(v);
            for(r=fail[u];r&&!ch[r][i];r=fail[r]);
            fail[v]=ch[r][i];
        }
    }
      
    for(i=1;i<=cnt;++i)addedge(fail[i],i);
    dep[0]=1,dfs(0);
    Lca_system::init();
      
    int Q=git();
      
    int qte,x;
    while(Q--){
        qte=git();
        if(qte==1){
            scanf("%s",s);
            len=strlen(s),p=0,num=0;
            for(i=0;i<len;++i){
                while(p&&!ch[p][s[i]-'a'])p=fail[p];
                p=ch[p][s[i]-'a'];
                if(p)seq[++num]=p;
            }
            sort(seq+1,seq+num+1,cmp);
            for(i=1;i<=num;++i)modify(in[seq[i]],1);
            for(i=1;i<num;++i)modify(in[Lca_system::lca(seq[i],seq[i+1])],-1);
        }
        else{
            x=git();
            print(ask(out[ins[x]])-ask(in[ins[x]]-1));
        }
    }
      
    fwrite(buf,1,o-buf,stdout);
    return 0;
}

BZOJ3743:[Coci2015]Kamp 树形dp

思路:

首先发现如果根确定的话,我们要求的答案就是根和关键点们组成的虚树的边长之和的2倍减去根到所有关键点的距离最大值.

这个应该不难理解.

 

然后觉得虚树很难处理,就抛弃虚树,弄了一个繁琐至极的两遍dp.(这个我就不写是怎么dp的啦,大家应该都会.)

 

然后看到某个题解说最上面说的那个东西bfs就行.

如何呢?

一个关键的性质:树上距离一个点最远的点必定是直径的一端!这个想想很显然.

然后就简单了.

 

下面是我的傻叉dp:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 1ll<<59
 
#define N 500010
int head[N],next[N<<1],end[N<<1],len[N<<1];
inline void addedge(int a,int b,int c){static int q=1;end[q]=b,next[q]=head[a],head[a]=q,len[q++]=c;}
inline void make(int a,int b,int c){addedge(a,b,c),addedge(b,a,c);}
 
bool c[N];
 
long long max_dis[N],cnt[N],total_dis[N];
inline void dp1(int x,int fa){
    for(int j=head[x];j;j=next[j])if(end[j]!=fa)dp1(end[j],x);
    cnt[x]=c[x],max_dis[x]=c[x]?0:-INF,total_dis[x]=0;
    for(int j=head[x];j;j=next[j])if(end[j]!=fa){
        cnt[x]+=cnt[end[j]];
        max_dis[x]=max(max_dis[x],max_dis[end[j]]+len[j]);
        total_dis[x]+=total_dis[end[j]]+(cnt[end[j]]?1ll:0ll)*len[j];
    }
}
 
long long re[N];
long long seq[N],pre[N],suc[N],g[N];
inline void dp2(int x,int fa,int fadis){
    long long real_total_dis,real_max_dis;
    if(x==1)real_total_dis=total_dis[x],real_max_dis=max_dis[x];
    else{
        real_total_dis=total_dis[x]+total_dis[fa]+(cnt[fa]?1ll:0ll)*fadis;
        real_max_dis=max(max_dis[x],max_dis[fa]+fadis);
    }
    re[x]=real_total_dis*2-real_max_dis;
     
    int num=0;
    for(int j=head[x];j;j=next[j])if(end[j]!=fa)seq[++num]=max_dis[end[j]]+len[j];
    pre[0]=suc[num+1]=-INF;
    for(int i=1;i<=num;++i)pre[i]=max(seq[i],pre[i-1]);
    for(int i=num;i>=1;--i)suc[i]=max(seq[i],suc[i+1]);
     
    num=0;
    for(int j=head[x];j;j=next[j])if(end[j]!=fa){
        ++num;
        g[end[j]]=max(pre[num-1],suc[num+1]);
    }
     
    int real_cnt=cnt[x];
    for(int j=head[x];j;j=next[j])if(end[j]!=fa){
        total_dis[x]=real_total_dis-total_dis[end[j]];
        if(cnt[end[j]])total_dis[x]-=len[j];
        max_dis[x]=g[end[j]];
        if(x!=1)max_dis[x]=max(max_dis[x],max_dis[fa]+fadis);
        if(c[x])max_dis[x]=max(max_dis[x],0ll);
        cnt[x]=real_cnt-cnt[end[j]]+cnt[fa];
         
        dp2(end[j],x,len[j]);
    }
}
 
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j;
    if(m==0){puts("0");return 0;}
    int a,b,x;
    for(i=1;i<n;++i)scanf("%d%d%d",&a,&b,&x),make(a,b,x);
     
    while(m--)scanf("%d",&x),c[x]=1;
    dp1(1,-1);
    dp2(1,-1,0);
     
    for(i=1;i<=n;++i)printf("%lld\n",re[i]);
    return 0;
}

BZOJ3810:[Coci2015]Stanovi dp

思路:

首先有一个性质:当前的矩形必定可以被划分成两个子矩形.

无脑dp.

记录四个状态表示当前矩形的四条边是不是原来的大矩形的边.

然后记忆化搜索即可.

(要非常注意常数优化)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 1ll<<60
 
#define N 310
long long f[2][2][2][2][N][N];
int n,m,k;
 
inline long long calc(int w,int h,int a,int b,int c,int d){
    if(w>h){
        swap(w,h);
        int aa=c,bb=d,cc=b,dd=a;
        a=aa,b=bb,c=cc,d=dd;
        if(a>b)swap(a,b);
        if(c>d)swap(c,d);
    }
    if(f[a][b][c][d][w][h]!=-1)return f[a][b][c][d][w][h];
    if(!a&&!b&&!c&&!d)return f[a][b][c][d][w][h]=INF;
    long long re=(long long)(w*h-k)*(w*h-k);
    if(a+b+c>0&&a+b+d>0)
        for(int i=1;i<w;++i)re=min(re,calc(i,h,a,b,c,0)+calc(w-i,h,a,b,0,d));
    if(a+c+d>0&&b+c+d>0)
        for(int i=1;i<h;++i)re=min(re,calc(w,i,a,0,c,d)+calc(w,h-i,0,b,c,d));
    return f[a][b][c][d][w][h]=re;
}
 
int main(){
    scanf("%d%d%d",&n,&m,&k);
    register int i,j;
     
    memset(f,-1,sizeof f);
    printf("%lld",calc(n,m,1,1,1,1));
     
    return 0;
}

BZOJ1560:[JSOI2009]火星藏宝图 dp

思路:

首先不难想到排序后dp,可是这样就\(O(n^2)\)超时了.

一开始想的是按照列从前往后做,然后给每一个之前的列维护一个单调队列.可是发现这样是\(O(m^3)\)的.

我们可以注意到一条性质:由于\(a,b>0\)时,\((a+b)^2>a^2+b^2\),且价值均\(>0\),所以路径上相邻两个点形成的矩形中不能存在别的点.

也就是说对于之前的每一列,只有最下面的才有用.

我们在扫的时候顺便记录一下这个就好了.

时间复杂度\(O(nm)\).

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

#define N 200010
#define M 1010
struct Pos{
	int x,y,lab;
	bool operator<(const Pos&B)const{return x<B.x||(x==B.x&&y<B.y);}
}P[N];

int w[N],f[N],g[M],x[N],y[N];
inline int sqr(int x){return x*x;}

int main(){
	int n,m;scanf("%d%d",&n,&m);register int i,j;
	
	for(i=1;i<=n;++i)scanf("%d%d",&P[i].x,&P[i].y),x[i]=P[i].x,y[i]=P[i].y,P[i].lab=i,scanf("%d",&w[i]);
	sort(P+1,P+n+1);
	
	f[P[1].lab]=w[P[1].lab],g[1]=P[1].lab;
	for(i=2;i<=n;++i){
		f[P[i].lab]=-1<<30;
		for(j=1;j<=P[i].y;++j)if(g[j])f[P[i].lab]=max(f[P[i].lab],f[g[j]]+w[P[i].lab]-sqr(P[i].y-j)-sqr(P[i].x-x[g[j]]));
		g[P[i].y]=P[i].lab;
	}
	
	for(i=1;i<=n;++i)if(x[i]==m&&y[i]==m)printf("%d",f[i]);
	return 0;
}

单纯形法的若干题目 BZOJ3112,3265,3550

利用一下对偶原理建模什么的都非常裸,就放一下代码吧.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
 
#define INF ~0U>>1
 
struct Solver{
    static const int N=10010;//变量个数
    static const int M=1010;//限制个数
    int n,m;
    int B[M];//基变量集合
    int NB[N];//非基变量集合
    f2 c[N],v;//目标函数的各项系数以及常数
    f2 A[M][N],b[N];//限制的系数
     
    Solver(){}
    Solver(int _n,int _m):n(_n),m(_m){}
     
    void debug(){
        puts("Function");
        printf("Maximize ");
        for(int i=1;i<=n;++i){
            if(i>1)putchar('+');
            printf("%.2lfx_%d",c[i],NB[i]);
        }
        printf("+%.2lf\n",v);
         
        puts("Limits");
        for(int i=1;i<=m;++i){
            printf("x_%d",B[i]);
            for(int j=1;j<=n;++j)printf("+%.2lfx_%d",A[i][j],NB[j]);
            printf("<=%.2lf\n",b[i]);
        }
    }
     
    inline void pivot(int l,int e){//转轴操作,将第l个基变量与第e个非基变量进行交换
        int i,j,k;
         
        //更改第l个限制,得到x_e与x_l的关系式
        b[l]/=A[l][e];
        for(i=1;i<=n;++i)if(i!=e)A[l][i]/=A[l][e];
        A[l][e]=1/A[l][e];
         
        //将x_e带入,更改剩余的所有限制
        for(i=1;i<=m;++i)if(i!=l&&A[i][e]!=0){
            b[i]-=b[l]*A[i][e];
            for(j=1;j<=n;++j)if(j!=e)A[i][j]-=A[i][e]*A[l][j];
            A[i][e]=-A[i][e]*A[l][e];
        }
         
        //更改目标函数
        v+=c[e]*b[l];
        for(i=1;i<=n;++i)if(i!=e)c[i]-=c[e]*A[l][i];
        c[e]=-c[e]*A[l][e];
        swap(B[l],NB[e]);
    }
    inline f2 solve(){//得到线性规划的最优解,或者返回无界区域
        int i,j,l,e,lim;
         
        while(1){
            for(e=0,i=1;i<=n;++i)if(c[i]>0){e=i;break;}//寻找最小标号的可行非基变量
            if(e==0)return v;//如果不存在这样的非基变量,则已经是最优解,直接返回
             
            //寻找最紧的上界
            for(lim=INF,i=1;i<=m;++i)if(A[i][e]>0&&lim>b[i]/A[i][e])l=i,lim=b[i]/A[i][e];
            if(lim==INF)return INF;//没有限制,返回无界区域
            else pivot(l,e);//否则进行转轴操作
        }
    }
}Complex;
 
void output(){Complex.debug();}
 
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    register int i,j;
     
    Complex.n=m,Complex.m=n;
    int x;
    for(i=1;i<=n;++i)scanf("%d",&x),Complex.b[i]=x;
     
    int l,r;
    for(i=1;i<=m;++i){
        scanf("%d%d%d",&l,&r,&x);
        for(j=l;j<=r;++j)Complex.A[j][i]=1;
        Complex.c[i]=x;
    }
     
    for(i=1;i<=Complex.n;++i)Complex.NB[i]=i;
    for(i=1;i<=Complex.m;++i)Complex.B[i]=Complex.n+i;
     
    //Complex.debug();
     
    printf("%d",(int)Complex.solve());
 
    return 0;
}

233剩下的两道题目也很类似.

BZOJ2221:[Jsoi2009]面试的考验 单调性+随机数据

思路:

宋文杰的题解很详细.

一开始每个点30s,结果在OJ上一共30s...

也就是说原来莫队是能过的,结果我无悬念TLE.

莫队怎么做我就不说了.(貌似官方正解就是莫队...)

莫队很暴力,因为没有利用一个题目中的性质:就是数据随机生成!

询问随不随机意义是不大的.

但是如果询问很特殊,我们就可以用科学的方法去处理:

(1)任意两个区间不互相包含.这种情况我们将区间随便排个序就能发现总移动次数是\(O(n)\)的.

(2)任意两个区间要么互相包含,要么不相交.这样就会形成一棵树.我们利用启发式合并,插入次数就为\(O(nlogn)\).

但是随机数据显然没有这种性质.

 

那么唯一可能有比较优秀的性质的就是随机数列了.

考虑一种朴素算法:

将所有询问离线按照右端点从小到大排序.

从前向后依次加入右端点,令\(f_i\)表示当前以\(i\)为起点的后缀的答案,那么朴素来看,如果当前加入的是\(n\),那么\(f_1-f_{n-1}\)都需要更新.

但是有很多冗余的更新.

例如我们考虑所有大于\(a_n\)的数,不妨令\(a_i,a_j>a_n,a_i>a_j,i<j\),那么如果我们能够维护一个后缀的答案,我们就只需更新\(f_j\)就可以了.

于是我们发现了某些单调性.

我们利用数据结构维护后缀的答案,那么只需更新一些点就行了.

那么我们的任务就是找到,对于\(n\)之前的数,一个均\(>a_n\)的递减序列,一个均\(<a_n\)的递增序列.然后我们就拿序列中的东西暴力更新答案.

然而由于是随机数据,序列中的元素个数是\(O(logn)\)级别的.

这样总时间复杂度就是\(O(qlogn+nlog^2n)\).

具体去看宋文杰的题解.

(另外此题要求结果\(>0\) 23333)

 

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

#define N 100010
#define Q 100010
int n,q,a[N];

struct Interval{
	int l,r,lab;
	bool operator<(const Interval&B)const{return r<B.r;}
}S[N];
int re[Q];

inline void mini(int&x,int y){if(x>y)x=y;}
struct SegmentTree{
	int A[262144],M;
	inline void Init(int _siz){
		for(M=1;M<(_siz+2);M<<=1);
		memset(A,0x3f,sizeof A);
	}
	inline void modify(int x,int d){
		for(x+=M;x;x>>=1)mini(A[x],d);
	}
	inline int query(int tl,int tr){
		int re=~0U>>1;
		for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
			if(~tl&1)mini(re,A[tl^1]);
			if(tr&1)mini(re,A[tr^1]);
		}
		return re;
	}
}Seg;

int preless[N],premore[N],small[N][30],big[N][30],stk[N],top;

int main(){
	//freopen("tt.in","r",stdin);
	scanf("%d%d",&n,&q);
	register int i,j,k;
	
	for(i=1;i<=n;++i)scanf("%d",&a[i]);
	
	for(i=1;i<=q;++i)
		scanf("%d%d",&S[i].l,&S[i].r),S[i].lab=i;
	sort(S+1,S+q+1);
	
	Seg.Init(n);
	
	for(i=1;i<=n;++i){
		while(top&&a[stk[top]]>=a[i])--top;
		preless[i]=stk[top];
		stk[++top]=i;
	}
	top=0;
	for(i=1;i<=n;++i){
		while(top&&a[stk[top]]<=a[i])--top;
		premore[i]=stk[top];
		stk[++top]=i;
	}
	
	for(i=1;i<=n;++i){
		if(premore[i]){
			big[i][++big[i][0]]=premore[i];
			j=big[i][1];
			while(1){
				bool find=0;
				for(k=1;k<=small[j][0];++k)if(a[small[j][k]]>a[i]){find=1;break;}
				if(find)big[i][++big[i][0]]=(j=small[j][k]);else break;
			}
		}
		if(preless[i]){
			small[i][++small[i][0]]=preless[i];
			j=small[i][1];
			while(1){
				bool find=0;
				for(k=1;k<=big[j][0];++k)if(a[big[j][k]]<a[i]){find=1;break;}
				if(find)small[i][++small[i][0]]=(j=big[j][k]);else break;
			}
		}
	}
	j=1;
	for(i=1;i<=n;++i){
		for(k=1;k<=small[i][0];++k)Seg.modify(small[i][k],a[i]-a[small[i][k]]);
		for(k=1;k<=big[i][0];++k)Seg.modify(big[i][k],a[big[i][k]]-a[i]);
		
		for(;j<=q&&S[j].r==i;++j)re[S[j].lab]=Seg.query(S[j].l,S[j].r);
		
	}
	
	for(i=1;i<=q;++i)printf("%d\n",re[i]);
	
	return 0;
}

BZOJ2560:串珠子 状压dp

思路:

令\(f[S]\)表示集合S形成连通图的方案数,\(g[s]\)表示集合S内部任意连边的方案数.

显然:

\[g[S]=\prod_{i,j\in{S},i<j}c_{i,j}+1\]

这个我们可以在\(O(2^n{n^2})\)的复杂度内算出来.

接下来考虑计算\(f[S]\).

我们用总数减去不连通的图的个数.

假设\(x\in{S}\),我们不妨枚举所有\(S\)的真子集\(S'\),其中\(S'\)就代表包含\(x\)的一个连通块,\(S-S'\)均与\(x\)不连通.

那么\(f[S']\)我们已经算过了,剩下的\(S-S'\)就利用我们之前预处理的随意连边的\(g\)数组.

于是我们得到转移:

\[f[S]=\sum_{S'\subset{S},x\in{S'}}f[S']g[S-S']\]

这个过程是\(O(3^n)\).

然后我们就在\(O(2^n{n^2}+3^n)\)的时间内解决了这题.

 

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
#define N 16
 
int f[1<<N],g[1<<N],h[1<<N],c[N][N];
static const int mod=(1e9)+7;
inline void inc(int&x,int y){if((x+=y)>=mod)x-=mod;}
 
#define p(S,x) (((S)>>(x))&1)
 
int main(){
    int n;scanf("%d",&n);register int i,j,k;
    for(i=0;i<n;++i)for(j=0;j<n;++j)scanf("%d",&c[i][j]);
    for(i=0;i<n;++i)f[1<<i]=g[1<<i]=1;
    for(i=1;i<(1<<n);++i)h[i]=h[i^(i&-i)]+1;
    for(i=1;i<(1<<n);++i){
        if(h[i]==1)continue;
        else{
            g[i]=1;
            for(j=0;j<n;++j)for(k=j+1;k<n;++k)if(p(i,j)&&p(i,k))
                g[i]=(LL)g[i]*(c[j][k]+1)%mod;
            int ins;
            for(j=0;j<n;++j)if(p(i,j)){ins=j;break;}
            for(int mas=(i-1)&i;mas;mas=(mas-1)&i)if(p(mas,ins))
                inc(f[i],(LL)f[mas]*g[i^mas]%mod);
            f[i]=(g[i]>=f[i])?g[i]-f[i]:g[i]+mod-f[i];
        }
    }
    printf("%d",f[(1<<n)-1]);
    return 0;
}

BZOJ1185:[HNOI2007]最小矩形覆盖 凸包+旋转卡壳+三分

思路:

首先有一个显然的性质:就是最小矩形必定有一条边与凸包的边重合.

然后我们自然就是对于每一条边考虑一下:首先找到距离这条边最远的点.然后从这个点到这条边做一条垂线段,用这条垂线段上下平移来得到两个边界.

于是我用旋转卡壳找最远的点,然后对于两边分别三分.

效率好像还不低.

 

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
 
static const f2 eps=1e-7;
inline int dcmp(const f2&x){return fabs(x)<eps?0:(x<0?-1:1);}
 
#define N 50010
struct Point{
    f2 x,y;
    Point(){}
    Point(f2 _x,f2 _y):x(_x),y(_y){}
     
    inline void read(){scanf("%lf%lf",&x,&y);}
    inline void print(){printf("%.5lf %.5lf\n",x,y);}
     
    bool operator<(const Point&B)const{return fabs(x-B.x)==0?y<B.y:x<B.x;}
     
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
    Point operator*(const f2&p)const{return Point(x*p,y*p);}
};
 
Point getvec(const Point&v){return Point(-v.y,v.x);}
Point getmid(const Point&a,const Point&b){return Point((a.x+b.x)/2,(a.y+b.y)/2);}
 
f2 getdis(const Point&a,const Point&b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
f2 cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;}
f2 area(const Point&a,const Point&b,const Point&c){return fabs(cross(a-b,a-c))*.5;}
 
struct Line{
    Point p,v;
    Line(Point p1,Point p2,bool d){p=p1,v=d?p1-p2:p2;}
};
 
Point getlineintersection(const Line&l1,const Line&l2){
    return l1.p+l1.v*(cross(l1.p-l2.p,l2.v)/cross(l1.v,l2.v));
}
 
Point P[N],stk[N<<1];int top;
 
Point move(Point p,Point v,f2 l){
    return p+v*(l/sqrt(v.x*v.x+v.y*v.y));
}
 
f2 res=1e10;
Point re[N];
 
int main(){
    //freopen("tt.in","r",stdin);
    int n;scanf("%d",&n);
    register int i,j;
     
    for(i=1;i<=n;++i)P[i].read();
     
    sort(P+1,P+n+1);
    int ins;for(ins=n;ins!=1&&dcmp(P[ins].x-P[ins-1].x)==0;--ins);
    for(i=ins;i<=(n+ins)/2;++i)swap(P[i],P[n+ins-i]);
     
    for(i=1;i<=n;++i){
        if(!top)stk[++top]=P[i];
        else{while(top>=2&&dcmp(cross(stk[top-1]-stk[top],stk[top]-P[i]))<=0)--top;stk[++top]=P[i];}
    }
    int instk=top;
    for(i=ins-1;i>=1;--i){
        if(top==instk)stk[++top]=P[i];
        else{while(top>=instk+1&&dcmp(cross(stk[top-1]-stk[top],stk[top]-P[i]))<=0)--top;stk[++top]=P[i];}
    }--top;
     
    for(i=top+1;i<=2*top;++i)stk[i]=stk[i-top];
     
    int r=2,L,R,ll,rr;
    f2 h1,h2;
    for(i=1;i<=top;++i){
        while(area(stk[i],stk[i+1],stk[r])<=area(stk[i],stk[i+1],stk[r+1]))++r;
         
        Line l1=Line(stk[i],stk[i+1],1);
        Line l2=Line(stk[r],getvec(l1.v),0);
        Point pr=getlineintersection(l1,l2);
         
        h1=h2=0;
        for(L=i+1,R=r;;){
            if(R-L+1<=5){for(j=L;j<=R;++j)h1=max(h1,area(stk[r],pr,stk[j])*2/getdis(stk[r],pr));break;}
             
            ll=L+(R-L+1)/3,rr=R-(R-L+1)/3;
            if(area(stk[r],pr,stk[ll])<=area(stk[r],pr,stk[rr]))L=ll;else R=rr;
        }
        for(L=r,R=i+top;;){
            if(R-L+1<=5){for(j=L;j<=R;++j)h2=max(h2,area(stk[r],pr,stk[j])*2/getdis(stk[r],pr));break;}
             
            ll=L+(R-L+1)/3,rr=R-(R-L+1)/3;
            if(area(stk[r],pr,stk[ll])<=area(stk[r],pr,stk[rr]))L=ll;else R=rr;
        }
         
        if(getdis(stk[r],pr)*(h1+h2)<res){
            res=getdis(stk[r],pr)*(h1+h2);
            re[0]=move(pr,stk[i]-stk[i+1],h1);
            re[1]=move(stk[r],stk[i]-stk[i+1],h1);
            re[2]=move(stk[r],stk[i+1]-stk[i],h2);
            re[3]=move(pr,stk[i+1]-stk[i],h2);
        }
    }
     
    printf("%.5lf\n",res);
    int bins;Point Minre;
    for(Minre=re[0],bins=0,i=1;i<4;++i)if(dcmp(re[i].y-Minre.y)<0||(dcmp(re[i].y-Minre.y)==0&&dcmp(re[i].x-Minre.x)<0))Minre=re[i],bins=i;
     
    for(i=0;i<4;++i)re[(i+bins)%4].print();
     
    return 0;
}

BZOJ1190:[HNOI2007]梦幻岛宝珠 dp

思路:

首先很显然注意到应该按照2的幂次分组dp.

我的想法乱七八糟,就不提了.

发一个详细的网址:http://blog.csdn.net/PoPoQQQ/article/details/43953609

顺便吐槽我太弱.

 

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 110
struct cost{
    int a,b;
    inline void init(int x){
        b=0;
        for(;x%2==0;x>>=1)++b;
        a=x;
    }
};
cost c[N];int v[N];
 
long long f[31][1010];
 
#define Max(x,y) ((x)>(y)?(x):(y))
 
int main(){
    int n,w,x;
    register int i,j,k;
    while(scanf("%d%d",&n,&w)&&(n+w>0)){
        memset(f,0,sizeof f);
        for(i=1;i<=n;++i)scanf("%d%d",&x,&v[i]),c[i].init(x);
         
        for(i=1;i<=n;++i)for(j=min(1000,w>>c[i].b);j>=c[i].a;--j)f[c[i].b][j]=Max(f[c[i].b][j],f[c[i].b][j-c[i].a]+v[i]);
         
        for(i=0;i<=30;++i)for(j=1;j<=1000&&j<=(w>>i);++j)f[i][j]=Max(f[i][j],f[i][j-1]);
         
        int re=0;
        for(k=1;k<=30&&(1<<k)<=w;++k){
            for(j=min(1000,w>>k);j>=0;--j)
                for(i=0;i<=j;++i)
                    f[k][j]=Max(f[k][j],f[k][j-i]+f[k-1][min(2*i+((w>>(k-1))&1),1000)]),re=Max(re,f[k][j]);
        }
         
        printf("%d\n",re);
    }
     
    return 0;
}

BZOJ1493:[NOI2007]项链工厂 Splay

思路:

脑补了半天发现还是不知道怎么上线段树,于是无脑Splay.

操作应该都非常容易实现吧.

对于每一个节点记录一下区间的左右端的颜色,自己的颜色以及颜色段数.

没什么好说的,详情见代码.

 

教训:

我得到区间是利用返回Splay中的一个点来实现的.

注意这个点并不是静态的.

所以得到之后立即将信息存下来.

否则再去得到别的区间的时候,这个点的信息会发生变化.

 

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 500010
 
#define l ch[0]
#define r ch[1]
 
int a[N];
struct Node{
    Node*ch[2],*pa;
    int siz,num,c,col,lcol,rcol;
    bool rev;
    Node():siz(0),num(0),rev(0){}
     
    bool d(){return this==pa->ch[1];}
    inline void sc(Node*p,bool d){ch[d]=p,p->pa=this;}
}mem[N],*P=mem,Tnull,*null=&Tnull,*Root;
 
inline void covit(Node*p,int c){
    p->c=p->col=p->lcol=p->rcol=c;
    p->num=1;
}
inline void revit(Node*p){
    p->rev^=1,swap(p->lcol,p->rcol),swap(p->l,p->r);
}
inline void down(Node*p){
    if(p->rev){
        if(p->l!=null)revit(p->l);
        if(p->r!=null)revit(p->r);
        p->rev=0;
    }
    if(p->c!=0){
        if(p->l!=null)covit(p->l,p->c);
        if(p->r!=null)covit(p->r,p->c);
        p->c=0;
    }
}
inline void up(Node*p){
    p->siz=p->l->siz+1+p->r->siz;
    p->num=p->l->num+p->r->num+1;
    if(p->l!=null&&p->col==p->l->rcol)--p->num;
    if(p->r!=null&&p->col==p->r->lcol)--p->num;
    p->lcol=(p->l!=null)?p->l->lcol:p->col;
    p->rcol=(p->r!=null)?p->r->rcol:p->col;
}
Node*Newnode(int col){
    P->l=P->r=P->pa=null;
    P->siz=1,P->num=1,P->c=P->rev=0,P->col=P->lcol=P->rcol=col;return P++;
}
Node*Build(int tl,int tr){
    if(tl>tr)return null;
    int mid=(tl+tr)>>1;
    Node*q=Newnode(a[mid]);
    q->sc(Build(tl,mid-1),0);
    q->sc(Build(mid+1,tr),1);
    up(q);
    return q;
}
inline void Rot(Node*p){
    bool d=p->d();Node*fa=p->pa;
    down(fa),down(p);
    fa->pa->sc(p,fa->d()),fa->sc(p->ch[!d],d),p->sc(fa,!d);
    up(fa);
    if(fa==Root)Root=p;
}
inline void Splay(Node*p,Node*Anc=null){
    while(p->pa!=Anc){
        if(p->pa->pa==Anc)Rot(p);
        else Rot(p->d()==p->pa->d()?p->pa:p),Rot(p);
    }up(p);
}
inline Node*kth(int k){
    Node*re=Root;
    while(1){
        down(re);
        if(re->l->siz>=k)re=re->l;
        else if(k==re->l->siz+1)return re;
        else k-=re->l->siz+1,re=re->r;
    }
}
inline Node*get(int dl,int dr){
    Node*p=kth(dl);Splay(p);
    Node*q=kth(dr+2);Splay(q,p);
    return q->l;
}
inline Node*del(int dl,int dr){
    Node*p=get(dl,dr);
    p->pa->sc(null,0),up(p->pa),up(p->pa->pa);
    return p;
}
inline void cover(int dl,int dr,int c){
    covit(get(dl,dr),c);
}
inline void reverse(int dl,int dr){
    revit(get(dl,dr));
}
inline void insert(int ins,Node*x){
    Node*p=kth(ins);Splay(p);
    Node*q=kth(ins+1);Splay(q,p);
    q->sc(x,0),up(q),up(p);
}
 
inline void pre(){
    Root=Newnode(0);
    Node*p=Newnode(0);
    Root->sc(p,1),up(Root);
}
 
int main(){
    int n,Maxc;scanf("%d%d",&n,&Maxc);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
     
    pre(),insert(1,Build(1,n));
     
    int m;
    scanf("%d",&m);
    char qte[10];int x,y,c;
    while(m--){
        scanf("%s",qte);
         
        if(qte[0]=='R'){
            scanf("%d",&x);
             
            Node*p=del(n-x+1,n);
            insert(1,p);
        }
         
        if(qte[0]=='F'){
            reverse(2,n);
        }
         
        if(qte[0]=='S'){
            scanf("%d%d",&x,&y);
            if(x!=y){
                 
                if(x>y)swap(x,y);
             
                Node*getx=del(x,x),*gety=del(y-1,y-1);
                insert(x,gety),insert(y,getx);
            }
        }
         
        if(qte[0]=='P'){
            scanf("%d%d%d",&x,&y,&c);
             
            if(x<=y)cover(x,y,c);
            else cover(x,n,c),cover(1,y,c);
        }
         
        if(strlen(qte)==1&&qte[0]=='C'){
            Node*re=get(1,n);
            printf("%d\n",re->num==1?1:re->num-(re->lcol==re->rcol));
        }
         
        if(qte[0]=='C'&&qte[1]=='S'){
            scanf("%d%d",&x,&y);
            if(x<=y){
                Node*re=get(x,y);
                printf("%d\n",re->num);
            }
            else{
                int re=0,rcol,lcol;
                Node*re1=get(x,n);re+=re1->num,rcol=re1->rcol;
                Node*re2=get(1,y);re+=re2->num,lcol=re2->lcol;
                printf("%d\n",re-(rcol==lcol));
            }
        }
    }
     
    return 0;
}