有空就写题解 A、Hard Way 思路
签到
特判，一条边平行于 y = 0 y = 0 y=0 的直线，且第三个点在该边下方
#include using namespace std;int main() { int t; cin >> t; while (t -- ) { int x1, y1, x2, y2, x3, y3; cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3; if (y1 == y2 && y1 && y3 < y1) { printf("%dn", abs(x1 - x2)); } else if (y2 == y3 && y2 && y1 < y2) { printf("%dn", abs(x3 - x2)); } else if (y1 == y3 && y1 && y2 < y1) { printf("%dn", abs(x1 - x3)); } else { printf("%dn", 0); } } return 0;}
B、Power Walking 思路
签到
#include using namespace std;int main() { int t; scanf("%d", &t); while (t -- ) { int n; map mp; scanf("%d", &n); for (int i = 1; i <= n; i ++ ) { int a; scanf("%d", &a); mp[a] ++; } int cnt = mp.size(); for (int i = 1; i <= n; i ++ ) if (i <= cnt) printf("%d ", cnt); else printf("%d ", i); puts(""); } return 0;}
C、Great Sequence 思路
签到
#include using namespace std;const int N = 2e5 + 10;char str[N];int main() { int t; scanf("%d", &t); while (t -- ) { int n, x; map mp; scanf("%d%d", &n, &x); for (int i = 1; i <= n; i ++ ) { int a; scanf("%d", &a); mp[a] ++; } int ans = 0; for (auto [val, cnt] : mp) { if (1ll * val * x <= 1e9 && mp[val * x]) { int num = mp[val * x]; mp[val * x] -= min(num, cnt); mp[val] -= min(num, cnt); } ans += mp[val]; } printf("%dn", ans); } return 0;}
优化版
#include using namespace std;int main() { int t; scanf("%d", &t); while (t -- ) { int n, x; scanf("%d%d", &n, &x); multiset st; VI a(n); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); sort(a.begin(), a.end()); for (int i = 0; i < n; i ++ ) { if (a[i] % x == 0 && st.find(a[i] / x) != st.end()) { st.erase(st.find(a[i] / x)); } else st.insert(a[i]); } printf("%dn", st.size()); } return 0;}
D、Repetitions Decoding 思路
每两个一样的数消除一次，最多要 n n n 个操作，那么 q q q 最多为 n 2 / 2 n ^ 2 / 2 n2/2，每次从后面开始找，每找到就往前面插入数字，然后消除这两个一样的数字。算了，举例子吧
3 2 1 1 2 3
操作 1：2 2 3 2 1 1 2 3
操作 2：2 1 1 2 3 2 1 1 2 3
操作 3：2 1 1 1 1 2 3 2 1 1 2 3
操作 4：2 1 1 2 2 1 1 2 3 2 1 1 2 3
2 1 1 2
操作 1：1 1 2 1 1 2
操作 2：1 1 1 1 2 1 1 2
1 1
操作 1：1 1 1 1
#include using namespace std;void work() { int n; cin >> n; VI a(n); for (int i = 0; i < n; i ++ ) cin >> a[i]; vector res; VI len; while (a.size()) { int i = a.size() - 1, j = i - 1; for (; j >= 0; j -- ) if (a[j] == a[i]) break; if (j == -1) { cout << -1 << endl; return; } for (int k = 0; k < i - j - 1; k ++ ) res.PB({j + k, a[i - k - 1]}); reverse(a.begin() + j, a.end() - 1); len.PB(2 * (i - j)); a.pop_back(), a.pop_back(); } cout << res.size() << endl; for (auto [p, c] : res) cout << p << ' ' << c << endl; cout << len.size() << endl; for (int i = len.size() - 1; i >= 0; i -- ) cout << len[i] << ' '; cout << endl;}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t -- ) { work(); } return 0;}