(CF 635 (Div2))
(A.)
给定 (a, b, c, d)，构造 (x, y, z) 满足 (aleq xleq bleq yleq cleq zleq d)，且 (x, y, z) 能构成三角形
贪心，(x = b, y = z = c)
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], "
"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 2e5 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
int t, n, a[N];
inline int read()
{
char c = getchar();
int ans = 0, f = 1;
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
return ans * f;
}
int main()
{
t = read();
while(t--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
printf("%d %d %d
", b, c, c);
}
return 0;
}
(B.)
给定一个 (x)，对 (x) 可以进行两个操作
- (x) 变为 (leftlfloorfrac{x}{2} ight floor + 10)
- (x) 变为 (x - 10)
第 (1) 个操作最多用 (n) 次，第 (2) 个操作最多用 (m) 次
询问是否可以在有限次数内让 (x) 小于等于 (0)
一个显然的 (observation) 是，不能一直用操作 (1)，那样会导致 (x) 不降反升
暴力跑循环，如果当前 (x) 可以被剩下的 (m) 次操作 (2) 完结，那么就可以成功；其他情况都无法成功
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], "
"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 1e5 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
int t, x, n, m;
inline int read()
{
char c = getchar();
int ans = 0, f = 1;
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
return ans * f;
}
int main()
{
t = read();
while(t--) {
x = read(), n = read(), m = read();
int f = 0;
while(1) {
if(x <= m * 10) {f = 1; break;}
else {
if(n) x = x / 2 + 10, n--;
else break;
}
}
if(!f) puts("NO");
else puts("YES");
}
return 0;
}
(C.)
给定一棵 (n) 个节点的无根树，选定 (1) 为根
任选 (k) 个节点作为工业区，剩下的 (n - k) 个节点作为旅游区，每个工业区节点派一个大使，定义一个大使的 (happiness) 为其前往点 (1) 的最短路上经过的旅游区的数量
求所有大使 (happiness) 和的最大值
对于 (i) 节点，定义 (dep[i]) 是 (i) 的深度，(sub[i]) 是 (i) 子节点的个数
考虑每个节点 (i) 对答案的贡献
(1.) 如果 (i) 是叶子，贡献即为 (dep[i] = dep[i] - 0)
(2.) 如果 (i) 是根，贡献即为 (dep[i] - sub[i])
第 (2) 点的简易正确性证明：
考虑 (i) 为根节点
若当前选定 (i)，那么在 (i) 被选取之前，其所有子节点都已经被选取，否则可以选取他的子节点，那样的话深度更大，子节点个数更小，对答案贡献更大
(dfs) 预处理深度和子节点个数，然后对 (dep[i] - sub[i]) 排序取前 (k) 个和即可
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], "
"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 2e5 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
inline int read()
{
char c = getchar();
int ans = 0, f = 1;
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
return ans * f;
}
int t, n, k;
vector<int> g[N];
int a[N], dep[N], sub[N];
void dfs(int u, int v)
{
for(auto i: g[u]) {
if(i != v) {
dep[i] = dep[u] + 1;
dfs(i, u);
sub[u] += 1 + sub[i];
}
}
}
int main()
{
n = read(), k = read();
for(int i = 1; i < n; ++i) {
int a, b;
a = read(), b = read();
g[a].push_back(b), g[b].push_back(a);
}
dfs(1, 0);
for(int i = 1; i <= n; ++i)
a[i] = dep[i] - sub[i];
sort(a + 1, a + 1 + n);
reverse(a + 1, a + 1 + n);
LL ans = 0;
for(int i = 1; i <= k; ++i)
ans += 1LL * a[i];
printf("%lld
", ans);
return 0;
}
对于无根树，任意一个节点都可以作为根，无需讨论