[冲刺国赛2022] 模拟赛15_c202044zxy-编程思维

数列 题目描述 你得到了一个长度为 \(n\) 的数列 \(a\),每个元素为 \([1,m]\) 中的整数,可以生成 \(b_i=\max\{j|j<i\and a_j>a_i\}\) 现在给你数列 \(b\),其中有一些位置被损坏了(值为 \(-1\)),请求出有多少满足条件的 \(a\) \(n\leq 100,m\leq 10^5\) 解法 可以根据 \(b\) 写出一个表示

codeforces round #749_c202044zxy-编程思维

还我Rating 我已经暴怒了,神\(^{\tt TM}\)前六道都是构造题,我真的受够了!!! 再也不拿大号打 \(\tt Div1+Div2\) 了,下次我打 \(\tt Div1\) 直接杀穿,吊打小 \(\tt T\) 做梦不是问题。 \(\tt RNM\),退钱!!! F. Defender of Childhood Dreams 题目描述 点此看题 有 \(n\) 个点,对于 \(a

cf1396e distance matching_c202044zxy-编程思维

一、题目 点此看题 二、解法 技巧性极强的构造题,惜吾构造而不终也,思路大体有了,但还差点火候。 首先考虑合法的必要条件,我们先考察边权的最大值和最小值来得到大体的范围。我们考虑每条边的贡献,边 \((u,v)\) 断开后形成的子树大小是 \(siz[u],siz[v]\),可以得到上下界分别是: \[siz[u]\%2\leq w\leq\min(siz[u],siz[v]) \]为了去掉 \

[提高组互测] day1_c202044zxy-编程思维

Poman Numbers 题目描述 点此看题 解法 以后做不出来第一题一定要打表找规律,这么辣鸡的题我空耗了两个小时 你发现每个数前面的符号是正或者负,打表发现最后一个位置的符号一定为正,倒数第二个位置的符号一定为负,其他位置的符合任填,构造方法: 因为已经知道结论了我们这里就用归纳法: 如果只有一个 +,符合条件,直接退出。 如果除了最后一个都是 -,那么把前面的依次拿出来即可,符合条件

cf600f edge coloring of bipartite graph_c202044zxy-编程思维

一、题目 点此看题 二、解法 \(\tt vizing\) 定理板题,可以去看看 oiwiki 当然我不会证这个定理,我只会给出二分图背景下这个定理的构造性证明。 结论:二分图的边染色最小颜色数是点的最大度数 考虑增量法构造,现在考虑边 \((x,y)\) 的染色,设点 \(x\) 未使用的最小颜色是 \(lx\),设点 \(y\) 未使用的最小颜色是 \(ly\),如果 \(lx=ly\) 那

cf1383c string transformation 2_c202044zxy-编程思维

一、题目 点此看题 二、解法 首先把转图论模型:有 \(20\) 个点,按时间顺序往里面加边,要求 \(\forall i,A_i\) 到 \(B_i\) 有一条时间单调递增的路径,问最小加边数量。这个模型成立的原因是我们按时间顺序操作,如果一个点达到了目标状态就可以把它固定下来。 记 \(G_1\) 为加边之后形成的图,\(G_2\) 为连有向边 \((A_i,B_i)\) 形成的图;记 \(

codeforces global round 11_c202044zxy-编程思维

E. Xum 题目描述 一开始黑板上写了一个奇数 \(x\),每次操作可以选取黑板上的两个数,把他们的和或者异或和写在黑板上,试在 \(10^5\) 次操作内使得黑板上出现 \(1\),并且要保证任意时刻黑板上的数都不超过 \(5\cdot 10^{18}\) \(3\leq x\leq 10^6\) 解法 发现不可能由加法直接得到 \(1\),得到 \(1\) 只能通过异或操作,那么求出一组偶

codeforces round #740 div. 2_c202044zxy-编程思维

E. Bottom-Tier Reversals 题目描述 点此看题 给定一个长度为 \(n\) 的排列(\(n\) 为奇数),每次你可以翻转一个长度为奇数的前缀,构造方案使得 \(\frac{5n}{2}\) 之内将这个排列排好序,如果无法达到这个目标输出 \(-1\) \(n\leq 2000\) 解法 考虑能排序的必要条件:对于所有 \(i\) 满足 \(i\) 和 \(a_i\) 有相同

cf1368h1 breadboard capacity_c202044zxy-编程思维

一、题目 点此看题 \(\tt H2\) 有点毒瘤,不是很想写。 二、解法 首先对原问题建出网络流图,我们把 \(S\) 连所有蓝色接口,\(T\) 连所有红色接口,矩形内的所有点也建出来,向四周连容量为 \(1\) 的无向边,然后对原图跑最大流就是答案。 这里补充一个小知识点,也就是网络流图怎么连无向边,举例:\((u,v)\) 之间一条容量为 \(1\) 的边。 拆分成两条边,\(u\ri

codeforces global round 15_c202044zxy-编程思维

E. Colors and Intervals 题目描述 点此看题 \(n\) 种颜色,每种颜色恰好有 \(k\) 个,他们排成一个长度为 \(n\times k\) 的颜色序列 \(a\) 每种颜色需要选两个端点,这两个点会构成一个区间,试构造方案使得每个点最多被覆盖 \(\lceil\frac{n}{k-1}\rceil\) 次。 \(n,k\leq 100\) 解法 不难转化题意:每 \(

atcoder grand contest 054_c202044zxy-编程思维

C.Roughly Sorted 题目描述 如果一个排列每个位置上的逆序对个数都 \(\leq k\),那么它是好排列。假设你有排列 \(P\),每次可以交换两个相邻元素,用最小的步数得到好排列 \(P'\) 现给定 \(P'\) 和 \(k\),求可能的 \(P\) 有多少个。 \(n\leq 5000\) 解法 首先考虑知道了排列 \(P\) 怎么求出排列 \(P'\),设第 \(i\) 个

cf1349f1 slime and sequences_c202044zxy-编程思维

一、题目 点此看题 二、解法 下次再也不找这种阴间题做了,根本想不到好吗? 首先做一个简单的转化:考虑让 \(k-1\) 第一次出现的位置大于 \(k\) 最后一次出现的位置。 考虑构造映射去描述好序列,你发现转化后的条件是比较连贯的,因为 \(k-1\) 第一次出现的位置大于 \(k\) 最后一次出现的位置,而 \(k\) 第一次出现的位置大于 \(k+1\) 最后一次出现的位置。 所以我们构

cf1499g graph coloring_c202044zxy-编程思维

一、题目 点此看题 二、解法 首先考虑定边怎么做,考虑构造得到最小解,我们先把所有环删掉,然后原图就剩下的若干条路径,我们把度为奇数的点作为某一条路径的端点,度为偶数的点不作为端点,那么答案就取到了下界:\(\sum[deg[u]\%2=1]\) 题目要求动态加边,并且强制在线,那就真的只能加边了呗,我们讨论一个新加边的两个节点的情况: 如果都不是路径的端点,那么可以直接把这条边当成路径加进去

codeforces round #699 (div. 2)_c202044zxy-编程思维

E.Sorting Books 题目描述 点此看题 解法 \(\tt Almost\space art!The\space art\space of\space enumeration!\) 不难发现每本书最多移动一次,移动多次一定是不优的。 那么每本书就有两种状态:不移动和移动。我们枚举每本书的状态,如果以最后一本不动书为界限,那么前面的书如果属于同一种类,那么一定同时移动或者同时不移动,否则

codeforces round #618 (div. 1)_c202044zxy-编程思维

E. So Mean 题目描述 点此看题 解法 其实我自己快做出来了,说出来我自己都不信,构造题就是要多观察: 虽然看到这题没什么思路,但是我们可以乱手玩一下,因为询问限制较弱我们就考虑先确定一个数吧,可以询问每组 \(n-1\) 个数,设没询问的数是 \(i\),我们可以提前算出他们的求和是: \[1+2+...+(i-1)+(i+1)+....+n=\frac{n(n+1)}{2}-i=\f

atcoder regular contest 120_c202044zxy-编程思维

B.Uniformly Distributed 题目描述 点此看题 解法 首先可以观察出必要条件,也就是对于所有 \((i,j)\) 要求 \((i+1,j)\) 和 \((i,j+1)\) 的颜色相等,这样才能保证无论用什么方法走到 \((i+1,j+1)\) 经过红色格子的数量都是一样的。 这也是充分条件,因为任意时候路径经过红色格子数都是全相等的。 所以对于每一个 \(i+j\) 统计颜色