题解034f agc rng
P1864 [NOI2009] 二叉查找树 题解
二叉查找树 首先该树的中序遍历是唯一可以确定的(直接按照数据值排序即可)。 然后,因为权值可以被修改成一切实数,故我们完全可以把权值离散化掉。 于是我们现在可以设置一个 DP 状态 \(f[l,r,lim]\) 表示: 区间 \([l,r]\) 中的所有东西构成了一棵子树,且树中最小权值不小于 \( ......
CF261D Maxim and Increasing Subsequence 题解
Maxim and Increasing Subsequence 首先,我们可以发现,当这个重复次数很大的时候,答案就等于序列中出现的不同权值个数。实际上,这个“很大”就可以被当作“大于等于不同权值个数”。 不同权值个数实际上是 \(\min(n,m)\) 级别的,其中 \(n\) 是序列长度,\( ......
CF979E Kuro and Topological Parity 题解
Kuro and Topological Parity 我们考虑在一张染色完成的图里,我们连上了一条边,会有何影响? \(\bullet\) 在同色节点间连边——明显不会有任何影响。 \(\bullet\) 在异色节点间连边,但是出发点是个偶点(即有偶数条路径以其为终点的节点),终点的路径数增加了, ......
洛谷P3607 [USACO17JAN] Subsequence Reversal P 题解
Subsequence Reversal P 思路: 发现,翻转一个子序列,就意味着两两互换子序列里面的东西。 于是我们就可以设 \(f[l][r][L][R]\) 表示: \(\max[1,l)=L,\min(r,n]=R\) 时的最长长度。 则边界为: \(L>R\) 时, \(f=-\inft ......
洛谷P3576 [POI2014] MRO-Ant colony 题解
MRO-Ant colony 根据下取整除法的性质 \((\left\lfloor\dfrac{\left\lfloor\dfrac{x}{y}\right\rfloor}{z}\right\rfloor=\left\lfloor\dfrac{x}{yz}\right\rfloor)\),我们可以反 ......
CF264B Good Sequences 题解
Good Sequences 状态很显然,设 \(f[i]\) 表示位置 \(i\) 的最长长度。 关键是转移,暴力转移是 \(O(n^2)\) 的,我们必须找到一个更优秀的转移。 因为一个数的质因子数量是 \(O(\log n)\) 的,而只有和这个数具有相同质因子的数是可以转移的; 因此我们可以 ......
CF908D New Year and Arbitrary Arrangement 题解
New Year and Arbitrary Arrangement 思路: 期望题果然还是恶心呀! 我们设 \(f[i][j]\) 表示当串中有 \(i\) 个 \(a\) 和 \(j\) 个 \(ab\) 时的方案数。为了方便,设 \(A=\dfrac{P_a}{P_a+P_b},B=\dfra ......
洛谷P3118 [USACO15JAN] Moovie Mooving G 题解
Moovie Mooving G 设 \(f[i][S]\) 表示在第 \(i\) 场(注意是场,不是部)电影时,已经看了 \(S\) 里面的电影是否合法。 然后贪心地取 \(|S|\) 最小的状态保存。光荣 MLE 了, \(21\%\)。 发现当一场电影结束后,无论这一场是在哪里看的都没关系。 ......
题解 AtCoder wtf22_day1_b【Non-Overlapping Swaps】
给定一个排列,要求交换最多 $n-1$ 对元素,使得这个排列变成 [1,2,...,n] 的有序排列。
当然没有那么简单,对于交换还是有限制的,对于相邻的两次交换,不妨叫做 $(l_i, r_i)$ 和 $(l_{i+1}, r_{i+1})$,必须满足**这两个交换所对应的区间,没有交集**,即... ......
题解 CF486D Valid Sets
题目链接 相当牛逼。 这种找数量的题型,确定树形 \(dp\) 没跑了。 首先思考常规树形 \(dp\),不难想到设 \(f_{u,a,b}\) 表示以 \(u\) 为根节点的子树内(包括点 \(u\)),最大值是 \(a\),最小值是 \(b\) 的连通子图数量,转移很容易,但是这样时间空间复杂度 ......
原创题题解
实时更新。 众所周知的,原创题就是即原神又创人的题。 当然有的题不会放,等考了在放。 波特 问题描述 流水线上有 \(n\) 个波特,每个波特有一个工作效能 \(a_i\) 。对于每一个波特,当它遇到一个工件时,它会对其进行加工,耗费 \(1\) 个单位时间,然后把它传递给它前面中工作效能最大的波特 ......
NOI2021 庆典题解
又是一道锻炼代码能力的题目。 首先遇到这种求经过多少个节点的题可以先缩点,然后我们考虑那个特殊限制怎么用。 如果对于两个强联通分量 \(x\) 能到 \(z\),\(y\) 能到 \(z\),则 \(x,y\) 之间一定有一个限制,假设这个限制是 \(x\) 能到 \(y\),那么我们可以只记录 \ ......
[AGC003D] Anticube题解
首先对每个数分解只因数,然后把只因数的指数对3取模,把 \(s\) 划分成多个等价类。对于每一个等价类,有唯一对应的另一个等价类不能同时选,取最多的即可。 分解只因数用 polard's rho 算法,时间复杂度 \(O(nw^{0.25})\) code: #include<bits/stdc++ ......
[AGC002D] Stamp Rally 题解
整体二分板题 首先瑞平翻译。 考虑整体二分,用分治函数 solve(l,r,L,R) 解决答案在 \([L,R]\) 之间的边。每次我们加入所有 \([1,MID]\) 之间的边,查询这时的询问是否满足要求,进行整体二分即可。 由于多次加入边比较麻烦,我们用可撤销并查集维护。 时间复杂度 \(O(n ......
[AGC001E] BBQ Hard 题解
一道十分有趣的题。 一眼推式子,发现自己不会。 看了题解,发现是有趣思维题。但是由于我的朋友学习了有趣的思维题做法,因此我决定学习更有趣的生成函数做法!!! 考虑把原式拆开, \[\frac{1}{2}\times \left( \sum_{i=1}^{n}\sum_{j=1}^{n} \binom ......
[AGC001D] Arrays and Palindrome 题解
非常有意思的思维题。 首先我先瑞平一下翻译,我根本没看懂,还是去看英文题面看懂的。 首先可以发现整个字符串被拆成了若干个奇回文串与偶回文串。现考虑如何判是否合法。可以发现一个回文串就是要求部分位置匹配。我们对这些匹配的位置建边,如果得到的图是联通的,那么就只能填入 \(1\) 种字符,否则就可以填入 ......
P5934 [清华集训2012]最小生成树 题解
考虑 kruskal 算法的过程。 先将边按边权排序,考虑当加入 \((u,v)\) 时只有 \((u,v)\) 不联通才可能使得其出现在最小生成树中,所以对于所有的边权小于 \(L\) 的边,我们希望去除尽可能少的边使得 \((u,v)\) 不联通。这显然是一个网络流模型。对于每一条边 \((x, ......
#9134. 翻转硬币 题解
首先考虑一些简单的情况,比如 \(m=1\)。 容易发现操作 1 和操作 2 的顺序不会影响结果,于是可以钦定所有操作 1 在操作 2 之前。并且可以发现,进行完所有 1 后 2 的次数即为 \((\text{连续段个数}-1)\)。 然后考虑将 \(m>1\) 的情况。显然最后序列上每 \(m\) ......
【AGC】云托管状态一直是“上线中”的问题
【关键字】 AGC、云托管、网址域名 【问题描述】 有开发者反馈开通了云托管服务,然后进行了相关域名设定,等待激活,无法活动,状态一直是‘上线中’。 开通托管已经一天了一直卡着,状态一直是“上线中”。并且表示,域名是有备案的。 【解决方案】 一、一般情况下,后台正在处理30分钟即可 ......
[CF1098E] Fedya the Potter 题解
[CF1098E] Fedya the Potter 题解 前言 一道类欧好题。 题解 这道题让求 \(c\) 数组的中位数,那么有一个比较套路的方法就是二分答案 \(mid\) 然后计算 \(b\) 数组中区间和小于 \(mid\) 的区间个数进行 \(check\)。但是 \(b\) 数组总共有 ......
CF882E1+CF1882E2 Two Permutations 题解-构造题
CF882E1+CF1882E2 Two Permutations 题解-构造题 哇,人类智慧,太智慧了。。。 此题作为20231010联考的 T3。 感觉赛时根本没有去往这方面想。 CF1882E1 CF1882E2 E1 是简单版,就是没有要求操作数最小化。 E1-Easy Version 方法 ......
[ABC245G] Foreign Friends 题解
[ABC245G] Foreign Friends 题解 想法 考虑所有颜色相同的弱化版。 这种情况下,只需要把所有特殊点都推入队列之后跑多源 Dijkstra 即可。 思路 正解与上述做法大致相同。 如果有颜色限制,那么可以考虑这个神仙思路: 把所有特殊点的颜色用二进制表示,对于每一位,这一位是 ......
[USACO17JAN] Promotion Counting P 题解
[USACO17JAN] Promotion Counting P 题解 前言 好久没写题解了,今天趁我心情好赶紧水一篇。 思路 首先拿到这题,关键词检索:子树,比 \(p_i\) 大的,树状数组!现在考虑如何去掉其他子树的贡献……emm,我直接在算贡献的时候去掉其他子树的贡献不就好了! 当然,暴力 ......
[USACO08FEB]meteor Shower S题解(bfs)
题目描述 贝茜听说一场特别的流星雨即将到来:这些流星会撞向地球,并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑,发誓要找到一个安全的地方(一个永远不会被流星摧毁的地方)。 如果将牧场放入一个直角坐标系中,贝茜现在的位置是原点,并且,贝茜不能踏上一块被流星砸过的土地。 根据预报,一共有 \(M\) ......
P1457 [USACO2.1] 城堡 The Castle 题解
分析 感觉没有蓝题难度 一道 bfs 题目,相较于大部分 bfs 题,它较为复杂,但分析一下还是很好水过的。 建立墙时,可以用三维数组,\(wall_{~i, ~j, ~pos}\) 表示 第 \(i\) 行第 \(j\) 列 \(pos\) 方向有墙。 观察发现,\(8 = 2^3,4 = 2^2 ......
Shuffle 题解
Shuffle 题目大意 给定一个长度为 \(n\) 的 01 序列 \(a\),你可以进行至多一次以下操作: 选定 \(a\) 的一个连续段,满足连续段内恰好有 \(k\) 个 \(1\),将该连续段任意排列。 问能产生多少种不同的 01 序列。 思路分析 (这题 \(n\) 完全可以开到 \(1 ......
【多校联考NOIP#2】比赛复盘 && 题解
A. 黑白染色 这类题没有做过,第一次做,很有新意。 染色的时候,如果一个点的出边中有2个同色点,那么就有一条路中有三个同色点,是不合法的。 不妨先把所有点染成一个颜色,然后再选点染成另一个颜色。 使用一个队列,先把所有的点入队。 每次取出队头 \(u\) ,如果发现他不合法: 1.自己颜色取反 2 ......
【题解 P3586】 LOG
[POI2015] LOG 题目描述 维护一个长度为 \(n\) 的序列,一开始都是 \(0\),支持以下两种操作: U k a 将序列中第 \(k\) 个数修改为 \(a\)。 Z c s 在这个序列上,每次选出 \(c\) 个正数,并将它们都减去 \(1\),询问能否进行 \(s\) 次操作。 ......
题解 AcWing 359.创世纪
题目描述 给你一个 \(n\) 个点 \(n\) 条边的有向图,若选了当前节点,那么当前节点的儿子节点至少有一个不能选。求最多能选多少个点。 具体思路 显然是一棵基环树,因此考虑基环树 dp。 我们先不管环的条件,先考虑朴素的树形 dp。 设 \(f_{x,0}\) 表示 \(x\) 节点不选,最多 ......
【NewStarCTF 2023】题解week1
easy_RE 先exeinfo 没有壳,直接上ida 看到有关键信息,但没有显示完,按f5反编译一下 拼接一下输入,注意字符串的部分字母由近似数字代替,提交 KE 运行一下,看到是KE,想着可能是壳的意思?exeinfo看一下 upx壳,尝试upx脱壳 呃呃 权限好像不对 尝试了一下用管理员权限打 ......