头部背景图片
星之所幸,尘之所哀。 |
星之所幸,尘之所哀。 |

2018暑假计划

2018-07-16

总进度:(18/300)

总错误:

    MLE:1

    RE:1

2018-7-16

    大包子的完美组合

    等差子序列

    普通平衡树

训练赛:

    gcd(100/100)

    次小生成树 tree(100/100)

    k个串 kstring(10/100)失分原因:NM打反导致线段树节点不够。

    场上得分:(210/300)

2018-7-15

    JSOI2008 火星人prefix

    Bracket

    zuma

训练赛:

    兔子与樱花(100/100)

    矩阵乘法(100/100)

    聪聪可可(100/100)

    场上得分(300/300)

2018-7-14

    rank

    sequence

    string

训练赛:

    game with probability(100/100)

    病毒(100/100)

    Count on a tree(0/100)失分原因:MLE

    场上得分(200/300)

大包子的完美组合

2018-07-16

题目大意:

   大包子的公司有n个人,编号分别为1至n。年底,大包子将要举办一场舞会,大包子要从中选出一些人参加这个舞会。 如果选出的这些人中,编号两两互质,我们就认为这是一个完美组合。比如 5 个人的公司中,3, 4, 5这三个人可以组成完美组合。请计算n个人可以选出的完美组合的方案数。 由于答案很大,你需要把答案对109+710^9+7取模。

题解:

    首先,我们先把n\sqrt{n}的素数筛出来,只有16个。

    首先我们把1到3000根据该数的最大质因子排序。

    我们对小于n\sqrt{n} 的素数做状压 DP ,每一位存当前该素数是否被取用过。

    对于大于 n\sqrt{n}的素数,我们发现同一个数中不可能存在两个大于n\sqrt{n}的因子,因此我们枚举每个素数,枚举最大质因子是这个素数的数,做一次状压 DP ,再记录一维表示这个大素数是否被取用。

    将最终答案减去空集。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm> 
#define P 1000000007
#define M 3200
#define K 16
using namespace std;
int prime[K]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; 
int n;
int f[2][1<<K][2];
struct node{int max,sc;}a[M];
int cmp(node x,node y){
    if(x.max!=y.max) return x.max<y.max;
    if(x.sc!=y.sc) return x.sc<y.sc;
}
int cut(int x){
    int ans=0;
    for(int j=0;j<K;j++)
        if(x%prime[j]==0) ans|=1<<j;
    return ans;
}
int main(void){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        a[i].max=i;
        a[i].sc=1;
        for(int j=0;j<K;j++)
            while(a[i].max%prime[j]==0)
            {a[i].max/=prime[j];a[i].sc*=prime[j];}
    }
    sort(a+1,a+n+1,cmp);
    f[0][0][0]=1;
    int p=0;
    for(int i=1;i<=n;i++){
        if(a[i].max!=a[i-1].max)
            for(int j=0;j<1<<K;j++)
                (f[p][j][0]+=f[p][j][1])%=P,f[p][j][1]=0;
        p^=1;
        for(int j=0;j<1<<K;j++)
        f[p][j][0]=f[p^1][j][0],f[p][j][1]=f[p^1][j][1];
        int is=a[i].max>1;
        int tmp=cut(a[i].sc);
        for(int j=(1<<K)-1;j>=0;j--)
            if( f[p^1][j][0]&&!(j&tmp) )
                (f[p][j|tmp][is]+=f[p^1][j][0])%=P;
    }
    int ans=0;
    for(int i=0;i<1<<K;i++)
    for(int j=0;j<=1;j++)
    (ans+=f[p][i][j])%=P;
    (ans+=P-1)%=P;
    printf("%d\n",ans);
}

原题链接:大包子的完美组合

等差子序列

2018-07-16

题目大意:

    给一个1到N的排列{A_i},询问是否存在1p1<p2<p3<p4<p5<...<pLenN(Len3)1\leq p_1<p_2<p_3<p_4<p_5<...<p_{Len}\leq N (Len\geq 3)

    使得Ap1,Ap2,Ap3,...ApLenA_{p1},A{p2},A{p3},...A{pLen}是一个等差序列。

题解:

    树状数组维护hash值。

