牛客小白月赛 42 官方题解

恭喜上百位同学 AK ! ! 你们太强辣 ! !

A 冰狱寒岚

考虑找规律,第 10241024 个位置是 1024-1024,也就是说第 20482048 个位置就又变回了 00

据此循环节是 20482048,首先令 nn mod2048n\leftarrow n~\bmod2048

然后考虑分类讨论:

  1. 0n10230\le n\le1023 时:直接输出 nn 即可。

  2. 1024n20471024\le n\le2047 时:观察到 n=ans+2048n=ans+2048,直接输出 n2048n-2048 即可。

B 光之屏障

考虑预处理出所有 [1,109][1,10^9]22 的幂次,即:

1,2,4,8,16,,536870912(229)1,2,4,8,16,\cdots,536870912(2^{29})

接着考虑对于每组询问,直接枚举每个答案 z=2i(0i29)z=2^i(0\le i\le29) 是否在 [x,y][x,y] 范围内即可。

预处理数组 aia_i 表示 2i2^i,一开始 a0=1a_0=1,以后每一项 ai=2×ai1a_{i}=2\times a_{i-1},递推即可。

查询时枚举 ii,直接提取出 aia_i 的值判断其是否满足 xai and aiyx\le a_i~\text{and}~a_i\le y 即可。

C 寒潭烟光

2n+12\sim n+1F\mathbf F 值为 AA1n+11\sim n+1F\mathbf F 值为 BB

根据定义可以知道:

A=x2+(x2+x3)++(x2+x3++xn+1)n=nx2+(n1)x3++1xn+1n   (α)\begin{aligned}A&=\dfrac{x_2+(x_2+x_3)+\cdots+(x_2+x_3+\cdots+x_{n+1})}{n}\\&=\dfrac{\color{red}n\cdot x_2+(n-1)\cdot x_3+\cdots+1\cdot x_{n+1}}{n}~~~(\alpha)\end{aligned}

同理:

B=(n+1)x1+nx2+(n1)x3++1xn+1n+1   (β)B=\dfrac{(n+1)\cdot x_1+\color{red}n\cdot x_2+(n-1)\cdot x_3+\cdots+1\cdot x_{n+1}}{n+1}~~~(\beta)

联立 (α),(β)(\alpha),(\beta) 两式:

B=An+(n+1)x1n+1B=\dfrac{A\cdot n+(n+1)\cdot x_1}{n+1}

D 金蛇狂舞

考虑 xx 的变化,阶乘可以使其数值大幅增加,而开方不论上取整下取整,均会使其数值大幅减少(但不如阶乘明显)。

对于 101810^{18},连续 55 次开根才能使其到达 7\le7 的位置,算上 22 次阶乘恰好是 77 步。

据此我们知道,当 xx 的值能使其一次阶乘之后超过 101810^{18} 我们就可以剪枝。

直接考虑 BFS(广度优先搜索),当 xx 很大时合理剪枝即可。

E 暗灭侵蚀

结论:每次以最左边的 aa 向右跳即可。

证明:考虑分别设 A=ab,B=bcA=|a-b|,B=|b-c|

一次以最左边向右的步,本质是将距离变成了 (B,A+B)(B,A+B)

而以中间向右的步,本质上是将距离变成了 (A+B,B)(A+B,B)

由于坐标增长的速率显然与相对距离呈正相关,所以前者的能使 a,b,ca,b,c 坐标更靠前方式显然更优。

F 火凤燎原

sol:https://www.luogu.com.cn/paste/vg035rgp

对于一个点 uu,假设 uu 的孩子结点有 kk 个,它们分别是 v1kv_{1\cdots k},首先特判掉 k<3k<3 不产生贡献的情况。

然后考虑枚举点 vv 不作为 单点的子树,作为链的起点:

  • 此时这个 vv 对于点 uu 的贡献,是以 vv 为根的子树大小减一(链的长度不少于 22,所以 vv 自己作为链的情况需要去除)。

考虑列出式子:

  for each vsize[v]1=  n1du[u]\begin{aligned}&~~\sum_{for~each~v}size[v]-1\\=&~~n-1-du[u]\end{aligned}

其中 size[v]size[v] 表示以 vv 为根的子树大小,du[u]du[u] 表示点 uu 的度。

这个等式就是考虑容斥,把不可能作为“链”的末端的点(所有与 uu 直接相连的点和 uu 本身)去掉即可。

总复杂度 O(n)O(n)

用等式左边直接做换根 dp 是内测时很受欢迎的解法,但我这个解法好写多了,不是吗?

std

A 冰狱寒岚

int main(){
    int n = init();
    while (n--) {
        int x = init();
        x %= 2048;
        if (x > 1023) print(x - 2048), putchar(' ');
        else print(x), putchar(' ');
    }
}

