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

POJ – 1661 Help Jimmy

题目链接

f[i][0]:从i平台左端跳下到地面的最短时间(不包括竖直距离)
f[i][1]:从j平台右端跳下到地面的最短时间(不包括竖直距离)

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;
struct level {
  int x1, x2, h;
} a[1005];

bool cmp(level a, level b) { return a.h > b.h; }

long long f[1005][2];

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int T, N, X, Y, MAX;
  cin >> T;
  while (T--) {
    cin >> N >> X >> Y >> MAX;
    for (int i = 1; i <= N; i++) {
      cin >> a[i].x1 >> a[i].x2 >> a[i].h;
    }
    //起点
    a[0].x1 = X;
    a[0].x2 = X;
    a[0].h = Y;
    //地面
    a[N + 1].x1 = -INF;
    a[N + 1].x2 = INF;
    a[N + 1].h = 0;
    sort(a + 1, a + 1 + N, cmp);  //从高到低排序
    for (int i = N; i >= 0; --i) {
      int j;
      //从i的左端跳下
      for (j = i + 1; j <= N + 1; ++j) {
        if (a[j].x1 <= a[i].x1 && a[i].x1 <= a[j].x2) {
          break;
        }
      }
      if (j == N + 1) {
        if (a[i].h <= MAX)
          f[i][0] = 0;
        else
          f[i][0] = INF;
      } else {
        if (a[i].h - a[j].h <= MAX) {
          int t1 = a[i].x1 - a[j].x1 + f[j][0];
          int t2 = a[j].x2 - a[i].x1 + f[j][1];
          f[i][0] = min(t1, t2);
        } else
          f[i][0] = INF;
      }
      //从i的右端跳下
      for (j = i + 1; j <= N + 1; ++j) {
        if (a[j].x1 <= a[i].x2 && a[i].x2 <= a[j].x2) {
          break;
        }
      }
      if (j == N + 1) {
        if (a[i].h <= MAX)
          f[i][1] = 0;
        else
          f[i][1] = INF;
      } else {
        if (a[i].h - a[j].h <= MAX) {
          int t1 = a[i].x2 - a[j].x1 + f[j][0];
          int t2 = a[j].x2 - a[i].x2 + f[j][1];
          f[i][1] = min(t1, t2);
        } else
          f[i][1] = INF;
      }
    }
    cout << f[0][0] + Y << endl;
  }
  return 0;
}

UVA – 11426 GCD – Extreme (II)

题目链接

给数n,求出所有gcd(i,j) (i<j<=n)的和.

对两个互质的数i,j,即gcd(i,j)=1,给它们都添加一个因子2,则有gcd(2i,2j)=2. 于是有gcd(ki,kj)=k.
求出所有互质的数对,然后就能进一步求出题目所需要的结果了.

用欧拉函数求出i以内与之互质的数的个数,并打表记录s=i*j内所有的数对i,j的gcd和:
sum[i*j]+=j*phi[i]

最后弄个前缀和,就能快速查询结果了.

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

int phi[4000005];
long long sum[4000005];
void euler(int n){
  for(int i=2;i<=n;++i) phi[i]=i;
  for(int i=2;i<=n;++i){
    if(phi[i]==i){
      for(int j=i;j<=n;j+=i){
        phi[j]=phi[j]/i*(i-1);
      }
    }
    for(int j=1;i*j<=n;++j){
      sum[j*i]+=j*phi[i];
    }
  }
  for(int i=1;i<=n;++i){
    sum[i]+=sum[i-1];
  }
}

int main() {
  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  int n;
  euler(4000000);
  while(cin>>n&&n){
    cout<<sum[n]<<endl;
  }
  return 0;
}

LightOJ – 1138 Trailing Zeroes (III)

题目链接

给一个整数Q(1<=Q<=10^8),求最小的N使N!的后缀有Q个0.

N!有多少个因子5,后缀就有多少个0,因为前面一定有足够多的因子2来与之相乘. 于是可以对N!求因子5的个数来确定后缀有几个0,求法可参考 阶乘分解

对N可确定一个范围,然后二分答案求解,注意最后得到的N,其5的因子个数可能是大于Q的.

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

int getCnt(int n){
    int cnt=0;
    while(n){
        cnt+=n/5;
        n/=5;
    }
    return cnt;
}

