牛客刷题-Day18
今日刷题：\(1001-1010\)
1001 模拟 · 例1-字符串展开
解题思路
模拟，注意细节就可以。
C++ 代码
#include <bits/stdc++.h>
#include <sstream>
using namespace std;
const int N = 20, M = 110;
typedef long long LL;int p1, p2, p3;
string str;int toLower(char c) {if (c >= 'A' && c <= 'Z')return c - 'A' + 'a';return c;
}int toUpper(char c) {if (c >= 'a' && c <= 'z')return c - 'a' + 'A';return c;
}bool isDigit(char c) {return c >= '0' && c <= '9';
}bool isUpper(char c) {return c >= 'A' && c <= 'Z';
}bool isLower(char c) {return c >= 'a' && c <= 'z';
}int main() {cin >> p1 >> p2 >> p3 >> str;int i = 0;while (i < str.size()) {if (str[i] != '-') { // 字母直接输出cout << str[i++];} else {if (str[i + 1] - str[i - 1] == 1) { // 后继忽略 -i++;continue;}if (!(isUpper(str[i - 1]) && isUpper(str[i + 1]) || isLower(str[i - 1]) && isLower(str[i + 1]) || isDigit(str[i - 1]) && isDigit(str[i + 1]))) { // 两侧不同cout << str[i++];continue;}if (str[i - 1] - str[i + 1] >= 0) { // 非递增直接输出cout << str[i++];continue;}if (str[i + 1] - str[i - 1] > 0) { // 递增if (isDigit(str[i - 1])) { // 数字if (p1 != 3) { // 填充数字if (p3 == 1) {for (char c = str[i - 1] + 1; c < str[i + 1]; c++)for (int i = 0; i < p2; i++)cout << c;} else {for (char c = str[i + 1] - 1; c > str[i - 1]; c--)for (int i = 0; i < p2; i++)cout << c;}} else { // 填充 *for (char c = str[i - 1] + 1; c < str[i + 1]; c++)for (int i = 0; i < p2; i++)cout << '*';}i++;continue;}if (p1 == 1) { // 填充小写字母if (p3 == 1) {for (char c = toLower(str[i - 1] + 1); c < toLower(str[i + 1]); c++)for (int i = 0; i < p2; i++)cout << c;} else {for (char c = toLower(str[i + 1] - 1); c > toLower(str[i - 1]); c--)for (int i = 0; i < p2; i++)cout << c;}} else if (p1 == 2) { // 填充大写字母if (p3 == 1) {for (char c = toUpper(str[i - 1] + 1); c < toUpper(str[i + 1]); c++)for (int i = 0; i < p2; i++)cout << c;} else {for (char c = toUpper(str[i + 1] - 1); c > toUpper(str[i - 1]); c--)for (int i = 0; i < p2; i++)cout << c;}} else { // 填充 *for (char c = str[i - 1] + 1; c < str[i + 1]; c++)for (int i = 0; i < p2; i++)cout << '*';}i++;}}}return 0;
}
1002 模拟 · 例2-多项式输出
解题思路
模拟，要考虑各种特殊情况。
C++ 代码
#include <bits/stdc++.h>
#include <sstream>
using namespace std;
typedef long long LL;
const int N = 110, M = 30;int n;
int a[N];
string item[N];int main() {cin >> n;for (int i = 0; i <= n; i++)cin >> a[i];for (int i = 0; i <= n; i++) {if (a[i] == 0) {item[i] = "";} else {if (n - i == 0) {item[i] = "" + to_string(a[i]);} else if (n - i == 1) {if (abs(a[i]) != 1) {item[i] = "" + to_string(a[i]) + "x";} else {if (a[i] == -1) {item[i] = "-x";} else {item[i] = "x";}}} else {if (abs(a[i]) != 1) {item[i] = "" + to_string(a[i]) + "x^" + to_string(n - i);} else {if (a[i] == -1) {item[i] = "-x^" + to_string(n - i);} else {item[i] = "x^" + to_string(n - i);}}}}}string res = "";for (int i = 0; i <= n; i++) {if (res.size() == 0) {res = res + item[i];} else {if (item[i].size() > 0 && item[i][0] != '-') {res = res + "+" + item[i];} else {res = res + item[i];}}}if (res.size() == 0)res = "0";cout << res << endl;return 0;
}
1005 枚举 · 例2-最大正方形
解题思路
枚举，枚举相邻的两个点，然后根据边长度相等和平行垂直的性质，计算余下两个点。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110;int n;
char g[N][N];
int x[4], y[4];int main() {scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%s", g[i] + 1);int len = 0;for (int x1 = 1; x1 <= n; x1++)for (int y1 = 1; y1 <= n; y1++)if (g[x1][y1] == '#')for (int x2 = 1; x2 <= n; x2++)for (int y2 = 1; y2 <= n; y2++)if (g[x2][y2] == '#') {int x3 = (x1 + x2 + y2 - y1) / 2, y3 = (y1 + y2 + x1 - x2) / 2;int x4 = (x1 + x2 + y1 - y2) / 2, y4 = (y1 + y2 + x2 - x1) / 2;if (x3 >= 1 && x3 <= n && y3 >= 1 && y3 <= n && x4 >= 1 && x4 <= n && y4 >= 1 && y4 <= n) {if (g[x3][y3] == '#' && g[x4][y4] == '#') {int t = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);if (t > len) {len = t;x[0] = x1, x[1] = x2, x[2] = x3, x[3] = x4;y[0] = y1, y[1] = y2, y[2] = y3, y[3] = y4;}}}}for (int i = 0; i < 4; i++)printf("%d %d\n", x[i], y[i]);return 0;
}
1010 枚举 · 例8扩展-校门外的树：hard
解题思路
区间合并。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;int n, len;
vector<PII> a, c; void merge(vector<PII> a, vector<PII> &c) {int st = -1, ed = -1;for (int i = 0; i < a.size(); i++) {if (ed < a[i].first) {if (st != -1)c.push_back(make_pair(st, ed));st = a[i].first, ed = a[i].second;} else {ed = max(ed, a[i].second);}}if (st != -1)c.push_back(make_pair(st, ed));
}int main() {scanf("%d%d", &len, &n);for (int i = 1; i <= n; i++) {int l, r;scanf("%d%d", &l, &r);a.push_back(make_pair(l, r));}sort(a.begin(), a.end());merge(a, c);int cnt = 0;for (int i = 0; i < c.size(); i++) {// printf("%d %d\n", c[i].first, c[i].second);cnt += (c[i].second - c[i].first + 1);}printf("%d\n", len + 1 - cnt);return 0;
}