目录
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
运行代码
#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中。输出计算得到的结果。
- 读取测试用例的数量
