比赛总结
手速场,开场 $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$ 进行排序使得序列满足
题解
对数组进行排序, 从中间往两边取即可
代码
#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