Part_1 题目
43956 引水入城 OJ编程题
【考点】这个题目综合了多种算法思想，包括搜索、动态规划、位运算、贪心算法和排序算法，需要综合考虑各种情况并进行相应的优化。
【解题思路】
1.深度优先搜索：定义一个 letsGo 函数，该函数用于深度优先搜索城市地图，寻找水流路径。通过递归方式遍历城市地图，判断当前位置是否已被访问，并且判断是否有相邻的位置比当前位置更低，若满足条件则继续搜索。若水流到达最下面一行，则标记该列为有水流出的列。
2.动态规划：使用一个向量 water 来记录每列是否有水流出。在 letsGo 函数中，当水流到达最下面一行时，将对应的列标记为有水流出的列。
3.位运算：枚举所有可能的水流路径，通过二进制状态表示，使用位运算进行状态的枚举。
4.贪心算法：在 letsGo 函数中，选择高度递减的路径进行搜索，以确保水流顺利流动。
5.排序算法：在生成所有可能的水流路径后，对这些路径进行排序，以确保按照长度递增的顺序尝试不同的路径。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> city;
vector<int> water;
int N, M;
void letsGo(vector<vector<int>>& visited, int x, int y) {
// if(!visited[x][y]) {
// cout << "(" << x + 1 << ", " << y + 1 << ") ";
// } else {
// cout << "(" << x + 1 << ", " << y + 1 << ")已被访问";
// }
visited[x][y] = 1;
if(x == N - 1) {
water[y] = 1;
}
if(x - 1 >= 0 && !visited[x - 1][y] && city[x - 1][y] < city[x][y]) { // 北
letsGo(visited, x - 1, y);
}
if(x + 1 < N && !visited[x + 1][y] && city[x + 1][y] < city[x][y]) { // 南
letsGo(visited, x + 1, y);
}
if(y - 1 >= 0 && !visited[x][y - 1] && city[x][y - 1] < city[x][y]) { // 西
letsGo(visited, x, y - 1);
}
if(y + 1 < M && !visited[x][y + 1] && city[x][y + 1] < city[x][y]) { // 东
letsGo(visited, x, y + 1);
}
}
bool compare(string a, string b) {
return a.length() < b.length();
}
void Begin(vector<string>& test) {
for(string t : test) {
vector<vector<int>> visited(N, vector<int> (M, 0));
for(char c : t) {
// cout << "\ndfs路线：";
letsGo(visited, 0, c - '0');
}
// cout << "\n";
int j = 0; // 检验是否满足条件
for( ; j < M; j++) {
if(!visited[N - 1][j]) break;
}
if(j == M){
cout << "1\n" << t.length();
return;
}
}
int impossible = 0;
for(int x : water) {
if(!x) impossible++;
}
cout << "0\n" << impossible;
}
int main() {
cin >> N >> M;
city.resize(N, vector<int> (M));
water.resize(M, 0);
for(int i = 0; i < N; i++) { // 输入数据
for(int j = 0; j < M; j++) {
cin >> city[i][j];
}
}
string str;
for(int i = 0; i < M; i++) {
str.push_back(i + '0');
}
vector<string> test;
for(int i = 0; i < (1 << M); i++) { // 枚举所有情况
string s;
for(int j = 0; j < M; j++) {
if(i & (1 << j)) {
s.push_back(str[j]);
}
}
if(!s.empty()){
test.push_back(s);
}
}
sort(test.begin(), test.end(), compare);
Begin(test);
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> city, visited;
int N, M;
void letsGo(int x, int y, int count) {
// cout << "(" << x + 1 << ", " << y + 1 << ") " << count << endl;
visited[x][y] = 1;
if (x - 1 >= 0 && !visited[x - 1][y] && city[x - 1][y] < city[x][y]) { // 北
letsGo(x - 1, y, count);
}
if (x + 1 < N && !visited[x + 1][y] && city[x + 1][y] < city[x][y]) { // 南
letsGo(x + 1, y, count);
}
if (y - 1 >= 0 && !visited[x][y - 1] && city[x][y - 1] < city[x][y]) { // 西
letsGo(x, y - 1, count);
}
if (y + 1 < M && !visited[x][y + 1] && city[x][y + 1] < city[x][y]) { // 东
letsGo(x, y + 1, count);
}
return; // 遍历结束
}
bool compare(int x, int y) {
return x > y;
}
int main() {
cin >> N >> M; // 输入数据
city.resize(N, vector<int>(M));
visited.resize(N, vector<int>(M, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> city[i][j];
}
}
vector<int> temp = city[0];
sort(temp.begin(), temp.end(), compare); // 从高往低选蓄水厂
int index = 0, count = 0;
while(index < M){
for(int y = 0; y < M; y++) {
if(!visited[0][y] && city[0][y] == temp[index]) {
letsGo(0, y, ++count);
}
}
int j = 0; // 检验是否满足要求
for (; j < M; j++) {
if (!visited[N - 1][j]) break;
}
if (j == M) {
break;
}
index++;
}
int dry = 0;
for (int p : visited[N - 1]) {
if (!p) dry++;
}
dry == 0 ? cout << "1\n" << count : cout << "0\n" << dry;
return 0;
}
43957 多项式输出 OJ编程题
【考点】这道编程题的考点是多项式输出，即将给定的多项式表达式按照一定的规则输出成标准形式。
【解题思路】
1.遍历数组：使用一个循环遍历整个系数数组a，从高次到低次。对于每个系数a[i]，进行一系列判断和输出操作。
2.输出规则：如果系数a[i]为0，表示该项为零，直接跳过。如果系数a[i]为正且i不为0，输出"+"符号。如果系数a[i]为负，输出"-"符号。输出系数的绝对值，如果绝对值不为1，则输出系数的绝对值。
3.判断指数的情况：如果n - i为0，说明是常数项，不需要输出"x"。如果n - i为1，输出"x"。如果n - i不为0且不为1，输出"x^(n-i)"。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i = 0; i < n + 1; i++) {
cin >> a[i];
}
for(int i = 0; i < n + 1; i++) {
if(a[i] == 0)
continue;
if(a[i] > 0 && i != 0) // 输出符号
cout << "+";
else if(a[i] < 0)
cout << "-";
if(abs(a[i]) != 1) // 输出系数
cout << abs(a[i]);
else if(n - i == 0) {
cout << abs(a[i]);
}
if(n - i == 1) // 输出指数
cout << "x";
else if(n - i != 0)
cout << "x^" << n - i;
}
return 0;
}
43960 道路游戏 OJ编程题
【考点】这道编程题是一个模拟题，考察了递归和模拟路径选择的思路。
【解题思路】
1.递归函数： letsGO 函数模拟了每一步的选择。在每个时间步中，选择可以获得最大利润的道路，同时考虑是否更换当前位置。
2.路径选择逻辑： 遍历每个道路，计算当前位置可以选择的道路中哪一条利润最大，然后根据条件进行选择。
3.终止条件： 递归的终止条件是达到设定的时间步 m 或者达到最大步数 p。
4.全局变量记录利润： 使用全局变量 Money 记录总利润，在每步递归中更新。
#include <iostream>
#include <vector>
using namespace std;
int n, m, p, Money = 0;
vector<vector<int>> roadMoney;
vector<int> payMoney;
void letsGO(int current, int time, int step) {
if(time == m)
return;
int maxMoney = -9999, temp = -1;
for(int i = 0; i < n; i++) {
int m = roadMoney[time][i] - payMoney[i];
if(m > maxMoney) {
maxMoney = m;
temp = i;
}
}
// cout << "temp: " << temp + 1 << " maxMoney: " << maxMoney << " time: " << time + 1;
// cout << " current: " << (current == -1 ? temp + 1 : current + 1) << " step: " << step << endl;
if(maxMoney > roadMoney[time][current] || current == -1 || step == p) {
// cout << " money = " << maxMoney << endl;
Money += maxMoney;
letsGO((temp + 1) % n, time + 1, current == -1 ? 1 : 0);
} else {
// cout << " money = " << roadMoney[time][current] << endl;
Money += roadMoney[time][current];
letsGO((current + 1) % n, time + 1, step + 1);
}
}
int main() {
cin >> n >> m >> p;
roadMoney.resize(m, vector<int>(n));
payMoney.resize(n);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> roadMoney[j][i];
}
}
for(int i = 0; i < n; i++) {
cin >> payMoney[i];
}
letsGO(-1, 0, 0);
cout << Money;
return 0;
}
43965 ISBN号码 OJ编程题
【考点】该题涉及了字符处理、加权求和、模运算等操作。
【解题思路】
1.验证前9位数字是否是有效的ISBN号码。这是通过计算加权和来实现的，即将每一位数字乘以其位置的权重，并求和。在这个问题中，权重从1到9递增。
2.将上一步得到的加权和取模11，以便得到校验位的期望值。检查期望的校验位与输入的校验位是否匹配。如果匹配，则打印"Right"。
3.如果不匹配，则根据期望的校验位修正最后一位，并打印出修正后的ISBN号。
#include <iostream>
using namespace std;
int main() {
char a[10];
scanf("%c-%c%c%c-%c%c%c%c%c-%c", &a[0], &a[1], &a[2], &a[3], &a[4], &a[5], &a[6], &a[7], &a[8], &a[9]);
int res = 0;
for (int i = 0; i < 9; ++i) {
res += (a[i] - '0') * (i + 1);
}
res %= 11;
if ((res == 10 && a[9] == 'X') || res == a[9] - '0') {
cout << "Right";
} else {
a[9] = res == 10 ? 'X' : res + '0';
printf("%c-%c%c%c-%c%c%c%c%c-%c\n",a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
}
return 0;
}
43992 图像模糊 OJ编程题
【考点】通过某种方式计算每个像素点周围像素的平均值，并将结果作为该像素点的新值。
【解题思路】
1.主要的处理逻辑在 func 函数中完成，该函数接收图像二维向量 Pic、以及要模糊处理的像素坐标 (x, y)。在函数中，遍历以 (x, y) 为中心的3x3的像素区域，计算该区域内所有像素的总和以及像素个数，并返回平均值作为模糊后的像素值。
2.最后，在 main 函数中，对图像的每个像素都调用 func 函数进行模糊处理，并将处理后的像素值输出。
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int func(vector<vector<int>>& Pic, int x, int y) {
int count = 0, total = 0;
for(int i = x - 1; i <= x + 1; i++) {
for(int j = y - 1; j <= y + 1; j++) {
if(0 <= i && i < n && 0 <= j && j < m) {
count++;
total += Pic[i][j];
}
}
}
return total / count;
}
int main() {
cin >> n >> m;
vector<vector<int>> Pic(n, vector<int>(m));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> Pic[i][j];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cout << func(Pic, i, j) << " ";
}
cout << endl;
}
return 0;
}
44177 合并果子 OJ编程题
【考点】这道编程题的考点主要是贪心算法和排序。
【解题思路】
1.输入： 首先，从输入中获取果子的数量n，然后读取n个整数，表示每个果子的大小，并将它们存储在一个vector中。
2.排序： 使用sort函数对果子的大小进行降序排序，这是为了确保每次合并都是选择两个最大的果子。
3.合并过程： 使用一个循环，只要果子的数量大于1，就执行以下步骤：取出最后两个果子（最大的两个）。将这两个果子的大小相加，得到合并后的果子大小。将合并后的果子大小插入到合适的位置，以保持降序排序。记录每次合并的代价，即两个果子的大小之和。
4.输出结果： 最后输出代价的累积值。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(int x, int y) {
return x > y;
}
int main() {
vector<int> apple;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
apple.push_back(x);
}
sort(apple.begin(), apple.end(), compare);
int res = 0;
while (apple.size() > 1) {
int a = apple.back();
apple.pop_back();
int b = apple.back();
apple.pop_back();
res += a + b;
int i = 0;
for( ; i < apple.size(); i++) {
if(apple[i] < a + b) break;
}
apple.insert(apple.begin() + i, a + b);
}
cout << res;
return 0;
}
44214 三连击 OJ编程题
【考点】这道题的考点主要是组合数学、字符串处理、排列组合和算法复杂度。
【解题思路】
1.字符串处理：首先，要将字符串中的数字提取出来。这是通过figure()函数实现的，它将一个表示数字的字符串转换为整数。
2.排列组合：题目要求找出满足一定条件的三个3位数的三连击，即满足条件的三个数字可以任意排列组合形成三个3位数。这里使用了next_permutation函数来生成所有数字的排列组合。
3.条件判断：在每次排列组合之后，通过判断每个数字的子串是否满足条件来筛选出符合要求的三连击。
4.算法复杂度：该算法使用了全排列，时间复杂度为O(n!)，其中n为字符串的长度。因此，该算法在大规模数据上可能会有较大的性能开销。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int figure(string s) {
int count = 0;
for(int i = 0; i < s.length(); i++) {
count *= 10;
count += s[i] - '0';
}
return count;
}
int main() {
vector<string> res;
string s = "123456789";
do{
int a = figure(s.substr(0, 3));
int b = figure(s.substr(3, 3));
int c = figure(s.substr(6, 3));
if(b % a == 0 && b / a == 2 && c % a == 0 && c / a == 3)
res.push_back(s);
} while(next_permutation(s.begin(), s.end()));
sort(res.begin(), res.end());
for(string o : res)
cout << o.substr(0, 3) << " " << o.substr(3, 3) << " " << o.substr(6, 3) << endl;
return 0;
}
43760 取球游戏 OJ编程题
【考点】这道题是关于取球游戏的问题，涉及递归和逻辑判断。
【解题思路】
1.确定递归的终止条件：当没有球可取时，游戏结束。
2.确定每一方取球的规则：根据题目规定，A和B两方轮流取球，A先手。A和B都会按照取球的规则来取球，这些规则包括取1个球、取3个球、取7个球或取8个球。
3.编写递归函数：根据规则，判断当前轮到的一方是否能取得胜利。递归调用时，传入当前球的数量和轮到的一方，然后根据规则判断对手是否能取得胜利。在主函数中，依次输入每一局游戏的球的数量，调用递归函数判断胜负，并输出结果。
#include <iostream>
using namespace std;
bool func(int n, int flag) {
if (flag == 1) { // 本方为A
if (n == 2 || n == 4 || n == 8 || n == 9)
return true;
else
return ((n > 1 && func(n - 1, -flag)) || (n > 3 && func(n - 3, -flag))
|| (n > 7 && func(n - 7, -flag)) || (n > 8 && func(n - 8, -flag)));
} else { // 本方为B
return ((n == 1 || func(n - 1, -flag)) && (n <= 3 || func(n - 3, -flag))
&& (n <= 7 || func(n - 7, -flag)) && (n <= 8 || func(n - 8, -flag)));
}
}
int main() {
int n;
cin >> n;
bool res[n];
for (int i = 0; i < n; i++) {
int x;
cin >> x;
res[i] = func(x, 1);
}
for (int o : res)
cout << o << endl;
return 0;
}
43966 排座椅 OJ编程题
【考点】这道编程题的考点主要涉及输入输出、数组和向量的使用、排序算法以及基本的条件判断。
【解题思路】
1.首先，读取输入的五个整数 M、N、K、L、D，分别表示座位区域的行数、列数、横向安排座位的数量、纵向安排座位的数量以及座位总数。
2.接下来，使用两个向量 row 和 col 分别记录行和列的信息。使用一个循环读取每个座位的信息，包括起始位置 (x, y) 和结束位置 (x2, y2)。
3.判断座位是水平排列还是垂直排列，如果横坐标相同，则将纵坐标加入 col 向量；如果纵坐标相同，则将横坐标加入 row 向量。
4.对 row 和 col 向量进行排序，以便按顺序输出。最后，输出排序后的 row 和 col 向量。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int M, N, K, L, D;
cin >> M >> N >> K >> L >> D;
vector<int> row, col;
for(int i = 0; i < D; i++) {
int x, y, x2, y2, j = 0;
cin >> x >> y >> x2 >> y2;
if(x == x2) {
for( ; j < col.size(); j++) {
if(col[j] == min(y, y2)) break;
}
if(j == col.size())
col.push_back(min(y, y2));
} else {
for( ; j < row.size(); j++) {
if(row[j] == min(x, x2)) break;
}
if(j == row.size())
row.push_back(min(x, x2));
}
}
sort(row.begin(), row.end());
for(int r : row) {
cout << r << " ";
}
cout << endl;
sort(col.begin(), col.end());
for(int c : col) {
cout << c << " ";
}
cout << endl;
return 0;
}
44725 数位排序 OJ编程题
【考点】这道编程题的考点主要涉及函数的定义、排序算法和数字处理。
【解题思路】
1.首先，定义了一个名为 compare 的函数，用于比较两个整数。该函数的作用是将两个整数按照它们的数位之和进行比较，如果数位之和相等，则比较它们的大小；如果数位之和不相等，则比较数位之和的大小。
2.在 main 函数中，首先读取输入的两个整数 n 和 k，分别表示数字范围和要求的第 k 小的数。
3.创建一个名为 arr 的向量，用于存储从 1 到 n 的所有数字。使用 sort 函数对 arr 向量进行排序，排序的依据是 compare 函数。最后，输出排序后的第 k 个数。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(int x, int y) {
int a = 0, b = 0, X = x, Y = y;
while(x){
a += x % 10;
x = (x - x % 10) / 10;
}
while(y){
b += y % 10;
y = (y - y % 10) / 10;
}
return a == b ? X < Y : a < b;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> arr;
for(int i = 1; i <= n; i++)
arr.push_back(i);
sort(arr.begin(), arr.end(), compare);
cout << arr[k - 1];
return 0;
}
Part_2 题目
OpenJ_Bailian-2942 吃糖果 1753 医学部计算概论2006期末考试题
【考点】递归和动态规划。
【解题思路】
递归函数 func 中，我们从当前糖果数量开始，每次可以选择吃一个或两个糖果，然后递归调用函数。当糖果数量达到或超过目标数量时，检查是否正好等于目标数量，如果是，则计数器加一。
#include <iostream>
using namespace std;
int count = 0, N;
void func(int current) {
if(current >= N){
if(current == N) count++;
return;
}
func(current + 1);
func(current + 2);
}
int main() {
cin >> N;
func(0);
cout << count;
return 0;
}
OpenJ_Bailian-3143 验证“歌德巴赫猜想” 1892 计算概论2007, XieDi
【考点】素数判定和质数分解。
【解题思路】
1.首先，定义一个函数 func 用来判断一个数是否为素数。这个函数的逻辑是从2开始，逐个检查到该数的一半（因为大于一半的数不可能整除），如果存在能整除的数，则返回 false，否则返回 true。
2.在 main 函数中，首先读入一个偶数 z。然后判断 z 是否小于6或者是否为偶数，如果是，则输出错误信息。
3.接着使用一个循环从2开始遍历到 z 的一半，寻找符合条件的两个素数。
4.在循环中，对于每一个数 x，检查 x 和 z-x 是否都是素数，如果是，则输出结果，表示 z 可以表示为 x 和 z-x 两个素数的和。
#include <iostream>
using namespace std;
bool func(int x) {
int i = 2;
for( ; i <= x / 2; i++) {
if(x % i == 0)
return false;
}
return true;
}
int main() {
int z;
cin >> z;
if(z < 6 || z % 2 != 0)
cout << "Error!\n";
for(int x = 2; x <= z / 2; x++) {
if(func(x) && func(z - x))
cout << z << "=" << x << "+" << z - x << endl;
}
return 0;
}
OpenJ_Bailian-2936 试剂配制 1384 医学部计算概论2006期末考试题
【考点】考察了对数组元素的查找和条件判断的能力。
【解题思路】
1.函数 func 中通过多个条件判断来确定数组中是否包含特定的数字。
2.首先，判断数组中是否同时包含数字1和2，如果不是，则返回false。然后，判断数组中是否同时包含数字3和4，如果不是，则返回false。
3.接着，判断数组中是否包含数字5但不包含数字6，如果不是，则返回false。再次，判断数组中是否包含数字6但不包含数字5，如果不是，则返回false。
4.最后，判断数组中是否同时不包含数字7和8，如果不是，则返回false。如果以上条件都满足，则返回true。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool func(vector<int>& arr) {
if(!(find(arr.begin(), arr.end(), 1) != arr.end()
&& find(arr.begin(), arr.end(), 2) != arr.end()))
return false;
if(!(find(arr.begin(), arr.end(), 3) != arr.end()
&& find(arr.begin(), arr.end(), 4) != arr.end()))
return false;
if( find(arr.begin(), arr.end(), 5) != arr.end()
&& find(arr.begin(), arr.end(), 6) == arr.end())
return false;
if( find(arr.begin(), arr.end(), 6) != arr.end()
&& find(arr.begin(), arr.end(), 5) == arr.end())
return false;
if(!(find(arr.begin(), arr.end(), 7) == arr.end()
&& find(arr.begin(), arr.end(), 8) == arr.end()))
return false;
return true;
}
int main() {
int n;
cin >> n;
vector<int> arr(n);
for(int i = 0; i < n; i++)
cin >> arr[i];
cout << (func(arr) ? "1" : "0");
return 0;
}
OpenJ_Bailian-3142 球弹跳高度的计算 1397 计算概论2007, XieDi
【考点】理解和应用数学中的等比数列以及循环结构。
【解题思路】
1.理解问题： 题目中给出的代码是用来计算球弹跳多次后的总高度和最后一次弹跳的高度。球每次弹跳的高度是上一次的一半。
2.循环结构： 通过 for 循环来模拟球弹跳的过程，循环 9 次，表示球弹跳了 9 次。
3.等比数列求和： 根据等比数列的性质，第一次弹跳高度为 h，第二次为 h/2，第三次为 h/4，以此类推。而总高度则是每次弹跳高度的累加，即 h + h/2 + h/4 + ... ，可以利用循环结构来计算。
4.输出结果： 输出总高度和最后一次弹跳的高度。
#include <iostream>
using namespace std;
int main() {
double h;
cin >> h;
double ANSWER = h;
for(int i = 0; i < 9; i++) {
h /= 2;
ANSWER += h * 2;
}
cout << ANSWER << endl << h / 2;
return 0;
}
OpenJ_Bailian-1835 宇航员 1002 qinlu@POJ
【考点】1.二维数组的使用：lr和ud分别是两个二维数组，用于存储行走路径中左右和上下移动的规则。这种二维数组的设计可以简化代码逻辑，提高可读性和维护性。
2.控制流：代码中使用了条件语句（if-else）和循环语句（while、for），这是模拟行走过程中不同情况的处理，关键在于根据输入执行相应的移动操作。
3.算法思维：通过模拟宇航员的行走路径，并根据指令调整坐标位置，最终输出宇航员的位置信息和当前朝向。
【解题思路】
1.初始化：定义了变量n表示指令数量，d表示移动步数，以及x、y、z分别表示三个坐标轴的位置。
2.行走操作：使用walk函数进行移动操作，根据指定的方向和步数更新坐标值。
3.输入处理：通过循环读取输入指令，根据指令类型调用相应的行走函数并更新朝向和位置信息。
4.输出结果：在每次移动后输出当前位置信息和朝向。
#include <iostream>
using namespace std;
int n, d, x = 0, y = 0, z = 0;
int lr[2][4] = {{0, 4, 3, 1}, {0, 2, 3, 4}};
int ud[2][4] = {{0, 2, 3, 4}, {1, 2, 5, 4}};
void walk(int p, int d) {
if(p == 0) x += d;
else if(p == 1) y += d;
else if(p == 2) z += d;
else if(p == 3) x -= d;
else if(p == 4) y -= d;
else if(p == 5) z -= d;
}
int main() {
int p = 0, choice = 0, choice2 = 0, i = 0;
cin >> n;
while(n--){
string s;
cin >> s >> d;
if(s == "left" || s == "right"){
int k = s == "left" ? 1 : -1;
for(int j = 0; j < 4; j++){
if(lr[choice][j] == p){
p = lr[choice][(j + k) % 4];
break;
}
}
choice2 = (choice2 + 1) % 2;
} else if(s == "up" || s == "down"){
int k = s == "up" ? 1 : -1;
for(int j = 0; j < 4; j++){
if(ud[choice2][j] == p){
p = ud[choice2][(j + k) % 4];
break;
}
}
choice = (choice + 1) % 2;
} else if(s == "back"){
p = (p + 3) % 6;
}
walk(p, d);
cout << x << " " << y << " " << z << " p = " << p << endl;
}
return 0;
}
OpenJ_Bailian-2946 玩游戏 947 医学部计算概论2006期末考试题
【考点】函数的定义和调用；字符串的比较（使用 == 操作符）；控制流（if-else 条件语句）；循环（for 循环）
【解题思路】
1.程序首先接受两个输入：k 和 N。其中，k 是一个整数，N 是要执行的操作数量。
2.接下来进入一个循环，循环 N 次。每次循环会接收两个输入：op 和 a。op 是一个字符串，表示要执行的操作（"multiply"、"minus" 或 "plus"），a 是一个整数，是要对 k 进行操作的值。
3.在循环中，通过调用 calculate 函数来执行对 k 的操作，并将结果赋值给 k。最后输出最终的 k 的值。
#include <iostream>
using namespace std;
int calculate(string op, int k, int a) {
if(op == "multiply")
return k * a;
else if(op == "minus")
return k - a;
else if(op == "plus")
return k + a;
}
int main() {
int k, N;
cin >> k >> N;
for(int i = 0; i < N; i++) {
string op;
int a;
cin >> op >> a;
k = calculate(op, k, a);
}
cout << k;
return 0;
}
OpenJ_Bailian-2803 碎纸机 713 翻译自Japan 2002 Kanazawa的试题
【考点】涉及了递归、字符串处理、动态规划（类似）、输入输出处理等多个知识点。
【解题思路】
1.递归：代码中使用递归来遍历所有可能的分割方式，并计算各种情况下的和。
2.字符串处理：使用substr函数来进行字符串的分割。
3.动态规划：虽然这段代码没有显式地使用动态规划，但是其递归的性质与动态规划类似，都是通过保存中间状态来避免重复计算。
4.输入输出处理：程序需要正确地读入输入并输出结果，同时处理特殊情况如target为0且S为"0"的情况。
#include <iostream>
#include <vector>
using namespace std;
string S, Res;
int target, Sum, flag, flag2;
void Func(string res, int sum, int index) {
if (index == S.length()) { // 分割结束
if (sum > 0 && sum <= target) {
flag = 0;
if (sum > Sum) {
Sum = sum;
Res = res;
}
}
return;
}
for (int i = index; i < S.length(); i++) {
string s = S.substr(index, i - index + 1); // 分割
Func(res + (res.empty() ? "" : " ") + s, sum + stoi(s), i + 1);
}
}
void Count(int sum, int index) {
if (index == S.length()) {
flag2 += sum == Sum ? 1 : 0;
return;
}
for (int i = index; i < S.length(); i++) {
string s = S.substr(index, i - index + 1);
Count(sum + stoi(s), i + 1);
}
}
int main() {
vector<string> result;
while (cin >> target >> S) {
if (target == 0 && S == "0")
break;
if (to_string(target) == S) { // 规则一
result.push_back(S + " " + S);
continue;
}
flag = 1; flag2 = 0; Sum = 0;
Func("", 0, 0);
Count(0, 0);
result.push_back(flag ? "error" : flag2 > 1 ? // 规则二
"rejected" : to_string(Sum) + " " + Res); // 规则三
}
for (string o : result)
cout << o << endl;
return 0;
}
OpenJ_Bailian-3256 矩阵的乘法 598 cs10107 C++ Final Exam
【考点】矩阵乘法的基本原理是将第一个矩阵的每一行与第二个矩阵的每一列对应元素相乘，然后将乘积相加得到结果矩阵的每个元素。
【解题思路】
1.读取两个矩阵的维度（行数和列数）。
2.创建两个二维向量 A 和 B，分别表示两个矩阵，并读取它们的元素值。进行矩阵乘法计算：遍历结果矩阵的每一行和每一列。
3.对于结果矩阵的每个元素，遍历第一个矩阵的当前行和第二个矩阵的当前列，将对应元素相乘并累加。
4.将累加的结果输出到结果矩阵的相应位置。输出结果矩阵。
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
int main() {
int x, y, z;
cin >> x >> y;
vector<vector<int>> A(x, vector<int>(y));
for(int i = 0; i < x; i++) {
for(int j = 0; j < y; j++)
cin >> A[i][j];
}
cin >> y >> z;
vector<vector<int>> B(y, vector<int>(z));
for(int i = 0; i < y; i++) {
for(int j = 0; j < z; j++)
cin >> B[i][j];
}
for(int i = 0; i < x; i++) {
for(int j = 0; j < z; j++) {
int c = 0;
for(int k = 0; k < y; k++) {
c += A[i][k] * B[k][j];
}
cout << setw(5) << c;
}
cout << endl;
}
return 0;
}
OpenJ_Bailian-4141 砝码称重 1947 NOIP1996复赛 提高组 第四题
【考点】考点是动态规划和位运算。
【解题思路】
1.从输入中读取每种砝码的数量，将其转换为一个字符串，其中每个字符表示对应的砝码的数量。
2.使用位运算枚举所有可能的组合，通过对每个组合求和来确定其总重量。
3.将每个总重量记录在一个布尔数组 map 中，以便统计不同总重量的数量。
4.最后，统计 map 中为 true 的项的数量，即为不同总重量的数量，并输出结果。
#include <iostream>
#include <vector>
using namespace std;
vector<bool> map(1001, false);
int g[6] = {1, 2, 3, 5, 10, 20};
int main() {
string str;
for(int i = 0; i < 6; i++) {
int n;
cin >> n;
for(int j = 0; j < n; j++) {
str.push_back(i + '0');
}
}
int n = str.length();
for (int i = 0; i < (1 << n); i++) { // 枚举所有情况
string s;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
s.push_back(str[j]);
}
}
if(!s.empty()) {
int x = 0;
for(char c : s) {
x += g[c - '0'];
}
map[x] = true; // 统计不同总重
}
}
int Total = 0;
for(int i = 0; i < 1001; i++) {
if(map[i]) Total++;
}
cout << "Total=" << Total;
return 0;
}
OpenJ_Bailian-3260 赛手查询 407 CDragon
【考点】考点主要是关于排序算法和二维向量的操作。
【解题思路】
1.首先，程序从输入中读取赛手的数量n，并创建一个大小为n的二维向量people，其中每个元素包含赛手的成绩和编号。
2.接下来，通过自定义的比较函数compare，根据赛手的成绩对二维向量进行排序，排序后的序号保存在每个赛手的第二列中。
3.然后，对排名进行计算，相同成绩的赛手将具有相同的排名，排名保存在每个赛手的第三列中。
4.用户输入要查询的排名k。遍历排名表，找到排名为k的赛手，将其编号保存在res中。
5.如果找不到排名为k的赛手，则将0加入res中。对res进行排序。将每次查询的结果存储在Res中。最后，将所有查询结果输出。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(vector<int>& x, vector<int>& y) {
return x[1] > y[1];
}
int main() {
vector<vector<int>> Res;
int n, k, top;
while(cin >> n) {
if(n == 0)
break;
vector<vector<int>> people(n, vector<int>(3));
for(int i = 0; i < n; i++) {
cin >> people[i][0]; // 成绩
people[i][1] = i + 1; // 编号
}
sort(people.begin(), people.end(), compare);
people[0][2] = 1;
for(int i = 1; i < n; i++) {
if(people[i][0] != people[i - 1][0]) {
top = i + 1;
people[i][2] = i + 1;
} else {
people[i][2] = top; // 排名
}
}
cin >> k;
vector<int> res;
for(int i = 1; i < n; i++) { // 统计
if(people[i][2] == k) {
res.push_back(people[i][1]);
}
}
if(res.empty()) {
res.push_back(0);
}
sort(res.begin(), res.end()); // 排序
Res.push_back(res);
}
for(int i = 0; i < Res.size(); i++) {
for(int id : Res[i]) {
cout << id << " ";
}
cout << endl;
}
return 0;
}
网友评论