首页 > 其他分享 >[省选联考 2024] 魔法手杖

[省选联考 2024] 魔法手杖

时间:2024-10-09 19:48:42浏览次数:8  
标签:min 省选 res mid 2024 dep oplus now 联考

一年之后再看好歹是会双log做法的84分的,虽然可能被卡常

首先显然有 \(x\oplus y\le x+y\)。

对于一个最优的方案 \(S,x\) 你显然如果不影响 $\oplus $ 部分的最值的话移走的最优的。

所以我们只会将会影响 $\oplus $ 部分最值的留在 \(S\)。

考虑二分答案 \(mid\),判断有没有 \(\ge mid\) 的方案。

则因为 \(x\oplus y\le x+y\),所以事实上有:

\[mid\le \min(\min_{i\in S}(a_i+x),\min_{i\notin S}(a_i\oplus x))\implies mid\le \min(\min (a_i+x),\min_{i\notin S}(a_i\oplus x)) \]

而那么在满足 \(x\ge mid-a_{\min}\) 的条件之下,如果不满足 \(a_i\oplus x\ge mid\),则必然需要加入 \(S\),且尽可能少加入。

则可以得到存在合法方案的充要条件是:

\[\exists x\in [mid-a_{\min},2^k-1],\sum_{a_i\oplus x<mid}b_i\le m \]

考虑将 \(a_i\oplus x\) 与 \(mid\) 作比较,感觉 \(x\) 很容易贪心地填 \(1\)。

转化对象,以 \(a_i\) 为主元。

感觉如果有 \(a_i\oplus x<mid\),那么显然可以数位DP划分出 $\log $ 个区间,那么就可以变成区间加,然后全局最小值查询了。

这样就得到了 $3\log $ 做法

优化?

其实还是对应了 \(trie\) 上的点,所以可以变成 \(trie\) 上的单点加全局 \(\min\) 维护。

感觉还是容易的,得到了 $2\log $ 做法。

然后我们需要一个后缀 min,可以实现

考虑Trie的实现细节

其实是看 \(mid\) 的每一位和 \(x\) 当前的每一位,然后统一算所有走到这里的 \(a\) 的贡献,其实这个 \(a\) 应该是在子树内部。

所以我们需要维护一个子树内 \(b\) 的和。

  • \(bit(mid)=1\),则

    取 \(x=1\) 相当于继续递归左子树,而左子树可以直接加上右子树的 \(b\) 了

    取 \(x=0\) 相当于继续递归右子树,而右子树可以直接加上左子树的 \(b\) 了。

  • \(bit(mid)=0\),则

    取 \(x=1\) 相当于继续递归右子树,左子树已经解决

    取 \(x=0\) 相当于继续递归左子树,右子树已经解决

所以可以子树内维护当前位置 \(mid\) 是 \(1\),更低位置全 \(0\) 在子树内是否有解,也就是要求 \(x\ge mid-a_1\),所以我们维护有解的最大 \(x\)?

我们不妨设一个 \(sol(p,mid,dep,now,mna,sumb)\)

也就是当前划分到的集合 \(S\) 里的 \(mna\),当前节点是 \(p\),深度 \(dep\),当前得到的答案是 \(mid\),当前填的 \(x\) 是 \(now\),当前已经得到了 \(sumb\) 的加法标。

枚举当前 \(mid\) 和 \(now\) 怎么取的 \(4\) 类情况讨论即可

ll sol(int p,int dep,ll mid,ll now,ll mna,int sumb){
    if(sumb>m)return 0;
    if(dep<0)return mid;
    ll res=0;
    //mid=1,now=1,递归左子树,算上右子树b
    //mid+=pw[d],now+=pw[d]
    int lc=ch[p][0],rc=ch[p][1];
    ll lmna=min(ma[rc],mna),rmna=min(ma[lc],mna);
    if(pw[dep]+now+pw[dep]-1+lmna>=mid+pw[dep]){
        res=max(res,sol(lc,dep-1,mid+pw[dep],now+pw[dep],lmna,sumb+sb[rc]));
    }
    //mid=1,now=0,递归右子树,算上左子树b
    if(now+pw[dep]-1+rmna>=mid+pw[dep]){
        res=max(res,sol(rc,dep-1,mid+pw[dep],now,rmna,sumb+sb[lc]));
    }
    if(res>0)return res;
    //mid=0,now=1,递归右子树,左子树无贡献,mna无需更新
    if(pw[dep]-1+pw[dep]+now+mna>=mid){
        res=max(res,sol(rc,dep-1,mid,now+pw[dep],mna,sumb));
    }
    if(pw[dep]-1+now+mna>=mid){
        res=max(res,sol(lc,dep-1,mid,now,mna,sumb));
    }
    return res;
}

然后优先 \(mid\) 是 \(1\) 的解,大力递归就好了。我们每一层根据 \(mna+now\ge mid\) 来减枝,可以保证每次往下搜的时候只要能够递归就可以得到解,所以每个点只会递归一次,复杂度 \(O(Tnk)\)

