题目链接
T1.Barn Tree
T2.Circular Barn
T3.Range Reconstruction
T1
下面均以\(1\)为根来进行分析。
算法思路:
首先,定义一个数组dis
表示当前子树的干草数和与应有的干草数和的差值(多了为正,少了为负)。dis
的求法就是裸的\(DFS\)。
接下来,进行\(DFS\)。
假设现在遍历到了以\(u\)为根的子树。
第一遍遍历\(u\)的所有孩子。如果当前孩子\(dis>=0\),则遍历以当前孩子为根的子树,并将该子树的所有多余干草全部干草上传到该孩子上,并将该孩子的干草上传到\(u\)上。
第二遍遍历\(u\)的所有孩子。如果当前孩子\(dis<0\),则遍历以当前孩子为根的子树,并将\(u\)的与\(-dis\)相等的干草全部干草下传到该孩子上,并在遍历以该孩子为根的子树。
代码实现
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long LL;
const int N = 2E5 + 5;
int n, u, v;
/*
up:pushup the things down:pushdown the things
*/
vector<LL> G[N], x, y, c;
LL h[N], ave, dis[N];
void newop(int from, int to, LL val) {
x.push_back(from);
y.push_back(to);
c.push_back(val);
}
void calc(int u, int f) {
dis[u] = h[u] - ave;
for (int v: G[u]) {
if (v == f) continue;
calc(v, u);
dis[u] += dis[v];
}
}
void dfs(int u, int f) {
for (int v: G[u]) {
if (v == f) continue;
if (dis[v] > 0) {
dfs(v, u);
newop(v, u, dis[v]);
}
if (dis[v] == 0) dfs(v, u);
}
for (int v: G[u]) {
if (v == f) continue;
if (dis[v] < 0) {
h[v] -= dis[v];
newop(u, v, -dis[v]);
dfs(v, u);
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", h + i), ave += h[i];
ave /= n;
for (int i = 1; i < n; i++) {
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
calc(1, 0);
dfs(1, 0);
printf("%d\n", x.size());
for (int i = 0; i < x.size(); i++) printf("%lld %lld %lld\n", x[i], y[i], c[i]);
}
T2
算法思路
我们考虑如果一个人选择了\(4k\)型数,那么这个人必败。
归纳证明:
样例证明,\(4\)为必败态。
假设\(4, 8, \dots, 4k\)均为必败态。
那么\(4(k - 1)\)无法通过减去\(4m\)转移到另一个必败态,因为\(4m\)为合数。
证毕。
所以,\(4k\)必败。
那么对于\(4k+1\)型数,只需找到最大的\(4k+1\)型质数,减去即可,\(4k+3\)型数同理。
对于\(4k+2\)型数,只能转移到\(4k+2\)解决。
这个过程可以边做\(Eratosthenes\)筛,边用\(dp\)来解决。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 1E5 + 5, M = 5E6 + 5;
long long t, n, a[N], m, dp[M];
bool flag[M];
void init() {
int one = 0, three = 0;
for (int i = 2; i * i <= M - 5; i++) {
if (flag[i] == 0) for (int j = i * i; j <= M - 5; j += i) flag[j] = 1;
}
for (int i = 1; i <= M - 5; i++) {
if (!flag[i]) {
if (i % 4 == 1) one = i;
else if (i % 4 == 3) three = i;
}
if (i % 2 == 0) dp[i] = dp[i - 2] + 1;
else if (i % 4 == 1) dp[i] = dp[i - one] + 1;
else if (i % 4 == 3) dp[i] = dp[i - three] + 1;
}
}
int main()
{
init();
scanf("%lld", &t);
while(t--) {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
long long jj = LLONG_MAX, nn = LLONG_MAX;
for (long long i = 1; i <= n; i++) {
if (a[i] % 4 == 0) {
nn = min(nn, (dp[a[i]] / 2ll) * n + i);
}
else {
jj = min(jj, (dp[a[i]] / 2ll) * n + i);
}
}
if (jj < nn) printf("Farmer John\n");
else printf("Farmer Nhoj\n");
}
}
T3
算法思想
思想:暴力(是不是很惊讶?)
我们可以将\(a_1\)确定下来,直接赋值为\(0\)
我们考虑前\(i\)个都确定下来了,来确定第\(i + 1\)个。
第\(i + 1\)个只有两个选择:\(a_i - b_{i, i + 1}\)和\(a_i + b_{i, i + 1}\)。
依次用\(b_{j, i + 1}, j \in [1, i]\)判断即可。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 305;
int n;
long long Distance[N][N], construction[N];
bool Validator(int u) {
for(int i = 1; i < u; i++) {
long long maximum = -0x3F3F3F3F3F3F3F3F, minimum = 0x3F3F3F3F3F3F3F3F;
for (int j = i; j <= u; j++) {
maximum = max(maximum, construction[j]);
minimum = min(minimum, construction[j]);
}
if (maximum - minimum != Distance[i][u]) return false;
}
return true;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
scanf("%lld", &Distance[i][j]);
}
}
construction[1] = 1;
for (int i = 2; i <= n; i++) {
construction[i] = construction[i - 1] + Distance[i - 1][i];
if (Validator(i)) continue;
construction[i] = construction[i - 1] - Distance[i - 1][i];
}
for (int i = 1; i <= n; i++) {
if (i != n) printf("%lld ", construction[i]);
else printf("%lld", construction[i]);
}
return 0;
}
标签:子树,int,2022USACO,long,干草,4k,DEC,Silver,dis
From: https://www.cnblogs.com/easonhe/p/2022USACO-DEC-Silver.html