B 光之屏障

int a[31];
int main(){
    for (int i = 0; i < 31; ++i)
        a[i] = 1 << i;
    int T = init();
    while (T--) {
        int x = init(), y = init();
        int ans = -1;
        for (int i = 0; i < 31; ++i)
            if (x <= a[i] && a[i] <= y)
                ans = a[i];
        print(ans), putchar('\n');
    }
}

C 寒潭烟光

#define int long long
signed main(){
    int T = init();
    while (T--) {
        int n = init(), Tn = init(), x1 = init();
        print((n * Tn + (n + 1) * x1) / (n + 1)), putchar('\n');
    }
}

D 金蛇狂舞

#define int long long
int factorial(int n){
    if (n == 0) return 1;
    return n * factorial(n - 1);
}
std::map<int, int>dis; std::queue<int>queue;
signed main(){
    int x = init(), y = init();
    dis[x] = 0; queue.push(x);
    while (!queue.empty()) {
        int u = queue.front(); queue.pop();
        if (dis[u] >= 7 || u == y) break;
        if (u <= 19) {
            int v = factorial(u);
            if (!dis.count(v)) dis[v] = dis[u] + 1, queue.push(v);
        }
        int w1 = floor(sqrt((double) u)), w2 = ceil(sqrt((double) u));
        if (!dis.count(w1)) dis[w1] = dis[u] + 1, queue.push(w1);
        if (!dis.count(w2)) dis[w2] = dis[u] + 1, queue.push(w2);
    }
    if (dis.count(y)) print(dis[y]), putchar('\n');
    else print(-1), putchar('\n');
}

E 暗灭侵蚀

#define int long long
struct Node{
    int a, b, c;
};
Node R(Node p){
    return (Node){p.b, p.c, p.c * 2 - p.a};
}
signed main(){
    int T = init();
    while (T--) {
        int a = init(), b = init(), c = init(), N = init();
        Node p = (Node){a, b, c};
        int ans = 0;
        while (p.c < N) ++ans, p = R(p);
        print(ans), putchar('\n');
    }
}

F 火凤燎原

typedef long long ll;
int main(){
    int T = init();
    while (T--) {
        memset(du, 0, sizeof(du));
        int n = init();
        for (int i = 1; i < n; ++i)
            ++du[init()], ++du[init()];
        ll ans = 0;
        for (int i = 1; i <= n; ++i)
            if (du[i] >= 3)
                ans += n - 1 - du[i];
        print(ans), putchar('\n');
    }
}

彩蛋

Problem A &\& Problem B

Problem D &\& Problem E

      ~~~~~~ 爱,是生命的扩充。
      ~~~~~~ 而且,是最有效、最良性的扩充。
      ~~~~~~ 爱上一个人,你的生命就结束了孑然一身的孤独状态,至少扩充了一倍。爱的对象有家人,有朋友,有职业,有单位,那就还会爱屋及乌,使爱意广泛弥散开来。因为相关的这一切都会让你入心,让你微笑,已经成为你生命的延伸地带。
      ~~~~~~ 如果你爱的人相当优秀,那事情就更大了。你从他的谈吐,亲近了冷漠历史、陌生远方;你从她的容貌,拥有了远山浅黛、秋云初雪。
      ~~~~~~ 更重要的是,一旦投入了这样的爱,你们就立即能与自古以来中外一切表述人间至情的作品心心相印。也就是说,你们的生命扩充到了人类最美好的领域,无边无际。

杂谈

感谢 CSP_Sept 提供 C 题的优质 idea。

D 题 idea 来源于《数学万花筒》系列,但是记不清是哪一本了。

事实上 E 题有个 “小哥哥”,但它并不是 D 题,而是这个题:https://www.luogu.com.cn/problem/U174241

这个结构的思路来源,是一道古典的 LCA 练习题,一些老年人都知道。

F 题 idea 来源于《八仙过海》系列树论题单,是不是很带劲?

一些个表情包

赛后评价

征集赛后评价:

  1. 题目描述需要改进的地方?(除广播过的内容之外,统一回复下 F 题关于“度”的定义,当时内测时经群内讨论,由于互联网上有很多关于该概念的定义,并且说法一致,并无争议,因此内测群当时即认为不需要解释,若因此为您带来不便,深感抱歉)
  2. 数据是否有过水的地方?(根据各题的性质,可能只有 F 题需要卡的没卡掉吧?)
  3. 答疑是否有需要改进的地方?(很重要)
  4. 题目名字和题目背景写的咋样啊?(很重要很重要)
  5. 其他想对出题人说的话,仅限与这场比赛的赛题或其背景有关的。

赛后第三天会在楼下以回复的形式展示本次调查的结果,为了之后的比赛做得更好,请您多多提出建议!感谢!

均为非必答题 ^_^

The Last but not least