分类目录归档:ACM-POJ

POJ 2081 有趣的统计!

此题求n!末尾有多少个0

容易想到末尾0必须是由质因数2*5得到

但是5出现的次数必然远小于2

故统计质因数5的个数即可。

然后这是一个非常巧妙的统计方法。列出前25个数据自己试试便能知道为什么啦。

# include <cstdio>
int t, n, ans;
int main()
{
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%d", &n);
        ans = 0;
        while( n ) ans += (n/=5);
        printf("%d\n", ans);
    }
    return 0;
}

POJ 1953 基础的DP递推思想

题意:求t个n位的2进制数中,有多少个没有连续的1.

dp0[x]表示以0开头长度为x的这类01串的个数,dp1[x]表示以1开头长度为x的这类01串的个数

dp0[x] = dp0[ x-1 ] + dp1[ x-1 ], dp0[1] = 1;

dp1[x] = dp0[ x-1 ] , dp1[1] = 1;

合并 dp0[x] + dp1[x] = dp0[x-1] + dp1[x-1] + dp0[x-1]
又dp0[x-1] = dp0[x-2] + dp1[x-2]
得:
ans[i] = ans[i-1] + ans[i-2]
由于第i位可任选0或1:
选1时,i-1位选0,i-2位选1的合法
选0时,i-1位选1,i-2位选0的合法
# include <iostream>
# include <algorithm>
using namespace std;

const int _ = 0;
long long ans[50] = {0};

int t, n;

int main()
{
    int i;
    ans[1] = 2LL, ans[2] = 3LL;
    for ( i = 3; i < 50; ++i ) ans[i] = ans[i-1] + ans[i-2];
    cin >> t;
    for ( i = 1; i <= t; ++i )
    {
        cin >> n;
        cout << "Scenario #" << i <<":" << endl;
        cout << ans[n] << endl << endl;
    }
    return 0>_<0;
}

POJ 1207 笔记

初看觉得可能是数学题,仔细一想记忆化搜索就可以了。

笔记:

数据范太大,因此采用部分记忆化搜索。

注意ACM常见坑,给定区间i , j时并未保证i <= j

另外注意输出要求维持原i, j顺序,不能直接swap原变量。

# include <cstdio>
int r[100007] = {0};

int dfs(int x)
{
    if ( x < 100007 && r[x] ) return r[x];
    int res;
    if ( x&1 ) res = dfs((x<<1)+x+1) + 1;
    else res = dfs(x>>1) + 1;
    if ( x < 100007 ) r[x] = res;
    return res;
}

int main()
{
    int i, j, a, b, k, m;
    r[1] = 1;
    while( scanf("%d%d", &i, &j) != EOF )
    {
        if ( j < i ) a = j, b = i;
        else a = i, b = j;
        m = 0;
        for (k = a; k <= b; ++k ) if ( dfs(k) > m ) m = dfs(k);
        printf("%d %d %d\n", i, j, m);
    }
    return 0;
}