GYM
gym 102452 Constructing Ranches 题解
题目 题意 给定一颗树,每个点有点权。求有多少对点对 \((x,y)\) 满足 \(x<y\) 且以 \(x\) 到 \(y\) 的简单路径上的所有点的点权作为边长,能围成一个凸多边形。 \(1 \leq n \leq 10^5\),\(1 \leq a_i \leq 10^9\)。 思路 遇到这种 ......
gym103415A Math Ball
套路生成函数。 写出答案的式子,设 \(f_i(x)=\sum j^{c_i} x^j\),不难得到答案为: \[[x^W]{1\over 1-x}\prod_{i=1}^n f_i(x) \]考虑求 \(f_i(x)\)。看到指数上有 \(c_i\),想到用斯特林数展开: \[f_i(x)=\su ......
题解 Gym 102341B【Bulbasaur】/ SS231107C【爬梯高手】
题解 SS231107C【爬梯高手】 撞原了,好耶!Gym 102341B 顺便把我的变异加强版爆标了!!! problem 有一个 \(n*m\) 个点的有向分层图,共有 \(n\) 层,每层 \(m\) 个点,每条边一定是从第 \(i\) 层连向第 \(i+1\) 层。 定义 \(f(i,j)\ ......
[Gym101194G] Pandaria 题解
[Gym101194G] Pandaria 题解 题目描述 给定一张无向图,边有边权,点有颜色 \(\le 10^6\),每次询问给定 \(x, w\),表示 Mr. Panda 从 \(x\) 出发,可以选定一个颜色 \(c\),使得在不走 \(> w\) 的边的情况下,能到达颜色为 \(c\) ......
[gym102538H] Horrible Cycles
题目链接 考虑把所有点按一定顺序排,使得左部点前面所有右部点恰好是他连向的所有右部点。 定义 \(dp_{i,j}\) 表示前 \(i\) 个点,那么此时一个环会被分出 \(j\) 条链的方案。强制钦定一条链的两边都是右部点。 如果 \(i\) 是一个右部点,他可以选择是否选到环中, \(dp_{i ......
Gym - 103119L的另类解法
题意 有一个长为\(n(n<=50)\)的整数序列\(A\),每个数都是随机生成的,并且每个数在\(1-n\)的范围内等概率生成。你的任务是计算有多少长度为\(n\)的排列(值域是\(1-n\))任意位置满足\(p_i<=a_i\),求期望的排列数量 输出要求 答案至少保留标准答案的前九位 解法1 ......
GYM103102/SEERC2020 J One Piece
GYM103102/SEERC2020 J One Piece 这题讲杂题的时候人没讲清楚,下来问做出来的大佬也没说清楚,网上翻半天题解一两句没了,心态炸了都。 题意略过,各位自己去看一遍原题目。 提前约定一些符号:\(\operatorname{dis}(a,b)\) 表示点 \(a,b\) 之间 ......
CF GYM 104020 G
link 首先,因为 \(w_i\le 10^6\),有点大,所以我们想方设法把他变小一点。 设一个快为 \(w_i=k\times x+r\)。其实,如果我们把他分为 \(x\) 个大小为 \(k\) 的块,然后一个大小为 \(r\) 的块是最优的。因为切成其他的大小的块,我们可以调整成这种切法, ......
Gym101064L The Knapsack problem
CF 传送门 发现物品的体积很小,尝试从此处入手。 设 \(K\) 为最大的物品体积。把背包体积 \(m\) 分成差不超过 \(K\) 的两部分,然后合并。这样需要求出 \(f(\frac{m}{2} - K \sim \frac{m}{2} + K)\)。 递归地,可以发现需要求出 \(f(\fr ......
Gym100078F Formula
非常好,竟然是有思维的模拟题。换句话讲就是有模拟的思维题 题意:给定一个由与或非组成的逻辑表达式,你需要把他化简成一个变量不重复的与或非逻辑表达式或报告无解。 发现如果允许变量重复了,这个逻辑表达式没有什么性质,任何一种真值表都可以通过合适的构造得来。所以题目相当于直接告诉我们一个真值表。 变量重复 ......
2021-2022 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2021) gym 104670 C
原题 容易想到最短路 DAG 求出来,起初我以为要求最小割,但这是错误的,因为可能有多条边联通了一个点的情况,这时候选择最小割不一定是最优的 我们猜想一个思路:答案一定是包含 \(1\) 号节点的连通块全部填 \(N\) ,剩下的填 \(S\) 。发现在最短路 DAG 中, \(1 \rightar ......
[gym103860D]Tree Partition
D - Tree Partition 考虑将树转换到一个序列上,钦定\(1\)为根节点,\(1\)的父亲为\(0\),在序列上,孩子向父亲连边 然后考虑设\(dp\)状态\(dp[i][j]\)表示前\(i\)个点,分成\(j\)段的方案数,那么\(dp[i][j]\)从\(dp[k][j-1]\) ......
《CF gym Reverse LIS》解题报告
原题链接 一开始看到这题就很像模拟费用流,不过立马就放弃了,然后之后就再也没想过这个思路了。。。 正解是模拟费用流,先讲一下答案长什么样,把 \(0\) 的权值记为 \(1\) , \(1\) 的权值记为 \(-1\) ,那么我们答案就是要选一段前缀和 \(k\) 段不相交的区间的最大值加上 \(1 ......
gym102331B Bitwise Xor
gym102331B Bitwise Xor 和我找到的题解都不同的做法。感觉简单一些。 首先将 \(a\) 排序,从高位往低位考虑,假设考虑第 \(p\) 位,不难发现这时序列按照第 \(p\) 位取值被划分为两部分,我们注意到如果 \(x\) 的这一位是 \(0\) 那么这两部分各取两个数异或起 ......
Gym 103428B Subset
CF 传送门 首先考虑没有选出的数互不相同的限制。设 \(f_m\) 为选出 \(m\) 个 \(\in [0, n]\) 的数,异或 \(\text{popcount} = k\) 的方案数。可以考虑枚举这 \(m\) 个数和 \(n\) 的 \(\text{LCP}\)(要求后一位为 \(1\) ......
Gym 104270 The 2018 ICPC Asia Qingdao Regional Programming Contest (The 1st Universal Cup, Stage 9: Qingdao)
A. Sequence and Sequence B. Kawa Exam 可以发现,对答案会产生影响的只有割边,把所有边双缩起来,然后就是一个森林。 考虑一个树的时候怎么做,就是对于每条边求出这条边两端的众数个数,考虑线段树合并,每次动态维护子树内的众数和子树外的众数。 #include<iost ......
Gym 104172 The 2023 ICPC Asia Hong Kong Regional Programming Contest (The 1st Universal Cup, Stage 2Hong Kong)
A. TreeScript 令 \(f_u\) 表示 \(u\) 及 \(u\) 子树中的节点都创建的最小数量。 如果 \(u\) 只有一个儿子,那么可以将子树最后一个节点存储在当前的 \(u\) 中,答案就是 \(f_v\)。 若 \(u\) 有多个儿子: 令 \(t=\max\limits_{v ......
gym100702D Log Set
gym100702D Log Set 版本 T0。 学背包不做 Log Set,就像打二游不玩某二字开放世界游戏,追星不追理塘王丁真珍珠,玩泣系旮旯不玩克拉纳的,只能度过一个相对失败的人生。 Problem 有一个大小为 \(m(m \le 60)\) 的多重集 \(S\),它的所有子集(包括空集) ......
题解 Gym 104077I【[ICPC2022 Xi'an R] Square Grid】
题解 Gym 104077I【[ICPC2022 Xi'an R] Square Grid】 problem 二维棋盘,边界是 \((0,0)\) 到 \((n,n)\)。 对于某个棋子,单次移动可以朝着上下左右四个方向之一移动一格。 对于 \(q\) 个独立的棋子,分别问时间 \(T\) 秒以后: ......
2023.9.20 CF gym 104128 vp
The 2022 ICPC Asia Nanjing Regional Contest https://codeforces.com/gym/104128 A ......
GYM104090A Modulo Ruins the Legend - exgcd -
题目链接:https://codeforces.com/gym/104090/problem/A 题解: 转化一下发现只需要求满足下式的解: \[ns+\dfrac{n\times (n+1)}{2}d \equiv C(\bmod m) \]设 \(a=n,b=\dfrac{n(n+1)}{2}, ......
2023.9.15 CF gym 104369 vp
The 2023 Guangdong Provincial Collegiate Programming Contest https://codeforces.com/gym/104369 A 枚举并判断即可。 B 注意到相邻的基站中不能有完整的区间, 我们可以双指针求出最小的 \(p_i\),使得 ......
GYM 104128 G
G. Inscryption 根据题意,需要把输入的\(0\)全部转换为\(1\)或\(-1\),使得\(p\over q\)最大。 当\(a[i]=1\)时,\({p \over q}={p'+1 \over q'+1}\) 当\(a[i]=-1\)时,\({p \over q}={p' \ove ......
gym104531 I Bracket
题意 题面 做法 结论:对于字符串\(s\),其为合法括号序列的充要条件为 (1)\(|s|\)为偶数, (2)构造序列\(a_i\),若\(s_i\)='(' or '?',则\(a_i=+1\);若\(s_i\)=')',则\(a_i=-1\),\({a_i}\)的前缀和均\(\ge 0\) ( ......
[2022 China Collegiate Programming Contest (CCPC) Guilin Site](https://codeforces.com/gym/104008) CEM
2022 China Collegiate Programming Contest (CCPC) Guilin Site CEM C. Array Concatenation 思路:数学推柿子 考虑有两种操作: 复制 \(b' = \{b_1,b_2,...,b_{|b|},b_1,b_2,..., ......
题解 Gym 104531D【Coffee】
2022 SYSU School Contest 题目不想翻译了,自己看能看懂。 problam The girls of HTT like drinking tea. But one day, they wanted a change and decided to try coffee in th ......
2022 Hubei Provincial Collegiate Programming Contest G. Brick(gym103729)
大意 给出底层高度,用1*2的砖块将总形状铺成等高矩形,使得高度最小(不能放在外面) 题解 奇妙做法 当高度同奇偶时显然x可以的话x+2也可以,直接加一层竖的,所以首先分奇偶二分高度 有解的必要条件1是,把矩形黑白方格染色之后未填的黑=白(一个1*2刚好覆盖1黑1白) 然后从左往右放砖块,可以感受一 ......
GYM 104128 M
M. Drain the Water Tank 这道题需要用到向量间的叉积运算。 首先输入所有点,储存在数组\(a\)中,并将其全部转化为向量,储存在数组\(b\)中。 为了排尽水箱里的所有水,需要找到每一个属于水箱内容物局部最低块中的一个点。 所以可以将判断分为两步 判断是否为局部最低点:当\(b ......
Gym102994M Travel Dream
题意:$n$ 个点的图,找一个有 $k$ 个点的的简单环,使其边权和最大。 随机黑白染色,拆成两条颜色不同的不相交链,做 $300$ 次即可。链的情况是好做的,做完后,可以枚举两条边,预处理 $f_{x,y}$ 表示 $x$ 到 $y$ 的最大距离。 链点数 $\leq 4$ 都是可以直接暴力枚举的 ......
安装强化学习包gym报错问题及解决方法
安装命令 pip install gymnasium[all] 如遇如下报错 error: command 'swig.exe' failed: No such file or directory [end of output] note: This error originates from a ......