url: http://oj.ecustacm.cn/problem.php?id=1361

tag:
数学

思路:
计算末尾零可以求每个因子中有多少对因子5和因子2,因为2 * 5 = 10,又因为2出现的次数会比5多,因为只要是偶数的情况就会出现因子2.所以只要计算这100个数中,每个数中因子5的个数,然后累加最后输出即可。

对于求阶乘来说,如果是某个数的阶乘,求这个数除以5,25,125……5k之后累加。例如100除以5之后等于20,那么对于1到20来说每个数乘以5后都会变成一个贡献5因子的数,除以25之后等于4说明1到4中每个数乘25都可以变成一个贡献25因子的数,而25 = 5 5,则是在原来贡献了5因子基础上多贡献一个5,为了避免重复,以及避免漏算,只需要将4 加上 20,即为答案。说明对于100!(1 2 3 …… * 100)来说,一共可以贡献出24个因子5,就是有24个末尾0.这种求阶乘末尾0的方式实际上和本题有出路。

代码:

// 乘积尾零
#include <iostream>
using namespace std;
int main()
{
    int n = 10;
    int cnt = 0;
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < n; j ++)
        {
            int a;
            cin >> a;
            while (a && a % 5 == 0)
            {
                if (a % 5 == 0)
                {
                    a /= 5;
                    cnt ++;
                }
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

答案:

#include <iostream>
using namespace std;
int main()
{
    cout << 31 << endl;
    return 0;
}

问题描述

小C在学习二进制运算,他了解到每个非负整数都有其二进制表示。例如,整数 5 可以被表示为二进制 "101",整数 11 可以被表示为二进制 "1011",并且除了 N = 0 外,任何二进制表示中都不含前导零。

二进制的反码表示是将每个 1 变为 0,每个 0 变为 1。例如,二进制数 "101" 的二进制反码为 "010"。现在小C想知道,给定一个十进制数 N,它的二进制反码对应的十进制数是多少。


测试样例

样例1:

输入:N = 5
输出:2

样例2:

输入:N = 10
输出:5

样例3:

输入:N = 0
输出:1

代码:

int solution(int N) {
    if (N == 0) {
        return 1;
    }
    int bits = std::log2(N) + 1;
    std::bitset<32> binary(N);
    std::bitset<32> inverted = ~binary;
    int result = (inverted.to_ulong() & ((1 << bits) - 1));
    return result;
}

解释

  • std::log2(N) + 1:

    • 计算 N 的二进制位数。
  • std::bitset<32> binary(N);:

    • 这行代码将整数 N 转换为一个 32 位的二进制表示。
  • std::bitset<32> inverted = ~binary;:

    • 这行代码对 binary 进行按位取反操作,得到 inverted
  • int result = inverted.to_ulong();:

    • 这行代码将 inverted 转换回无符号长整型。
  • (1 << bits) - 1:

    • 生成一个掩码,只保留低 bits 位。
  • inverted.to_ulong() & ((1 << bits) - 1):

    • 只取 inverted 的低 bits 位,忽略高位部分。

url: http://oj.ecustacm.cn/problem.php?id=1370

tag:
动态规划

思路:
使用动态规划的思想,令 f[i][j] 表示在i层楼内,使用j部手机,在使用最佳策略下,最多的测试次数,换句话说就是在i层楼内,使用j部手机最少需要花费的最大的测试次数。对于只有1部手机的情况来说,有几层就要测试几次。对于0层来说,不管几部手机都是0次。因为不知道从那一层开始掉落可以得到最优的答案,所以可以枚举对于每一个i都枚举从1开始到i层,表示从第k层开始掉落得到的结果。而对于每一个k来说,需要取一个最大值一共只有两种情况一种是摔坏,那么可以是 dp[k - 1][j - 1] 表示从k - 1层内用j - 1部手机测试次数,如果没有摔坏就是 dp[i - k][j] 即,剩余的i - k层内使用j部手机测试次数,之后两者取max再加上第k层的1次,对每种k的结果取min就是最后答案。最后输出 dp[1000][3] 表示1000层内,3部手机测试次数。

代码:

// 测试次数
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n = 1000;
int dp[1001][4];
int main()
{
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; i ++) dp[i][1] = i;
    for (int i = 1; i <= 3; i ++) dp[0][i] = 0;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= 3; j ++)
            for (int k = 1; k <= i; k ++)
                dp[i][j] = min(dp[i][j], max(dp[k - 1][j - 1], dp[i - k][j]) + 1);
    cout << dp[1000][3];
    return 0;
}

