首页 > 其他分享 >CF 口胡笔记 2200Ct辑

CF 口胡笔记 2200Ct辑

时间:2024-11-06 21:59:15浏览次数:5  
标签:10 le vert text CF 笔记 题解 区间 2200Ct

¿ 如何 搞笑 高效做题 ?

只需要口胡CF题就行啦!(

前天起口胡 CF 按照洛谷通过人数排序的题单

这期我们来口胡 CF2200 Part 1 吧 ~

CF617E XOR and Favorite Number

给定一个长度为 \(n\) 的序列 \(a\),然后再给一个数字 \(k\),再给出 \(m\) 组询问,每组询问给出一个区间,求这个区间里面有多少个子区间的异或值为 \(k\)。

\(1 \le n,m \le 10 ^ 5\),\(0 \le k,a_i \le 10^6\),\(1 \le l_i \le r_i \le n\)。

想了半天还是不会啊,看看样例吧……

等等,\(k\) 不变?!

Easy! 先把询问离线下来按 \(q_r\) 排序。从左到右依次更新每个点 \(r\)。把 \(\oplus[l,r]=k\) 的区间全部加进树状数组里,索引是 \(l\) 。(显然总共最多 \(2n\) 个区间),询问的时候在 \(q_r\) 点询问 \(l\ge q_l\) 的有多少个区间就行了。

看看题解吧,什么,居然是莫队 \(O(n\sqrt n)\) 的? 不优!(

那我写写我的 \(n \log n\) 高妙方法吧。

好了,TLE 了,原来总共最多 \(\frac{n(n-1)}{2}\) 个区间,我傻了。比如 k=0:0 0 0 0 0 0 或者 k=3:1 1 1 2 2 2 就能卡到 \(O(n^2\log n)\),寄。

那我还是莫队吧,寄。顺便附上错代码。

#include<bits/stdc++.h>
using namespace std;
#define ff(i,l,r) for(auto i=(l);(i)<=(r);++i)
#define fi(l,r) ff(i,l,r)
#define lowbit(x) ((x)&(-(x)))
#define ll long long
#define ul unsigned ll
#define ui unsigned int
#define P 998244353
#define N 100005
#define L 1048578
int a[N],c[N],n,kk,m,fir[L],nxt[N],ans[N],cnt,s[N];
struct Req{
	int l,r,i;
}req[N];
void add(int x){++cnt;for(;x<=n;x+=lowbit(x))++c[x];}
int que(int x){int res=0;for(;x;x-=lowbit(x))res+=c[x];return res;}
int main(){
	scanf("%d %d %d",&n,&m,&kk);
	fi(1,n)scanf("%d",&a[i]);
	fi(1,m){scanf("%d %d",&req[i].l,&req[i].r);req[i].i=i;}
	sort(req+1,req+m+1,[&](Req x,Req y){return x.r<y.r;});
	int it=1;
	fi(1,n){
		s[i]=s[i-1]^a[i];
		for(int e=fir[kk^s[i]];e;e=nxt[e])add(e+1);
		nxt[i]=fir[s[i]];fir[s[i]]=i;
		if(s[i]==kk)add(1);
		for(;it<=m&&req[it].r==i;++it)ans[req[it].i]=cnt-que(req[it].l-1);
	}
	fi(1,m)printf("%d\n",ans[i]);
	return 0;
}

CF13C Sequence

给定一个序列,每次操作可以把某个数加上 \(1\) 或减去 \(1\)。要求把序列变成非降数列。最小化操作次数。

\(n \le 5000,|a_i| \le 10^9\)

设 \(f[i]\) 代表 \(a_i\) 不动,让 \(a_{1 \sim i}\) 不升的最小代价。

image

这种情况下虽然 \(u\) 点不动最优,但 \(u\) 不动是属于 \(u \rightarrow i\) 这个转移方案里的。 \(j \rightarrow i\) 这个转移必须要动 \(u\) 。要把中间的所有值变成 \(a_i\) 。

\(f[i]=\min(f[j\in[1,i)]+\text{cost}(a_{(j \sim i)}\rightarrow a_i))\)

但是这种方法是错误的。

题解方法是记录 \(f[i][j]\) 代表把 \(a_i\) 变成 \(a_j\) 时维护 \(a_{i\sim j}\) 不升的成本。
.
另外,其实题目要求是维护不降,我现在才发现(

拓展 P4597 Sequence【加强版】

给定一个序列,每次操作可以把某个数加上 \(1\) 或减去 \(1\)。要求把序列变成非降数列。最小化操作次数。

\(n \le 5\times 10^5,|a_i| \le 10^9\)

考虑按顺序加入每个点后,该点权值修改为 \(x\) 时的代价 \(y\) (类似于 \(f[i][j]\)):

image

image

image

没错,永远是个下凸包!

所以只用维护凸包就行了。

ll ans;
int a,n;
priority_queue<int>q;
int main(){
	scanf("%d",&n);
	fi(1,n){
		scanf("%d",&a);
		q.push(a);
		if(a<q.top()){
			ans+=q.top()-a;
			q.pop();
			q.push(a);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

CF570D Tree Requests

给定一个以 \(1\) 为根的 \(n\) 个结点的树,每个点上有一个字母(a-z),每个点的深度定义为该节点到 \(1\) 号结点路径上的点数。\(m\) 个询问,每次询问 \(a, b\) 查询以 \(a\) 为根的子树内深度为 \(b\) 的结点上的字母重新排列之后是否能构成回文串。

\(n,m \le 5\times 10^5\)

做法一

启发式合并分别统计每个点 abcdefgh...z 的数量。复杂度 \(O(26n\log n)\)

看题解,可以状压。

做法二

题解还有一种做法,很高级,没有 \(\log\) : dfs 作差。记录 \(\text{cnt}[\text{dep}]\) 代表深度为 \(\text{dep}\) 的异或值。进入的时候记录原先的二进制数,出节点的时候再异或上进入时的内容。复杂度 \(O(n+m)\)

做法三

题解还有一种做法,更高级,在线:记录每个节点的 \(\text{dfn}\) ,分配 \(\text{maxdep}\) 个 vector 存储每个深度里面节点的前缀异或和。每次 lower_bound 查询作差即可。

【悬疑题】 CF280C Game on Tree

给出一棵树,每次随机等概率选择一未染黑的点,将它及其子树染黑。问期望多少次操作可以将树全部染黑。

\(n \le 10^5\)

不会做。看题解:

设 \(f_i\) 代表 \(i\) 被选中次数的期望(\(f_i\in[0,1]\)),也就是被选中的概率。

则 \(\text{ans}=\sum f_i\)

考虑任意一个不一定合法的操作序列,\(i\) 号点未被删除的概率是 \(\frac{i}{\text{dep}[i]}\)

那么 \(f_i\) 就是 \(\frac{1}{\text{dep}[i]}\)

读完题解,问题来了:这个操作序列没有保证合法,为什么能推出 \(f_i\)?

现在我又获得了一种新的做法:

记任意一种合法的操作序列为 \(L\),记所有 \(L\) 的集合为 \(\{L\cdots\}\), 记一个点 \(x\) 的祖先(及自己)的点集为 \(F_x\) ,那么:

可重集 \(A_x=\{L\cap F_x\cdots\}\) 代表的是一条链的操作序列可重集合。

集合 \(C_x=\{L\cap F_x\cdots\}\) 代表的是一条链的操作序列集合。

我猜想, \(\forall c \in C_x , A_x \rightarrow \text{count}(c)\) 相等。

也就说:每一种"链上操作序列"在 \(C_x\) 中出现的次数是一样的。

证明:不会

所以

\[\begin{align} f_i &= \frac{\left\vert\left\{L\cdots\vert i\in L \right\}\right\vert}{\left\vert\left\{L\cdots\right\}\right\vert}\\ &= \frac{\left\vert A_i\left\{i\in A_i\right\}\right\vert}{\left\vert\left\{A_i\right\}\right\vert}\\ &=\frac{1}{\text{dep}_i} \end{align} \]

所以 \(ans=\sum \frac{1}{\text{dep}_i}\)

记录一下隔壁巨佬看到这道题的思路:先考虑链和菊花图的情况

这题存疑,还不太会。

CF559C Gerald and Giant Chess

给定一个 \(h\times w\) 大小的棋盘,其中有 \(n\) 个点为黑色。
每次只能向右或向下移动,求从 \((1,1)\) 不经过黑色点到达 \((h,w)\) 的方案数。

\(h,w \le 10^5 ; n\le 2000\)

考虑容斥。

记 \(f[i][0/1]\) 代表最后一个经过的黑点是 \(i\) 号点,迄今经过的黑点数量奇偶为 \(0/1\)

\(f[i][x]=\sum f[j][!x]\times \text{pathcount}(i,j)\)

记 \(U[i][j]=\text{pathcount}(i,j)\) ……

好像不行。看看题解吧……

记 \(f[i]\) 代表从 \(1\) 开始走不经过其他黑点,到达 \(i\) 点的路径数。

\(f[i]=C_{x_i+y_i-2}^{x_i-1}-\sum f[j]\times C_{x_i+y_i-x_j-y_j}^{x_i-x_j}\)

由于每个 \(f_j\) 都有一个独立代表性的必经黑点 \(j\) ,因此这样可以不重不漏地统计答案。

妙啊

CF833B The Bakery

将一个长度为 \(n\) 的序列分为 \(k\) 个连续段,使得总价值最大。

一段区间的价值表示为区间内不同数字的个数。

\(n\leq 35000,k\leq 50\)

看起来是 \(O(nk^{(2?)}(\log?))\) 的做法

记 \(f_{i,j}\) 代表 \(i\) 位置是第 \(j\) 段的最后一个点时,之前的最大总价值。

\(f_{i,j}=\max(f_{k,j-1}+j-k-重复的数量(k+1,i))\)

复杂度 \(O(n^2m)\)

然后就不会了

看看题解吧:

\(不同颜色的数量(i,j)\) 居然可以用线段树求出?!!

如题解图,上面一行数字代表的是 \(a\) ,每个 \(a_i\) 对 \((pre[i]+1) \sim i\) 造成贡献(如图不同颜色区间),这样就可以线段树维护了。

优雅的图片

本质是对于一根扫描线,枚举这个线往后第一次出现 x 值是什么时候。那显然,扫描线在左端点的时候最优。

所以我们记录一个点 \((x,y)\) 代表 \(i\) 点造成贡献的区间 \([x,y]\) ,所有 \(x \le k\) 的和 \(y \ge i\) 的区间贡献都被减掉,这是一个典中典二位偏序题目。

对于 \(x\) 的限制,我们可以让线段树节点代表区间的左端点作为 \(x\) 限制。

对于 \(y\) 的限制,在枚举 \(i:1 \rightarrow n\) 时,先不加入线段树上 \(i\) 点以后的区间。

拓展题 CF868F Yet Another Minimization Problem

将一个长度为 \(n\) 的序列分为 \(k\) 个连续段,使得总价值最小。

一段区间的价值表示为区间内相同数字的个数。

\(n\leq 10^5,k\leq 20\)

记 \(f_{i,j}\) 代表 \(i\) 位置是第 \(j\) 段的最后一个点时,之前的最小总价值。

\(f_{i,j}=\min(f_{k,j-1}+j-k-不同颜色的数量(k+1,i))\)

一模一样的题,就变成紫了。

标签:10,le,vert,text,CF,笔记,题解,区间,2200Ct
From: https://www.cnblogs.com/DZhearMins/p/18531150

相关文章

  • python+flask计算机毕业设计个人旅游笔记服务端(程序+开题+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容一、选题背景关于旅游笔记的研究,现有研究主要以旅游目的地的推广、旅游攻略的撰写为主。专门针对个人旅游笔记,从其涵盖的多种系统功能角度进行深入......
  • 数据结构学习笔记(C)--半期复习
    第一章---第四章(哈夫曼树)之前1.0绪论1.1数据结构三要素:逻辑结构a.线性​ 线性结构--一对一b.非线性​ 集合结构--属于同一集合”​ 树结构--一对多​ 图结构或网状结构--多对多存储结构顺序链式数据的运算1.2数据类型和抽象数据类型抽象数据类型ADT抽......
  • Python学习笔记-生成器的应用与原理
    生成器是Python中一种特殊的迭代工具,通过延迟计算的方式来逐步生成序列中的元素。这种特性使得生成器在处理大数据、无限序列或需要惰性求值的场景中十分有效。生成器的核心思想是通过yield语句逐步返回值,暂停并保留当前状态,直到下次调用继续执行,从而节省内存并优化性能......
  • Python学习笔记-断点操作结合异常处理
    在编程中,调试和错误处理是提升代码质量和开发效率的关键环节。调试能帮助识别并修复问题,异常处理则使得程序能在出现错误时有效地管理而不至于崩溃。断点与异常处理的结合应用是高级编程中不可或缺的技巧,能够帮助更高效地定位问题,提高程序的鲁棒性。本文将通过详细的断点和......
  • 算法笔记——马拉核弹(Mana Nuclear)
    0x00摘要“马拉核弹”算法由SXHT同学(2009~今)发明,并在2024年11月于某不知名学校机房内正式公布。该算法基于1975年发明的Manacher算法,并将其推广至对称正方形问题。原文链接与密码:sunxuhetai2009。关键词:Manacher算法信息学对称正方形0x01缘由先来看这道题目:......
  • 学习笔记(二十七):ArkUi-警告弹窗(AlertDialog)
    概述:警告弹窗,需要向用户提问或得到用户的许可。警告弹窗用来提示重要信息,但会中断当前任务,尽量提供必要的信息和有用的操作。避免仅使用警告弹窗提供信息,用户不喜欢被信息丰富但不可操作的警告打断。必选内容包含:标题、可选信息文本、最多3个按钮。可选内容包含:输入框、icon......
  • CF1270 Good Bye 2019
    Dashboard玩构造玩的,服了。A拥有最大牌的必胜。linkB若相邻的差\(\ge2\)则有解,否则根据变化连续性一定无解。linkC加两个数,第一个数为之前所有数的异或和。加进来之后异或为0。第二个数为加完第一个数之后的和。linkD考虑\(k=n-1\)时,分别询问除去每个数之后的第\(......
  • CF 1438 题解
    CF1438题解ASpecificTastesofAndre考虑一种非常简单的构造:\(a_i=1\).不难发现满足条件.BValeriiAgainstEveryone结论:符合条件当且仅当有两个一样的元素.证明:充分性显然,下证必要性.若不存在两个一样的元素,则由于无法进位,故没有办法得到两个区间和在相......
  • 学习笔记(二十六):资源分类与访问(Resources)
    概述:应用开发中使用的各类资源文件,需要放入特定子目录中存储管理。资源目录的示例如下所示,base目录、限定词目录、rawfile目录、resfile目录称为资源目录;element、media、profile称为资源组目录。resources|---base||---element|||---string.json||---media......
  • STM32H563核心板调试笔记(一)
    前言这是组里师兄负责的项目,以FPGA为数据采集核心,但还需要执行一些流程性的指令,因此还需要一个CPU。我们不用Zynq是因为它里面的CPU性能比较强,功耗比较高(其实我们没有人很懂Zynq,可以说这是我们选型的假设,现在选都选好了,你就承认吧)。而MCU部分组里也就我比较懂,于是我经过一番比较......