ABC347题解

时间：2024-03-30 22:33:23浏览次数：22

标签：code 题解 long popcnt ABC347 text

省流：输+赢

按位分析。

既然两个数异或后的结果是 $C$，那就考虑 $C$ 中为 $1$ 的数中有几个是在 $X$ 当中的。

假如 $\text{a - popcnt(X) == b - popcnt(Y)}$，那么在 $C$ 中为 $0$ 的数中随便选 $\text{a - popcnt(x)}$ 个即可。

注意 long long。

code

假如说这个点被删除了，那么就在此计算他从这次进入到这次删除中间的贡献，这个用前缀和维护即可。

然后注意最后要统计一遍此时还在 set 里的数的共线。

code

标签：code,题解,long,popcnt,ABC347,text
From： https://www.cnblogs.com/Carousel/p/18106157

CF712E Memory and Casinos 题解
假设只保留数组上$[l,r]$的这段数，记$f_i$表示从点$i$出发到达$n+1$的概率，则有$f_0=0,f_{n+1}=1,f_i=(1-p_i)f_{i-1}+p_if_{i+1}$，题目要求的是$f_1$。考虑对最后一个等式进行一些变换，把$f_i$的系数拆开得：\[p_if_i+(1-p_i)f_i=(1-p_i)f_{i-1}+p_if_{i+1......
ABC347G题解
我不会，但是我会退火！第一眼，$n\le20$。退火，启动！大致思路就是随机选一个初始为0的数置为$1\sim5$中的某个数，显然图中没有0一定不比有0劣（把所有0改成同一个数一定不劣）。然后把单次计算的复杂度从$O(n^2)$变成$O(1)$：更新有变化位置的值就行了。瞎调调参数......
P5624 [Celeste-A] Black Moonrise 题解
考虑莫队。记数$i$的个数为$c_i$，套路地用莫比乌斯函数容斥，发现答案为$\sum_{i=1}^{10^5}\frac{c_i(c_i+1)}2\sum_{d|i}\mu(\fracid)d$。先预处理出前面的常数和每个数的因子，每次移动端点枚举因子更新答案即可。因为数是随机的，所以时间复杂度\(\mathcalO(n\sqrtn......
信息工程大学第五届超越杯程序设计竞赛（同步赛）题解
比赛传送门c++模板框架#pragmaGCCoptimize(3,"Ofast","inline")#include<bits/stdc++.h>#definerep(i,a,b)for(inti=a;i<b;++i)#defineper(i,a,b)for(inti=a;i>b;--i)#definesesecond#definefifirst#defineendl'\n�......
luogu P1543 [POI2004] SZP 题解
题目传送门前置知识树形DP解法将$a_{i}$向$i$连一条有向边，这样就形成了基环外向树森林。基环外向树森林内每棵基环外向树是相互独立的，需要单独处理。对于每棵基环外向树，任取环上一点$x$，断开$x$到$fa_{x}$的有向边，外向树就变成了一棵以$x$为根的树。......
Enumerating Rational Numbers 题解
EnumeratingRationalNumbers题解先下结论，这道题是一道欧拉函数板子题观察题面可以发现，生成的分数有如下特性:分数都是最简分数分母与分子互质，且分子$\le$分母当然第一个除外，那个特判即可，不用纳入考虑范围我们知道，对于任意正整数n，欧拉函数，即$\varphi(n)$是小......
题解 CF698C【LRU】
题解CF698C【LRU】题目描述有$n$种物品和大小为$k$的队列。每次操作，以$p_i$的概率选择第$i$种物品放入队尾，如果已经有物品$i$了就将物品$i$拿出来扔到队尾。若队列大小$\gtk$，弹出队首。求$10^{100}$次操作后每种物品在队列里的概率。\(1\leq......
upload-labs简单题解
upload-labs详解1-19关通关全解（最全最详细一看就会）-CSDN博客Upload-labs1-21关靶场通关笔记(含代码审计)_upload-labs21关-CSDN博客搭建upload-labs环境参考文章渗透测试——upload-labs环境部署_upload-loadsphpstudy-CSDN博客文件上传浅谈-CSDN博客 Pass-01考点：J......
题解 ARC175C【Jumping Through Intervals】
先不考虑构造字典序最小的方案，只考虑求出最小的$\sum\limits_{i=1}^{N-1}|A_{i+1}-A_i|$。设定义域为$[L_i,R_i]$的函数$F_i(x)$表示考虑后缀$[i,N]$，令$A_i=x$时上式最小的值。初值为$F_N(x)=0,(x\in[L_N,R_N])$。显然有转移方程：\[F_i(x)=\min\limits_{y......
题解 CF70E【Information Reform】
题解CF70E【InformationReform】题目描述$n$个点的树，边权为$1$。可以花费常数$k$，在一个点上建基站。每个点$i$需要找到离他最近的基站$a_i$，花费$d[dis(i,a_i)]$。一种方案的总花费是建基站的花费加上每个点的花费之和。最小化总花费。输出方案$a_i$。......

ABC347题解

相关文章

赞助商

阅读排行