分类目录归档:算法

Kick Start 2018 Round B B题

Sherlock and the Bit Strings

构造一个长度为N的只有‘0’和‘1’的串s,满足K个限制(s[A,B]中含有C个1),且这个串在所有满足限制的合法串当中为字典序第P大.

状压dp,f[i][j]:假设前i个字符已固定,且这前i个中最后16个字符为j时的合法方案数(注意j前面的到底是什么我们不用管,反正看作前缀是固定的,而这个结果统计的是前缀之后的部分可以有多少种变化)。我们从后往前转移,最终得到每个位置的情况。如何转移看代码就很清楚了,再次感到熟练位操作对做状压方面的题目很重要。

官方题解开头就讲到固定前缀的合法方案数与字典序第p大的关系,一开始没理解...就是如果串是i开头的话(我们以字典序的顺序来尝试i),f[1][i]>=p,那么第p大就一定是在这f[1][i]方案中了,否则从P中减掉f[1][i](f[1][i]的方案里都是些比P小的啊,减掉f[1][i]之后的P(用P'表示吧)就是开头字典序比i大时的方案里第p'大的,也是原来那个第P大的),i再转向下一个字典序更大的选择。然后可以一个一个位置构造出这个串。

#include<bits/stdc++.h>
using namespace std;

long long f[105][1<<16];
vector <pair<int,int> > limits[105];
int cnt[1<<16];
int shl[1<<16];

bool check(int i,int last){
    for(int j=0;j<limits[i].size();++j){
        if(cnt[((1<<limits[i][j].first)-1)&last]!=limits[i][j].second){
            return false;
        }
    }
    return true;
}

int main(){
    int T,kase=0;
    scanf("%d",&T);
    for(int i=1;i<(1<<16);++i){
        cnt[i]=cnt[i>>1]+(i&1);
        shl[i]=(i<<1)&((1<<16)-1);
    }
    while(T--){
        int n,k;
        long long p;
        scanf("%d%d%lld",&n,&k,&p);
        for(int i=1;i<=n;++i) limits[i].clear();
        for(int i=1;i<=k;++i){
            int A,B,C;
            scanf("%d%d%d",&A,&B,&C);
            limits[B].push_back(make_pair(B-A+1,C));
        }
        for(int i=0;i<(1<<16);++i){
            if(check(n,i)){
                f[n][i]=1;
            }
            else f[n][i]=0;
        }
        for(int i=n-1;i>0;--i){
            for(int j=0;j<(1<<16);++j){
                if(check(i,j)){
                    f[i][j]=f[i+1][shl[j]]+f[i+1][shl[j]^1];
                    if(f[i][j]>1e18) f[i][j]=1e18+1;
                }
                else f[i][j]=0;
            }
        }

        printf("Case #%d: ",++kase);
        for(int i=1,j=0;i<=n;++i,j=shl[j]){
            if(f[i][j]>=p){
                printf("0");
            }
            else{
                p-=f[i][j];
                j^=1;
                printf("1");
            }
        }
        printf("\n");

    }
    return 0;
}

SGU385 Highlander

题目来源:SGU 385
图片来自国家集训队论文《浅析竞赛中一类数学期望问题的解决方法》

其中min(j,i-j+1) 更改为min(j-1,i-j)貌似更合适。

#include<bits/stdc++.h>

using namespace std;

double d[105];
double fac[105];
double f[105][105][105];
double g[105][105];

double A(int i,int j){
    return fac[i]/fac[i-j];
}

int main(){
    int n;
    scanf("%d",&n);

    fac[0]=1;
    for(int i=1;i<=n;++i){
        fac[i]=i*fac[i-1];
    }

    d[1]=0,d[2]=1;
    for(int i=3;i<=n;++i){
        d[i]=(i-1)*(d[i-1]+d[i-2]);
    }

    for(int i=2;i<=n;++i){
        for(int j=2;j<i;++j){
            for(int l=2;l<=min(j-1,i-j);l++){
                f[i][j][1]+=g[i-j][l];
            }
            f[i][j][1]*=A(n-i+j,j)/j;
            g[i][j]+=f[i][j][1];
            for(int k=2;k<=i/j;k++){
                f[i][j][k]=f[i-j][j][k-1]*A(n-i+j,j)/j/k;
                g[i][j]+=f[i][j][k];
            }
        }
        f[i][i][1]=A(n,i)/i;
        g[i][i]+=f[i][i][1];
    }

    double res=0;
    for(int j=2;j<=n;++j){
        for(int k=1;k<=n;++k){
            res+=f[n][j][k]*j*k;
        }
    }
    printf("%.10f\n",res/d[n]);

    return 0;
}

[NOI2005]聪聪与可可

聪聪与可可

在一个单位时间内,聪聪根据可可的位置,会先走出最短路中的下一步,然后被抓者可等概率随意走一步,也可原地不动。
在距离一步或者两步的时候,只要一个单位时间就可以抓到了,这是递归基。然后记忆化搜索解决之。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF=0x3f3f3f3f;
int ver[2010],edge[2010],Next[2010],head[2010];
int t[1005],v[1005];
int dis[1005][1005]; //i到j的最短路长度
int p[1005][1005]; //p[i][j]从i到j的最短路中,i第一步到达的地方
double f[1005][1005]; //f[i][j] 初始地点i和j,抓到时的期望步数
int N,tot;

void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}

