标签归档:二分答案

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