CSP部分模拟题题解

CSP历年模拟题

随便写写，主要是写了删了怪可惜（

2022年CSP-J 逻辑表达式

题目链接

#include <bits/stdc++.h>
using namespace std;/*
非短路：运算结果的值就是表达式中最后一个值 -> 如果没有发生短路，扫描到数字就更新答案短路：// 短路期间只看 运算符 不看 数字1. 0与短路，可以一直短路到后面的所有与&运算，直到遇到或|运算符 或着 遇到本层的右括号例如：0 & 1 & 1 | 1 = 1       (0 & 1 & 1 & 0) | 1 = 12. 1或运算，可以短路到本层的右括号，因为与运算优先进行，也就是说进行或运算的时候后面的所有与运算都进行完了例如：(1 | 0 | 1 & 0) | 1 = 1如果包含子级括号的话不需要进行计算，直接跳过
*/int main()
{string s;cin >> s;// ans 记录的答案，op 是否短路以及哪种短路 0无短路，1 0&; 2 1|// s1 记录0&短路数量，s2int n = s.size(), ans = 0, op = 0, s1 = 0, s2 = 0;for (int i = 0; i < n; i ++){if (op == 0) // 没有短路{if (s[i] == '0') ans = 0; // 没有短路，最后一个值就是答案if (s[i] == '1') ans = 1; // 没有短路，最后一个值就是答案if (s[i] == '&' && ans == 0) s1 ++, op = 1; // 发生0与短路if (s[i] == '|' && ans == 1) s2 ++, op = 2; // 发生1或短路}else {if (op == 1 && s[i] == '&') s1 ++; // 0与短路 后面遇到 与运算 就继续短路else if (op == 2 && s[i] == '|') s2 ++; // 1或短路 后面遇到 或运算 继续短路else if (op == 1 && s[i] == '|') op = 0; // 0与短路 遇到 或运算 停止短路else if (s[i] == ')') op = 0; // 遇到右括号 停止短路else if (s[i] == '(') // 短路期间遇到左括号，直接跳过整个括号范围的所有计算{int cnt = 1; // 记录没有配对的左括号个数while (cnt) // 如果还存在没有配对的左括号{i ++; // 扫描下一个符号if (s[i] == ')') cnt --; // 如果是右括号，配对一个左括号else if (s[i] == '(') cnt ++; // 如果还遇到左括号，数量增加}}}}cout << ans << '\n' << s1 << ' ' << s2 << '\n';return 0;
}

2023CSP-J 一元二次方程

题目链接

