首页 > 其他分享 >P10220 [省选联考 2024] 迷宫守卫

P10220 [省选联考 2024] 迷宫守卫

时间:2024-03-04 11:33:52浏览次数:24  
标签:const 省选 ll P10220 int cost 联考 dp

二分+贪心+DP。跟 D1T2 思路有点类似,反正很简单。

复杂度大约是 \({\rm O}(n^22^n)\)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const ll inf = 1e18;
int T, n, q[N]; ll K, w[N];
vector<int> Q;
ll dp(int o, int d, int ub) {
    if (d == 0)
        return q[o ^ (1 << n)] <= ub ? inf : 0;
    ll left = dp(o << 1, d - 1, ub), right = dp(o << 1 | 1, d - 1, ub);
    return left + min(w[o], right);
}
void solve(int o, int d, ll &k) {
    if (d == 0) {
        Q.push_back(q[o ^ (1 << n)]);
        return;
    }
    int l = 1, r = 1 << n;
    ll delta = 0;
    while (l < r) {
        int mid = l + r >> 1;
        ll cost = dp(o, d, mid);
        if (cost <= k) l = mid + 1, delta = cost;
        else r = mid;
    }
    Q.push_back(l);
    k -= delta;
    int u = o << d;
    while (q[u ^ (1 << n)] != l) u++;
    for (int i = 0; i < d; i++, u >>= 1) {
        ll cost = dp(u ^ 1, i, l);
        if (u & 1)
            k += cost;
        else {
            k += min(cost, w[u >> 1]);
            if (k < cost) k -= w[u >> 1];
        }
        solve(u ^ 1, i, k);
    }
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%lld", &n, &K);
        for (int i = 1; i < 1 << n; i++)
            scanf("%lld", &w[i]);
        for (int i = 0; i < 1 << n; i++)
            scanf("%d", &q[i]);
        Q.clear();
        solve(1, n, K);
        for (int v : Q) printf("%d ", v);
        putchar('\n');
    }
    return 0;
}

标签:const,省选,ll,P10220,int,cost,联考,dp
From: https://www.cnblogs.com/ac-evil/p/18051472

相关文章

  • LY1156 [ 20230320 CQYC省选模拟赛 T3 ] 集结
    题意平面上\(n\)个点,每个点按照曼哈顿距离移动。要求在\(m\)时刻后,所有点都处于同一位置。求方案数。Sol平凡地,考虑曼哈顿距离转切比雪夫距离。这样\(x\)和\(y\)就完全独立了。考虑先算\(x\)的贡献,再算\(y\)的贡献。判断一下是否能到当前的\(x\)或\(y\)就......
  • 联合省选2024游记/退役记
    等到风吹过树梢,等到蝴蝶扇动翅膀,等到鹿在林间漫步,等到鲸吞吐海洋。等到历尽千帆,我们再次相逢。Day-4做了一个梦。梦中的自己出现在跑道上,一声哨响过后,奋力向前奔跑。但胸口仿佛负千斤,被压得胸闷,被挤得气短,逐渐远远落于众人身后。醒来时才发觉,胸口的大石,是需要自己移除的......
  • 爆零记——2024省选篇
    这是我短暂的不到半年的OI生涯中第一次爆零。不过我知道这绝对不会是最后一次的:)\[Day\;-1\]瞄了一眼各种板子,唯独没看数论。\[Day\;1\]上来先看了一眼题目,觉得T1T2是可做题。觉得T1简单,先写T1。然后写了将近两个半小时之后发现自己看错题了……题目:\[\sum_{i=0}^{m-1}(......
  • NOI2023联合省选 HE省选体验
    写在前面照了挺多照片,本来只想传照片不写文字的,但博客园只让传小于等于2MB的照片(这大小是个手机照的照片都传不上去吧),那好吧,我就写写;Day0出发时还是很激动的,但没有CSP和NOIP那么紧张(那两篇等以后看看再写吧);熟悉的大巴,熟悉的路线(毕竟也是第三次了),确实勾起了很多回忆;大巴上没......
  • noi省选体验赛游记
    3.1上午早上吃完饭先拿了手机然后上了节奥赛课,十点左右我们就出发了,先坐大巴到德州,中午自己安排吃饭,我,w1210,cpa,zhengchenxi坐一起吃的巴拉永和,盖饭+虾饺+蒸饺,吃完自己坐高铁到秦皇岛,然和我们集合又坐大巴去住了高档的首旅京伦(晚上打车出去转,司机说你们是学生吧,怎么还住上首旅京伦......
  • NOI2024联合省选 游寄
    day-62024/2/24元宵节下午去黄河北玩的路上发现没进NOIP的可以去省选锻炼,而且就在zzc的捞胆位——山师附中,就填了报名表交了上去,期待CCF能让我去。day02024/3/1等了一周,中午终于下通知了,但选Windows的被发配到山师二附中了。激动得很。晚上5:15从学校窜了出来,......
  • 省选?
    ......
  • 省选日寄
    省选的前几天莫名有些害怕,听别人说要带枕头和睡袋。day0晚上放学回家,为了早上多睡会精神饱满,在开发区订了酒店,晚上恶补了考试机器操作流程。(感谢yxcat提供的“指北”)晚上狼狈地背着板子。day1早上六点半醒的,吃饭,去考场拿到了准考证。当然,第一天的考试非常劲爆。打开机器以后......
  • [省选联考 2024] 魔法手杖
    退役三年选手回来做了下~这题直观感觉很吓人,其实看到异或就可以往Trie树上思考了。这题有两个未知量\(S\)和\(x\),其中\(S\subseteq[n]\),\(x\in[0,2^k)\cap\Z\),状态过于复杂,肯定不能枚举,从答案的角度考虑。首先直观感受是有点像二分,其实我们可以从高位往低位确定答案\(ans......
  • 考完省选神志不清写的考场技巧
    原本写在文本文档里的,懒得改,就发纯文字了写作思路混乱,想到什么写什么 总:先想正解再想部分再冲正解再打暴力再打部分再乱搞随机化:平面随机旋转、随机排序随机游走,序列随机排序随机染色分组,随机染色异或哈希想不出来考虑图论建模,万一图论秒了?时空卡瓶颈了?考虑......