codeforces #299 div 2

（总算是5题都做完了- -）

暂时做了4题，先放一下有时间做最后一题（当然如果我真的能做出的话。。。）（看了大神的代码总算是理解了E题，做完发现也没那么难，果然想出一个思路的过程对于我这种弱渣来说还是太强求了啊。。。）

A题：

英文单词别拼错就没什么问题吧

#include <cstdio>
#include <cstring>

using namespace std;

char str[10][10] = {"" , "" , "twenty" , "thirty" , "forty" , "fifty" , "sixty" , "seventy" ,"eighty" , "ninety"};
char single[10][10] = {"zero" , "one","two","three","four","five","six","seven","eight","nine"};
char dou[10][10] = {"ten" ,"eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"};
int main()
{
    int x;
    while(~scanf("%d" , &x)){
        if(x<10){
            printf("%s
" , single[x]);
        }
        else if(x<20){
            printf("%s
" , dou[x%10]);
        }
        else{
            int tmp = x%10;
            printf("%s" , str[x/10]);
            if(tmp){
                printf("-%s" , single[tmp]);
            }
            printf("
");
        }
    }
    return 0;
}

B题：
给定一个1~n的范围，问这个范围内只包含4或者7的数字有多少个

假设n是一个长度为l的整数，那么肯定所有 <l 长度的整数包含4,7的都能取到

就是(2^1+2^2+...2^(l-1))

那么就要确定 l 位整数的情况，不断从前往后按照那时的位置上的数字进行判断

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int dig[15];

int qpow(int digit)
{
    int a=2 , b=digit , ans=1;
    while(b)
    {
        if(b&1) ans*=a;
        a*=a;
        b>>=1;
    }
    return ans;
}

int getDigit(int x)
{
    int ans=0;
    while(x){
        x/=10;
        ans++;
    }
    return ans;
}

void getHead(int x , int len)
{
    int  index=len;
    while(x){
        dig[index--]=x%10;
        x/=10;
    }
}

int main()
{
    int n;
    while(~scanf("%d" , &n))
    {
        int len = getDigit(n);
        int ans=0;
        for(int i=1 ; i<=len-1 ; i++)
            ans+= qpow(i);
        if(ans == 1) ans-=1;
        getHead(n , len);
        for(int i=1 ; i<=len ; i++){
             //   cout<<dig[i]<<endl;
            if(dig[i]>7){
                ans += qpow(len-i+1);
                break;
            }
            else if(dig[i] == 7){
                ans += qpow(len-i);
                if(i == len) ans+=1;
            }
            else if(dig[i]>4){
                ans += qpow(len-i);
                break;
            }
            else if(dig[i]==4){
                if(i == len) ans+=1;
                continue;
            }
            else break;
        }
        printf("%d
" , ans);
    }
    return 0;
}

C题：

一个二分题，当且仅当t在，第一个数时输出-1 ， 否则二分判断 t>=最大数，且所有数之和<=t*m即可，这个略微想一下就好了，注意乘法溢出，我在这一直wa

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 1000005
int l,t,m;
int a , b , n;
#define ll long long

bool check(int mid)
{
    ll cnt = mid-l+1;
    ll st = a+(ll)(l-1)*b , la=(ll)(mid-1)*b+a;
    if(t>=la && (st+la)*cnt/2<=(ll)t*m) return true;
    else return false;
}

int bin_search()
{
    if(a+(ll)(l-1)*b > (ll)t) return -1;
    int left = l , right = N , ans = l;
    while(left<=right)
    {
        int mid = left+(right-left)/2;
        if(check(mid)){
            left = mid+1;
            ans = mid;
        }else right=mid-1;
    }
    return ans;
}

int main()
{
   // freopen("a.in" , "r" , stdin);

    while(~scanf("%d%d%d" , &a , &b , &n))
    {
        for(int i=1 ; i<=n ; i++){
            scanf("%d%d%d" , &l , &t , &m);
            printf("%d
" , bin_search());
        }
    }
    return 0;
}

D题：

后缀数组题，这里虽然一看就想到暴力，但是看一下时间复杂度就呵呵了

利用后缀数组判断当前位置插入一个新的p ， 覆盖前一个p的时候是否有冲突即可

当前位置 cur ， 其实就是判断cur的后缀是不是 0 开头的子串

然后就用vis[]保存插在当前点是否影响即可

然后i=1~m按顺序查询，单位时间内就解决了

这里各种特殊情况要考虑，我太欠缺考虑了，完全是依赖cf上可以错了看数据慢慢改对的。。。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 1000005
#define ll long long
const int MOD = 1e9+7;

char str[N];
int a[N] , n , m;
int r[N] , sa[N] , height[N] , rank[N] , wa[N] , wb[N] , wsf[N] , wv[N];
bool vis[N];

int cmp(int *r , int a , int b , int l)
{
    return r[a]==r[b] && r[a+l]==r[b+l];
}

void get_sa(int *r , int *sa , int n , int m)
{
    int *x=wa , *y=wb , *t;
    int i,j,p;
    for(i=0 ; i<m ; i++) wsf[i]=0;
    for(i=0 ; i<n ; i++) wsf[x[i]=r[i]]++;
    for(i=1 ; i<m ; i++) wsf[i]+=wsf[i-1];
    for(i=n-1 ; i>=0 ; i--) sa[--wsf[x[i]]]=i;

    p=1 ;
    for(j=1 ; p<n ; j*=2 , m=p){
        for(p=0 , i=n-j ; i<n ; i++) y[p++] = i;
        for(i=0 ; i<n ; i++) if(sa[i]>=j) y[p++]=sa[i]-j;

        for(i=0 ; i<n ; i++) wv[i]=x[y[i]];
        for(i=0 ; i<m ; i++) wsf[i]=0;
        for(i=0 ; i<n ; i++) wsf[wv[i]]++;
        for(i=1 ; i<m ; i++) wsf[i]+=wsf[i-1];
        for(i=n-1 ; i>=0 ; i--) sa[--wsf[wv[i]]]=y[i];

        t=x , x=y , y=t;
        x[sa[0]]=0;
        for(p=1 , i=1 ; i<n ; i++)
            x[sa[i]] = cmp(y , sa[i-1] , sa[i] , j)?p-1:p++;
    }
}

void callHeight(int *r , int *sa , int n , int m)
{
    int i , j , k=0;
    for(i=1 ; i<=n ; i++) rank[sa[i]]=i;
    for(i=0 ; i<n ; height[rank[i++]]=k)
        for(k?k--:0 , j=sa[rank[i]-1] ; r[i+k] == r[j+k] ; k++) ;
    return;
}

void biaoji(int n)
{
    memset(vis , 0 , sizeof(vis));
    vis[0]=true;
    int order = 0; //记录以开头为起点的排名
    for(int i=1 ; i<=n ; i++){
        if(sa[i] == 0) order = i;
    }
    int len=N;
    for(int i=order ; i>=1 ; i--){
        int pos = sa[i-1];
        len = min(len , height[i]);
        if(pos+len>=n) vis[pos]=true;
    }
    len=N;
    for(int i=order+1 ; i<=n ; i++){
        int pos = sa[i];
        len = min(len , height[i]);
        if(pos+len>=n) vis[pos]=true;
    }
}

int qpow(int cnt)
{
    if(!cnt) return 0;
    ll ans = 1 , a = 26 ;
    while(cnt)
    {
        if(cnt&1) ans = (ans*a)%MOD;
        a = (a*a)%MOD;
        cnt>>=1;
    }
    return (int)ans;
}

int main()
{
   // freopen("a.in" , "r" , stdin);

    while(~scanf("%d%d" , &n , &m))
    {
        scanf("%s" , str);
        for(int i=0 ; i<m ; i++) scanf("%d" , a+i);
        sort(a , a+m);

        int len = strlen(str);
        for(int i=0 ; i<len ; i++){
            r[i] = (int)str[i];
        }
        r[len]=0;
        get_sa(r , sa , len+1 , 128);
        callHeight(r , sa , len , 128);
        biaoji(len);

        int cnt = a[0]-1;
        bool flag = true;
        for(int i=1 ; i<m ; i++){
            int dis = a[i]-a[i-1];
            if(dis>=len){
                cnt+=dis-len;
            }else{
                if(!vis[dis]) {
                  //  cout<<i<<" "<<dis<<endl;
                    flag = false;
                    break;
                }
            }
        }
        cnt+=n+1-a[m-1]-len;
        int ans;
        if(!flag){
         //   cout<<"exist "<<endl;
            ans = 0;

        }
        else if(m == 0){
            ans = qpow(n);
        }
        else{
               // cout<<"no "<<endl;
            if(cnt)
                ans = qpow(cnt);
            else ans=1;
        }
        printf("%d
" , ans);
    }
    return 0;
}

 E题:

题目大意就是希望找到一个可能的游泳长度和跑步长度，对应那个队员的两种速度使其有机会夺冠，输出可能夺冠的队员编号

我们很容易就能想到，如果一个队员其中一项速度是最大的，那么他必然是能夺冠的

我们从游泳速度从上到下依次将当前跑步所能达到最快速度的人添加进入数组，结构体只保存s(swimming) , r(running)

当我们每次添加进一个元素时，当前元素是因为跑步最快所以不用删除，那么如果数组中除了游泳最快的那个无需考虑，中间的队员两个速度被夹在中间，此时要考虑能不能存在一个这样的lenS , lenR 使其夺冠

每次拿三个人的只进行考虑

比如这里举例 s1:1 , r1:3     s2:2,r2:2     s3:3,r3:1

那么假设这样的长度存在，设游泳长度为x ， 跑步长度为y

那么

t1=x/1+y/3

t2=x/2+y/2

t3=x/3+y/1

2号能夺冠，那么t2<=t1 && t2<=t3

t2<=t1-> x/y>=(1/2-1/3)/(1/1-1/2) = 1/3

t2<=t3 -> x/y<=(1/1-1/2)/(1/2-1/3) = 3/1

那么 1/3<=x/y<=3/1 成立，所以2号能夺冠

根据上述例子就可以自己计算了

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <map>
using namespace std;
#define N 10000
#define ll long long
#define eps 1e-9
int run[N*20+10]; //游泳速度为i的人中跑步速度最快达到run[i]

struct Ath{
    int s , r;
    Ath(int s=0 , int r=0):s(s),r(r){}
}ath[N*20+10];
int k , s[N*20+10] , r[N*20+10];

bool can_win(int s1 , int r1 , int s2 , int r2 , int s3 , int r3)
{
    //s1<s2<s3 , r1>r2>r3 , 判断s2,r2在包夹下能否有机会夺冠
    double t1 = (1.0/r2-1.0/r1) / (1.0/s1-1.0/s2);

    double t2 = (1.0/r3-1.0/r2) / (1.0/s2-1.0/s3);
  //  cout<<t1<<" "<<t2<<endl;
    if(t2-t1>=-eps) return true;
    else return false;
}

int main()
{
  //  freopen("a.in" , "r" , stdin);
    int n;
    while(~scanf("%d" , &n))
    {
        memset(run , 0 , sizeof(run));

        for(int i=1 ; i<=n ; i++){
            scanf("%d%d" , &s[i] , &r[i]);
            run[s[i]] = max(run[s[i]] , r[i]);
        }
        k=0;
        int i;
        for(i=N ; i>=0 ; i--){
            if(run[i]){
                ath[k++] = Ath(i , run[i]);
                break;
            }
        }
        for(i=i-1 ; i>=0 ; i--){
            run[i] = max(run[i] , run[i+1]);
            if(run[i] > run[i+1]){
                while(k>1){
                    if(!can_win(i , run[i] , ath[k-1].s , ath[k-1].r , ath[k-2].s , ath[k-2].r)){
                        k--;
                    }else
                        break;
                }
                ath[k++] = Ath(i , run[i]);
            }
        }
        map<int , int> m;
        for(int i=0 ; i<k ; i++){
            m[ath[i].s] = ath[i].r;
        }
        bool flag=true;
        for(int i=1 ; i<=n ; i++){
            if(m[s[i]] == r[i]){
                if(flag) printf("%d" , i);
                else printf(" %d" , i);
                flag = false;
            }
        }
        puts("");
    }
    return 0;
}