void shortest_path(int *d,int len,int s){
     memset(d,0x3f,len);
     memset(v,0,sizeof(v));
     d[s]=0;
     v[s]=1;
     queue<int> q;
     q.push(s);
     while(q.size()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(!v[y]){
                v[y]=1;
                d[y]=d[x]+1;
                q.push(y);
            }
        }
     }
}

double solve(int i,int j){
    if(f[i][j]||i==j) return f[i][j];
    int fir=p[i][j],sec=p[fir][j];
    if(fir==j||sec==j) return f[i][j]=1;
    for(int k=head[j];k;k=Next[k]){
        f[i][j]+=solve(sec,ver[k]);
    }
    f[i][j]+=solve(sec,j);
    return f[i][j]=f[i][j]/(t[j]+1)+1;
}

int main(){
    //freopen("testdata.in","r",stdin);
    int E,C,M;
    scanf("%d%d%d%d",&N,&E,&C,&M);
    for(int i=0;i<E;++i){
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        add(t1,t2,1);
        add(t2,t1,1);

    }

    for(int i=1;i<=N;++i){
        for(int j=1;j<=N;++j){
            dis[i][j]=INF;
        }
    }

    for(int i=1;i<=N;++i){
        shortest_path(dis[i],sizeof(dis[i]),i);
    }

    memset(p,0x3f,sizeof(p));
    for(int i=1;i<=N;++i){
        p[i][i]=i;
        for(int j=head[i];j;j=Next[j]){
            int y=ver[j];
            for(int k=1;k<=N;++k){
                if(dis[y][k]==dis[i][k]-1){
                    p[i][k]=min(p[i][k],y);
                }
            }
            t[i]++;
        }
    }

    printf("%.3lf\n",solve(C,M));

    return 0;
}

扫描线(POJ 1151)

在平面坐标系里给出一些矩形,求面积并.
Atlantis

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

const int N=106;
int n,m,num=0;

struct P{
    double x,y,z;
    int k;
    bool operator<(const P w) const{
        return x<w.x;
    }
}a[N<<1];

double raw[N<<1];
map<double ,int > val ;

struct Tree{
    int l,r,cnt;
    double len;
}t[N<<3];

void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    t[p].cnt=0;
    t[p].len=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}

void change(int p,int l,int r,int k){
    if(l<=t[p].l&&r>=t[p].r) t[p].len=((t[p].cnt+=k)>0?raw[t[p].r+1]-raw[t[p].l]:0);
    if(t[p].l==t[p].r) return;
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) change(p<<1,l,r,k);
    if(r>mid) change(p<<1|1,l,r,k);
    t[p].len=(t[p].cnt>0?raw[t[p].r+1]-raw[t[p].l]:t[p<<1].len+t[p<<1|1].len);
}

