赞
踩
不同的分数段有不同的^数量,Takahashi想要使得他的^数量增加,问他所需要的最少分数增幅。
我们只需要找到下一阶段的下限。
a / 100 是本阶段
+1 变成下一阶段,再 * 100变成下限,再与原来的相减即可。
- inline void solve() {
- int a; cin >> a;
- cout << (a / 100 + 1) * 100 - a << endl;
- return;
- }
有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;
- }
给你一个字符串,你可以任意改变其中的字符位置,问不包含长度为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;
- }
求第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;
- }
当地段高度小于等于海平面的时候就可以称之为沉没,海平面每年升高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;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。