开题顺序：A - C - F - D - B - E。
A
直接模拟即可。
bool begmem;
#include <bits/stdc++.h>
#define int long long
using namespace std;
class FastIO {
public:
int read() {
int o = 1, x; char ch;
while (!isdigit(ch = getchar())) {
if (ch == '-') {
o = -1;
}
}
x = ch ^ 48;
while (isdigit(ch = getchar())) {
x = (x << 3) + (x << 1) + (ch ^ 48);
}
return o * x;
}
} ; FastIO io;
void calcqwq();
const int N = 500100, inf = 1e18;
inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a < b ? a : b; }
inline void swap(int &a, int &b) { a ^= b ^= a ^= b; }
int f[N], s[N], a[N];
signed main() {
atexit(calcqwq);
int n, k, x;
n = io.read(), k = io.read(), x = io.read();
for (int i = 1; i <= n; ++i) a[i] = io.read();
for (int i = 1; i <= k; ++i) printf("%lld ", a[i]);
printf("%lld ", x);
for (int i = k + 1; i <= n; ++i) printf("%lld ", a[i]);
printf("\n");
return 0;
}
bool endmem;
void calcqwq() {
fprintf(stderr, "Memory = %.5lf\n", (&begmem - &endmem) / 1048576.);
}
B
考虑使用高中数学中立体几何知识解决问题。容易发现两个立体图形之间存在公共地区，就是把三维问题拆开看作三个一维问题。一维问题相对而言好处理，即判断两个区间 \([p_1,p_2]\) 和 \([q_1,q_2]\) 的交是否至少包含了一个小数元素即可。时间复杂度为 \(O(1)\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Syx {
double x1, y1, z1, x2, y2, z2;
Syx(double x1, double y1, double z1, double x2, double y2, double z2) : x1(x1), y1(y1), z1(z1), x2(x2), y2(y2), z2(z2) {}
};
bool check(const Syx& c1, const Syx& c2, double eps = -1e-9) {
if (c1.x2 < c2.x1 - eps || c1.x1 > c2.x2 + eps) return false;
if (c1.y2 < c2.y1 - eps || c1.y1 > c2.y2 + eps) return false;
if (c1.z2 < c2.z1 - eps || c1.z1 > c2.z2 + eps) return false;
return true;
}
signed main() {
int a, b, c, d, e, f, g, h, i, j, k, l;
cin >> a >> b >> c >> d >> e >> f >> g >> h >> i >> j >> k >> l;
Syx c1(a, b, c, d, e, f);
Syx c2(g, h, i, j, k, l);
if (check(c1, c2))
cout << "Yes\n";
else
cout << "No\n";
}
C
降智了。贪心的发现答案一定是把原数组排序，然后删除 \(k\) 个元素之后剩下的数的值尽量连续，才能保证极差最小。所以考虑使用 ST 表维护静态区间最值，时间复杂度为 \(O(n\log n)\)。
注：其实有序数组中求 \([l,r]\) 区间的极差可以直接 \(a_r-a_l\)。使用 ST 表求是【】的日常 AT 降智行为。
bool begmem;
#include <bits/stdc++.h>
#define int long long
using namespace std;
class FastIO {
public:
int read() {
int o = 1, x; char ch;
while (!isdigit(ch = getchar())) {
if (ch == '-') {
o = -1;
}
}
x = ch ^ 48;
while (isdigit(ch = getchar())) {
x = (x << 3) + (x << 1) + (ch ^ 48);
}
return o * x;
}
} ; FastIO io;
void calcqwq();
const int N = 500100, inf = 1e18;
inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a < b ? a : b; }
inline void swap(int &a, int &b) { a ^= b ^= a ^= b; }
int f[N][20], g[N][20], lg[N], a[N];
int q1(int l,int r){
if(l>r)
return 0;
int len=r-l+1,k=lg[len];
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int q2(int l,int r){
if(l>r)
return 1e18;
int len=r-l+1,k=lg[len];
return min(g[l][k],g[r-(1<<k)+1][k]);
}
signed main() {
atexit(calcqwq);
int n, k, x;
n = io.read(), k = io.read();
for (int i = 1; i <= n; ++i) a[i] = io.read();
sort(a + 1, a + n + 1);
lg[0] = -1;
for (int i = 1; i <= n; ++i) lg[i] = lg[i / 2] + 1, f[i][0] = a[i], g[i][0] = a[i];
for (int j = 1; j < 20; ++j)
for (int i = 1; i <= n - (1ll << j) + 1; ++i) {
f[i][j] = max(f[i][j - 1], f[i + (1ll << (j - 1))][j - 1]);
g[i][j] = min(g[i][j - 1], g[i + (1ll << (j - 1))][j - 1]);
}
int mi = 1e18;
for (int l = 1, r = n - k; r <= n; l++, r++) {
int f1 = q1(l, r), f2 = q2(l, r);
mi = min(mi, f1 - f2);
}
printf("%lld\n", mi);
return 0;
}
bool endmem;
void calcqwq() {
fprintf(stderr, "Memory = %.5lf\n", (&begmem - &endmem) / 1048576.);
}
D
发现 \(n\le 14\)，启发使用指数级算法。每一个位置可以为 B，W 或者什么也没有，因此用 \(0/1/2\) 来表示这三个状态。可以用一个 \(n+2\) 位三进制数来存储当前的状态，广搜一遍求答案即可。时间复杂度为 \(O(n^2\times 3^{n+2})\)，看上去过不去，但是因为有效状态数量极少所以随便冲。
bool begmem;
#include <bits/stdc++.h>
#define int long long
using namespace std;
class FastIO {
public:
int read() {
int o = 1, x; char ch;
while (!isdigit(ch = getchar())) {
if (ch == '-') {
o = -1;
}
}
x = ch ^ 48;
while (isdigit(ch = getchar())) {
x = (x << 3) + (x << 1) + (ch ^ 48);
}
return o * x;
}
} ; FastIO io;
void calcqwq();
const int N = 500100, inf = 1e18;
inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a < b ? a : b; }
inline void swap(int &a, int &b) { a ^= b ^= a ^= b; }
int n, now, mask; string s, t;
signed f[63333333];
signed main() {
atexit(calcqwq);
n = io.read();
cin >> s >> t;
now = 0, mask = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'B') now = now * 3 + 1;
else now = now * 3 + 2;
if (t[i] == 'B') mask = mask * 3 + 1;
else mask = mask * 3 + 2;
}
now = now * 9, mask = mask * 9;
memset(f, -1, sizeof f);
f[now] = 0;
queue<int> q;
q.push(now);
while (q.size()) {
int t = q.front();
q.pop();
int f1 = 0, f2 = 0;
vector<int> wei;
int tmp = t;
for (int i = 0; i < n + 2; ++i) {
wei.push_back(tmp % 3);
tmp /= 3;
}
reverse(wei.begin(), wei.end());
for (int i = 0; i < n + 1; ++i)
if (!wei[i] && !wei[i + 1]) f1 = i, f2 = i + 1;
for (int i = 0; i < n + 1; ++i)
if (wei[i] && wei[i + 1]) {
vector<int> wei2 = wei;
wei2[f1] = wei[i], wei2[f2] = wei[i + 1], wei2[i] = wei2[i + 1] = 0;
int calc = 0;
for (auto &j : wei2) calc = calc * 3 + j;
if (!~f[calc]) {
f[calc] = f[t] + 1;
q.push(calc);
}
}
}
if (~f[mask]) cout << f[mask] << '\n';
else cout << "-1\n";
}
bool endmem;
void calcqwq() {
fprintf(stderr, "Memory = %.5lf\n", (&begmem - &endmem) / 1048576.);
}
E
根据某一次 NOIP 集训 T1 的思路，容易发现一定是有一条路径上的边只经过了一次，其他的边都经过了两次。为了让经过的边的边权和最小，只需要让这一条路径为树的直径即可。时间复杂度为 \(O(n\log n)\)，这是因为要求两点之间距离需要倍增 LCA 求（其实又是降智行为）。
bool begmem;
#include <bits/stdc++.h>
#define int long long
using namespace std;
class FastIO {
public:
int read() {
int o = 1, x; char ch;
while (!isdigit(ch = getchar())) {
if (ch == '-') {
o = -1;
}
}
x = ch ^ 48;
while (isdigit(ch = getchar())) {
x = (x << 3) + (x << 1) + (ch ^ 48);
}
return o * x;
}
} ; FastIO io;
void calcqwq();
const int N = 500100, inf = 1e18;
inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a < b ? a : b; }
inline void swap(int &a, int &b) { a ^= b ^= a ^= b; }
int f[N][20], id, vis[N], dis[N], n, sum;
vector<pair<int, int>> z[N];
void bfs(int st) {
memset(dis, 0x3f, sizeof dis);
queue<int> q; q.push(st); vis[st] = 1, dis[st] = 0;
while (q.size()) {
int f = q.front(); q.pop(); vis[f] = 0;
for (auto &[g, w] : z[f]) if (dis[g] > dis[f] + w) {
dis[g] = dis[f] + w;
if (!vis[g]) {
vis[g] = 1;
q.push(g);
}
}
}
id = -233;
for (int i = 1; i <= n; ++i)
if (id == -233 || dis[i] > dis[id]) id = i;
}
int dep[N], yhb[N];
void dfs(int u, int fa) {
f[u][0] = fa, yhb[u] = yhb[fa] + 1;
for (auto &[v, _] : z[u]) if (v != fa) dep[v] = dep[u] + _, dfs(v, u);
}
int lca(int u, int v) {
if (yhb[u] < yhb[v]) swap(u, v);
int delta = yhb[u] - yhb[v];
for (int i = 0; i < 20; ++i) if (delta >> i & 1) u = f[u][i];
// cout << "qvq " << u << '\n';
if (u == v) return u; for (int i = 19; ~i; --i)
if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
return f[u][0];
}
int qwq(int a, int b) {
return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}
signed main() {
atexit(calcqwq);
n = io.read(), sum = 0;
for (int i = 1; i < n; ++i) {
int u = io.read(), v = io.read(), w = io.read();
z[u].emplace_back(v, w);
z[v].emplace_back(u, w);
sum += w;
}
bfs(1);
int st = id;
bfs(st);
int st2 = id;
dfs(1, 0);
for (int i = 1; i < 20; ++i)
for (int j = 1; j <= n; ++j)
f[j][i] = f[f[j][i - 1]][i - 1];
// cout << st << ' ' << st2 << ' ' << lca(st, st2) << ' ' << qwq(st, st2) << '\n';
cout << sum * 2 - qwq(st, st2) << '\n';
}
bool endmem;
void calcqwq() {
fprintf(stderr, "Memory = %.5lf\n", (&begmem - &endmem) / 1048576.);
}
F
最简单的一集。为 P9118 春测原题弱化版。即此题 \(k=2\) 情况。
首先对于 \(a^b\)，若 \(b\ge 3\) 则 \(a\) 最大不会超过 \(10^6\)，可以直接暴力枚举。难点在于 \(k=2\) 的情况。
考虑容斥。容易发现 \(b=2\) 时答案为 \(\lfloor\sqrt n\rfloor-R\)。其中 \(R\) 表示需要容斥的部分。即 \(b>2\) 时成立且 \(b=2\) 时也成立的数。因为 \(b>2\) 即 \(b\ge 3\) 的情况数量很少可以暴力枚举，所以在枚举 \(b\ge 3\) 的时候直接算出来里面又多少个完全平方数，即为要容斥的数的数量 \(R\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
map<int, int> mp;
int R, cnt;
void solve(int n, int k) {
for (int i = 2; i * i * i <= n; ++i) {
int t = i * i, m = 2;
while (t <= n / i) {
t *= i, m++;
if (m < k || mp[t]) continue;
else {
if ((int)sqrtl(t) * sqrtl(t) == t) R++;
cnt++, mp[t] = 1;
}
}
}
}
signed main() {
int n;
cin >> n;
solve(n, 2);
cout << (int)sqrtl(n) - R + cnt << '\n';
}