A、进攻
需要最终权值最大，那么肯定是优先选择可以拿到价值对大的房子一直打。
那么就是能打这个房子的飞机就一直打这一个房子。当飞机无法击败这个房子的时候考虑换第二大价值的房子一直打。
这样下来就只需要对全部飞机能力值降序排序，对全部房子按照可以拿到的价值降序排序，依次遍历即可。
这里还有一个坑点就是，看他数据范围，每个数的权值是绝对值小于某个数，也就是可能出现负权值，遇到负权值的直接跳出。
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;
int n, m;
int a[N];
struct Node {
int d, v;
bool operator > (const Node& A) const {
return v > A.v;
}
}p[N];
void solve() {
n = read(), m = read();
for (int i = 1; i <= n; ++i) a[i] = read();
sort(a + 1, a + 1 + n, greater<int>());
for (int i = 1; i <= m; ++i) p[i].d = read();
for (int i = 1; i <= m; ++i) p[i].v = read();
sort(p + 1, p + 1 + m, greater<Node>());
ll ans = 0;
for (int i = 1, j = 1; i <= n and j <= m; ++j) {
if (p[j].v < 0) break; // 别加到负数了
while (i <= n and a[i] > p[j].d) {
ans += p[j].v;
++i;
}
}
print(ans);
}
int main() {
//int T = read(); while (T--)
solve();
return 0;
}
B、二进制
首先我最开始读题的时候出问题了，他说的是对于任何一个数进行 n 次下面操作等价于进行 m 次操作。
注意是任何一个数，我最开始以为是 0 ，那不是直接异或最后的答案就行了嘛？那么答案显然是不对的。
那么我们就要拿一个20位的 int 假设位x 初始化全为0，在拿一个20位全是 1的数假设为 y。
分别按位进行 n 次操作，当x，y都变成了0，说明这一位需要与一个0，其他的时候这一位与就是1
当x，y都变成了1，说明这一位需要或一个1，其他时候就是或一个0。
当 x 变成1，y 变成了0，说明这一位异或了一个1。
那么这样下来就可以得到三个需要按位与，按位或，按位异或的答案。
进行三次这样的操作，等价于上面 n 次操作。
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 7;
int n, m;
int op[N], a[N];
void solve() {
n = read();
for (int i = 1; i <= n; ++i)
op[i] = read(), a[i] = read();
int And = (1 << 20) - 1, Or = 0, Xor = 0;
for (int i = 0; i < 20; ++i) { // 遍历每一位
int x = 0, y = 1;
for (int j = 1; j <= n; ++j) { // 遍历全部的操作
int tmp = a[j] >> i & 1;
if (op[j] == 1)
x &= tmp, y &= tmp;
else if (op[j] == 2)
x |= tmp, y |= tmp;
else
x ^= tmp, y ^= tmp;
}
if (!x and !y) And -= (1 << i); // 0 1 都变成0了与了一个0
else if (x and y) Or += (1 << i); // 0 1 都变成1 或了一个1
else if (x and !y) Xor += (1 << i); // 0 1 分别取反 说明异或了一个1
}
print(3);
printf("1 %d\n", And);
printf("2 %d\n", Or);
printf("3 %d\n", Xor);
}
int main() {
//int T = read(); while (T--)
solve();
return 0;
}
C、积木
不难发现当n是奇数的时候是无解的。
当n是偶数的时候，可以用 2 * 2 * 2的小矩阵依次填充。
1 1
0 0
1 1
0 0
就是需要的小矩阵，只需要依次翻转的正确顺序放入即可。
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;
int n, m;
int a[N];
void solve() {
n = read();
if (n & 1) {
puts("-1");
return;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
int x = i % 4 < 2 ? 0 : 1;
if (j % 2) x = !x;
if (k % 4 < 2) x = !x;
printf("%d ", x);
}
puts("");
}
}
}
int main() {
//int T = read(); while (T--)
solve();
return 0;
}
D、种树
首先观察发现，可以找到使用剪刀次数就是有子节点的节点个数。这样就可以求道我们有几个大剪刀
接着，我们就可以想，我们最终能拿的一定是叶子节点的权值。以为非叶子节点的权值会被叶子节点覆盖。
那么问题就变成了，我们可以执行一定次数的（假定为 k 次）操作，拿到一个叶子节点的值，现在要你把这个值最大化。
居然有大剪刀，那就一定有小剪刀。那么我们要拿到某个节点的权值，一定是要首先保证他兄弟节点权值比它小。
而且需要最少 它深度那么多个大剪刀！那么答案也就被我们找到了。
具体实现的时候，我们不需要取保证兄弟节点，只需要枚举全部的点去找到符合要求的最大值即可。
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 7;
int n, m;
int p[N][2], dep[N];
void dfs(int u, int now) {
if (!u) return;
dep[u] = now;
dfs(p[u][0], now + 1);
dfs(p[u][1], now + 1);
}
void solve() {
n = read();
int cnt = 0;
dep[1] = 0;
for (int i = 1; i <= n; ++i) {
p[i][0] = read(), p[i][1] = read();
if (p[i][0]) ++cnt;
}
dfs(1, 0);
int ans = 0, k = (cnt + 1) / 2;
for (int i = 1; i <= n; ++i) {
int x = read();
if (!p[i][0] and dep[i] <= k)
ans = max(ans, x);
}
print(ans);
}
int main() {
//int T = read(); while (T--)
solve();
return 0;
}
E、考试
首先统计两个序列不同的个数有几个，可以使用异或操作。
接着去判断一下和输入的 m 的大小关系，如果大于等于 m 说明可以把他错的全部改对，直接把答案 + m
如果小于了 m 说明我们也一定有某些题是错的。重新统计答案即可。
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;
int n, m;
int a[N];
void solve() {
n = read(), m = read();
ll ans = 0;
for (int i = 1; i <= n; ++i) a[i] = read();
for (int i = 1; i <= n; ++i) ans += a[i] ^ read();
if (ans >= m) print(n - ans + m);
else print(n - m + ans);
}
int main() {
//int T = read(); while (T--)
solve();
return 0;
}
F、项链
多次移动操作，想到链表的结构。
多次翻转操作，想到双向链表。
如果想到了这个方向，那么这个题目也就可以仔细一点写出来。
只需要仔细的去模拟移动操作去处理操作数的前驱和后继。
每次翻转操作的时候就去把输出方向调转一遍。
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;
int n, m;
int node[N][2];
void solve() {
n = read(), m = read();
int x = 0;
for (int i = 1; i <= n; ++i)
node[i][x] = i - 1,
node[i][x ^ 1] = i + 1;
node[1][x] = n;
node[n][x ^ 1] = 1;
while (m--) {
int op = read();
if (op == 1) {
int a = read(), b = read();
node[node[a][x]][x ^ 1] = node[a][x ^ 1];
node[node[a][x ^ 1]][x] = node[a][x];
node[a][x ^ 1] = node[b][x ^ 1];
node[node[b][x ^ 1]][x] = a;
node[b][x ^ 1] = a;
node[a][x] = b;
}
else if (op == 2) {
int a = read(), b = read();
node[node[a][x]][x ^ 1] = node[a][x ^ 1];
node[node[a][x ^ 1]][x] = node[a][x];
node[a][x] = node[b][x];
node[a][x ^ 1] = b;
node[node[b][x]][x ^ 1] = a;
node[b][x] = a;
}
else if (op == 3) x ^= 1;
else {
printf("1 ");
for (int i = node[1][x ^ 1]; i != 1; i = node[i][x ^ 1])
printf("%d ", i);
puts("");
}
}
}
int main() {
//int T = read(); while (T--)
solve();
return 0;
} G、涂色
题目规定10不允许出现，首先第一反应，动态规划
dp[i][1]是第i位是1的方案数，dp[i][0]是第i位是0的方案数
状态转移方程也很好写
dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD,
dp[i][0] = dp[i - 1][0];
那么接下来也是赛后看到别人的题解发现这个题目是可以O(1)直接计算出来的。
居然一个10都不能出现，那么很显然第一种方法是全为1。
第二种放入一个0，只能出现在第零位。
第三种放入两个0，只能出现在第零和第一位。
这样下来就有n+1种方案了，与动态规划求解答案相同。
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;
int n, m;
ll dp[N][2];
void solve() {
n = read();
dp[1][0] = dp[1][1] = 1;
for (int i = 2; i <= n; ++i)
dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD,
dp[i][0] = dp[i - 1][0];
print((dp[n][1] + dp[n][0]) % MOD);
}
int main() {
//int T = read(); while (T--)
solve();
return 0;
}
H、圆
签到题了，求圆心距离，判断是否内含与相离即可。
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;
int n, m;
int a[N];
void solve() {
ll x1 = read(), y1 = read(), r1 = read(), x2 = read(), y2 = read(), r2 = read();
double dis = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
if (dis > r1 + r2 or dis < abs(r1-r2)) puts("NO");
else puts("YES");
}
int main() {
int T = read(); while (T--)
solve();
return 0;
}
I、修改
把区间全部加1或者减1，而且可以执行无数次。
区间修改？？差分干它！
它也没有给你初始数组，那么也就是你要能够修改任意的节点，那么如何去判断上面出现的差分数组是不是全部节点都可以被修改到呢，并且要拿到最终花费的最小值？
等等全部修改到?，全部的节点都要在一个集合中，还要最小值？
有一个算法，它叫 Kruskal 。
这个题，想到了建立差分数组后面一个点为终点，依次跑kruskal，实现起来比较简单了。
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 7;
int n, m;
struct Node {
int u, v, w;
bool operator < (const Node& A) {
return w < A.w;
}
}edge[N];
int fa[N];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void solve() {
n = read(), m = read();
for (int i = 1; i <= m; ++i)
edge[i].u = read(), edge[i].v = read() + 1, edge[i].w = read();
sort(edge + 1, edge + 1 + m);
for (int i = 1; i < N; ++i) fa[i] = i;
int cnt = 0;
ll ans = 0;
for (int i = 1; i <= m; ++i) {
int fu = find(edge[i].u), fv = find(edge[i].v);
if (fu != fv) {
fa[fv] = fu;
++cnt;
ans += edge[i].w;
}
}
if (cnt != n) puts("-1");
else print(ans);
}
int main() {
//int T = read(); while (T--)
solve();
return 0;
}
J、克隆
观察题目，可以发现最终你可以走过的节点数一定是大于等于 2 * n 个节点的。
我要可以去全部的节点？最多 2 * n个节点？）刚刚学到一个新的树形遍历序列叫做 欧拉序。
只要保证每个子节点走完之后有一个回到父节点的路径。
这样就可以依次放入k个人，顺序走完这个序列了，多出来的人，直接输出0即可
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 7;
int n, m;
struct Node {
int u, v, w;
bool operator < (const Node& A) {
return w < A.w;
}
}edge[N];
int fa[N];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void solve() {
n = read(), m = read();
for (int i = 1; i <= m; ++i)
edge[i].u = read(), edge[i].v = read() + 1, edge[i].w = read();
sort(edge + 1, edge + 1 + m);
for (int i = 1; i < N; ++i) fa[i] = i;
int cnt = 0;
ll ans = 0;
for (int i = 1; i <= m; ++i) {
int fu = find(edge[i].u), fv = find(edge[i].v);
if (fu != fv) {
fa[fv] = fu;
++cnt;
ans += edge[i].w;
}
}
if (cnt != n) puts("-1");
else print(ans);
}
int main() {
//int T = read(); while (T--)
solve();
return 0;
} 
京公网安备 11010502036488号