【Codeforces】1617-E Christmas Chocolates 题解

题目大意

有 n ( 2 ≤ n ≤ 1 0 5 ) n(2 \le n \le 10^5) n(2≤n≤105)个正整数的数组 a n , 1 ≤ a i ≤ 1 0 9 a_n,1 \le a_i \le 10^9 an​,1≤ai​≤109。

对于每个数 a i a_i ai​,可以进行如下操作: 找到一个自然数 k k k,满足 2 k ≥ a i 2^k \ge a_i 2k≥ai​,使 a i = 2 k − a i a_i = 2^k - a_i ai​=2k−ai​。

通过数次这种操作,总可以使得变化后 a i a_i ai​等于其它任意一个数 a j a_j aj​。

那么请问,把哪两个数的变成相同所需次数的最小值最大?

题目链接

思路

这种操作的本质就是,二进制下选择 a i a_i ai​的任意一个比最高位 1 1 1的位,把它后面的所有位数取反,比如 1001 1001 1001,选择 100000 100000 100000这一位,转换后变成 010110 010110 010110,通过数次这种操作,是可以把一个数变成 0 0 0的,也可以从 0 0 0开始构造起来每一个数的。

但是呢,从 0 0 0开始往上构造比较困难,所以我们不如考虑这个数怎么用最短的方法变成0。在二进制下,每次选择最高位 1 1 1前面的那一位进行反转,这么做就是最快的方法,十进制下就是找到最小的 k k k,使得 2 k ≥ a i 2^k \ge a_i 2k≥ai​,然后 a i = 2 k − a i a_i = 2^k - a_i ai​=2k−ai​。

我们先观察一下样例的变化 6 → 2 → 0 → 1 → 7 → 9 6 \rightarrow 2 \rightarrow 0 \rightarrow 1 \rightarrow 7 \rightarrow 9 6→2→0→1→7→9,是不是有点像在遍历边?实际上这道题的重点就是把这转化为图。

其实也不一定所有情况都要经过 0 0 0,比如 7 , 9 7,9 7,9但 9 9 9在向 0 0 0经过的时候,是会经过 7 7 7的,所以这种情况也是会被计算的。

那么我们在建立新的点的时候,对于每个 a i a_i ai​,按照把这个数最快变成 0 0 0的方式去建立新的点,如果遇到已经建好的点,那就停止,进行下一个。比如 6 , 9 , 10 6,9,10 6,9,10。 10 10 10在转化成 0 0 0的时候会经过 6 6 6,所以遇到 6 6 6之后就没必要继续建立新的点了(因为后续操作都一样),并且意味着 6 , 10 6,10 6,10之间的转化不需要经过 0 0 0了。

那么答案就是求树的直径

为什么一定是一个树呢?假设有 x , y , z x,y,z x,y,z三个点(值各不相同), x , y x,y x,y相连, x , z x,z x,z相连,那么 y , z y,z y,z一定不会相连。

证明:设 x + y = 2 m , x + z = 2 n x + y = 2^m,x + z = 2^n x+y=2m,x+z=2n,则 y + z = 2 m + 2 n − 2 x y + z = 2^m + 2^n - 2x y+z=2m+2n−2x,是没法构造出 2 m + 2 n − 2 x = 2 l 2^m + 2^n - 2x = 2^l 2m+2n−2x=2l的。

代码

G [ x ] G[x] G[x]是个点 x x x的出边, d [ x ] d[x] d[x]是在两次 d f s dfs dfs求直径中点 x x x离根节点的距离,用 m a p < x , y > map<x,y> map<x,y>去储存权值为 x x x的点在图中的编号为 y y y

#include <cstdio>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
 
const int maxN = 2e5 + 7;
 
int n, a[maxN], cnt, d[maxN * 31];
vector<int> G[maxN * 31];
unordered_map<int, int> mp;
 
inline int GetFa(int x)
{
    int t = 0;
    while((1 << t) < x)
        t++;
    return (1 << t) - x;
}
 
inline void dfs(int x, int fa)
{
    d[x] = fa ? d[fa] + 1 : 0;
    for(int i = 0; i < G[x].size(); ++i)
        if(G[x][i] != fa)
            dfs(G[x][i], x);
}
 
int main()
{
    scanf("%d", &n);
    mp[0] = cnt = 1;
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        int p = a[i];
        if(mp[p]) continue;
        mp[p] = ++cnt;
        int nxt = GetFa(p);
        while(!mp[nxt]) {
            mp[nxt] = ++cnt;
            G[mp[nxt]].emplace_back(mp[p]);
            G[mp[p]].emplace_back(mp[nxt]);
            p = nxt; nxt = GetFa(p);
        }
        G[mp[nxt]].emplace_back(mp[p]);
        G[mp[p]].emplace_back(mp[nxt]);
    }
    int st = 1, ed = 1;
    dfs(mp[a[1]], 0);
    for(int i = 2; i <= n; ++i)
        if(d[mp[a[st]]] < d[mp[a[i]]])
            st = i;
    dfs(mp[a[st]], 0);
    for(int i = 2; i <= n; ++i)
        if(d[mp[a[ed]]] < d[mp[a[i]]])
            ed = i;
    printf("%d %d %d\n", st, ed, d[mp[a[ed]]]);
    return 0;
}
上一篇:1043. 输出PATest


下一篇:SQL Tuning 基础概述02 - Explain plan的使用