Codeforces Round#633(Div2)解题报告

Codeforces Round#633(Div2)解题报告

比赛总结
手速场,开场 $30$ 分钟写完 $A, B, C$,开始看 $D$, 结论推出来的但是感觉很特异,没敢写,自己演自己了。
Snipaste_20200413_170944.png

A.Filling Diamonds

题意

给定 $n$ 个菱形,要将它们组成一个钻石,问所有的摆放方案

题解

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];

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$。问该树,最多能填多少不同的权值, 最少能填多少不同的权值

题解

  • 最少
    最小偶数.png

    • 针对两个叶子节点为偶数的情况,如 $1$ -> $6$,最小的情况则可以为全填一样的数字即可

最小奇.png

  • 针对两个叶子节点为基数的情况,如 $1$ -> $5$,奇数的路径必然是对称的,所以最小只需要填三个不同的数字即可

规律一:当这颗树的任意两叶子节点的路径为奇数时最小为$3$, 否则为$1$


  • 最多
    最大偶.png

    • 由于题目中已知, 边权可以无穷大, 所以无论路径长度是奇是偶,都可以任意填写, 在路径的最后一条边上, 将前面的边权一次性异或为 $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