ABC414C
https://atcoder.jp/contests/abc414/tasks/abc414_c
回文数预处理+10进制转换为A进制
点击查看代码
#include <bits/stdc++.h>using namespace std;
#define int long longint A, N, ans;bool check(string s) { // 判断回文串string t = s;reverse(t.begin(), t.end());return s == t;
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> A >> N;// 构造回文串vector<int> v;for (int i = 1; i <= 999999; ++i) {string t = to_string(i);string s = t;reverse(t.begin(), t.end());s += t;int sum = 0;for (int j = s.size() - 1; j >= 0; --j) sum += pow(10, s.size() - j - 1) * (s[j] - '0');v.push_back(sum);}for (int i = 1; i <= 999999; ++i) {string t = to_string(i);string s;for (int j = 0; j < t.size(); ++j) s += t[j];for (int j = t.size() - 2; j >= 0; --j) s += t[j];int sum = 0;for (int j = s.size() - 1; j >= 0; --j) sum += pow(10, s.size() - j - 1) * (s[j] - '0');v.push_back(sum);}sort(v.begin(), v.end());// 进制转换for (auto i : v) {if (i > N) break; // 超过直接退出，否则TLEint j = i;string s;while (j) {s += j % A + '0';j /= A;}if (check(s)) ans += i;}cout << ans << '\n';return 0;
}
ABC413e
https://atcoder.jp/contests/abc413/tasks/abc413_e
分治 类似于归并排序的思想
观察一：排列的字典序：没有重复数字
观察二：2的次方想到 分治思想 子+子=原
观察三：手模所有的翻转操作，画图后发现是分治
n等于4时可以翻转哪些区间---画图一下
观察四：操作顺序不影响答案
由主定理：T(n) = 2T(n / 2) + O(n)
复杂度为O(Tnlogn)
点击查看代码
#include <bits/stdc++.h>using namespace std;
#define int long longconst int N = 3e5 + 5;
int a[N], n;void Sort(int l, int r) {if (l >= r) return;int mid = (l + r) / 2;Sort(l, mid);Sort(mid + 1, r);if (a[l] > a[mid + 1]) {for (int i = l, j = mid + 1; i <= mid; ++i, ++j) swap(a[i], a[j]);}
}void solve() {cin >> n;n = 1 << n;for (int i = 1; i <= n; ++i) cin >> a[i];Sort(1, n);for (int i = 1; i <= n; ++i) cout << a[i] << " \n"[i == n];
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}
ABC413d
https://atcoder.jp/contests/abc413/tasks/abc413_d
按绝对值从小到大排序
若存在绝对值相等的两个数
要么全部相等，要么1 -1 1 -1...或者-1 1 -1 1...
什么样的条件是等比数列，逆向思维：什么样的条件不是等比数列
两个观察：
正负都存在，且个数相差>1 一定不是等比数列
abs(a[1])!=abs(a[n])一定不是等比数列
否则
判断等比数列即可
点击查看代码
#include <bits/stdc++.h>using namespace std;
#define int long longconst int N = 2e5 + 5;
int n, a[N];void solve() {cin >> n;for (int i = 1; i <= n; ++i) cin >> a[i];sort(a + 1, a + n + 1, [](const int &x, const int &y) {return abs(x) < abs(y);});bool ok = 1;for (int i = 1; i < n; ++i) ok &= (abs(a[i]) != abs(a[i + 1])); // 若存在绝对值相等的情况，要么1 1 1 1...// 要么 1 -1 1 -1...或者-1 1 -1 1...if (!ok) {if (abs(a[1]) != abs(a[n])) {cout << "No" << '\n';return;}int cnt1 = 0, cnt2 = 0;for (int i = 1; i <= n; ++i) if (a[i] > 0) ++cnt1; else ++cnt2;if (cnt1 && cnt2 && abs(cnt1 - cnt2) > 1) {cout << "No" << '\n';return;}cout << "Yes" << '\n';return;}for (int i = 2; i <= n - 1; ++i) { // 等比数列判断if (a[i] * a[i] != a[i + 1] * a[i - 1]) ok = 0;}cout << (ok ? "Yes" : "No") << '\n';
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}
ABC412c
https://atcoder.jp/contests/abc412/tasks/abc412_c
a[2...n-1]排序
贪心的找到一个最小的子序列
点击查看代码
#include <bits/stdc++.h>using namespace std;
#define int long longconst int N = 2e5 + 5;
int a[N], n;void solve() {cin >> n;for (int i = 1; i <= n; ++i) cin >> a[i];sort(a + 2, a + n);int lst = a[1];int ans = 2;// 多看看这个代码逻辑for (int i = 2; i < n; ++i) {if (lst * 2 >= a[n]) break;if (a[i] > lst && a[i] <= 2 * lst && a[i + 1] > 2 * lst) {lst = a[i];++ans;}}if (lst * 2 >= a[n]) cout << ans << '\n';else cout << -1 << '\n';
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}