比赛总结
手速场，开场 $30$ 分钟写完 $A, B, C$，开始看 $D$， 结论推出来的但是感觉很特异，没敢写，自己演自己了。
A.Filling Diamonds
题意
给定 $n$ 个菱形，要将它们组成一个钻石，问所有的摆放方案
题解
可以发现每个钻石，只有一个菱形是立着的，找到这个钻石中有几个是立着的就行了。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,int> P;
const int MAXN = 1e6 + 5;
const int INF = 0x3f3f3f3f;
int a[MAXN];
void solve() {
int n;
cin >> n;
cout << n << endl;
}
signed main() {
int T;
cin >> T;
//T = 1;
while(T--) {
solve();
}
return 0;
}
B.Sorted Adjacent Differences
题意
给定数组 $a$， 让你对 $a$ 进行排序使得序列满足
$$
|a_1 - a_2| \leq |a_2 - a_3|...... \leq |a_{n-1} - a_n|
$$
题解
对数组进行排序， 从中间往两边取即可
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,int> P;
const int MAXN = 1e6 + 5;
const int INF = 0x3f3f3f3f;
int a[MAXN];
vector<int> b;
void solve() {
int n;
cin >> n;
for(int i = 1;i <= n;i++)
cin >> a[i];
sort(a+1, a+1+n);
int l = 1, r = n, op = 0;
for(;l <= r;){
if(op == 0)
b.push_back(a[r]), r--;
else
b.push_back(a[l]), l++;
op ^= 1;
}
//sort(b.begin(), b.end());
for(int i = n-1;i >= 0;i--)
cout << b[i] << " ";
cout << endl;
b.clear();
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T;
cin >> T;
//T = 1;
while(T--) {
solve();
}
return 0;
}
C.Powered Addition
题意
给你一个数组 $a_n$，你可以在第 $x$ 秒选一些元素让它们加 2^(x-1) 询问最短的时间使得数组变成单调不降
题解
只需要找到最大得差值 $max(a_i - a_j) (i < j)$ 然后取 $log$即可
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,int> P;
const int MAXN = 1e6 + 5;
const int INF = 0x3f3f3f3f;
int a[MAXN];
vector<int> b;
void solve() {
int n;
cin >> n;
for(int i = 1;i <= n;i++)
cin >> a[i];
int mx = a[1], cnt = 0;
for(int i = 2;i <= n;i++){
if(mx > a[i])
cnt = max(cnt, mx - a[i]);
mx = max(mx, a[i]);
}
if(cnt == 0)
cout << cnt << endl;
else
cout << (int)log2(cnt) + 1 << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T;
cin >> T;
//T = 1;
while(T--) {
solve();
}
return 0;
}
D.Edge Weight Assignment
题意
给定一有 $n$ 个点 $n-1$ 条边的无根树，对该树的边权进行赋值。赋值的边权要保证，该树的任意两个叶子节点的简单路径上的边权逐位异或和为 $0$， 且权值 $v_i > 0$。问该树，最多能填多少不同的权值， 最少能填多少不同的权值
题解
-
最少：
- 针对两个叶子节点为偶数的情况，如 $1$ -> $6$，最小的情况则可以为全填一样的数字即可
- 针对两个叶子节点为基数的情况，如 $1$ -> $5$，奇数的路径必然是对称的，所以最小只需要填三个不同的数字即可
规律一：当这颗树的任意两叶子节点的路径为奇数时最小为$3$， 否则为$1$
-
最多：
- 由于题目中已知， 边权可以无穷大， 所以无论路径长度是奇是偶，都可以任意填写， 在路径的最后一条边上， 将前面的边权一次性异或为 $0$，所以最大边值为 $n-1$。但是观察 $1$ -> $2$ 的路径， 发现两人公用一个父亲节点， 这种情况下，两天边权必须相等所以要减去一个数字，有几个就要减几个，即可。
规律二：最多能赋值 $n-1-$ （连在同一个父亲节点上的叶子节点的个数 - 1）
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,int> P;
const int MAXN = 1e6 + 5;
const int INF = 0x3f3f3f3f;
vector<int> E[MAXN];
int cnt[MAXN], vis[MAXN];
bool flag = true;
void dfs(int u, int fa, int dep){
if(dep % 2 == 1 && cnt[u] == 1){
flag = false;
}
for(int i = 0;i < E[u].size();i++){
if(!vis[E[u][i]] && E[u][i] != fa)
dfs(E[u][i], u, dep+1);
}
}
void solve() {
int n;
cin >> n;
for(int i = 1;i < n;i++){
int u, v;
cin >> u >> v;
cnt[u]++;
cnt[v]++;
E[u].push_back(v);
E[v].push_back(u);
}
int maxx = n - 1, pos;
for(int i = 1;i <= n;i++){
if(cnt[i] == 1){
if(vis[E[i][0]])
maxx--;
else
vis[E[i][0]] = 1;
pos = i;
}
}
memset(vis, 0, sizeof(vis));
dfs(pos, 0, 0);
if(flag)
cout << 1 << " " << maxx << endl;
else
cout << 3 << " " << maxx << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T;
//cin >> T;
T = 1;
while(T--) {
solve();
}
return 0;
}
待补
E