#include<iostream>
#include<string.h>
#include<stdio.h>
#define N 120000
#define P 1000000007
#define lowbit(x) (x&-x)
using namespace std;
int n,pw[N],a[N];
struct node{
    long long a[N];    
    int add(int x,int b){
        for(int i=x;i<=n;i+=lowbit(i))(a[i]+=b)%=P;
    }
    long long sum(int x){
        long long ans=0;
        for(int i=x;i>0;i-=lowbit(i))(ans+=a[i])%=P;
        return ans;
    }
    int clear(){
        memset(a,0,sizeof(a));
    }
}L,R;
long long power(long long x,int k){
    long long ans=1;
    while(k){
        if(k&1)(ans*=x)%=P;
        (x*=x)%=P;
        k>>=1;
    }
    return ans;
}
int main(){
    int T;
    pw[0]=1;
    scanf("%d",&T);
    for(int i=1;i<=N-10;i++)pw[i]=pw[i-1]*2%P;
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        bool ans=false;
        L.clear();
        R.clear();
        for(int i=1;i<=n;i++){
            int o=a[i];
            L.add(o,pw[o]);
            R.add(n-o+1,pw[n-o+1]);
            if(o<=n/2)
            if(L.sum(o-1)!=((R.sum(n-o)-R.sum(n-o-o+1))*power(pw[n-o-o+1],P-2)%P+P)%P){
                ans=true;
                break;
            }
            if(o>n/2)
            if(((L.sum(o-1)-L.sum(o-1-(n-o)))*power(pw[o-1-(n-o)],P-2)%P+P)%P!=R.sum(n-o)){
                ans=true;
                break;
            }
        }
        if(ans)printf("Y\n");
        else printf("N\n");
    }
}

原题链接:等差子序列

普通平衡树

2018-07-16

题目大意:

    1、插入xx数

    2、删除xx数(若有多个相同的数,因只删除一个)

    3、查询xx数的排名(若有多个相同的数,因输出最小的排名)

    4、查询排名为xx的数

    5、求xx的前驱(前驱定义为小于xx,且最大的数)

    6、求xx的后继(后继定义为大于xx,且最小的数)

#include<iostream>
#include<stdio.h>
#include<string.h>
#define lc(x) (ch[x][0])
#define rc(x) (ch[x][1])
#define N 120000
using namespace std;
int sum[N],ch[N][2],fa[N],val[N],cnt[N],o;
int n,root,tot;
int update(int x){
	sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+cnt[x];
}
int rotate(int x,int a){
	int Fa=fa[x];
	if(fa[Fa])ch[fa[Fa]][ch[fa[Fa]][1]==Fa]=x;
	fa[x]=fa[Fa];
	fa[Fa]=x;
	if(ch[x][a])fa[ch[x][a]]=Fa;
	ch[Fa][a^1]=ch[x][a];
	ch[x][a]=Fa;
	update(Fa);
	update(x);
}
int splay(int x,int y){
	while(fa[x]!=y){
    	int Fa=fa[x];
    	if(ch[fa[x]][1]==x){
        	if(fa[Fa]!=y&&ch[fa[Fa]][1]==Fa)rotate(Fa,0); 
        	rotate(x,0);
        }else{
        	if(fa[Fa]!=y&&ch[fa[Fa]][0]==Fa)rotate(Fa,1); 
        	rotate(x,1);
        }
    }
	if(y==0)root=x;
	return root;
}int insert(int rt,int x,int Fa){
	if(!rt){
    	tot++;
    	val[tot]=x;
    	sum[tot]++;
    	cnt[tot]++;
    	fa[tot]=Fa;
    	o=tot;
    	return tot;
    }
	if(x<val[rt])ch[rt][0]=insert(ch[rt][0],x,rt);
	if(x>val[rt])ch[rt][1]=insert(ch[rt][1],x,rt);
	if(x==val[rt])cnt[rt]++,o=rt;
	update(rt);
	return rt;
}
int ins(int x){
	insert(root,x,0);
	splay(o,0);
}
int delet(int rt,int x){
	if(x>val[rt])delet(rc(rt),x);
	if(x<val[rt])delet(lc(rt),x);
	if(x==val[rt]){
    	o=rt;
    	if(cnt[rt])cnt[rt]--;
    }
	update(rt);
}
int del(int x){
	delet(root,x);
	if(cnt[o])return 0;
	splay(o,0);
	int l=rc(o);
	int k=lc(o);
	while(lc(l))l=lc(l);
	while(rc(k))k=rc(k);
	splay(k,0);
	splay(l,k);
	l=rc(k);
	while(lc(l))l=lc(l);
	ch[fa[l]][rc(fa[l])==l]=0;
	fa[l]=0;
}
int find(int rt){
	int x=ch[rt][0];
	while(ch[x][1])x=ch[x][1];
	return val[x];
}
int kind(int rt){
	int x=ch[rt][1];
	while(ch[x][0])x=ch[x][0];
	return val[x];
}
int get(int rt,int x){
	if(sum[ch[rt][0]]<x-1&&sum[ch[rt][0]]+cnt[rt]>x-1)return val[rt];
	if(sum[ch[rt][0]]>x-1)return get(ch[rt][0],x);
	if(sum[ch[rt][0]]<x-1)return get(ch[rt][1],x-sum[ch[rt][0]]-cnt[rt]);
	return val[rt];
}
int want(int rt,int x){
	if(x<val[rt])return want(ch[rt][0],x);
	if(x>val[rt])return want(ch[rt][1],x);
	return rt;
}
int main(){
	scanf("%d",&n);
	int inf=2147483647;
	ins(inf);
	ins(-inf);
	for(int i=1;i<=n;i++){
    	int type,x;
    	scanf("%d%d",&type,&x);
    	if(type==1)ins(x); 
    	if(type==2)del(x);
    	if(type==3){
        	splay(want(root,x),0);
        	printf("%d\n",sum[ch[root][0]]);
        }
    	if(type==4){
        	printf("%d\n",get(root,x+1));
        }
    	if(type==5){
        	ins(x);
        	printf("%d\n",find(root));
        	del(x);
        }
    	if(type==6){
        	ins(x);
        	printf("%d\n",kind(root));
        	del(x);
        }
    }
} 

