赛时卡题坐大牢。
A
构造成要么全 ，要么全
。
使用 ，
。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
string t;
cin >> n >> t;
string s0(n, '0');
string s1(n, '1');
auto s = t + '$' + t + s0 + t;
int m = s.size();
int len = t.size();
vector<int> z(m);
int cnt = 0;
for (int i = 1, l = 0, r = 0; i < m; i++) {
if (i <= r && z[i - l] <= r - i) {
z[i] = z[i - l];
} else {
z[i] = max(0, r - i + 1);
while (i + z[i] < m && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
}
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
if (z[i] == len) {
cnt++;
}
}
if (cnt == 2) {
cout << s0 << '\n';
} else {
cout << s1 << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
C
看成是若干个半径为 有权值的圆，在以
为圆心，以
为半径的圆
中找一个点
，使包含
点的圆的权值加起来最大。
为避免一些不好的事情发生，将一开始 的权值设为无穷大。
使用 中的
来进行计算几何操作。
。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using Point = complex<double>;
const double Pi = acos(-1.0);
constexpr i64 inf = 1E18;
void fix(double &rad) {
while (rad < 0) {
rad += 2 * Pi;
}
while (rad >= 2 * Pi) {
rad -= 2 * Pi;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, r1, r2, R, x0, y0;
cin >> n >> r1 >> r2 >> R >> x0 >> y0;
vector<Point> a(n + 1);
vector<i64> r(n + 1), v(n + 1);
a[0] = Point(x0, y0);
r[0] = r1 + r2;
v[0] = inf;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
a[i] = Point(x, y);
r[i] = R;
}
i64 ans = -inf;
for (int i = 0; i < n + 1; i++) {
i64 sum = v[i];
vector<pair<double, i64>> e;
for (int j = 0; j < n + 1; j++) {
if (i == j) {
continue;
}
auto d = abs(a[i] - a[j]);
if (d > r[i] + r[j] || d < abs(r[i] - r[j])) {
if (d <= r[j] - r[i]) {
sum += v[j];
}
} else {
auto ang = arg(a[j] - a[i]);
auto t = acos((r[i] * r[i] + d * d - r[j] * r[j]) / (2 * r[i] * d));
auto l = ang - t;
auto r = ang + t;
fix(l), fix(r);
e.push_back({l, v[j]});
e.push_back({r, -v[j]});
if (l > r) {
sum += v[j];
}
}
}
ans = max(ans, sum);
sort(e.begin(), e.end());
for (auto &[_, x] : e) {
sum += x;
ans = max(ans, sum);
}
}
ans -= inf;
cout << ans << '\n';
return 0;
}
D
先考虑枚举到 进制，大于
进制，
的数位必定小于等于
，接着枚举数位，枚举在当前
位数下，最高的一位的值，此时二分确定
允许的取值范围，这里猜想能使
在某进制下数位变小的
就在求出来这个允许的最大值的附近。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using i128 = __int128;
istream &operator>>(istream &is, i128 &v) {
string s;
is >> s;
v = 0;
for (auto &si : s) {
v = v * 10 + si - '0';
}
return is;
}
i128 f(i128 n, i128 k) {
i128 s = 0;
while (n) {
s += n % k;
cnt++;
n /= k;
}
return s;
}
constexpr i128 inf = 1E38;
constexpr i128 lim = 1E4;
void solve() {
i128 n, K;
cin >> n >> K;
int ans = 10000;
for (i128 i = 2; i <= min(K, lim); i++) {
ans = min(i128(ans), f(n, i));
}
if (K > lim) {
for (int d = 1; d <= 8; d++) {
for (int a = 1; a < ans; a++) {
i128 lo = lim, hi = n;
while (lo < hi) {
i128 m = (lo + hi + 1) / 2;
i128 sum = a;
for (int i = 0; i < d; i++) {
if (sum <= inf / m) {
sum *= m;
} else {
sum = inf;
break;
}
}
if (sum <= n) {
lo = m;
} else {
hi = m - 1;
}
}
i128 k = min(K, lo);
for (int times = 0; k > lim && times <= 30; times++, k--) {
ans = min(i128(ans), f(n, k));
}
}
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
F
模拟一下。
。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
deque<int> d(a.begin(), a.end());
sort(d.begin(), d.end());
while (d.size() > 1) {
int d1 = d.front(), d2 = d.back();
double ave = 1.0 * (d1 + d2) / 2;
if (d[((int) d.size() - 1) / 2] <= ave) {
d.pop_back();
} else {
d.pop_front();
}
}
cout << find(a.begin(), a.end(), d[0]) - a.begin() + 1 << '\n';
return 0;
}
H
每次割成左上右下两个正方形和左下右上两个矩形。
先预处理出割法，然后 进行分割。
表示对于边长为
的正方形割成
的正方形和
的正方形和两个
的矩形。
复杂度不会算。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int get(int a, int b) {
if (!b) {
return 0;
}
return a / b + get(b, a % b);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> f(1001);
for (int i = 2; i <= 1000; i++) {
for (int j = 1; j < i; j++) {
if (2 + 2 * get(i, i - j) <= 50) {
f[i] = j;
break;
}
}
}
int n;
cin >> n;
vector<array<int, 3>> ans;
function<void(int, int, int, int)> dfs = [&](int x1, int y1, int x2, int y2) {
if (x2 - x1 == y2 - y1) {
if (x2 - x1 == 1) {
return;
}
int k = f[x2 - x1];
dfs(x1, y1, x1 + k, y1 + k);
dfs(x1 + k, y1 + k, x2, y2);
dfs(x1, y1 + k, x1 + k, y2);
dfs(x1 + k, y1, x2, y1 + k);
ans.push_back({x1, y1, x2 - x1});
return;
}
if (x2 - x1 > y2 - y1) {
int k = y2 - y1;
dfs(x1, y1, x1 + k, y2);
dfs(x1 + k, y1, x2, y2);
} else {
int k = x2 - x1;
dfs(x1, y1, x2, y1 + k);
dfs(x1, y1 + k, x2, y2);
}
};
dfs(0, 0, n, n);
cout << ans.size() << '\n';
for (auto &[x, y, k] : ans) {
cout << x + 1 << ' ' << y + 1 << ' ' << k << '\n';
}
return 0;
}
L
倒过来考虑，。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<string> a(q), c(q);
vector<int> b(q);
for (int i = 0; i < q; i++) {
cin >> a[i] >> b[i] >> c[i];
b[i]--;
}
i64 ans = 0;
vector<int> R(n), C(m);
for (int i = q - 1; i >= 0; i--) {
if (a[i][0] == 'r') {
if (!R[b[i]]) {
ans += m * (c[i] == "on");
R[b[i]] = 1;
n--;
}
} else {
if (!C[b[i]]) {
ans += n * (c[i] == "on");
C[b[i]] = 1;
m--;
}
}
}
cout << ans << '\n';
return 0;
}
京公网安备 11010502036488号