这贪心是真NB

这个题涉及到了很多技巧:

  • 贪心将不会影响答案的东西移走,使最优方案更容易满足边界条件
  • 整体与单体的视角转化,\(\sum_{a_i\oplus x<mid}b_i\) 从枚举 \(x\) 单体——整体计算变成对于每个 \(a_i\) 的单体整体统计贡献,有时候正难则反。
  • 限制条件的解决形式,如 \(x\ge [mid-a_{\min},2^k-1]\) 不用再计算单 \(a_i\) 贡献时考虑边界,而是在贡献完之后整体照边界
  • 位运算题目二分答案往往可以被按位贪心讨论简化掉

标签:min,省选,res,mid,2024,dep,oplus,now,联考
From: https://www.cnblogs.com/spdarkle/p/18455028

相关文章

  • 2024CSP前集训10.9
    不想学东西了,,,T1普及题,之前还做过,没啥好说的。T295kmp不对,挂了5分。莫队奇偶性优化还是要加的。对\(s_{i,\dots,n}\)跑kmp,也就是跑了\(n\)遍,答案是: while(m--){ intl=read(),r=read(); intres=0; for(inti=l;i<=r;i++) for(intj=......
  • [44] (多校联训) A层冲刺NOIP2024模拟赛04
    A.02表示法这题放在ABCD题我可能不会奇怪,但是它放模拟赛T1了赛时代码#include<bits/stdc++.h>usingnamespacestd;classnum_string{ private: stringx; inlinevoiddevided_2(){ stringans="";intnow=0; for(inti=0;i<=(int)x.length()-1;++i){ ......
  • 多校A层冲刺NOIP2024模拟赛04
    多校A层冲刺NOIP2024模拟赛04学校OJ赛时rank28,T10pts,T2100pts,T320pts,T425ptsaccodersrank15,T1100pts,T2100pts,T320pts,T425pts不是,也没人告诉我两个OJ文件名不一样啊02表示法递归+高精除低精。点此查看代码#include<bits/stdc++.h>#include<bits/extc++.h>//......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛04
    Rank赤石场。A.02表示法签。若干天前在洛谷随到过,不过当时只看了眼讨论区就走了www还好本来不是很难。发现大体上是一个拆分二的幂的问题,从大到小枚举2的幂,判断有没有这个幂只用比较大小关系,然后再对指数做一个同样的操作,递归至不大于2为止,注意\(2^1\)不用输出(1......
  • 2024.10.9 总结
    决定以后分开写,显的博客多。A:首先考虑对给定树计算权值,假设我们已经知道了一个权值最小的划分,那么可以通过调整得到新的划分使得权值不变,目的是简化虚树的形态。考虑该划分中任意一个集合形成的虚树,有两种情况:如果根节点\(r\)存在于任何一个最大独立集中,即\(f_{r,1}>f_{r,0}......
  • 多校A层冲刺NOIP2024模拟赛04
    多校A层冲刺NOIP2024模拟赛04\(T1\)A.02表示法\(0pts/100pts\)弱化版:luoguP1010[NOIP1998普及组]幂次方递归模拟即可,二进制分解时需要写高精除低精。点击查看代码intr[810],t[810];chars[810],id[810][10];stringa;intchu(chars[]){ intn=strlen(s......
  • 20222327 2024-2025-1 《网络与系统攻防技术》实验一实验报告
    一.实验内容1.了解Linux系统下的基本操作命令,能够处理一些命令出现的error。2.掌握了栈与堆的概念以及在进程内存管理中的应用。3.了解基本的汇编语言指令及其功能。4.能够深刻理解BoF的原理以及如何运用payload完成BoF的攻击二.实验过程任务一直接修改程序机器指令,改变程......
  • NewStar CTF 2024 week1 题解
    1.base题目给了以下内容:Thisisabasequestion!4C4A575851324332474E324547554B494A5A4446513653434E564D444154545A4B354D45454D434E4959345536544B474D5134513D3D3D3D观察给出的字符串发现,字符串由数字0-9以及字母A-F组成,于是推测这可能是一个base16编码,于是将其解码,......
  • 【test】2024.10.8
    次大值思路发现性质,对于一个数\[a[i]\%a[j]\lea[i]\]当他取得最大值时\(a[i]<a[j]\)于是对于前&n-1&大的数,他的贡献值就是他本身,所以我们只需要保存第\(n-1\),\(n-2\)大的数就可以。但是此时要注意第\(n\)大的数的贡献值没有计算,由于\(a[n]\%a[n-2]<a[n-2]\),所以如果他要......
  • 华为OD机试真题-战场索敌-2024年OD统一考试(E卷)
    最新华为OD机试考点合集:华为OD机试2024年真题题库(E卷+D卷+C卷)_华为od机试题库-CSDN博客     每一题都含有详细的解题思路和代码注释,精选c++、JAVA、Python三种语言解法。帮助每一位考生轻松、高效刷题。订阅后永久可看,发现新题及时跟新。题目描述有一个大小是N*M的......