原题链接:【BZOJ3224】【TYVJ1728】普通平衡树

k个串 kstring

题目大意:

    兔子们在玩k个串的游戏。首先,它们拿出了一个长度为n的数字序列,选出其中的一个连续子串,然后统计其子串中所有数字之和(注意这里重复出现的数字只被统计一次)。

    兔子们想知道,在这个数字序列所有连续的子串中,按照以上方式统计其所有数字之和,第k大的和是多少。

题解:

    考虑每次加入一个右端点,只有preaipre_{a_{i}}到i上的值会增加aia_i,对于每个右端点维护一颗可持久化线段树,这样我们可以快速得到每个右端点的区间最大值。

    然后将每个右端点加入优先队列,(v,l,r,p,x)(x表示当前树根(既哪个右端点),lr表示当前区间,p表示在l到r中的最大值是多少,v表示当前最大值),每次拔出堆顶然后分裂区间后顶进去,重复k次后就能得到最大值。

失分原因:

    NM打反,导致线段树节点数不够。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<map>
#include<queue>
#define N 120000
#define M 7200000
using namespace std;
struct illyasviel{
	long long x,y;
}v[N];
illyasviel get(long long x,long long y){
	illyasviel ans;
	ans.x=x;
	ans.y=y;
	return ans;
}
illyasviel max(illyasviel x,illyasviel y){
	if(x.x==y.x){
    	if(x.y<y.y)return y;
    	return x; 
    }
	if(x.x>y.x)return x;
	return y;
}
int n,m;
int tot,rt[N],lc[M],rc[M];
long long tag[M];
map<int,int>pre;
struct node{
   	long long v,x,l,r,now;
    friend bool operator < (const node &a,const node &b){return a.v<b.v;}
};
node get(long long v,int x,int l,int r,int now){
	node ans;
	ans.v=v;
	ans.x=x;
	ans.l=l;
	ans.r=r;
	ans.now=now;
	return ans;
}
priority_queue<node>q;
int build(int l,int r){
    int x=++tot;v[x]=get(0,l);
    if(l==r)return x;
    int mid=l+r>>1;
    lc[x]=build(l,mid);
	rc[x]=build(mid+1,r);
    return x;
}
int add(int y,long long p){
    int x=++tot;
    lc[x]=lc[y];
	rc[x]=rc[y];
	v[x]=v[y];
	v[x].x+=p;
	tag[x]=tag[y]+p;
    return x;
}
int pushdown(int x){
    lc[x]=add(lc[x],tag[x]);
	rc[x]=add(rc[x],tag[x]);
    tag[x]=0;
}
int insert(int y,int l,int r,int ll,int rr,int p){
    if(ll<=l&&r<=rr)return add(y,p);
    if(tag[y])pushdown(y);
    int x=++tot;lc[x]=lc[y],rc[x]=rc[y],v[x]=v[y];
    int mid=l+r>>1;
    if(ll<=mid)lc[x]=insert(lc[y],l,mid,ll,rr,p);
    if(rr>mid)rc[x]=insert(rc[y],mid+1,r,ll,rr,p);
    v[x]=max(v[lc[x]],v[rc[x]]);
    return x;
}
illyasviel query(int x,int l,int r,int ll,int rr){
    if(ll<=l&&rr>=r)return v[x];
    if(tag[x])pushdown(x);
    int mid=l+r>>1;
    illyasviel ans;
    ans.x=-1e15;ans.y=-1e15;
 	if(ll<=mid)ans=max(ans,query(lc[x],l,mid,ll,rr));
 	if(rr>mid)ans=max(ans,query(rc[x],mid+1,r,ll,rr));
 	return ans;
}
int add(int x,int l,int r){
    if(l>r)return 0;
    illyasviel t=query(x,1,n,l,r);
    q.push(get(t.x,x,l,r,t.y));
}
int main(){
	freopen("1.in","r",stdin);
    scanf("%d%d",&n,&m);
    rt[0]=build(1,n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        rt[i]=insert(rt[i-1],1,n,pre[x]+1,i,x);
        pre[x]=i;
    	add(rt[i],1,i);
    }
    node x;
    for(int i=1;i<=m;i++){
        x=q.top();q.pop();
        add(x.x,x.l,x.now-1);
        add(x.x,x.now+1,x.r);
    }
    printf("%lld",x.v);
}