url: https://www.luogu.com.cn/problem/P2851

tag:
动态规划,背包DP,进制,USACO,2006

思路:
可以用背包来做。用 f[i] 表示john付i块钱时最少的硬币数,用 g[i] 表示店主找零i块钱时最少的硬币数,对于f来说,因为硬币数量有限所以需要用多重背包来完成。而对于g来说因为硬币无限多,所以可以用完全背包。对于体积上限取多少可以参考: https://www.luogu.com.cn/article/sd0bx6un

代码:

#include <iostream>  
#include <cstring>  
#include <cstdio>  
#include <algorithm>  
using namespace std;  
typedef long long LL;  
const int N = 10010, M = 150;  
int c[M], v[M];  
int f[N + M * M], g[N + M * M];  
int n, t, mx, sum;  
int main()  
{  
    cin >> n >> t;  
    for (int i = 1; i <= n; i ++)  
    {  
        cin >> v[i];  
        mx = max(mx, v[i] * v[i]);  
    }  
    for (int i = 1; i <= n; i ++)  
    {  
        cin >> c[i];  
        sum += v[i] * c[i];  
    }  
    if (sum < t)  
    {  
        cout << -1 << endl;  
        return 0;  
    }  
    memset(f, 0x3f, sizeof f);  
    memset(g, 0x3f, sizeof g);  
    g[0] = 0;  
    f[0] = 0;  
    for (int i = 1; i <= n; i ++)  
        for (int j = v[i]; j <= mx; j ++)  
            g[j] = min(g[j], g[j - v[i]] + 1);  
    for (int i = 1; i <= n; i ++)  
    {  
        for (int j = 1; j <= c[i]; j *= 2)  
        {  
            for (int k = mx + t; k >= j * v[i]; k --)  
                f[k] = min(f[k], f[k - j * v[i]] + j);  
            c[i] -= j;  
        }  
        if (c[i])  
            for (int k = mx + t; k >= c[i] * v[i]; k --)  
                f[k] = min(f[k], f[k - c[i] * v[i]] + c[i]);  
    }  
    int res = 0x3f3f3f3f;  
    for (int i = t; i <= t + mx; i ++)  
        res = min(res, f[i] + g[i - t]);  
    cout << (res == 0x3f3f3f3f ? -1 : res) << endl;  
    return 0;  
}

url: https://www.luogu.com.cn/problem/P4158

tag:
动态规划,递推,枚举,背包DP

思路:
f[i][j] 表示前i块木板粉刷j次最多的正确次数。用 g[i][j][k] 表示第i块木板粉刷j次粉刷前k个格子时最多的正确次数。用 sum[i][j] 表示第i块木板,前j个格子中需要涂成蓝色的有几个。
所以可以知道状态转移方程为 f[i][j] = max(f[i][j], f[i - 1][j - k] + g[i][k][m])
g[i][j][k] = max(g[i][j][k], g[i][j - 1][q] + max(sum[i][k] - sum[i][q], k - q - sum[i][k] + sum[i][q])) 最后遍历不同种粉刷次数中最多的粉刷格子数。

代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int f[51][2550], sum[51][2550];
int g[51][2550][51];
int n, m, t;
char s[100];
int main()
{
    cin >> n >> m >> t;
    for (int i = 1; i <= n; i ++)
    {
        cin >> s;
        for (int j = 1; j <= m; j ++)
        {
            if (s[j - 1] == '1') sum[i][j] = sum[i][j - 1] + 1;
            else sum[i][j] = sum[i][j - 1];
        }
    }
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            for (int k = 1; k <= m; k ++)
                for (int q = j - 1; q < k; q ++)
                    g[i][j][k] = max(g[i][j][k], g[i][j - 1][q] + max(sum[i][k] - sum[i][q], k - q - sum[i][k] + sum[i][q]));
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= t; j ++)
            for (int k = 0; k <= min(j, m); k ++)
                f[i][j] = max(f[i][j], f[i - 1][j - k] + g[i][k][m]);
    int res = 0;
    for (int i = 1; i <= t; i ++) res = max(res, f[n][i]);
    cout << res << endl;

    return 0;
}