西山居初赛二 总结

hdu 4548 美素数

　　用线性筛法筛选出10^6的素数，然后预处理统计下.. O(1)就能得到结果了.

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int N = (int)1e6+10;

bool vis[N];
int p[N], sum[N];
void GetPrime(){
    memset(vis,0,sizeof(0));
    vis[1] = 1;
    int cnt = 0;
    for(int i = 2; i < N; i++){
        if( !vis[i] ) p[cnt++] = i;
        for(int j = 0; (j<cnt)&&(p[j]*i<N); j++){
            vis[ p[j]*i ] = 1;
            if( i%p[j] == 0 )break;
        }
    }
}
int Dight(int x){
    int s = 0;
    while(x) s+=x%10, x /= 10;
    return s;
}
void init(){
    GetPrime();
    sum[0] = sum[1] = 0;
    for(int i = 2; i < N; i++){
        sum[i] = sum[i-1];    
        if( !vis[i] && !vis[ Dight(i) ] ) sum[i]++; 
    }
}
int main(){
    init();
    int T;
    scanf("%d", &T);
    for(int Case = 1; Case <= T; Case++ ){
        int a, b;
        scanf("%d%d", &a,&b);
        printf("Case #%d: %d\n", Case, sum[b] - sum[a-1] );    
    }
    return 0;
}

hdu 4549 M斐波那契数列

　　直接搞显然不行, 没有线性关系. 简单推导下有,  a, b, a^1*b^1, a^1*b^2 .... 可以知道a,b的幂满足Fib, 然后构造矩阵快速幂...就好了.还需要个性质: A^X = A^( X mod Eular(M) ) ( mod M ) .

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;
const int mod = (int)1e9+7;

struct Matrix{
    LL mat[2][2];
    void zero(){memset(mat,0,sizeof(mat)); }
    void unit(){zero();mat[0][0]=mat[1][1]=1;}    
}A, T;

void init_Matrix(){
    A.zero(); T.zero();
    A.mat[0][0]=A.mat[1][0]=1;
    T.mat[0][1]=T.mat[1][0]=T.mat[1][1]=1;
}
void print(Matrix a){
    printf("Matrix:\n");
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++)    
            printf("%d ", (int)a.mat[i][j]);
        puts("");
    }
}
Matrix mult(Matrix a, Matrix b){
    Matrix c; c.zero();
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                c.mat[i][k]=(c.mat[i][k]+a.mat[i][j]*b.mat[j][k])%(mod-1);
    return c;
}
Matrix Pow(Matrix x,int n){
    Matrix c; c.unit();
    while( n ){
        if(n&1) c = mult(x,c);
        x = mult(x,x);
        n >>= 1;
    }
    return c;
}
LL Fib(int n){
    init_Matrix();
    A = mult( Pow(T,n-1), A );        
    return A.mat[0][0];
}
LL pow( LL x, int n ){
    LL c = 1;
    while(n){
        if(n&1) c = c*x%mod;
        x = x*x%mod;
        n >>= 1;
    }
    return c;
}
int main(){
    int a, b, n;    
    while( scanf("%d%d%d",&a,&b,&n) != EOF){
        if( n < 2 ){
            if( n == 0 ) printf("%d\n", a);
            else printf("%d\n", b);
        }                
        else{
            LL n1 = Fib( n-1 ), n2 = Fib( n );
    //        printf("n1 = %d, n2 = %d\n", (int)n1, (int)n2 );    
            LL ans = pow(a,n1)*pow(b,n2)%mod;    
            printf("%d\n", (int)ans );    
        }    
    }    
    return 0;
}

hdu 4550卡片游戏

　　和波神讨论了好久...有0的情况好恶心. 最后邪恶的处理第一次出现0 的情况. 主要是出现了0, 则此时,在之后选定一个最小非0的数放在前面必定最优. 其他情况就是大的放后,小的放前面.....稀里哗啦写了好多..  A掉了后看到别人代码好短- - .....才发现好多地方做了无用工.......

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
using namespace std;

const int N = 110;

char s[N];
string t;
int len;
// S( i, len-1 )
void gao( int i ){
        char tm = '9'+10; 
        int pos = -1, cnt = 0;      
        for(int j = i; j < len; j++){    
            if( (s[j]!='0') && (tm>=s[j]) ) tm = s[j], pos = j;    
        }        
        if( (pos==-1) || ( (t[0]!='0')&&(s[pos]>t[0]))){
            for(int j = i; j < len; j++) t = t+s[j];    
        }
        else{
            for(int j = i; j < pos; j++){
                if( s[j] == '0' ) cnt++;    
                else t = t+s[j];    
            }    
            for(int j = 0; j < cnt; j++ ) t = '0' + t;    
            t = s[pos] + t;
            for(int j = pos+1; j < len; j++ ) 
                t = t + s[j];
        }    
        //printf("%s\n", t.c_str() );
}

int main(){
    int T;
    scanf("%d", &T);
    while( T-- ){
        scanf("%s", s);
        t.clear();
        len = strlen(s);
        int i = 1; t = s[0];
        if( s[0] == '0' ) gao(1);    
        else{
            while( (i<len) && (s[i]!='0') ){
                if( s[i] > t[0] ) t = t+s[i];
                else t = s[i] + t;
                i++;    
            }    
            if( i < len ) gao(i);    
        }
        printf("%s\n", t.c_str() );    
    }
    return 0;
}

　　精简的代码思路:  就是找一个非0最小所在下标pos, 放在最前面. 其中 下标i < pos的, 用大在后,小在前.  然后i > pos的直接原样丢后面...不用考虑0的特殊情况....真心好..

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int N = 110;

char s[N];

int main(){
    int _;
    scanf("%d", &_);
    while( _-- ){
        scanf("%s", s);
        string t;
        t += s[0];
        char ch = '9';
        int pos;
        for(int i = 0; s[i]; i++)
            if( (s[i]!='0') && (ch>=s[i]) ) ch = s[pos=i];
        for(int i = 1; s[i]; i++){
            if( i == pos ) t = s[i] + t;
            else if( i < pos ){
                if( s[i] <= t[0] ) t = s[i] + t;
                else t = t + s[i];
            }
            else t = t + s[i];    
        }
        printf("%s\n", t.c_str() );    
    }
    return 0;
}