AtCoder Beginner Contest 363

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;
}