标签 - 组合数

? 解题记录 ? ? FFT|NTT ? ? 树链剖分 ? ? 虚树 ? ? 组合数 ?    2019-03-18 12:09:49    1141    0    3
题目描述 给你一棵n个点的树,每一个点有个颜色ci" role="presentation" style="position: relative;">cicic_i。定义一种颜色的树是:把该颜色的点两两路径上的点和边都拿出来构成的图形。你可以选出k" role="presentation" style="position: relative;">kkk种颜色来,求:有多少种方案可以使每种颜色交集产生的树非空。对k∈[1,m]" role="presentation" style="position: relative;">k∈[1,m]k∈[1,m]k
? 解题记录 ? ? Atcoder ? ? 组合数 ? ? 构造 ?    2019-03-01 11:21:44    352    0    0
A Digits Sum for" role="presentation" style="position: relative;">forforfor循环题目,就不翻译了。 B RGB Coloring 题意:一个长度为n" role="presentation" style="position: relative;">nnn的序列,可以染成三种颜色或者不染,得分分别为A,B,A+B,0" role="presentation" style="position: relative;">A,B,A+B,0A,B,A+B,0A,B,A+B,0。问有多少种本质不同的
? 解题记录 ? ? Atcoder ? ? 线段树 ? ? 组合数 ? ? 贪心 ? ? 动态规划 ?    2019-02-16 15:14:38    584    0    0
A Two Abbreviations 签到题,就不翻译了 找两个串一段长度的gcd" role="presentation" style="position: relative;">gcdgcdgcd,判一判对应位置一不一样就可以了。 B Removing Blocks 题意:给你一个长度为N" role="presentation" style="position: relative;">NNN的序列,将N" role="presentation" style="position: relative;">NNN个数依次删掉。每一次删掉一个数的代价是这个数
? 解题记录 ? ? 组合数 ? ? 动态规划 ? ? UOJ ?    2018-12-19 14:41:24    395    0    0
我是原题 题目等价于求最长下降子序列长度不超过2" role="presentation" style="position: relative;">222的排列个数,否则就不可能让冒泡排序在复杂度下限。 先想一个dp" role="presentation" style="position: relative;">dpdpdp做法:设f(i,j)" role="presentation" style="position: relative;">f(i,j)f(i,j)f(i,j)是放到了第i" role="presentation" style="position:
? 解题记录 ? ? LOJ ? ? 动态规划 ? ? 状态压缩 ? ? 组合数 ?    2018-12-05 20:33:53    860    0    0
题目地址:呀,戳轻点qwq 一开始自己就想错了,本来以为只要选择的点集定了,那么覆盖状态也就定了。 但是发现并不对,和点选择的顺序还有关。 …… 我们去Orz" role="presentation" style="position: relative;">OrzOrzOrz题解吧。 发现自己仍然是没有完全理解增量的构造方式。 考虑到选择点的顺序其实是和答案有关的,我们考虑对整个操作序列增量的过程进行dp" role="presentation" style="position: relative;">dpdpdp。 设f(i,S)" role="presenta
? 解题记录 ? ? LOJ ? ? 组合数 ? ? 动态规划 ?    2018-12-05 20:07:46    695    0    0
题目地址:大家好,我是"题目地址" 想比较不容易偏,但写着细节贼多的题。 首先考虑最优策略,注意到题目给出强化牌的wi>1" role="presentation" style="position: relative;">wi>1wi>1wi>1的条件。 因此,优先打出最大的强化牌一定是最优的,考虑选择了两张最大的攻击牌,仍然与选择最小的强化牌等价。 接下来我们考虑选牌的情况: 设拿到了强化牌c" role="presentation" style="position: relative;">ccc张,攻击牌m−c
? 解题记录 ? ? 洛谷 ? ? 组合数 ? ? 筛法 ?    2018-11-04 15:28:51    671    0    0
2.1 题目描述 九条可怜是一个热爱游戏的女孩子,她经常在网上和一些网友们玩一款叫做《僵尸危机》 游戏。 在这款游戏中,玩家们会需要在成为僵尸之前与黑恶势力斗智斗勇,逃离被病毒感染的小 岛。但是黑恶势力不会让玩家轻易得逞,他会把一些玩家抓走改造成僵尸。变成僵尸的玩家会 攻击其他的玩家,被攻击的玩家会被” 感染”,成为病毒的潜在宿主。 具体来说,游戏开始时,所有的玩家会获得一个 l ∼ r 的编号 (如果一共有 r − l + 1 个玩 家),不同的玩家的编号不同。 游戏分轮次进行,在每一轮中一次会发生这样的事情。 • 如果所有当前所有的正常人都已经被感染,那么游戏结束。 •
? 解题记录 ? ? 洛谷 ? ? 组合数 ?    2018-11-04 15:01:22    502    0    0
题目背景 2018年11月17日,中国香港将会迎来一场XM大战,是世界各地的ENLIGHTENED与RESISTANCE开战的地点,某地 的ENLIGHTENED总部也想派Agent去参加这次的XM大战,与世界其他地方的ENLIGHTENED并肩作战。 题目描述 某地的ENLIGHTENED总部总部有N" role="presentation" style="position: relative;">NNN个Agent,每个Agent的能力值互不相同,现在ENLIGHTENED行动指挥想要派出A,B两队Agent去参加XM大战。但是参加大战的两个队伍要满足两个要求: A队中能
? 解题记录 ? ? 洛谷 ? ? 组合数 ? ? 动态规划 ?    2018-11-04 14:41:27    734    0    0
题目描述称一个1,2,...,N的排列P1,P2...,Pn是Magic的,当且仅当2<=i<=N时,Pi>Pi/2. 计算1,2,...N的排列中有多少是Magic的,答案可能很大,只能输出模P以后的值 输入输出格式输入格式:   输入文件的第一行包含两个整数 n和p,含义如上所述。   输出格式:   输出文件中仅包含一个整数,表示计算1,2,⋯, ���的排列中, Magic排列的个数模 p的值。   输入输出样例输入样例#1: 复制20 23 输出样例#1: 复制16 说明100%的数据中,1 ≤N ≤ 1
? 解题记录 ? ? 洛谷 ? ? 组合数 ? ? 模拟 ?    2018-11-04 14:09:05    775    0    0
1.1 题目描述 九条可怜是一个热爱思考的女孩子。 九条可怜最近正在研究各种排序的性质,她发现了一种很有趣的排序方法:gobo sort! Gobo sort 的算法描述大致如下: • 1. 假设我们要对一个大小为 n 的数列 a 排序。 • 2. 等概率随机生成一个大小为 n 的排列 p 。 • 3. 构造一个大小为 n 的数列 b 满足 bi = api,检查 b 是否有序,如果 b 已经有序了就结 束算法,并返回 b ,不然返回步骤 2 。 显然这个算法的期望时间复杂度是 O(n × n!) 的,但是九条可怜惊奇的发现,利用量子的 神奇性质,在量子系统中,可以把这个算法