HDU1153——Magic Bitstrings，HDU1171——Big Event in HDU，HDU1261——字串数

本文主要是介绍HDU1153——Magic Bitstrings，HDU1171——Big Event in HDU，HDU1261——字串数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HDU1153——Magic Bitstrings

题目描述

问题 - 1153 (hdu.edu.cn)

运行代码

#include <iostream>
#include <vector>int main() {long long p;while (std::cin >> p) {if (p == 0) break;if (p == 2) {std::cout << "Impossible" << std::endl;} else {std::vector<int> a(p, 1);for (long long i = 1; i < p; i++) {a[i * i % p] = 0;}for (int i = 1; i < p; i++) {std::cout << a[i];}std::cout << std::endl;}}return 0;
}

代码思路

1. 从标准输入不断读取整数 p，直到读取到 0 为止。
2. 对于每个非零的输入 p，进行以下处理：
   • 如果 p 等于 2，直接输出 "Impossible"，因为在这种情况下无法按照后续逻辑生成所需的序列。
   • 否则，创建一个长度为 p 的 std::vector<int> 容器 a，并初始化为所有元素都是 1。
   • 接着通过一个循环，对于从 1 到 p - 1 的每个整数 i，计算 i * i % p，并将向量 a 中对应位置的元素设置为 0。
   • 最后遍历向量 a，输出其中从索引 1 到 p - 1 的每个元素，得到最终的序列。

3. 输入处理循环：while (std::cin >> p) 这个循环会不断读取标准输入的整数赋值给 p。只要输入不为 0，循环就会继续执行，这样可以处理多个输入值。

4. 特殊情况判断：当 p 等于 2 时，根据问题的要求输出 "Impossible"。这是因为当 p = 2 时，无法按照后续的逻辑生成满足条件的序列。

5. 向量初始化与修改：std::vector<int> a(p, 1) 创建了一个长度为 p 的向量 a，并将所有元素初始化为 1。这意味着初始状态下，向量中的每个位置都被设置为 1。for (long long i = 1; i < p; i++) { a[i * i % p] = 0; } 这个循环遍历从 1 到 p - 1 的整数 i。对于每个 i，计算 i * i % p，这实际上是找到 i 的平方对 p 取模的结果。然后将向量 a 中对应这个位置的元素设置为 0。这样就标记了所有平方数模 p 的位置。

6. 输出结果：for (int i = 1; i < p; i++) { std::cout << a[i]; } 遍历向量 a，从索引 1 开始输出每个元素，从而得到最终的序列。如果 a 的索引从 0 开始，那么当 p = 2 时，可能会导致输出错误的结果，所以从索引 1 开始输出。输出的序列中，对应平方数模 p 的位置为 0，其余位置为 1。

HDU1171——Big Event in HDU

题目描述

Problem - 1171 (hdu.edu.cn)

运行代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {int n;while (cin >> n && n > 0) {vector<int> values;double sum = 0.0;for (int i = 0; i < n; ++i) {int x, y;cin >> x >> y;sum += x * y;for (int j = 0; j < y; ++j) {values.push_back(x);}}double target = sum / 2.0;sort(values.begin(), values.end(),greater<int>());double a = 0.0;for (int v : values) {if (a + v > target) continue;a += v;}double b = sum - a;if (b > a) swap(a, b);cout << (long long)a << " " << (long long)b << endl;}return 0;
}

代码思路

一、整体思路

1. 不断从输入读取设施的数量 n，只要 n 大于 0 就继续处理一个测试用例。
2. 对于每个测试用例，读取 n 组设施的价值 x 和数量 y，并计算所有设施的总价值 sum，同时将每个设施的值按照数量加入到一个 vector 容器 values 中。
3. 确定总价值的一半作为分割目标 target。
4. 对 values 中的设施价值进行降序排序。
5. 从大到小遍历排序后的设施价值，将设施分配给两个学院，使得两个学院的价值尽量接近总价值的一半，记录下最终两个学院的价值 a 和 b，并保证 a 不小于 b。
6. 输出 a 和 b。

二、原理分析

1. 输入处理循环：while (cin >> n && n > 0) 这个循环会持续读取输入的 n，只要 n 是正整数，就表示有一个新的测试用例需要处理。如果 n 小于或等于 0，则退出循环，结束程序。

2. 读取设施信息和计算总价值：

   • 对于每个测试用例，循环 n 次读取每组设施的价值 x 和数量 y。
   • sum += x * y 这句代码计算所有设施的总价值，通过将每个设施的价值乘以数量并累加到 sum 中。
   • 同时，通过嵌套的循环 for (int j = 0; j < y; ++j) 将每个设施的值按照数量加入到 values 容器中，这样 values 中存储了所有设施的具体价值。

