首页 > 其他分享 >题解:CF507C Guess Your Way Out!

题解:CF507C Guess Your Way Out!

时间:2024-08-02 12:17:06浏览次数:11  
标签:Guess end int 题解 long cz Way pow

CF507C Guess Your Way Out! 题解

算法

模拟

思路

按照左右左右的方式先往下找,每次找到一个子节点时就看此节点为根的子树是否包含目标节点,如果包含就继续往下走,不包含说明目标叶子节点在另一边的子树上,那么肯定是先需要把这边的子树遍历完才能换到另一边,所以答案直接加上这个子树的大小。

代码中 \(cz\) 代表操作是左还是右,通过亦或实现取反的操作。注意要开 long long。本题主要需要掌握二叉树的各种性质,基本不需要算法。

示例代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace Ryan
{
    int h, n;
    signed work()
    {
        cin >> h >> n;
        int cz = 0;
        int end = pow(2, h - 1);
        int ans = 0;
        for (int i = h - 1; i >= 0; i--)
        {
            ans++;
            if (!cz)
            {
                if (n > end)
                {
                    ans += (pow(2, i + 1) - 1);
                    if (i)
                        end += pow(2, i - 1);
                    cz ^= 1;
                }
                else if (i)
                    end -= pow(2, i - 1);
            }
            else
            {
                if (n <= end)
                {
                    ans += (pow(2, i + 1) - 1);
                    if (i)
                        end -= pow(2, i - 1);
                    cz ^= 1;
                }
                else if (i)
                    end += pow(2, i - 1);
            }
            cz ^= 1;
        }
        cout << ans << endl;
        return 0;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return Ryan::work();
}

标签:Guess,end,int,题解,long,cz,Way,pow
From: https://www.cnblogs.com/RyanAdam/p/18338489

相关文章

  • HT-018 Div3 构造 题解 [ 黄 ] [ 数学 ] [ 结论 ]
    构造:结论题,gcy数竞大佬tql%%%orz。结论先放结论:如果\(x\bmod4=2\),那么\(x\)无法被表示为\(a^2-b^2\)的形式;除此之外的其他数都可以。证明对\(a^2-b^2\)因式分解,得\(x=(a+b)(a-b)\)。当\(x\bmod2=1\)时包含\(x\bmod4=1\)和\(x\bmod4=3\)的情况。......
  • Educational Codeforces Round 168 (Rated for Div. 2)A——D题解
    EducationalCodeforcesRound168(RatedforDiv.2)A——D题解A.StrongPassword题意:给一个小写字符串密码,添加一个小写字母,使得密码更加复杂。题解:有相同的相邻的字母,再其中间添加不同的字母;如果没有相同的相邻的字母,则最后添加一个字母。#include<bits/stdc++.h>......
  • HT-018 Div3 能量消耗 题解 [ 绿 ] [ 线性 dp ] [ 前缀和优化 ]
    能量消耗:一个前缀和优化dp的大典题,要是数据水一点\(O(n^3)\)都能硬草过去。思路显然,定义\(dp[i]\)为考虑前\(i\)个塔,并且将前面的精灵全部收集的最小代价。于是转移:\[dp[i]=min(dp[i],dp[j]+w(j,i)+c[i])\]其中\(0\lej<i\lem\),\(w(j,i)\)表示收集从塔\(j\)到......
  • CF1987C Basil's Garden 题解
    CF1987CBasil'sGarden题解壹·题目描述有$n$个数字排成一排,接下来每隔一秒进行一次操作:如果$i=n$或$h_i>h_{i+1}$,则第$i$盆花的高度$h_i$将变为$\max(0,h_i-1)$。请问至少经过多少秒后,所有的数字都为$0$。贰·思路分析可以知道,$h_i\leq1$时$h_i←0$。显然可......
  • [题解]P6927 [ICPC2016 WF] Swap Space
    思路显然要按\(a_i,b_i\)的大小关系分类:\(a_i<b_i\):假令有两对数\((a_1,b_1),(a_2,b_2)\),且\(a_1\leqa_2\)。如果\(b_1\geqa_2\)。则按照12的顺序,将带来\(a_1\)的花费,以及\(b_1+b_2\)的额外空间;而按照21的顺序,将带来\(a_2\)的花费,以及\(b_1+b_2......
  • CF553E Kyoya and Train 题解
    Description给定一张\(n\)个点\(m\)条边的无重边无自环的有向图,你要从\(1\)号点到\(n\)号点去。如果你在\(t\)时刻之后到达\(n\)号点,你要交\(x\)元的罚款。每条边从\(a_i\)到\(b_i\),走过它需要花费\(c_i\)元,多次走过同一条边需要多次花费。走过每条边所需......
  • 【问题解决方案】npm install报错问题:npm ERR! - 多种解决方案,总有一种可以解决
    @[toc]1.问题重述安装package.json里面的包,使用npminstall但是报错2.解决方案方案1.确认根目录正确确认自己的目录是根目录(也就是处于./package.json可以找到的位置)例如--根目录----package.json----其他文件----其他文件方案2.确认文件名正确确认自己的pack......
  • P9308 「DTOI-5」#1f1e33 题解
    声明:截止\(2024.8.1\),拿下洛谷最优解最短解,代码长度不到1k。复杂度\(O(n\log\logn)\)。先骂:官方题解菜!这种纯洁的数论题居然敢引入NTT作为标算,说明出题人不会推式子。还有题解区一车\(\log\)的题解凭啥顶那么上面,推的一坨狗屎推出来的复杂度还不优秀。说明:下面除法默......
  • 2024牛客暑期多校训练营6 A.cake(题解)
    A.Cake题意两个人玩游戏,游戏分两阶段第一阶段在一棵有根树上轮流走,走到叶子停止,有根树边上有01标记,记录下走过的01串第二阶段分蛋糕,Oscar按自己的意愿切蛋糕,然后按照第一阶段获得的01串顺序依次拿蛋糕(1代表Grammy拿,0代表Oscar拿)两人都想让自己获得尽量多的蛋糕,......
  • CF2B The least round way
    设\(f_{i,j}\)表示走到点\((i,j)\)获得因数2的最小数量。设\(g_{i,j}\)表示走到点\((i,j)\)获得因数5的最小数量。那么到点\((i,j)\)胃部获得的最小0的个数为\(\min(f_{i,j},g_{i,j})\),因为如果选择数量小的那个因数,另外一个因数的个数一定多于它,就会往......