博客

A–2022

问题描述

将 2022 拆分成 10 个互不相同的正整数之和, 总共有多少种拆分方法?

注意交换顺序视为同一种方法, 例如 2022=1000+1022 和 2022=1022+1000 就视为同一种方法。

答案提交

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

运行限制

最大运行时间：3s

最大运行内存: 512M

考察的是二维费用01背包问题，简单题。

令dp[i][j][k]表示在前i个数中选，总和不超过j，总个数不超过k的方案数，则dp[2022][2022][10]即为答案（在1~2022这些数中选，总和为2022，个数为10的方案数），注意初始化时dp[0][0][0]要赋值为1，且要long long！

代码我用了滚动数组进行空间优化，答案是：379187662194355221

代码：

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int N = 2050;
int v[N], dp[N][15];

signed main()
{
	for (int i = 1; i <= 2022; ++i) {
		v[i] = i;
	}
	dp[0][0] = 1;
	for (int i = 1; i <= 2022; ++i) {
		for (int j = 10; j >= 1; --j) {
			for (int k = 2022; k >= v[i]; --k) {
				dp[k][j] += dp[k - i][j - 1];
			}
		}
	}
	cout << dp[2022][10] << '\n';

	return 0;
}

B – 钟表



枚举时分秒，分别计算秒针、分针、时针与0时的夹角度数

秒针的夹角度数为：360 * m / 60；（一圈360度，秒针转了m / 60圈）

分针的夹角度数为：360 * f / 60 + 6 * m / 60；（分针转了f / 60圈，另外每两分钟之间相差6度（60秒），已经过了m秒，故再加上 6 * m / 60度）

时针的夹角度数：360 * s / 12 + 30 * (f * 60 + m) / 3600; （时针转了s / 12圈，另外每两小时之间相差30度（3600秒），已经过了f * 60 + m秒，故再加上30 * (f * 60 + m) / 3600度）

分针与时针之间的夹角度数即为分针与0时的夹角度数减去时针与0时的夹角度数的绝对值，同时要取小于180度的夹角值

分针和秒针的夹角同理

（转自：


polarday.


）

代码：

#include<bits/stdc++.h>

using namespace std;

signed main()
{
    double m = 0, f = 0, s = 0;
    for (double i = 0; i < 60; ++i)
    {
        m = 360 * i / 60;
        for (double j = 0; j < 60; ++j)
        {
            f = 360 * j / 60;
            f += 6 * i / 60;
            for (double k = 0; k <= 6; ++k)
            {
                s = 360 * k / 12;
                s += 30 * (j * 60 + i) / 3600;
                double A = fabs(f - s);
                A = min(A, 360 - A);
                double B = fabs(f - m);
                B = min(B, 360 - B);
                if (A == 2 * B && (i || j || k))
                {
                    cout << k << ' ' << j << ' ' << i << '\n';
                    return 0;
                }
            }
        }
    }
    return 0;
}