目录
HDU1059——Dividing
题目描述
运行代码
代码思路
HDU1060——Leftmost Digit
题目描述
编辑编辑 运行代码
代码思路
HDU1061——Rightmost Digit
题目描述
运行代码(快速幂)
代码思路
HDU1059——Dividing
题目描述
Problem - 1059
运行代码
#include <iostream>
#include <vector>
#include<algorithm>
#include<stdio.h>
using namespace std;const int MAX_N = 50000 + 7;
const int MAX_W = 120005 + 7;int dp[MAX_W];
int w[MAX_N];int main() {int s[7];int count = 0;while (cin >> s[1] >> s[2] >> s[3] >> s[4] >> s[5] >> s[6], s[1] || s[2] || s[3] || s[4] || s[5] || s[6]) {fill(dp, dp + MAX_W, 0);int k = 0;int sum = 0;for (int i = 1; i <= 6; i++) {sum += s[i] * i;for (int a = 1; a <= s[i]; a *= 2) {w[k++] = i * a;s[i] -= a;}if (s[i] > 0)w[k++] = i * s[i];}for (int i = 0; i < k; i++)for (int j = sum / 2; j >= w[i]; j--)dp[j] = max(dp[j - w[i]] + w[i], dp[j]);cout << "Collection #" << ++count << ":" << endl;if (2 * dp[sum / 2] == sum)cout << "Can be divided." << endl;elsecout << "Can't be divided." << endl;cout << endl;}return 0;
}
代码思路
-
定义了一些常量和数组:
MAX_N
和MAX_W
分别表示可能的最大数量和最大权重。dp
数组用于动态规划过程中的状态存储。w
数组用于存储不同组合的弹珠权重。
-
在
main
函数中:- 定义了一个整数数组
s
来存储每种价值的弹珠数量。 - 定义了一个计数器
count
用于标记集合的编号。 - 通过一个循环不断读取弹珠的数量,只要输入的弹珠数量不全为 0 。
- 计算弹珠的总价值
sum
,同时将不同组合的弹珠价值存储到w
数组中。 - 然后使用两层循环进行动态规划:外层循环遍历
w
数组,内层循环从总价值的一半开始递减,更新dp
数组中的值,表示在当前权重下能达到的最大价值。 - 根据最终
dp[sum / 2]
的值是否为总价值的一半,判断能否将弹珠公平划分,并输出相应的结果。 - 每次处理完一个集合,增加集合编号,并输出一个空行。
- 定义了一个整数数组
HDU1060——Leftmost Digit
题目描述
Problem - 1060
![](https://i-blog.csdnimg.cn/direct/5e1ffbe29bf54202b27b19b3d990776d.png)
运行代码
#include <iostream>
#include <cmath>using namespace std;int main() {int T;cin >> T;while (T--) {long long N;cin >> N;double num = N * log10(N);num = num - floor(num);int digit = pow(10, num);cout << digit << endl;}return 0;
}
代码思路
- 首先,读取测试用例的数量
T
。 - 进入一个循环,处理
T
个测试用例。 - 在每个测试用例中,读取一个正整数
N
。 - 通过数学公式
num = N * log10(N)
计算一个中间值num
。log10(N)
表示以 10 为底N
的对数。N * log10(N)
得到的值的小数部分与N^N
的对数的小数部分有关。
- 然后,通过
num = num - floor(num)
提取出num
的小数部分。 - 最后,使用
pow(10, num)
计算出一个值,并取整数部分作为N^N
的最左边的数字进行输出。
HDU1061——Rightmost Digit
题目描述
Problem - 1061
运行代码(快速幂)
#include <iostream>
using namespace std;
int fastPowerMod(int base, int exponent, int modulus) {int result = 1;base %= modulus;while (exponent > 0) {if (exponent & 1) {result = (result * base) % modulus;}exponent >>= 1;base = (base * base) % modulus;}return result;
}int main() {int T;cin >> T;while (T--) {long long N;cin >> N;int last = fastPowerMod(N, N, 10);cout << last << endl;}return 0;
}
代码思路
-
定义了一个函数
fastPowerMod
,用于计算快速幂取模。- 初始化结果
result
为 1 。 - 将底数
base
对模modulus
取余,以防止中间计算过程中数值过大。 - 当指数
exponent
大于 0 时,进行循环:如果指数的最低位为 1 (通过exponent & 1
判断),则更新结果为result = (result * base) % modulus
,即在当前结果的基础上乘以底数,并对模取余。将指数右移一位(exponent >>= 1
),同时将底数平方并对模取余(base = (base * base) % modulus
)。 - 最终返回计算得到的结果。
- 初始化结果
-
在
main
函数中:- 读取测试用例的数量
T
。 - 进入一个循环,处理
T
个测试用例:读取一个正整数N
。调用fastPowerMod
函数,以N
作为底数和指数,以 10 作为模,计算并得到N^N
对 10 取模的结果,存储在last
中。输出计算得到的结果。
- 读取测试用例的数量