算法刷题记录(Day 13)

小中大（csp 201903-1）

原题链接

#include
#include
using namespace std;
#define NMAX 100005
int n;
int num[NMAX];
int mx, mn;
float mid;
int main() {cin >> n;for (int i = 1; i <= n; i++) cin >> num[i];mx = max(num[1], num[n]);mn = min(num[1], num[n]);if (n % 2 == 1) mid = num[(n + 1) / 2];else mid = ((float)(num[n / 2] + num[n / 2 + 1])) / 2;if (mid - ((int)mid) == 0) printf("%d %d %d", mx, (int)mid, mn);else printf("%d %.1f %d",mx, mid, mn);return 0;
}

debug过程:
1.运行时错误卡了好久，结果发现是数组开小了。
2.不能忘记return 0。

二十四点(csp 201903-2)

原题链接
定义优先级后求解即可

#include
#include
using namespace std;
int n;
char c;
stack<int > num;
stack<int > op;
int p[6][6] = {0,0,0,0,0,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0,0,0,0,0};
void ca(int op2) {int op1 = op.top();while (p[op1][op2]) {int num1 = num.top();num.pop();int num2 = num.top();num.pop();int num3;if (op1 == 1) num3 = num1 + num2;else if (op1 == 2) num3 = num2 - num1;else if (op1 == 3) num3 = num2 * num1;else num3 = num2 / num1;num.push(num3);op.pop();op1 = op.top();}op.push(op2);return;
}
int main() {cin >> n;getchar();//注意读取换行符while (n--) {while (!num.empty()) num.pop();while (!op.empty()) op.pop();int cur;op.push(0);while ((c = getchar()) != '\n') {if (c >= '0' && c <= '9') num.push(c - '0');else {//注意这里一定要有一个else,只有在有运算符的情况下才会运算if (c == '+') cur = 1;else if (c == '-') cur = 2;else if (c == 'x') cur = 3; //乘法用小写字母x来表示else cur = 4;ca(cur);}}ca(5);int res = num.top();num.pop();if (res == 24) cout << "Yes" << endl;else cout << "No" << endl;}
}

损坏的RAID5(csp 201903-3)

原题链接
解题思路:R[i][j]存储第i块磁盘的第j块的内容，当拿到一个块号时，首先需要将该块号定位到位于那一块磁盘的第几块的位置。若存在该盘，则直接输出；否则若能够计算出来，则直接进行计算即可。

在提交过程中，总是会出现超时的情况，得分为40分，初始代码如下所示。

#include
#include
using namespace std;
#define NMAX 10010
vector<string> R[NMAX];
vector<int > id;
int n, s, l, m;
int tot_strip;
int disk_strip;
string res;//代表最后的返回结果
long long zhuanbian(string x) {//将x转化为整数long long ret = 0;for (int i = 0; i < 8; i++) {char c = x[i];if (c >= '0' && c <= '9') ret = ret * 16 + c - '0';else  ret = ret * 16 + c - 'A' + 10;}return ret;
}string zhuanbian2(long long x) {//将x转变为string类型char ret[9];for (int i = 7; i >= 0; i--) {int cur = x % 16;if (cur < 10) ret[i] = cur + '0';else ret[i] = cur - 10 + 'A';x /= 16;}ret[8] = 0;string res = ret;return res;
}
int find(int x, int y) {if (R[x].size()) {res = R[x][y];return 1;}else {//最多只能缺一块if (l < n - 1) return 0;else {//把所有的都进行按位异或long long ret=0;for (int i = 0; i < id.size(); i++) {ret ^= zhuanbian(R[id[i]][y]);}//将ret转化为stringres = zhuanbian2(ret);return 1;}}
}int main() {cin >> n >> s >> l;for (int i = 0; i < l; i++) {int num;cin >> num;id.push_back(num);char c = getchar();while ((c = getchar()) != '\n') {string s;s += c;for (int i = 0; i < 7; i++) {c = getchar();s += c;}R[num].push_back(s);}disk_strip = R[num].size() / s;//for (int i = 0; i < R[num].size(); i++) cout << R[num][i] << endl;//cout << "----------------" << endl;}cin >> m;tot_strip = (n - 1) * disk_strip - 1;//最大的条带的编号for (int i = 0; i < m; i++) {int block_num;cin >> block_num;//block_num++;//判断是否超出范围int strip_num = (block_num) / s;//strip_num++;if (strip_num > tot_strip) {cout << "-" << endl;}else {int x1 = strip_num % (n * n - n);int x2 = strip_num / (n * n - n);int x3 = x1 / (n - 1);int j = (x3 + x2 * n) * s + (block_num) % s ; //这里应该乘上的是s，代表的是阵列的条带大小int check = n - 1 - x3;check=(check+1)%n;//代表的是第一个盘的编号int i = (check + strip_num - (x3 * (n - 1)+x2*n*(n-1)))%n;//该块在第i块的第j个块上if (!find(i, j)) cout << "-" << endl;else cout << res << endl;}}return 0;
}

改进1：
1.fgets直接读入一行，然后在进行一个分拣的工作。此时能有70分。需要注意的是fgets会读入回车，因此strlen fgets所读入的字符串的时候，其长度是包括回车在内的。

总结

对于即将到来的CSP认证，需要静下心来，不求超过上次的分数，但求问心无愧。模拟题手有点生了，需要多加练习。在做题目之前，一定要首先看清楚题目所给的数据的范围，切不可盲目地做题，这样会变得浮躁而漏洞百出。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！