#include <bits/stdc++.h>
using namespace std;int main()
{int t = 0, m = 0, a = 0, b = 0, c = 0, d = 0, x1 = 0, x2 = 0, ans = 0;cin >> t >> m;for (int i = 0; i < t; i ++){cin >> a >> b >> c; // ax^2 + bx + c = 0 d = b * b - 4 * a * c; // 判别式 Δ = b^2 - 4acif (d < 0){cout << "NO" << '\n'; // 小于0无解}else if (d == 0) // 等于0只有一个解(-b / 2a){if (b == 0) cout << 0 << '\n'; // 分子为0else {if (a * b > 0) cout << "-"; // 如果分子分母异号，则为负数b = abs(b); // 都取绝对值a = abs(2 * a); // 都取绝对值int x = __gcd(a, b); // 约分b /= x; a /= x;if (a == 1) cout << b << '\n'; // 分子为1else cout << b << '/' << a << '\n'; // 输出分数}}else // 有两个解{int k = 1; // 设根号前的系数为1for (int i = 2; i * i <= d; i ++) // 判断是否可以进行化简{while (d % (i * i) == 0) // 表示可以开出根号{d /= i * i; k *= i; }}if (d == 1) // 如果化简到根号下为1，则没有根号了，只剩系数{if (a < 0) b = -b - k; // 分母小于0的话，较大者是 -b - kelse b = -b + k; // 反之为 -b + ka = 2 * a; if (a * b < 0) cout << '-'; // 如果分母异号的话，输出负号if (b == 0) cout << 0 << '\n'; // 分母为0的话输出0else {a = abs(a); // 取绝对值b = abs(b); // 取绝对值int x = __gcd(a, b); // 约分a /= x;b /= x;if (a == 1) cout << b << '\n'; // 分母为1只输出分子else cout << b << '/' << a << '\n'; // 输出分式}}else // 如果根号下不为1，则需要输出sqrt{if (a * b > 0) cout << '-'; // 判断分母分子是否异号if (b) // 如果有理数部分存在{b = abs(b); // 输出有理数部分int a1 = abs(2 * a);int x1 = __gcd(b, a1);b /= x1;a1 /= x1;if (a1 == 1) cout << b;else cout << b << '/' << a1;cout << '+';}int a2 = abs(2 * a);int x2 = __gcd(k, a2); // 分母和根号前的系数约分k /= x2;a2 /= x2;if (k != 1) cout << k << '*'; // 如果系数不为1，则要输出cout << "sqrt(" << d << ")"; // 输出根号if (a2 != 1) cout << '/' << a2; // 如果分母不为1，输出分母cout << '\n'; // 最后输出换行}}}return 0;
}

2006年NOIP-S 作业调度方案

题目链接

#include <bits/stdc++.h>
using namespace std;struct node
{int id; // 在第 id 号机器上加工int cost; // 需要花费 cost 个时间
} a[21][21]; //  第 i 个工件 的 第 j 道工序 需要在机器id上运行cost时间片
int order[501]; // 记录加工顺序
int step[21]; // 第i个工件执行完了第step[i]个工序：初始值都为0
int mac[21][10001]; // 记录第 i 台机器的第 j 个时间片是否空闲
int last_time[21]; // 记录每个工件上一步是在第几个时间片完成的
int ans = 0; // 答案int main()
{int m, n;cin >> m >> n; for (int i = 1; i <= m * n; i ++) // 输入加工顺序cin >> order[i];for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++)cin >> a[i][j].id; // 输入第i个工件的第j道工序在哪台机器上运行for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++)cin >> a[i][j].cost; // 输入第i个工件的第j道工序需要花费多少时间片for (int i = 1; i <= m * n; i ++) // 枚举加工顺序{int now = order[i]; // now 表示现在应该加工哪个工件step[now] ++; // 更新step[now]为现在加工的工序int id = a[now][step[now]].id; // 获取这道工序需要在哪个机器上进行int cost = a[now][step[now]].cost; // 获取这道工序需要花费多少个时间片int j = last_time[now] + 1; // j表示当前工件的上一道工序结束时间的下一个时间片int s = 0; // s表示合适的时间片，累计的时间长度while (1){if (mac[id][j] == 0) s ++; // 如果机器在j时刻空闲else s = 0; // 否则不能插入if (s == cost) // 如果找到足够长的一段时间{for (int k = j - cost + 1; k <= j; k ++) // 从后往前依次占用时间片mac[id][k] = 1;if (j > ans) ans = j; // 如果超过记录的总时间就更新last_time[now] = j; // 更新当前工件的最后一道工序的完成时间break; // 跳出死循环}j ++; // 继续寻找下一个时间片}}cout << ans << '\n'; // 输出答案return 0;
}

2021年CSP-J 网络连接

题目链接

#include<bits/stdc++.h>
using namespace std;bool check(string s)
{int a, b, c, d, port;if (sscanf(s.c_str(), "%d.%d.%d.%d:%d", &a, &b, &c, &d, &port) != 5)  return false;if (a < 0 || a > 255 || b < 0 || b > 255 || c < 0 || c > 255 || d < 0 || d > 255 || port < 0 || port > 65535)  return false;stringstream ss;ss << a << '.' << b << '.' << c << '.' << d << ':' << port; // 可以判断是否有前置0return ss.str() == s;
};int main()
{int n;cin >> n;map<string, int> mp;string op, ad;for (int i = 1; i <= n; i ++){cin >> op >> ad;if (!check(ad)) // 如果不合法{cout << "ERR" << '\n';continue;}if (op[0] == 'S') // 如果是服务器端{if (mp[ad]) cout << "FAIL" << '\n'; // 如果已经存在了，则不行else mp[ad] = i, cout << "OK" << '\n'; // 更新服务器端}else  // 客户端{if (!mp.count(ad)) cout << "FAIL" << '\n'; // 如果不存在服务器else cout << mp[ad] << '\n'; // 输出服务器}}return 0;
}

1999年NOIP-S 回文数

题目链接

#include <bits/stdc++.h>
using namespace std;const int N = 110;
char m[N];
int a[N], b[N], m1[N], n, len;void num()
{for (int i = 0; i < len; i ++){a[i] = m1[i];b[len - i - 1] = m1[i]; // b数组存的是逆序的数字}
}void add()
{int x = 0; // 进位memset(m1, 0, sizeof m1); // 把m1数组初始化为全0for (int i = 0; i < len; i ++){m1[i] = a[i] + b[i] + x;x = m1[i] / n;m1[i] %= n;}if (x != 0){m1[len] = x;len ++;}
}bool judge()
{int i = 0, j = len - 1;while (i <= j){if (m1[i] != m1[j]) return false;i ++, j --;}return true;
}int main()
{cin >> n >> m;len = strlen(m);for (int i = 0; i < len; i ++){if (m[i] <= '9') m1[len - i - 1] = m[i] - 48;else m1[len - i - 1] = m[i] - 55;}for (int i = 1; i <= 30; i ++){num(); // 准备相加数组add(); // 高精度加法if (judge()) // 判断结果是否回文{cout << "STEP=" << i << '\n';return 0;}}cout << "Impossible!" << '\n';return 0;
}