3. 确定分割目标：double target = sum / 2.0 计算总价值的一半，这是分割设施的目标值。目的是将设施分配给两个学院，使得每个学院的价值尽量接近总价值的一半。

4. 排序设施价值：sort(values.begin(), values.end(), greater<int>()); 使用标准库的排序函数对 values 中的设施价值进行降序排序。这样做的目的是在分配设施时，从价值较大的设施开始考虑，以便更快地接近分割目标。

5. 分配设施并计算两个学院的价值：

   • double a = 0.0; 和 double b = sum - a; 分别表示两个学院的价值，初始时 a 为 0，b 为总价值。
   • 遍历排序后的设施价值，对于每个设施价值 v，如果将其加入 a 后不超过分割目标 target，则将其加入 a，即 a += v;。如果超过了目标，则不加入。
   • 最后，b = sum - a; 计算出另一个学院的价值。如果 b 大于 a，则交换 a 和 b，以保证 a 不小于 b。

6. 输出结果：cout << (long long)a << " " << (long long)b << endl; 将 a 和 b 转换为长整型后输出，代表两个学院最终的价值。

HDU1261——字串数

题目描述

问题 - 1261 (hdu.edu.cn)

运行代码

#include <iostream>
#include <vector>
#include<algorithm>
#include <numeric>
using namespace std;// 高精度乘法
vector<int> multiply(const vector<int>& v, int factor) {vector<int> result;int carry = 0;for (int i = 0; i < v.size(); ++i) {int temp = v[i] * factor + carry;result.push_back(temp % 10);carry = temp / 10;}while (carry > 0) {result.push_back(carry % 10);carry /= 10;}return result;
}// 高精度除法
vector<int> divide(const vector<int>& v, int divisor) {vector<int> result;int remainder = 0;for (int i = v.size() - 1; i >= 0; --i) {int temp = remainder * 10 + v[i];result.push_back(temp / divisor);remainder = temp % divisor;}reverse(result.begin(), result.end());while (result.size() > 1 && result.back() == 0) result.pop_back();return result;
}void solve(int n, const vector<int>& a) {vector<int> factorial{ 1 };for (int i = 2; i <= accumulate(a.begin(), a.end(), 0); ++i) {factorial = multiply(factorial, i);}for (int i = 0; i < n; ++i) {for (int j = 2; j <= a[i]; ++j) {factorial = divide(factorial, j);}}for (int i = factorial.size() - 1; i >= 0; --i) {cout << factorial[i];}cout << endl;
}int main() {int n;while (cin >> n && n != 0) {vector<int> a(n);int sum = 0;for (int i = 0; i < n; ++i) {cin >> a[i];sum += a[i];}solve(n, a);}return 0;
}

代码思路

一、整体思路

1. 从标准输入不断读取整数 n，只要 n 不为 0，就处理一个新的测试用例。
2. 对于每个测试用例，读取 n 个整数存入 vector<int> a，并计算这些整数的总和 sum。
3. 通过一系列高精度计算函数，计算出给定数字组合下的结果并输出。

二、具体函数分析

1. 高精度乘法函数 multiply：

   • 接收一个整数向量 v 和一个整数 factor，模拟高精度乘法。
   • 遍历输入向量的每个元素，将其与 factor 相乘并加上进位 carry，计算出当前位的结果和新的进位。
   • 当进位不为 0 时，继续将进位加入结果向量中。
   • 最终返回表示乘积的向量。

2. 高精度除法函数 divide：

   • 接收一个整数向量 v 和一个整数 divisor，模拟高精度除法。
   • 从高位到低位遍历输入向量，将当前位与上一位的余数组合，进行除法运算，得到商和新的余数。
   • 将商存入结果向量中，最后反转结果向量并去除前导零。
   • 返回表示商的向量。

3. 求解函数 solve：

   • 接收整数 n 和整数向量 a，用于计算特定问题的结果。
   • 首先初始化一个表示 1 的向量 factorial。
   • 通过循环从 2 到输入数字总和（通过 std::accumulate(a.begin(), a.end(), 0) 计算得到），每次将 factorial 与当前数字相乘，模拟求阶乘的过程。
   • 然后对于每个输入的数字 a[i]，从 2 到 a[i] 循环，将 factorial 除以当前数字，去除重复的组合。
   • 最后，从高位到低位输出 factorial，即最终结果。

4. 主函数 main：

   • 循环读取输入的 n，如果 n 为 0 则结束程序。
   • 对于每个测试用例，创建一个长度为 n 的向量 a，读取 n 个整数存入 a，并计算这些整数的总和 sum。
   • 调用 solve 函数处理当前测试用例并输出结果。

这篇关于HDU1153——Magic Bitstrings，HDU1171——Big Event in HDU，HDU1261——字串数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---