GYM

# 题目大意 构造一个01网格图，1能走0不能走 使得从左上走到右下（只能走右或走下）的方案数恰好为x n=当前p[i]就减p[i]，a[i]+1（也类似**进制转换**） （也可以理解成让**ai尽量小**，所以一次**减的数尽量大**，每次**减最大的能减的数** # code ```cpp # ......

首先考虑 $dp_{i,msk}$ 表示当前连通了 $msk$ 中所有关键点，并且当前连通的非关键点包含 $i$ 的最小代价。 然后考虑如何转移。我们先用 $Floyd$ 预处理所有点对之间的最短路 $dist_{i,j}$。同时，每次选取的两个用于合并的关键点集合一定没有交集，所以我们可以直接枚举 ......

自己下午闲着没事单挑了一下，两小时左右一度rk1，但后继无力了。。。。 A. Max or Min 肯定沿着出现过的数操作；然后发现如果a[i]=k,a[j]>k,a[k]<k就会增加一次操作 所以维护一下差分序列即可。 B. Level Up 两维DP，这个疑似edu出过。 要注意的是：需要关于x ......

题目链接：https://codeforces.com/gym/103743/problem/H 这应该是近期做出来的最难的题之一了……想了一个多小时 首先，如何由 $S$ 求得 $a^{(n)}(S) $ ？ 考虑 $S$ 的每一位 0/1 如果第一位是 1，那么相当于就知道了剩下的数字在 $re ......

problem 一个长为 $m$ 的数组 $a$，每个数的取值为 $[1,n]$ 的正整数；另外有一个长为 $m$ 的数组 $b$，初始全零；另外有一棵 $n$ 个点的树，求树上两点距离的函数为 $dist$。请支持三种操作： 输入 $l,r,c$，枚举 $i\in [l,r]$，使得 $b_i\g ......

首先可以看出这是一个条件概率 $P(A/B) = \frac{P(AB)}{P(B)}$，其中 $A$ 事件为“满足在 $Z$ 城市时寄出第 $Q$ 张明信片”，$B$ 事件为“满足得到的明信片序列与给出的明信片序列相同” 那只需要求出 $P(AB)$ 和 $P(B)$ 就能得到最终答案了 首先考虑 ......

一道需要一些猜结论技巧的中档题。 首先突破口在于排列长度恰好等于不是额外输入的某个数 $k$ 而是 LDS 与 LIS 的乘积，这显然启示我们去找一些性质。根据 dilworth 定理，最长反链等于最小链覆盖，故 LIS 的长度，就是最少需要的递减数列的个数使得每个元素被覆盖至少一次，而每个递减数列 ......

比赛链接：https://codeforces.com/gym/104081 目前就做了 8 题，里面还有 4 个水题…… 水题：ACEG，模拟题意即可，C 和 E 有一些细节。不想写题解了 F 首先目标是如何将这 9 个数分组，由于答案一定存在，考虑随机化，固定 $a_1 \in S_1$，然后随 ......

CF Gym 上的原题保证序列长度为 $2$ 的幂，这里介绍的做法可以针对 $n$ 任意（虽然也没强到哪儿去） 首先充要条件是序列中所有数之和是 $\lfloor\dfrac{n}{2}\rfloor$ 的倍数，因为每次操作对序列中所有数之和的增量都是 $\lfloor\dfrac{n}{2}\rf ......

首先考虑 $k$ 表示 $2^k+k-1\le n$ 的最大的 $k$，打表猜测最优情况满足： 所有长度为 $k$ 的子串恰好覆盖了全部 $2^k$ 种不同的长度为 $k$ 的 01 串。 所有长度为 $k+1$ 的子串互不相同。 考虑规约到图论模型，建立一张有 $2^k$ 个点的图，点 $i$ 向 ......

发现每次对行的操作相当于将这一行的元素复合上一个排列，对列也同理。不妨记这两个排列为 $p,q$。 首先考虑一个弱化版：如果 $p,q$ 都是一个环怎么处理。如果 $n=1$ 那么答案显然是 $a$ 的最小周期，使用 KMP 求解。对于 $m=1$ 的情况也同理。考虑 $n,m\ge 2$，发现我们 ......

一个巨烦的时间轴分块做法，有点类似于 P2137 Gty的妹子树 先考虑静态的情况。看上去就一脸线段树合并对吧？一次修改的操作对一个点 $x$ 贡献可以写成 $k·dep_x+b$ 的形式，开两棵线段树合并维护一次项和零次项系数即可。 由于静态问题可做，因此考虑时间轴分块。设阈值 $B$，每 $B$ ......

Gym104076L Tree Distance 题目链接。 $\text{difficulty}={4,2.5}$。 $\text{tags}=点分治,扫描线$。 没见过确实想不到。 由于查询是区间对区间，分块等数据结构并不好直接维护。考虑找一些性质，如果两个点 $l,r(l <r)$ 的距离大于 ......

题目链接：https://codeforces.com/gym/103688/problem/E 题解： 辣鸡题解，好多地方有错，遂自己写一个 // by SkyRainWind #include <bits/stdc++.h> #define mpr make_pair #define debug ......

传送门 「Gym102759L」Steel Slicing 2 题目大意 给定一个只有水平边和竖直边的铁片，每次可以水平或竖直方向把一个铁片分成两个部分。注意只能是两个部分。求最少切多少刀才能使得每一个部分都是长方形。 铁片形状如下图，以输入 $h,l$ 的方式给出。 思路 手玩几组数据之后，我们可 ......

有 n 个人，m 个怪兽，k 瓶药水，现在依次给出每个人可以杀的怪物的数量 t 以及怪物的编号， 每个人只能杀他能杀的一个怪物，但可以领取一瓶药水复活再杀一个（只能领取一次)，问最多能杀死的怪物 最大流 建图： S--> 人(1) , S->S+1(K) , S+1 --> 人 （1) , 人--》 ......

传送门 「Gym102759B」Cactus Competition 题目大意 有一个 $n \times m$ 的网格图，一个长度为 $n$ 的序列 $a$，和一个长度为 $m$ 的序列 $b$。 网格图中，第 $i$ 行第 $j$ 列的位置有一个数 $c_{i,j}=a_i+b_j$。$c_{i ......