原题链接:k个串 kstring

次小生成树 tree

题目大意:

   求一个严格的次小生成树。

题解:

    先求出最小生成树,然后对于每一条非最小生成树上的边都求出将这条边加入最小生成树中增大的最小代价,最后统计答案即可。(求代价时可用倍增求出链上最大值和次大值(次大值是为了保证是严格的最小生成树))

    不知道为什么sort来合并比O(1)合并快两倍……

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 620000
using namespace std;
int fa[N],Next[N],v[N],h[N],w[N],tot,f[N/6][21],dep[N/6],c[N];
int b[5],n,m;
struct node{
	int x,y,z;
}a[N];
struct illyasviel{
	int x,y;
	int clear(){x=0,y=0;}
}g[N/6][21];
bool cmp(node x,node y){
	return x.z<y.z;
}
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
int add(int x,int y,int z){
	tot++;
	Next[tot]=h[x];
	v[tot]=y;
	w[tot]=z;
	h[x]=tot;
}
illyasviel merge(illyasviel x,illyasviel y){
	illyasviel ans;
	ans.clear();
	b[1]=x.x;
	b[2]=x.y;
	b[3]=y.x;
	b[4]=y.y;
	sort(b+1,b+1+4);
	ans.x=b[4];
	for(int i=1;i<=3;i++)if(b[i]<b[4])ans.y=b[i];
	return ans;
}
int dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	f[x][0]=fa;
	for(int i=1;i<=20;i++)f[x][i]=f[f[x][i-1]][i-1];
	for(int i=1;i<=20;i++)g[x][i]=merge(g[x][i-1],g[f[x][i-1]][i-1]);
	for(int i=h[x];i;i=Next[i]){
    	if(v[i]==fa)continue;
    	g[v[i]][0].x=w[i];
    	dfs(v[i],x);
        
    }
}
illyasviel lca(int x,int y){
	illyasviel ans;
	ans.clear();
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--)if(dep[f[x][i]]>=dep[y])ans=merge(g[x][i],ans),x=f[x][i];
	if(x==y)return ans;
	for(int i=20;i>=0;i--){
    	if(f[x][i]!=f[y][i]){
        	ans=merge(ans,g[x][i]);
        	ans=merge(ans,g[y][i]);
        	x=f[x][i];y=f[y][i];
        }
    }
	ans=merge(ans,g[x][0]);
	ans=merge(ans,g[y][0]);
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
    	scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    }
	long long ans=0;
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(a+1,a+1+m,cmp);
	int oo=0;
	for(int i=1;i<=m;i++){
    	if(find(a[i].x)!=find(a[i].y)){
        	c[i]=1;
        	ans+=0LL+a[i].z;
        	fa[find(a[i].x)]=find(a[i ].y);
        	add(a[i].x,a[i].y,a[i].z);
        	add(a[i].y,a[i].x,a[i].z);
        	oo=max(a[i].z,oo);
        }
    }
	dfs(1,0);
	long long bns=0x7fffffff; 
	for(int i=1;i<=m;i++){
    	if(a[i].z-oo>=bns)continue;
    	if(c[i]==0){
        	illyasviel p=lca(a[i].x,a[i].y);
        	bns=min(bns,(a[i].z-p.x>0)?0LL+a[i].z-p.x:0LL+a[i].z-p.y);
        }
    }
	printf("%lld\n",ans+bns);
}