void  Atlantis(){
    for(int i=1;i<=n;++i){
        int k=i<<1;
        double y,z; //竖直方向坐标
        scanf("%lf %lf %lf %lf",&a[k-1].x,&y,&a[k].x,&z);
        raw[k-1]=a[k-1].y=a[k].y=y;//矩形左边界
        raw[k]=a[k-1].z=a[k].z=z; //矩形右边界
        a[k-1].k=1;
        a[k].k=-1;
    }
    n<<=1;
    //离散化
    sort(raw+1,raw+n+1);
    int m=unique(raw+1,raw+n+1)-(raw+1);
    for(int i=1;i<=m;++i) val[raw[i]]=i;
    sort(a+1,a+n+1);
    build(1,1,m-1);
    double ans=0;
    for(int i=1;i<n;++i){
        int y=val[a[i].y],z=val[a[i].z]-1;  // y:[val[a[i].y], val[a[i].y]+1]  z: [val[a[i].z]-1, val[a[i].z]]
        change(1,y,z,a[i].k); //y~z: [val[a[i].y], val[a[i].z]
        ans+=t[1].len*(a[i+1].x-a[i].x); //t[1].len 整个扫描线覆盖的长度
    }
    printf("Test case #%d\nTotal explored area: %.2f\n\n", ++num, ans);
}

int main() {
    while (cin >> n && n) Atlantis();
    return 0;
}

线段树延迟标记 (POJ3468)

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int SIZE = 100010;

struct SegmentTree{
    int l,r;
    long long sum,add;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define sum(x) tree[x].sum
    #define add(x) tree[x].add
} tree[SIZE*4];

int a[SIZE],n,m;

void build(int p,int l,int r){
    l(p)=l,r(p)=r;
    if(l==r) { sum(p)=a[l];return; }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    sum(p)=sum(p*2)+sum(p*2+1);
}

void spread(int p){
    if(add(p)){
        sum(p*2)+=add(p)*(r(p*2)-l(p*2)+1);
        sum(p*2+1)+=add(p)*(r(p*2+1)-l(p*2+1)+1);
        add(p*2)+=add(p);
        add(p*2+1)+=add(p);
        add(p)=0;
    }
}

void change(int p,int l,int r,int d){
    if(l<=l(p) && r>=r(p)){
        sum(p)+=(long long) d*(r(p)-l(p)+1);
        add(p)+=d;
        return;
    }
    spread(p);
    int mid=(l(p)+r(p))/2;
    if(l<=mid) change(p*2,l,r,d);
    if(r>mid) change(p*2+1,l,r,d);
    sum(p)=sum(p*2)+sum(p*2+1);
}

long long ask(int p,int l,int r){
    if(l<=l(p) && r>=r(p)) return sum(p);
    spread(p);
    int mid=(l(p)+r(p))/2;
    long long val=0;
    if(l<=mid) val+=ask(p*2,l,r);
    if(r>mid) val+=ask(p*2+1,l,r);
    return val;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(m--){
        char op[2];
        int l,r,d;
        scanf("%s%d%d",op,&l,&r);
        if(op[0]=='C'){
            scanf("%d",&d);
            change(1,l,r,d);
        }
        else printf("%lld\n",ask(1,l,r));
    }
    return 0;
}

最大连续子段和

RT,线段树单点修改,区间查询.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <utility>
using namespace std;
const int INF = 1e9;
const int maxn = 1e6;

#define SIZE 500000

int a[SIZE+1];
struct SegmentTree {
    int l,r;
    int dat,sum,lmax,rmax;
    SegmentTree() {
        l = r = sum = 0;
        lmax = rmax  =dat= -INF;
    }
} t[SIZE*4];

void build(int p,int l,int r) {
    t[p].l=l,t[p].r=r;
    if(l==r) {
        t[p].dat=t[p].lmax=t[p].rmax=t[p].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].dat=max(max(t[p*2].dat,t[p*2+1].dat),t[p*2].rmax+t[p*2+1].lmax);
    t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
    t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
}

