AtCoder Beginner Contest 363_atcoder beginner contest 363 d palindromic number

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