原题链接:次小生成树 Tree

gcd

题目大意:

    对于给出的n个询问,每次求有多少个数对(x,y)(x,y),满足axba\leq x\leq bcydc\leq y\leq d,且gcd(x,y)=kgcd(x,y)=kgcd(x,y)gcd(x,y)函数为x和y的最大公约数。

题解:

    莫比乌斯反演

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 120000
using namespace std;
int p[N],prime[N],mu[N],f[N],tot;
int pre(){
    mu[1]=1;
    for(int i=2;i<=N-10;i++){
        if(p[i]==0)prime[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&i*prime[j]<=N-10;j++){
            p[i*prime[j]]=1;
            mu[i*prime[j]]=-mu[i];
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }
        }
    }
    for(int i=1;i<=N-10;i++)f[i]=f[i-1]+mu[i];
}
long long cal(int n,int m){
    long long ans=0;
    if(n*m==0)return 0;
    if(n>m)swap(n,m);
    for(int i=1;i<=n;i++){
        int j=min(n/(n/i),m/(m/i));
        ans+=1LL*(n/i)*(m/i)*(f[j]-f[i-1]);
        i=j;
    }
//  printf("%d %d %d\n",n,m,ans);
    return ans;
}
int main(){
    int n;
    pre();
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int a,b,c,d,k;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        printf("%lld\n",cal(b/k,d/k)-cal(b/k,(c-1)/k)-cal((a-1)/k,d/k)+cal((a-1)/k,(c-1)/k));
    }
}

原题链接:gcd

JSOI2008 火星人prefix

2018-07-15

题目大意:

    求一个动态字符串的某两个位置的最长公共前缀。

题解:

    用splay维护hash值然后二分长度即可。

#include<iostream>
#include<stdio.h>
#include<string.h>
#define P 9875321
#define N 220000
using namespace std;
char s[N],c[N];
int n,m;
int p[N];
struct spaly{
    int ch[N][2],id[N];
    int fa[N],siz[N],v[N],hs[N];
    int rt,tot;
    int update(int x){
        int l=ch[x][0],r=ch[x][1];
        siz[x]=siz[l]+siz[r]+1;
        hs[x]=(hs[l]+1LL*v[x]*p[siz[l]]%P+1LL*p[siz[l]+1]*hs[r]%P)%P;
    }
    int rotate(int x,int &k){
        int y=fa[x],z=fa[y],l,r;
        if(ch[y][0]==x)l=0;else l=1;r=l^1;
        if(y==k)k=x;
        else {if(ch[z][0]==y)ch[z][0]=x;else ch[z][1]=x;}
        fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;
        ch[y][l]=ch[x][r];ch[x][r]=y;
        update(y);update(x);
    }
    int splay(int x,int &k){
        while(x!=k){
            int y=fa[x],z=fa[y];
            if(y!=k){
                if((ch[y][0]==x)^(ch[z][0]==y))rotate(x,k);
                else rotate(y,k);
            }
            rotate(x,k);
        }
    }
    int find(int x,int rk){
        int l=ch[x][0],r=ch[x][1];
        if(siz[l]+1==rk)return x;
        if(siz[l]+1<rk)return find(r,rk-siz[l]-1);
        if(siz[l]+1>rk)return find(l,rk);
    }
    int insert(int k,int val){
        int x=find(rt,k+1),y=find(rt,k+2);
        splay(x,rt);splay(y,ch[x][1]);
        tot++;ch[y][0]=tot;fa[tot]=y;v[tot]=val;
        update(tot);update(y);update(x);
    }
    int query(int k,int val){
        int x=find(rt,k),y=find(rt,k+val+1);
        splay(x,rt);splay(y,ch[x][1]);
        return hs[ch[y][0]];
    }
    int solve(int x,int y){
        int l=1,r=min(tot-x,tot-y)-1,ans=0;
        while(l<=r){
            int mid=(l+r)/2;
            if(query(x,mid)==query(y,mid)){l=mid+1;ans=mid;}
            else r=mid-1;
        }
        return ans;
    }
    void build(int l,int r,int f){
        if(l>r)return;
        int now=id[l],last=id[f];
        if(l==r){
            v[now]=hs[now]=c[l]-'a'+1;
            fa[now]=last;siz[now]=1;
            if(l<f)ch[last][0]=now;
            else ch[last][1]=now;
            return;
        }
        int mid=(l+r)>>1;now=id[mid];
        build(l,mid-1,mid);build(mid+1,r,mid);
        v[now]=c[mid]-'a'+1;fa[now]=last;update(now);
        if(mid<f)ch[last][0]=now;
        else ch[last][1]=now;
    }
}splay;
int main(){
    scanf("%s",c+2);
    n=strlen(c+2);
    p[0]=1;for(int i=1;i<=150004;i++)p[i]=p[i-1]*27%P;
    for(int i=1;i<=n+2;i++)splay.id[i]=i;
    splay.build(1,n+2,0);splay.tot=n+2;splay.rt=(n+3)>>1;
    scanf("%d",&m);
    int x,y;
    char s[2],d[2];
    for(int i=1;i<=m;i++){
        scanf("%s",s+1);
        scanf("%d",&x);
        if(s[1]=='Q'){
            scanf("%d",&y);
            printf("%d\n",splay.solve(x,y));
        }
        if(s[1]=='R')scanf("%s",d+1),x=splay.find(splay.rt,x+1),splay.splay(x,splay.rt),splay.v[splay.rt]=d[1]-'a'+1,splay.update(splay.rt);
        if(s[1]=='I')scanf("%s",d+1),splay.insert(x,d[1]-'a'+1);
    }
    return 0;
}

