2019百度之星复赛题解 A.B.C
1001. Diversity
题意
给你一棵n个点的树，对于节点i，你要给它标上一个 [li,ri]之间的数，要求所有边两端节点上标的数字的差的绝对值的总和最大。
解法
一开始以为一边取大一边取小就会最优
其实不对 所以最后写了一遍树形DP
/* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <stack>
#include <cmath>
#include <deque>
#include <queue>
#include <list>
#include <set>
#include <map>
#define line printf("---------------------------\n")
#define mem(a, b) memset(a, b, sizeof(a))
#define pi acos(-1)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef double db;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 2e5+10;
void add(int &x, int y) {
x = (x + y) % mod;
}
ll dp[maxn][2];
vector<int> g[maxn];
ll l[maxn], r[maxn];
void dfs(int root, int x) {
int len = g[root].size();
for(int i = 0; i < len; i++) {
if(g[root][i] == x) continue;
dfs(g[root][i], root);
}
for(int i = 0; i < len; i++) {
if(g[root][i] == x) continue;
dp[root][0] += max(dp[g[root][i]][1] + abs(l[g[root][i]] - r[root]),
dp[g[root][i]][0] + abs(r[g[root][i]] - r[root]));
dp[root][1] += max(dp[g[root][i]][1] + abs(l[g[root][i]] - l[root]),
dp[g[root][i]][0] + abs(r[g[root][i]] - l[root]));
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t, n;
cin>>t;
int u, v;
while(t--) {
for(int i = 0; i < maxn; i++) {
g[i].clear();
}
memset(dp, 0, sizeof(dp));
cin>>n;
for(int i = 0; i < n-1; i++) {
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 1; i <= n; i++) {
cin>>l[i]>>r[i];
}
dfs(1, -1);
ll ans = -1;
for(int i = 1; i <= n; i++){
ans = max(ans, max(dp[i][1], dp[i][0]));
}
cout<<ans<<endl;
}
return 0;
}
1002. Transformation
题意
给你一个二元组(a,b)，支持AB两种操作，分别是将其变成(a,2b−a)和(2a−b,b)。问能否通过大于等于零次操作将其变成(c,d)。
解法
答案一定满足以下规律规律：
c=((x+1)a-xb)
d=((y+1)a-yb)
那么我只要逆推回去即可
判断x和y哪个大，就用哪一种方式逆推回去
/* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <stack>
#include <cmath>
#include <deque>
#include <queue>
#include <list>
#include <set>
#include <map>
#define line printf("---------------------------\n")
#define mem(a, b) memset(a, b, sizeof(a))
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 2000+10;
void add(int &x, int y) {
x = (x + y) % mod;
}
stack<char> ans;
bool isOdd(ll a) {
return a % 2;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--) {
ll a, b, c, d;
cin>>a>>b>>c>>d;
if((a - b) == 0) {
if(a == c && b == d) {
printf("Yes\n\n");
} else {
printf("No\n");
}
continue;
}
ll x = (c - a) % (a - b);
ll y = (d - b) % (b - a);
if(x != 0 || y != 0) { //判断一下 c和d符不符合公式
puts("No");
} else {
x = (c - a) / (a - b) + 1; // a的系数
y = (d - b) / (b - a) + 1; // b的系数
if(x <= 0 || y <= 0) {
puts("No");
continue;
}
bool f = 1;
while(!ans.empty()){
ans.pop();
}
while(c != a || b != d){
if(isOdd(c + d)){
f = 0;
break;
}
if(x > y){
c = (c + d) / 2;
if(isOdd(x - (y - 1))) {
f = 0;
break;
}
x = (x - (y - 1)) / 2;
ans.push('B');
}else {
d = (c + d) / 2;
if(isOdd(y - (x - 1))) {
f = 0;
break;
}
y = (y - (x - 1)) / 2;
ans.push('A');
}
}
if(!f){
puts("No");
}else {
puts("Yes");
while(!ans.empty()){
printf("%c", ans.top());
ans.pop();
}
puts("");
}
}
}
return 0;
}
