月度归档:2019年07月

最大连续子段和

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;
}

HDU – 4513 吉哥系列故事——完美队形II

HDU 4513

在回文子串的基础上加了限制条件, manacher算法里加个判断即可.

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

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

int manacher(int 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] = 2;
  int mx = 0, id = 0;
  int ans = 0;
  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]] &&
           ((i - Mp[i]) % 2 || Ma[i - Mp[i]] <= Ma[i - Mp[i] + 2])) {
      Mp[i]++;
    }
    ans = max(ans, Mp[i] - 1);
    if (i + Mp[i] > mx) {
      mx = i + Mp[i];
      id = i;
    }
  }
  return ans;
}

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

HDU – 3613 Best Reward

Best Reward

扩展kmp与回文串问题

在扩展kmp中,设模式串为P1,目标串为P2
extend[i]表示P2[i]~P2[n]与P1的最长公共前缀长度.

设原串为P,将其倒置为S.
以P为模式串执行一遍e-KMP,得到extend1数组,P的前缀是回文串的条件是extend1[i]+i=length(S)
以S为模式串执行一遍e-KMP,得到extend2数组,P的后缀是回文串的条件是extend2[i]+i=length(P)
画出图更好理解.

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

int Next[500001];
int extend1[500010];
int extend2[500010];
char p[500001];
char s[500001];
int value[500001];
void eKMP_pre(char x[],int m,int next[]){
  next[0]=m;
  int j=0;
  while(j+1<m&&x[j]==x[j+1]) j++;
  next[1]=j;
  int k=1;
  for(int i=2;i<m;++i){
    int p=next[k]+k-1;
    int L=next[i-k];
    if(i+L-1<p) next[i]=L;
    else{
      j=max(0,p-i+1);
      while(i+j<m&&x[i+j]==x[j]) j++;
      next[i]=j;
      k=i;
    }
  }
}

void eKMP(char x[],int m,char y[],int n,int next[],int extend[]){
  eKMP_pre(x,m,next);
  int j=0;
  while(j<n&&j<m&&x[j]==y[j]) j++;
  extend[0]=j;
  int k=0;
  for(int i=1;i<n;++i){
    int p=extend[k]+k-1;
    int L=next[i-k];
    if(i+L-1<p) extend[i]=L;
    else{
      j=max(0,p-i+1);
      while(i+j<n&&j<m&&y[i+j]==x[j]) j++;
      extend[i]=j;
      k=i;
    }
  }
}

int v[26];

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int kase=0;
  int n,T;
  scanf("%d",&T);
  while(T--){
    for(int i=0;i<26;++i){
      scanf("%d",&v[i]);
    }
    scanf("%s",p);
    int len=strlen(p);
    int k=0;
    for(int i=len-1;i>=0;i--){
        s[k]=p[i];
        value[k]=v[s[k]-'a'];
        if(k)  value[k]=value[k]+value[k-1];
        k++;
    }
    eKMP(p,len,s,len,Next,extend1);
    eKMP(s,len,p,len,Next,extend2);
    int ans=-INF;
    for(int i=1;i<len;++i){
      int temp=0;
      if(i+extend1[i]==len){
          temp+=value[i+extend1[i]-1]-value[i-1];
          if(extend1[i]+extend2[extend1[i]]==len){
            temp+=value[i-1];
          }
      }
      else{
         if(len-i+extend2[len-i]==len){
           temp+=value[i-1];
         }
      }
      ans=max(ans,temp);
    }
    printf("%d\n",ans);
  }

  return 0;
}

HDU – 1358 Period

Period

KMP算法和周期性字符串.

i-next[i] 为最小循环元长度,i/(i-next[i])为最大循环次数.

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

int Next[1000010];
char p[1000010];

void kmp_pre(char x[],int m,int next[]){
    int i,j;
    j=next[0]=-1;
    i=0;
    while(i<m){
      while(-1!=j&&x[i]!=x[j]) j=next[j];
      next[++i]=++j;
    }
}

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int kase=0;
  int n;
  while(cin>>n&&n){
    scanf("%s",p);
    kmp_pre(p,n,Next);
    int i=n;
    printf("Test case #%d\n",++kase);
    for(int i=2;i<=n;++i){
        if(i/(i-Next[i])>1&&i%(i-Next[i])==0){
            printf("%d %d\n",i,i/(i-Next[i]));
        }
    }
    printf("\n");
  }

  return 0;
}

Comet OJ 双倍快乐

双倍快乐

f[i][j]: 两个子序列分别以i和j结尾时的最大和.
LIS的变形,每次可将第k个元素尝试添加到两个序列里.

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

int a[505];
int f[505][505];

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int n;
  cin>>n;
  for(int i=1;i<=n;++i){
    cin>>a[i];
  }
  int ans=0;
  for(int k=1;k<=n;++k){
    for(int i=0;i<k;++i){
      for(int j=0;j<k;++j){
          if(a[k]>=a[i]) {
            f[k][j]=max(f[k][j],f[i][j]+a[k]);
          }
          if(a[k]>=a[j]){
            f[i][k]=max(f[i][k],f[i][j]+a[k]);
          }
      }
    }
  }
  for(int i=0;i<=n;++i){
    for(int j=0;j<=n;++j){
      ans=max(ans,f[i][j]);
    }
  }
  cout<<ans<<endl;
  return 0;
}

POJ – 3186 Treats for the Cows

题目链接

f[i][j]:只剩第i个到第j个时,将其取完获得的最大价值.

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

int f[2005][2005];
int a[2005];
int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int n;
  cin>>n;
  for(int i=1;i<=n;++i){
    cin>>a[i];
    f[i][i]=n*a[i];
  }
  for(int i=1;i<n;++i){
      for(int l=1;l+i<=n;++l){
        int r=l+i;
        f[l][r]=max(f[l+1][r]+(n-i)*a[l],f[l][r-1]+(n-i)*a[r]);
      }
  }
  cout<<f[1][n]<<endl;
  return 0;
}