本文最后更新于 851 天前,其中的信息可能已经有所发展或是发生改变。
A. Compare T-Shirt Sizes
题目大意:
- 给定不同衬衫大小的尺寸编号如:S,M,L。
- 除 M 之外,X 作为尺寸前缀代表其倍数大小。
- 如:XXL>XL,XXS<XS。
- 给定两个代表衬衫尺寸的字符串,判断衬衫大小。
思想:
- 签到题。
- 判断模拟即可。
代码:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define re register #define fi first #define se second #define endl '\n' typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; const int N = 1e6 + 3; const int INF = 0x3f3f3f3f, mod = 1e9 + 7; const double eps = 1e-6, PI = acos(-1); void solve(){ string s1, s2; cin >> s1 >> s2; if(s1 == s2) cout << "=" << endl; else{ char p1 = s1.back(), p2 = s2.back(); int t1 = s1.size(), t2 = s2.size(); if(p1 == 'S'){ if(p2 == 'S'){ if(t1 > t2) cout << "<" << endl; else cout << ">" << endl; } else cout << "<" << endl; } else if(p1 == 'M'){ if(p2 == 'S') cout << ">" << endl; else cout << "<" << endl; } else{ if(p2 == 'L'){ if(t1 > t2) cout << ">" << endl; else cout << "<" << endl; } else cout << ">" << endl; } } } int main(){ IOS; int _ = 1; cin >> _; while(_ --){ solve(); } return 0; }
B. Funny Permutation
题目大意:
- 给定一个 1∼N 的序列 p。
- 求是否存在一种排列形式,使得:
- 对于 pi 至少存在一个相邻的元素保证他们之差不超过 1。
- 且保证 pi=i。
- 存在输出任意满足条件的序列,不存在输出 −1。
思想:
- 构造。
- 将一个 1∼N 的序列从中间拆分,两两组合。
- 特判 n=1,3 时不存在满足条件的排列。
代码:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define re register #define fi first #define se second #define endl '\n' typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; const int N = 1e6 + 3; const int INF = 0x3f3f3f3f, mod = 1e9 + 7; const double eps = 1e-6, PI = acos(-1); void solve(){ int n; cin >> n; if(n == 1 || n == 3) cout << -1 << endl; else{ int j = n; if(n % 2 == 0){ for(int i = n; i >= n / 2; i --) cout << i << ' '; for(int i = 1; i < n / 2; i ++) cout << i << ' '; } else{ int t = (n - 1) / 2; int p = n; for(int i = 1; i <= t; i ++){ cout << p << ' '; p --; } for(int i = 1; i <= n - p + 1; i ++) cout << i << ' '; } cout << endl; } } int main(){ IOS; int _ = 1; cin >> _; while(_ --){ solve(); } return 0; }
C. Minimize the Thickness
题目大意:
- 给定一个长度为 n 的数组,将其分成连续不重合的若干区间,使得各区间内部元素之和相等。
- 求满足上述条件的切分方案下,最长的一个区间的最小可能值。
思想:
- 前缀和,模拟。
- 从 1 枚举区间长度,设当前区间的和为 t。
- 每次向后枚举找到和 t 相等的区间,并且更新最长的区间。
- 当枚举到和大于 t 的区间剪枝。
- 枚举结束,判断是否切分掉了所有的区间,最后更新答案区间。
代码:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define re register #define fi first #define se second #define endl '\n' typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; const int N = 1e6 + 3; const int INF = 0x3f3f3f3f, mod = 1e9 + 7; const double eps = 1e-6, PI = acos(-1); LL a[N]; void solve(){ int n; cin >> n; for(int i = 1; i <= n; i ++){ cin >> a[i]; a[i] += a[i - 1]; } int res = INF; for(int i = 1; i <= n; i ++){ int t = a[i] - a[0]; int p = i; int k = i + 1; //当前的区间长度 for(int j = i + 1; j <= n; j ++){ if(a[j] - a[k - 1] == t){ p = max(p, j - k + 1); //最大的区间长度 k = j + 1; } else if(a[j] - a[k - 1] > t) break; //剪枝 } if(k != n + 1) p = INF; //若最后内部和相等的区间没有用完,则此次切分不成立 res = min(res, p); } cout << res << endl; } int main(){ IOS; int _ = 1; cin >> _; while(_ --){ solve(); } return 0; }
D. Masha and a Beautiful Tree
题目大意:
- 给定一个满二叉树(即树的叶子节点数目为 2n),叶子节点的权值是 1−n 的排列,每个节点拥有不同的权值。
- 一次操作可以交换一个子树的两个儿子,求最小化交换的操作使得叶子节点上的权值递增。
思想:
- 归并。
- 子儿子交换的过程,类比于归并排序的过程。
代码:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define re register #define fi first #define se second #define endl '\n' typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; const int N = 1e6 + 3; const int INF = 0x3f3f3f3f, mod = 1e9 + 7; const double eps = 1e-6, PI = acos(-1); int n, ans; int q[N], t[N]; bool vis; void merge_sort(int q[], int l, int r){ if(l >= r) return ; int mid = l + r >> 1; merge_sort(q, l, mid), merge_sort(q, mid + 1, r); int k = 0, i = l, j = mid + 1; bool flag1 = 1, flag2 = 1; while(i <= mid && j <= r){ if(q[i] <= q[j]) t[k ++] = q[i ++], flag2 = 0; else{ t[k ++] = q[j ++]; if(flag1) ans ++, flag1 = 0; } } if(!flag2 && i <= mid) vis = 0; while(i <= mid) t[k ++] = q[i ++]; if(!flag1 && j <= r) vis = 0; while(j <= r) t[k ++] = q[j ++]; for(int i = l, j = 0; j <= k - 1; ) q[i ++] = t[j ++]; } void solve(){ cin >> n; vis = 1; ans = 0; for(int i = 0; i <= n; i ++) q[i] = t[i] = 0; for(int i = 1; i <= n; i ++) cin >> q[i]; if(n == 1){ cout << 0 << endl; return ; } merge_sort(q, 1, n); if(vis) cout << ans << endl; else cout << -1 << endl; } int main(){ IOS; int _ = 1; cin >> _; while(_ --){ solve(); } return 0; }