A 四则运算

直接输出 a * b 即可

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    cout << a * b << endl; 
    return 0;
}

B 四则运算+判断

当n个数中有 0 时，直接输出 0。

当n个数中无 0 时，每次计算时判断答案是否 > 10 ^ 18。

注：记得开 long long！！！

#include <bits/stdc++.h>
#define int long long
using namespace std;

int a[100005];

signed main()
{
    int n;
    cin >> n;
    int z = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        z += (a[i] == 0);
    }
    if (z > 0)
    {
        cout << 0 << endl;
        return 0;
    }
    int ans = 1;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] <= 1000000000000000000 / ans)
        {
            ans *= a[i];
        }
        else
        {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans << endl;
    return 0;
}

C 小数+四则运算

输入时将小数（已规定是两位小数）转化为整数，计算时再将答案除以 100 即可。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long a, b, c; 
    scanf("%lld%lld.%lld", &a, &b, &c);
    long long ans = a * (100 * b + c) / 100;
    printf("%lld", ans);
    return 0;
}

D 哈希+贪心统计答案个数

贪心统计 n 中每个质因数（2、3、5……）的个数能够分成多少个大于 0 的不同的数。

例：n = 2 ^ 7，因为 7 = 1 + 2 + 3 + 1，所以能分成 3 个，答案 = 3。

O（√n）即可

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    int n;
    cin >> n;
    map<int, bool> p;
    int ans = 0;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i) continue;
        int sum = 1;
        while (n % i == 0)
        {
            sum *= i;
            if (!p[sum])
            {
                ans++;
                p[sum] = true;
                sum = 1;
            }
            n /= i;
        }
    }
    if (n > 1)
    {
        ans++;
    }
    cout << ans << endl;
    return 0;
}

E 排序+数学+简单动脑筋

a，b 两数组分别排序后可以得到，x 的中位数只能在 a，b 数组的中位数之间的范围内选。

讨论 n 的奇偶性：

1. n 为奇数：
   x 的中位数为在 a[n / 2 + 1] ~ b[n / 2 + 1] 中间的（包括 a[n / 2 + 1]，b[n / 2 + 1] ）所有数。

2. n 为偶数：
   x 的中位数为在 a[n / 2] + a[n / 2 + 1] ~ b[n / 2] + b[n / 2 + 1] 中间的（包括 a[n / 2] + a[n / 2 + 1]，b[n / 2] + b[n / 2 + 1] ）所有数。

#include<bits/stdc++.h>
using namespace std;

long long n, sum, a[1000005], b[1000005];

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld %lld", &a[i], &b[i]);
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    if (n % 2 == 1)
    {
        printf("%lld", b[n / 2 + 1] - a[n / 2 + 1] + 1);
    }
    else
    {
        sum = (b[n / 2 + 1] + b[n / 2] - a[n / 2] - a[n / 2 + 1] + 1);
        printf("%lld", sum);
    }
    return 0;
}

F dp+简单动脑筋

这个问题可以改成：有多少对 (T，U) 使得它们都是 {1，2，……，N} 的子集并且还满足下面的条件？

1.U是T的子集

2.设U = {x1，x2，……，xk}，那么a[x1] + a[x2] + …… + a[xk] = S。
那么，对于每个i (1 ≤ i ≤ n)，有三个选择：

1）放在 U 和 T 中

2）放在 T 中，但不要放在 U 中

3）都不放

通过分析可以得到：只有在选择了第一个选项的情况下，总和才会增加a[i]。

可以看出，递归关系为: dp[i][j] = 当i的选择已经确定时，组合的数量使得U中的每个k的a[k]之和等于j。

所以答案是 dp[n][s]，时间复杂度为 O（ns）。

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;

int n, s, a[3005], dp[3005][3005];

int main()
{
    cin >> n >> s;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    dp[0][0] = 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= s; j++)
        {
            dp[i + 1][j] += 2 * dp[i][j];
            dp[i + 1][j] %= mod;
            if (j + a[i] <= s)
            {
                dp[i + 1][j + a[i]] += dp[i][j];
                dp[i + 1][j + a[i]] %= mod;
            }
        }
    }
    cout << dp[n][s] << endl;;
    return 0;
}

逆元 + 01背包:

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;

long long f[3005], a[3005];

int main()
{
    int n, s;
    cin >> n >> s;
    f[0] = 1; 
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        f[0] *= 2;
        f[0] %= mod;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = s; j >= a[i]; j--)
        {
            f[j] = (f[j - a[i]] * 499122177 % mod + f[j]) % mod;
        }
    }
    printf("%d", f[s]);
    return 0;
}