void change(int p,int x,int v) {
    if(t[p].l==t[p].r) {
        t[p].dat=t[p].lmax=t[p].rmax=t[p].sum=v;
        return;
    }
    int mid=(t[p].l+t[p].r)/2;
    if(x<=mid)
        change(p*2,x,v);
    else
        change(p*2+1,x,v);
    t[p].dat=max(max(t[p*2].dat,t[p*2+1].dat),t[p*2].rmax+t[p*2+1].lmax);
    t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
    t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
}

SegmentTree ask(int p,int l,int r) {
    if(l<=t[p].l&&r>=t[p].r) {
        return t[p];
    }
    SegmentTree res,a,b;
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid) {
        a=ask(p*2,l,r);
        res.sum+=a.sum;
    }
    if(r>mid) {
        b=ask(p*2+1,l,r);
        res.sum+=b.sum;
    }
    res.lmax=max(a.lmax,a.sum+b.lmax);
    res.rmax=max(b.rmax,b.sum+a.rmax);
    res.dat=max(max(a.dat,b.dat),a.rmax+b.lmax);
    return res;
}

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) {
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(m--) {
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(k==1) {
            if(x>y)
                swap(x,y);
            printf("%d\n",ask(1,x,y).dat);
        } else {
            change(1,x,y);
        }
    }
    return 0;
}

HDU – 6214 Smallest Minimum Cut

HDU 6214

求最小割的最小割边数量.
每边以w*(m+1)+1为边权加入图中,最小割为maxflow/(m+1),最小割的边数为maxflow%(m+1).
精髓在于将已选边数加到了流量信息里.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <utility>
using namespace std;
const int INF = 1e9;
const int maxn = 1e6;

struct Edge{
  int from,to,cap,flow;
  Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};

struct Dinic{
  int n,m,s,t;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool vis[maxn];
  int d[maxn];
  int cur[maxn];

  void init(int n){
    for(int i=0;i<=n;++i) G[i].clear();
    edges.clear();
  }

  void AddEdge(int from, int to, int cap){
    edges.push_back(Edge(from,to,cap,0));
    edges.push_back(Edge(to,from,0,0)); //反向弧
    m=edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
  }

  bool BFS(){
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(s);
    d[s]=0;
    vis[s]=1;
    while(!Q.empty()){
      int x=Q.front();Q.pop();
      for(int i=0;i<G[x].size();++i){
        Edge &e=edges[G[x][i]];
        if(!vis[e.to]&&e.cap>e.flow){
          vis[e.to]=1;
          d[e.to]=d[x]+1;
          Q.push(e.to);
        }
      }
    }
    return vis[t];
  }

  int DFS(int x,int a){
    if(x==t||a==0) return a;
    int flow=0,f;
    for(int &i=cur[x];i<G[x].size();++i){
      Edge &e=edges[G[x][i]];
      if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){
        e.flow+=f;
        edges[G[x][i]^1].flow-=f;
        flow+=f;
        a-=f;
        if(a==0)  break;
      }
    }
    return flow;
  }

  int Maxflow(int s,int t){
    this->s=s;
    this->t=t;
    int flow=0;
    while(BFS()){
      memset(cur,0,sizeof(cur));
      flow+=DFS(s,INF);
    }
    return flow;
  }

} flow;

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
   int T,n,m;
   scanf("%d",&T);
   while(T--){
     scanf("%d%d",&n,&m);
     int s,t;
     scanf("%d%d",&s,&t);
     flow.init(n);
     for(int i=0;i<m;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        flow.AddEdge(u,v,w*(m+1)+1);
        flow.AddEdge(v,u,0);
     }
     printf("%d\n",flow.Maxflow(s,t)%(m+1));

   }
   return 0;
}

Distinct Substrings SPOJ – DISUBSTR

Distinct Substrings

求不同子串个数.
对排好序的后缀,相邻两个后缀产生的不同子串数为:
(n-sa[i])+(n-sa[i-1])-height[i].

