A - Piling Up
题意
不同的分数段有不同的^数量，Takahashi想要使得他的^数量增加，问他所需要的最少分数增幅。
思路
我们只需要找到下一阶段的下限。
a / 100 是本阶段
+1 变成下一阶段，再 * 100变成下限，再与原来的相减即可。
代码
inline void solve() {int a; cin >> a;cout << (a / 100 + 1) * 100 - a << endl;return;
}B - Japanese Cursed Doll
题意
有n个人，每个人的头发长度每天都会增加1，问至少有p个人的头发长度大于等于T的最小天数。
思路
我们只需要找到第k头发长的人。
如果他已经比T大了，就说明一开始就满足，输出0
否则找到他与T的差值，就是最小天数
代码
inline void solve() {int n, t, p; cin >> n >> t >> p;vector<int> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];nth_element(a.begin() + 1, a.begin() + n - p + 1, a.end());cout << max(t - a[n - p + 1], 0) << endl;return;
}C - Avoid K Palindrome 2
题意
给你一个字符串，你可以任意改变其中的字符位置，问不包含长度为k的回文子串的字符串数量有多少个。
思路
数据范围很小，最差阶乘的复杂度，直接暴力模拟即可。
代码
inline void solve() {int n, k; cin >> n >> k;string s; cin >> s;vector<int> a(n);for (int i = 0; i < n; i ++ ) a[i] = s[i] - 'a';sort(a.begin(), a.end());function<bool()> check = [&]() {for (int i = 0; i <= n - k; i ++ ) {int c = i + k - 1;bool flag = true;for (int j = i; j < c; j ++ , c -- ) {if (a[j] != a[c]) {flag = false;}}if (flag) return true;}return false;};int ans = 0;do {if (!check()) ans += 1;} while (next_permutation(a.begin(), a.end()));cout << ans << endl;return;
}D - Palindromic Number
题意
求第N小的回文数
思路
首先我们可以观察对于i位所含的回文数的数量，这可以帮助我们找到第N个在哪
1位 10个
2位 9个
3位 90个
4位 90个
5位 900个
其实也很好推，对于1和2位，自己手玩就可以知道了。
然后对于位数为奇数的，相当于在之前位数为偶数的中间插入0~9
xx0xx
xx1xx
...
所以奇数位所含的回文数数量是上一位的10倍
而偶数位与上一位所含相同
因为
111 --必须是-> 1111
121 --必须是-> 1221
那我们只要一开始减1，然后按此操作 -9 -9 - 90 -90 -900 ...就可以知道它有几位了。
然后，回文的进位和正常的进位的区别不就在于它是向两边进位吗，所以我们只需观察中间。
比如
191 --> 202
1991 --> 2002
又我们观察到的数据是1e18，输入可以是ll，但是输出要是字符串。
所以我们可以用字符串维护一个前缀。
然后奇数位的话会影响到到下一位的数量
4位有90个回文数，5位有900个
偶数位的话会影响到前缀
代码
inline void solve() {ll x; cin >> x;x -= 1;string pre;ll nd = -1;for (int d = 1; ; d ++ ) {if (d & 1) {if (nd == -1) nd = 9;else nd *= 10;if (x <= nd) {if (!pre.size()) return cout << x << endl, void();x -= 1;ll num = stoll(pre) + x / 10;string pre = to_string(num);string s = pre + to_string(x % 10);reverse(pre.begin(), pre.end());s += pre;cout << s << endl;return;}x -= nd;}else {if (x <= nd) {if (!pre.size()) return cout << x << x << endl, void();x -= 1;ll num = stoll(pre) + x / 10;string pre = to_string(num);string s = pre + to_string(x % 10 * 11);reverse(pre.begin(), pre.end());s += pre;cout << s << endl;return;}x -= nd;if (!pre.size()) pre = "1";else pre += "0";}}return;
}E - Sinking Land
题意
当地段高度小于等于海平面的时候就可以称之为沉没，海平面每年升高1，问今后的Y年中各有多少个地段没有沉没？
思路
模拟题，我用了优先队列优化的bfs，我们只需要把跟海接触的放到queue里面，然后一直判断即可。
代码
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
struct node {int x, y, v;bool operator > (const node& a) const {return v > a.v;}
};
inline void solve() {int n, m, k; cin >> n >> m >> k;vector<vector<int>> a(n + 1, vector<int>(m + 1)), vis(n + 1, vector<int>(m + 1));priority_queue<node, vector<node>, greater<node>> q;for (int i = 1; i <= n; i ++ ) {for (int j = 1; j <= m; j ++ ) {cin >> a[i][j];if (i == 1 || i == n || j == 1 || j == m) q.push({i, j, a[i][j]}), vis[i][j] = 1;}}int ans = n * m;for (int i = 1; i <= k; i ++ ) {while (q.size() && q.top().v <= i) {node T = q.top(); q.pop();int x = T.x, y = T.y, v = T.v;ans -= 1;for (int i = 0; i < 4; i ++ ) {int x1 = x + dx[i], y1 = y + dy[i];if (x1 < 1 || x1 > n || y1 < 1 || y1 > m || vis[x1][y1]) continue;q.push({x1, y1, a[x1][y1]});vis[x1][y1] = 1;}}cout << ans << endl;}return;
}