原题链接: JSOI2008火星人prefix

Bracket

2018-07-15

题目大意:

    现在有一个括号序列(不保证合法),你能够进行以下两个操作:

    1:在任意位置加入一个左括号或者右括号

    2:将序列最末的括号移到最前

    现在想要知道,经过若干次操作后,得到的最短的字典序最小的括号序列是什么?

    (“(”<“)”)

题解:

    通过旋转变换得到最小字典序的序列再在前后补足括号即可。

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 1200000
#define getl(x) (-min(0,min(ms[x],msum[x-1]+sum2[x])))
using namespace std;
int msum[N],ms[N],sum1[N],sum2[N];
int l,r,len,cl,cr,ans,minl,a[N];
char s[N];
int check(int l,int r,int ll,int rr){
    for(int i=l;i<=r;i++)
        if(s[i]=='('&&s[ll+i-l]==')')return 0;else
        if(s[i]==')'&&s[ll+i-l]=='(')return 1;
    return 0;
}
int main(){
    scanf("%s",s+1);
    len=strlen(s+1);
    for(int i=1;i<=len;i++) 
        if(s[i]=='(')a[i]=1;else a[i]=-1;
    for(int i=1;i<=len;i++){
        s[i+len]=s[i];
        a[i+len]=a[i];
    }
    for(int i=1;i<=len;i++){
        sum1[i]=sum1[i-1]+a[i];
        msum[i]=min(msum[i-1],sum1[i]);
    }
    for(int i=len;i;i--){
        sum2[i]=sum2[i+1]+a[i];
        ms[i]=min(ms[i+1]+a[i],a[i]);
    }
    minl=len;
    for(int i=1;i<=len;i++)minl=min(minl,getl(i));
    l=1,r=len;
    for(int i=1;i<=len;i++)if(getl(i)==minl&&check(l,r,i,i+len-1))l=i,r=i+len-1;
    for(int i=1;i<=minl;i++)printf("(");
    for(int i=l;i<=r;i++)printf("%c",s[i]);
    for(int i=l;i<=r;i++)if(s[i]=='(')cl++;else cr++;
    for(int i=cr;i<cl;i++)printf(")");
    printf("\n");
}

原题链接:Bracket

zuma

2018-07-15

题目大意:

    给出一串数列v[1…n],一次可以消去其中的一段回文串(例如1 2 3 2 1),然后将这一段数字从v中移除。请问最少消多少次可以消除整个数列。

题解:

    设f[l,r]为消去区间v[l,r]的最少需要的次数。 dfs即可。

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 520
using namespace std;
int f[N][N],a[N],n;
int dfs(int l,int r){
    if(f[l][r])return f[l][r];
    if(l>r)return 0;
    f[l][r]=1+dfs(l+1,r);
    for(int i=l+1;i<=r;i++)if(a[i]==a[l]){
        if(i==l+1)f[l][r]=min(f[l][r],1+dfs(i+1,r));
        else f[l][r]=min(f[l][r],dfs(l+1,i-1)+dfs(i+1,r));
    }
    return f[l][r];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    printf("%d",dfs(1,n));
}

原题链接:zuma