而(n-sa[i])+(n-sa[i-1])的累加就是(n+1)*n/2

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <utility>
using namespace std;
const int INF = 1e9;
const int MAX_V = 10005;
const int MAX_E= 200005;

int c[20010],_rank[20010],temp[20010],sa[20010],height[20010];
void da(int str[],int n,int m){
  n++;
  int i,j,p;
  for(i=0;i<m;++i) c[i]=0;
  for(i=0;i<n;++i) c[_rank[i]=str[i]]++;
  for(i=1;i<m;++i) c[i]+=c[i-1];
  for(i=n-1;i>=0;--i) sa[--c[_rank[i]]]=i;
  for(j=1;j<=n;j<<=1){
    p=0;
    //若未对str进行离散化,第一轮rank不是真正的rank,是大小关系相对确定的rank.
    //_rank[i]为上一轮第i个位置的rank(也是此轮第i个位置的第一关键字, 第i-j个位置的第二关键字)
    //temp[i]为第i小的第二关键字对应的串首位置(第一关键字的下标)
    for(i=n-j;i<n;++i) temp[p++]=i; //无第二关键字
    for(i=0;i<n;++i){
      if(sa[i]>=j) temp[p++]=sa[i]-j;
    }
    //排序第一关键字_rank[i],当_rank[i]相等时,让第二关键字小的排前面
    for(i=0;i<m;++i) c[i]=0;
    for(i=0;i<n;++i) c[_rank[temp[i]]]++;
    for(i=1;i<m;++i) c[i]+=c[i-1];
    for(i=n-1;i>=0;--i) sa[--c[_rank[temp[i]]]] = temp[i];
    //新的rank数组要由老的rank数组得到,因而将rank转移到temp上
    swap(_rank,temp);
    p=1;
    _rank[sa[0]]=0;
    for(i=1;i<n;++i){
      _rank[sa[i]]=temp[sa[i-1]]==temp[sa[i]]&&temp[sa[i-1]+j]==temp[sa[i]+j]?p-1:p++;
    }
    if(p>=n) break;
    m=p;
  }

  int k=0;
  n--;

  //height[rank[i]]>=height[rank[i-1]]-1
  for(i=0;i<n;++i){
    if(k) k--;
    j=sa[_rank[i]-1];
    while(str[i+k]==str[j+k]) k++;
    height[_rank[i]]=k;
  }

}

char s[1005];
int t[1005];
int main(){
  int T;
  cin>>T;
  while(T--){
    scanf("%s",s);
    int len=strlen(s);
    int m=0;
    for(int i=0;i<len;++i){
       t[i]=s[i]-0;
       m=max(s[i]-0,m);
    }
    t[len]=0;
    da(t,len,m+1);
    int ans=len*(len+1)/2;
    for(int i=0;i<=len;++i){
        ans-=height[i];
       // cout<<height[i]<<endl;
    }
    printf("%d\n",ans);
  }

}

POJ 1743 -Musical Theme

Musical Theme

求最长不重叠重复子串.

依题意进行了作差转化.
二分长度+height分组判断.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;