int main() {
  int T,kase=0;
  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  scanf("%d",&T);
  while(T--){
     int Q;
     cin>>Q;
     int l=5,r=Q*5;
     while(l<r){
         int mid=(l+r)/2;
         if(getCnt(mid)<Q) l=mid+1;
         else r=mid;
     }
     printf("Case %d: ",++kase);
     if(getCnt(r)==Q) printf("%d\n",r);
     else printf("impossible\n");
  }
  return 0;
}

POJ – 1015 Jury Compromise

POJ 1015
f[i][j][k]:从前i个人中选j个人,辩控差为k时的最大辩控和

状态转移即在第i(i<=j)个阶段,要么选第i个人,要么不选第i个人.
其实是个01背包.
注意下标范围,防负数出现.
嗯...代码写得挫,先这样吧.

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

int p[201], d[201];
int f[201][21][801];
int P, D, N, M;
int ans[21];

struct Path {
  int n, m, k, id;
} path[201][21][801];

void goBack(int n, int m, int k) { //状态回溯 
  int cnt = 0;
  while (path[n][m][k].id) {
    int next_n = path[n][m][k].n;
    int next_m = path[n][m][k].m;
    int next_k = path[n][m][k].k;
    if (path[n][m][k].id != path[next_n][next_m][next_k].id)
      ans[cnt++] = path[n][m][k].id;
    n = next_n, m = next_m, k = next_k;
  }
}

int main() {
  int kase = 0;
  while (cin >> N >> M && N&&M) {
    for (int i = 1; i <= N; ++i) {
      cin >> p[i] >> d[i];
    }
    P = 0, D = 0;
    memset(f,-1,sizeof(f));
    path[0][0][400].id=0;
    f[0][0][400] = 0;
    for (int i = 1; i <= N; ++i) {
      for (int j = 0; j <= M; ++j) {
        for (int k = -400; k <= 400; ++k) {
          if (j > 0 && k + p[i]-d[i] + 400 >= 0 && k + p[i]-d[i] + 400 <= 800 &&
              f[i - 1][j - 1][k + 400] != -1 &&
              f[i][j][k + p[i]-d[i] + 400] < f[i - 1][j - 1][k + 400] + p[i]+d[i]) {
            f[i][j][k + 400 + p[i]-d[i]] = f[i - 1][j - 1][k + 400] + p[i]+d[i];
            path[i][j][k + 400 + p[i]-d[i]].id = i;
            path[i][j][k + 400 + p[i]-d[i]].k = k + 400;
            path[i][j][k + 400 + p[i]-d[i]].m = j - 1;
            path[i][j][k + 400 + p[i]-d[i]].n = i - 1;
          }
          if (f[i - 1][j][k + 400] != -1 &&
              f[i - 1][j][k + 400] > f[i][j][k + 400]) {
            f[i][j][k + 400] = f[i - 1][j][k + 400];
            path[i][j][k + 400].id = path[i - 1][j][k + 400].id;
            path[i][j][k + 400].k = k + 400;
            path[i][j][k + 400].m = j;
            path[i][j][k + 400].n = i - 1;
          }
        }
      }
    }
    for (int k = 0; k <= 400; ++k) {
      if (f[N][M][400 + k] != -1 || f[N][M][400 - k] != -1) {
        if (f[N][M][400 + k] > f[N][M][400 - k]) {
          goBack(N, M, k + 400);
          P = (f[N][M][400 + k] + k) / 2;
          D = (f[N][M][400 + k] - k) / 2;
        } else {
          goBack(N, M, 400 - k);
          P = (f[N][M][400 - k] - k) / 2;
          D = (f[N][M][400 - k] + k) / 2;
        }
        printf("Jury #%d\n", ++kase);
        printf(
            "Best jury has value %d for prosecution and value %d for "
            "defence:\n",
            P, D);
        for (int i = M - 1; i >= 0; --i) {
          printf(" %d", ans[i]);
        }
        printf("\n");
        break;
      }
    }
  }
  return 0;
}

LightOJ – 1234 Harmonic Number

Harmonic Number

(有技巧的打表)

直接打表爆内存,隔50个打表还行.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#define ll long long
using namespace std;
const int maxn = 1e8;

double H[2000000];
void getH(){
    int k=0;
    double res=0;
    for(int i=1;i<=maxn;++i){
        res=res+1.0/i;
        if(i%50==0) H[++k]=res;
    }
}

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int T, kase = 0;
  getH();
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    double ans=H[n/50];
    int t=(n/50)*50;
    for(int i=1;i<=n%50;++i){
        ans=ans+1.0/(t+i);
    }
    printf("Case %d: %.10lf\n", ++kase,ans);
  }
  return 0;
}