难度：A < B < C < E ≈ F << D
做题顺序：A -> B -> C -> F -> E -> D
其实 VP 的时候 perf 还是有 \(2000+\) 的（虽然说 D 炸了），perf 应该是 \(2028\) 左右
A
signed main() {
int n;
cin >> n;
int cnt = 0;
do {
++cnt;
++n;
} while (n % 100);
cout << cnt << '\n';
return 0;
}
B
问题即为：两个操作：整体加一，区间求 \(k\) 大。
因为整体加一之后相对的大小关系不会变化所以直接从大到小排序，然后暴力看整体加多少次 \(1\) 之后 \(a_p\ge t\) 即可。
时间复杂度为 \(O(n^2)\)。当然如果只维护一个 \(a_p\) 的值时间复杂度为 \(O(n)\)。
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
int l[N];
signed main() {
int n, t, p;
cin >> n >> t >> p;
for (int i = 1; i <= n; ++i)
scanf("%lld", &l[i]);
sort(l + 1, l + n + 1, greater<>());
// 至少有 p 个人头发长度超过为 t
if (l[p] >= t) {
puts("0");
return 0;
}
for (int i = 1; ; ++i) {
for (int j = 1; j <= n; ++j)
++l[j];
if (l[p] >= t) {
printf("%lld\n", i);
return 0;
}
}
return 0;
}
C
直接枚举字符串 \(s\) 的所有排列，然后暴力找有没有长度为 \(k\) 的回文字符串即可。记得去重。
枚举字符串所有排列可以先给字符串排序，然后用 next_permutation 找下一个排列。
时间复杂度为 \(O(n!nk)\)。
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
int l[N];
signed main() {
int n, k;
scanf("%lld%lld", &n, &k);
set<string> se;
string s;
cin >> s;
sort(s.begin(), s.end());
do {
int ok = 1;
for (int i = 0, j = k - 1; j < n; ++i, ++j) {
string tmp;
for (int p = i; p <= j; ++p)
tmp += s[p];
string we = tmp;
reverse(we.begin(), we.end());
if (we == tmp) {
ok = 0;
break;
}
}
if (ok) se.insert(s);
} while (next_permutation(s.begin(), s.end()));
cout << se.size() << '\n';
return 0;
}
D
其实不会做.jpg
有一个很好的搞这一类题的方法：首先打表找一下规律，可以发现，对于一个长度为 \(n\) 的字符串：
- 若 \(n=1\)，则有 \(10\) 个长度为 \(n\) 的回文串。
- 否则，有 \(9\times 10^{\lceil\frac{n}{2}\rceil}\) 个长度为 \(n\) 的回文字符串。
然后就各种乱七八糟处理就行了。具体是怎么过的我也不知道。
大体上就是说，考虑每一位的贡献，枚举这个位置的答案 \(p\)，判断如果后面全选择 \(9\)，比他小的回文串的数量是否够用。如果够用了就选择她。时间复杂度不太好分析。
然后就是说这个东西细节特别多，就是看到哪里不太对劲就扯一下，凑过去就行。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int ans = 1;
int n, f[55];
signed main(){
scanf("%lld", &n);
if (n == 1) {
puts("0");
return 0;
}
--n;
f[1] = 9;
for (int i = 2; i <= 40; ++i){
if (i & 1)
f[i] = f[i - 1] * 10;
else
f[i] = f[i - 1];
}
int k;
for (k = 1; ; ++k) {
if (n > f[k])
n -= f[k];
else
break;
}
int wei = k + 1 >> 1;
for (int i = 1; i <= wei; ++i) {
int st = (i == 1) ? 1 : 0;
while (n > f[k] / 9) n -= f[k] / 9, ++st;
--k, --k;
if (i == 1) ans = st;
else ans = ans * 10 + st;
}
cout << ans;
if (k & 1)
ans /= 10;
while (ans) {
printf("%lld", ans % 10);
ans /= 10;
}
puts("");
return 0;
}
E
又回到了简单题。考虑枚举 \(i\) 的值，容易发现，小岛的某一个部分，若在 \(i\) 时刻沉，则 \(i+1\) 时刻也一定是沉的。
然后考虑维护一下当前所有在边上的地段。对于每一个地段，若在 \(i\) 时刻她第一次沉，则枚举和其四连通的四个格子并将其放到新的边界上。为了快速的找到边界上一个格子是否会沉，可以使用一个堆来维护。
时间复杂度为 \(O(nm\log nm)\)。容易发现每一个地段最多只会入队一次出队一次。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int ans = 1;
int n, f[55];
signed main(){
scanf("%lld", &n);
if (n == 1) {
puts("0");
return 0;
}
--n;
f[1] = 9;
for (int i = 2; i <= 40; ++i){
if (i & 1)
f[i] = f[i - 1] * 10;
else
f[i] = f[i - 1];
}
int k;
for (k = 1; ; ++k) {
if (n > f[k])
n -= f[k];
else
break;
}
int wei = k + 1 >> 1;
for (int i = 1; i <= wei; ++i) {
int st = (i == 1) ? 1 : 0;
while (n > f[k] / 9) n -= f[k] / 9, ++st;
--k, --k;
if (i == 1) ans = st;
else ans = ans * 10 + st;
}
cout << ans;
if (k & 1)
ans /= 10;
while (ans) {
printf("%lld", ans % 10);
ans /= 10;
}
puts("");
return 0;
}
F
还是简单题。容易发现满足条件的字符串 \(S\) 共有两类：
- \(S\) 中有偶数个元素。
- \(S\) 中有奇数个元素。
其中偶数个元素的情况可以归结到奇数个元素的情况中。即在正中间的两个元素之间加一个数字 \(1\) 就可以满足条件。
然后开始暴力搜索。枚举当前剩余的数 \(x\) 的每一个因子 \(d\)，记 \(D\) 为 \(d\) 的倒序得到的数。如果 \(d\) 和 \(D\) 都满足条件，并且 \(x\bmod (D\times d)=0\)，则 \(D\) 和 \(d\) 都是满足条件的，就可以考虑 \(\frac{x}{D\times d}\) 的子问题了。特殊的，若此时 \(x\) 已经可以满足条件了，则可以直接将 \(x\) 作为中间元素输出。
最后警示一下：有返回值的函数一定要返回。这个【】因为没有返回调试了 20+min。
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
int l[N];
bool check(int n) {
string s = to_string(n);
string t = s;
reverse(t.begin(), t.end());
return s == t && !count(s.begin(), s.end(), '0');
}
int mysqrt(int x) {
int l = 0, r = x + 10, best = -1;
while (l <= r) {
int mid = l + r >> 1;
if ((__int128)(mid) * (__int128)(mid) <= x)
best = mid, l = mid + 1;
else
r = mid - 1;
}
return best;
}
vector<int> Div(int x) {
vector<int> v;
for (int i = 1; i * i <= x; ++i)
if (x % i == 0) {
if (i != 1)
v.emplace_back(i);
if (i * i != x && i != 1)
v.emplace_back(x / i);
}
sort(v.begin(), v.end());
return v;
}
void fun(int x, int you, string qian) {
// cout << "x = " << x << '\n';
if (check(x)) {
// cout << "x = " << x << '\n';
// cout << "qwq: " << qian << '\n';
// exit(0);
// cout << "dbg " << qian << ' ' << you << '\n';
cout << qian;
if (x) {
if (qian.size()) cout << "*";
cout << x;
if (qian.size()) cout << "*";
} else {
cout << "*";
}
reverse(qian.begin(), qian.end());
cout << qian << '\n';
exit(0);
}
vector<int> dx = Div(x);
// cout << "qwq: ";
// for (auto &x : dx) cout << x << ' ';
// cout << "All = " << x << '\n';
for (auto &d : dx) {
string sd = to_string(d);
reverse(sd.begin(), sd.end());
if (count(sd.begin(), sd.end(), '0')) continue;
int dd = 0;
for (auto &x : sd) dd = dd * 10 + x - '0';
// cout << "qwq " << d << ' ' << dd << '\n';
if ((x / d) % dd == 0) {
int val = x / d / dd;
string nw = qian;
if (nw.size()) nw += "*";
nw += to_string(d);
fun(val, you, nw);
}
}
}
signed main() {
int n;
scanf("%lld", &n);
if (check(n)) {
printf("%lld\n", n);
return 0;
}
vector<int> div = Div(n);
fun(n, 0, "");
// for (auto &d : div)
// if (check(d)) {
// int rem = n / d;
// fun(rem, d, "");
// }
cout << "-1\n";
return 0;
}
G
待补。
标签：AtCoder,return,Beginner,int,long,++,补题,ans,-- From： https://www.cnblogs.com/yhbqwq/p/18314564