//_rank[i]:位置i开始的子串排名
//sa[i]:排名为i的子串开始位置,
//height[i]:sa[i]和sa[i-1]对应子串的最长公共前缀长度
//c[i]:计数桶
int c[120010],_rank[120010],temp[120010],sa[120010],height[120010];
void da(int str[],int n,int m){
  n++;
  int i,j,p;
  //第一轮基数排序
  for(i=0;i<m;++i) c[i]=0;
  for(i=0;i<n;++i) c[_rank[i]=str[i]]++;
  for(i=1;i<m;++i) c[i]+=c[i-1];
  for(i=n-1;i>=0;--i) sa[--c[_rank[i]]]=i;
  //倍增
  for(j=1;j<=n;j<<=1){
    p=0;
    //若未对str进行离散化,第一轮rank不是真正的rank,是大小关系相对确定的rank.
    //_rank[i]为上一轮第i个位置的rank(也是此轮第i个位置的第一关键字, 第i-j个位置的第二关键字)
    //temp[i]为第i小的第二关键字对应的串首位置(第一关键字的下标)
    for(i=n-j;i<n;++i) temp[p++]=i; //无第二关键字
    for(i=0;i<n;++i){
      if(sa[i]>=j) temp[p++]=sa[i]-j;
    }
    //基数排序第一关键字_rank[i],当_rank[i]相等时,让第二关键字小的排前面
    for(i=0;i<m;++i) c[i]=0;
    for(i=0;i<n;++i) c[_rank[temp[i]]]++;
    for(i=1;i<m;++i) c[i]+=c[i-1];
    for(i=n-1;i>=0;--i) sa[--c[_rank[temp[i]]]] = temp[i];
    //新的rank数组要由老的rank数组得到,因而将rank转移到temp上
    swap(_rank,temp);
    p=1;
    _rank[sa[0]]=0;
    for(i=1;i<n;++i){
      _rank[sa[i]]=temp[sa[i-1]]==temp[sa[i]]&&temp[sa[i-1]+j]==temp[sa[i]+j]?p-1:p++;
    }
    if(p>=n) break;
    m=p;
  }

  int k=0;
  n--;

  //height[rank[i]]>=height[rank[i-1]]-1
  for(i=0;i<n;++i){
    if(k) k--;
    j=sa[_rank[i]-1];
    while(str[i+k]==str[j+k]) k++;
    height[_rank[i]]=k;
  }

}

bool judge(int k,int n){
  int Max=sa[0],Min=sa[0];
  for(int i=1;i<n;++i){
    if(height[i]>=k-1){
      Max=max(Max,sa[i]);
      Min=min(Min,sa[i]);
    }
    else{
      Max=sa[i],Min=sa[i];
    }
    if(Max-Min>=k){
      return true;
    }
  }
  return false; 
}

int a[20010];

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
   int n;
   while(~scanf("%d",&n)&&n){
     for(int i=0;i<n;++i){
       scanf("%d",&a[i]);
     }

     int _size=0;
     for(int i=1;i<n;++i){
       a[i-1]=a[i-1]-a[i]+88;
       _size=max(_size,a[i-1]);
     }
     a[n-1]=0;
     da(a,n-1,_size+1);

     int Min=0;
     int Max=n;
     int ans;
     while(Min<=Max){
       int mid=(Min+Max)/2;
       if(judge(mid,n)) Min=mid+1,ans=mid;
       else Max=mid-1;
     }
     if(ans>=5){
       printf("%d\n",ans);
     }
     else printf("0\n");
   }
}

LightOJ – 1258 Making Huge Palindromes

Making Huge Palindromes

通过对字符串添加最少的字母,使其变为回文串,有点意思.
用manacher求出原串中能覆盖其后缀并且最左端最前的回文子串,这样原串左端没有被回文子串覆盖的部分就是要添加的了.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;

char Ma[2000005];
int Mp[2000005];

int manacher(char s[], int len) {
  int l = 0;
  Ma[l++] = '$';
  Ma[l++] = '#';
  for (int i = 0; i < len; ++i) {
    Ma[l++] = s[i];
    Ma[l++] = '#';
  }
  Ma[l] = 0;
  int mx = 0, id = 0;
  int ans = len - 1;
  for (int i = 0; i < l; ++i) {
    Mp[i] = mx > i ? min(Mp[2 * id - i], mx - i) : 1;
    while (Ma[i + Mp[i]] == Ma[i - Mp[i]]) {
      Mp[i]++;
    }
    if ((i - Mp[i]) / 2 < ans && i + Mp[i] == l) {
      ans = (i - Mp[i]) / 2;
    }
    if (i + Mp[i] > mx) {
      mx = i + Mp[i];
      id = i;
    }
  }
  return ans + len;
}

char s[1000005];
int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int kase = 0, T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", s);
    printf("Case %d: %d\n", ++kase, manacher(s, strlen(s)));
  }
  return 0;
}