dtoj专题
DTOJ 2937. Sum of LCM
题意： 对于 A 1 , A 2 , … , A N A_1, A_2, \ldots, A_N A1,A2,…,AN ，求 ∑ i = 1 N ∑ j = 1 N l c m ( A i , A j ) \sum_{i = 1}^N \sum_{j = 1}^N \mathrm{lcm}(A_i, A_j) ∑i=1N∑j=1Nlcm(Ai,Aj) 的值。 l c m ( a
DTOJ#4170. 「PKUWC2018」猎人杀
题意： 猎人杀是一款风靡一时的游戏“狼人杀”的民间版本，他的规则是这样的： 一开始有 n n n 个猎人，第 i i i 个猎人有仇恨度 w i w_i wi ，每个猎人只有一个固定的技能：死亡后必须开一枪，且被射中的人也会死亡。 然而向谁开枪也是有讲究的，假设当前还活着的猎人有 [ i 1 … i m ] [i_1\ldots i_m] [i1…im]，那么有 w i k
DTOJ #4235. 交朋友
题意： 给定一个n个点m条边的有向图，对于同一个点连向的两个点可以互相连双向边，求图中最多有几条边。 题解： 直观地想，首先对于每一个点，若它的出度大于1，则它连向的边为一个完全图，但每个点做完后又会产生影响，因此没法保证效率。 发现“对于同一个点连向的两个点可以互相连双向边”这个条件类似于并查集，即把双向边视为无向边，这样恰好满足了并查集的性质。 因为原始的边不在并查集的考虑范围内，故用原始的边
（CSP2019模拟）DTOJ 4644. speike
题意 众所周知，Speike 狗是一条特别喜欢追着Tom 打的狗。 现在，Tom 又把Speike 惹生气了，现在Speike 需要跨越千山万水找Tom 报仇。 Speike 所在的世界可以看成是一个无穷大的平面，平面由一个平面直角坐标系确定。在平面上有许多不相交的矩形障碍，矩形的四边平行于坐标轴。 Speike 需要从 ( 0 , 0 ) (0,0) (0,0) 出发，在尽量短的时间内
DTOJ 4538. 「TJOI / HEOI2016」排序
题意 在 2016 年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。 这个难题是这样子的：给出一个 $1 $ 到 n n n 的全排列，现在对这个全排列序列进行 m m m 次局部排序，排序分为两种： ( 0 , l , r ) (0, l, r) (0,l,r) 表示将区间 [ l , r ] [l, r] [l,r]
（CSP2019模拟）DTOJ 4629. 世界
题意 有一个虚无的结界，隔开了两个世界。 人们在结界内游荡，而远方的星辰在结界外。 我们可以把结界看作 x x x 轴，那么人们都在 x x x 轴下方，而星星都在 x x x 轴上方。 人们本应该能看到所有的星星，但是结界外( x x x 轴上方)出现了几座墙，挡住了人们的视线。墙是平行于 x x x 轴的。 现在想问，每个人分别能看到多少星星。 测试点编号 n n n m
（CSP2019模拟）DTOJ 4632. 隐蔽的居所
题意 在小G的家乡，有很多人住在一个大湖的边上。 他告诉小D，这个大湖可以被视作一个圆。一共有 N N N 户人家， 他们住在这个圆的 N N N 等分点上，每个 N N N 等分点上恰好有一户人家. 这里的每户人家都有不同的信仰，其中第 i i i 户人家信仰第 i i i 种宗教。很显然，宗教对于生活会产生一定的影响，具体来说，相邻两户人家信仰的宗教的编号之差的绝对值不可以超过
（CSP2019模拟）DTOJ 4624. 树
题意 给定一棵 n n n 个结点的树，共有 q q q 次询问。 第 i i i 次询问首先包含了三个数 k i , m i , r i k_i,m_i,r_i ki,mi,ri ，接着给定了树上互不相同的 k i k_i ki 个关键点 a i , 1 , a i , 2 , … , a i , k a_{i, 1}, a_{i, 2}, \dots, a_{i, k}
（CSP2019模拟）DTOJ 4628. 黎明
题意 有一片云海形成的世界，有陆地有海洋，可以看作 R × C R \times C R×C 的网格。 随着岁月的变迁，有时候水位上涨，一部分区域会变成水道。 神奇的是，每次变成水道的区域都是一个矩形。(若这个矩形中有一部分原来就是水道，那么这部分不变，其他为陆地的部分变成水道) 有时候这个世界上会有人想从 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 通过在水道
（2019CSP模拟）DTOJ 4627. 灰烬
题意 灰烬之地有一排石柱，从左到右共有 n n n 个，其中有一些上面有灰烬，有一些上面没有。 你现在可以操控风的力量，风只能从左到右吹，每次你可以选择一个 k k k ( k k k 每次都可以变化)，扬起前 n − k n-k n−k 个石柱上的一半的灰烬(你可以认为灰烬无穷多，每次取当前的一半，换言之是可以无限复制的)，将其向右吹动 k k k 个位置。 问至少多少次可以使灰
（CSP2019模拟）DTOJ 4617. 逛公园
题意 小凯做题做累了，他想去逛公园。 公园里有 m m m 个亲子项目，每个项目一天只能一个家庭参加。一共有 n n n 个家庭，第 i i i 个家庭希望在第 l i l_i li 到 r i r_i ri 天内参加恰好一次第 p i p_i pi 个项目。但是公园的工作人员很懒，他们希望上班的天数尽量少。某天要上班当且仅当至少有一个家庭参加了任意一个项目。 工作人员看到
（FJWC2020）DTOJ 4695. lg
题意 有两个正整数 n n n 和 m m m。 我们考虑所有长度为 n n n，每个元素在 [ 1 , m ] [1, m] [1,m] 的整数序列。对于所有整数序列，设 l c m lcm lcm 为这个序列中元素的最小公倍数， g c d gcd gcd 为这个序列中元素的最大公约数，我们希望求出 l c m g c d lcm^{gcd} lcmgcd。你需要对于所有这些整数
(FJWC2020) DTOJ 4690. 亚特兰大
题意 司令部截获了深海的电报，你的镇守府即将被深海轰炸。 虽然你作为历战提督，已经有了很多局地战、火箭机，但是刚刚击破 E6 甲，拥有亚特兰大以及最高倍率对空 ci 的你，决定只用亚特兰大抵挡对面的炸家。 你的镇守府可以看成一棵树，深海的轰炸是在某两个点之间进行的（起点终点交换视为一种），轰炸路径是树上的简单路径。也就是说，深海一共有 C n 2 C_n^2 Cn2 种可能的轰炸方案。 你的
(FJWC2020) DTOJ 4686. 字符串
题意 你喜欢字符串。有人送了你一个仅含小写字母的字符串。 由于你是一名优秀的 OIer，所以你决定对这个字符串展开研究。 定义两个字符串是相似的，当且仅当存在至多一个 i i i，使得这两个字符串中只有第 i i i 个字母不同。 你取出了这个字符串中所有长度为 m m m 的子串。你想知道，对于每个长度为 m m m 的子串，有多少个其它长度为 m m m 的子串与它相似。 子任务
（FJWC2020） DTOJ 4689 图（graph）
题意 有一张 n n n 个点， m m m 条边的无向图，你想选出一个非空点集，使得仅保留这个点集中的点和两个端点都在这个点集里的边后得到的图是连通的。你想知道有多少种可能的选点集的方案。 由于出题人不是毒瘤，所以本题不对 998244353 998244353 998244353 取模，改为对 2 2 2 取模。 对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 50
（FJWC2020）DTOJ 4696. pm
题意 有一个长度为 n n n的排列 p p p，你可以对它进行若干次把相邻两个数交换的操作，使得操作数 + ( i ! = p [ i ] ) +(i!=p[i]) +(i!=p[i])的 i i i的个数之和最小。 题解 考场思路： 剩下不到一小时开始想，注意到相同的操作不会重复进行，（容易证明）。于是交换操作是有用的，当且仅当能把完全乱序的包含 l , . . . , r l,...,
（FJWC2020）DTOJ 4681. 楼房搭建
题意 小 H 是一个建筑师，他接到了一个任务——按照计划图搭建一排楼房。计划图上从左到右 给出了 n n n 个非负整数，对于第 i i i 个数 h i h_i hi ，它表示在 i i i 这个位置搭建出来的楼房的高度不能小于 h i h_i hi 。 小 H 搭建楼房的方式也很特别。在每一时刻，它总可以让相邻的两个楼房分别增高 1 1 1 个单位和增高 2 2 2 个
（FJWC2020）DTOJ 4680. 红黑兔
题意 上个月，PinkRabbit 在算法竞赛网站 Codeforces 一把打上了 ILGM。 PinkRabbit 现在看到了一道简单题，但他忙于水知乎夺取 Codeforces 世界榜首，于是把问题交 给了你： 给定一个长度为 n n n 的只包含小写英文字母的字符串 s s s，你需要找到一个最大的 k k k ，使得存在： 1 ≤ l 1 ≤ r 1 < l 2 ≤ r 2
（FJWC2020）DTOJ 4679. 赢家
题意 给定一个 n n n个点 m m m条边的无向图，给每一条边定向，使得存在一个点，1号点和2号点能同时到达，求边定向的方案数。 n ≤ 15 n\le 15 n≤15 题解 暴力做法就是枚举每条边的方向，判断1号点和2号点能走到的点集是否有交集。 发现有交集是不好直接计数的，考虑容斥：总方案数减去无交集的方案数。于是预处理出1号点和2号点分别能到达极大的每个集合的方案数，枚举它们到达
DTOJ 4844. 数据结构
题意 联测题不方便写出来。 题解 原本的想法是先按照 B B B降序排序， 把 i i i套进 j j j看作 i i i连到 j j j的一条有向边，这样每个点能连到的点就是一段前缀，求所有极大的连边方案数。但这样由于前缀长度不是单调的，DP时难以用多项式的效率记录状态。 考虑如何使前缀长度单调，即连出边的点按照 A A A从大到小考虑，被连边的点依然按照 B B B从大到小排序（即把每
DTOJ 4792. 清扫银河
题解 “环银河系航行计划所面临的最大危险是失败主义。” 章北蚤非常严肃地对你说，“失败主义的思想根源，主要是盲目的技术崇拜，轻视或忽视人的精神和主观能动性在发展工质发动机中的作用。” 为了避免失败主义在军队中的蔓延，章北蚤建议先进行清扫银河计划，提振士气，增强信心。 银河系共有 n n n 颗行星，编号为 1 , … , n 1,…,n 1,…,n。环银河系航行可能会经过的无向航道共有
DTOJ 4793. 通用测评号
题意 完成清扫银河计划带来的信心并不能让跳蚤们的航天科技突飞猛进，你看不到任何用现有的工质发动机技术完成环银河系航行的可能性。但这时，章北蚤向你展示了最新的通用测评号恒星级宇宙飞船 —— 它拥有最新一代的工质发动机，全功率推进时，理论上可以加速到光速的千分之五。 为了实验通用测评号的实际效果，你被安排给通用测评号装填燃料。通用测评号上有 n n n 个燃料舱，初始时均为空。一个燃料舱被填满时
DTOJ 4780. 病毒研究
题意 病毒科学家陈博士正在带领着她的团队在研究病毒，她要研究如何降低病毒的活性。病毒的活性可以用一个整数来表示，但她不知道具体的活性是多少。 她可以执行 m + 1 m+1 m+1 种操作，对于前 m m m 种操作，第 i i i 种操作为花费 v i v_i vi 的代价使得病毒 的活性减少 w i w_i wi；第 m + 1 m+1 m+1 种操作为查看当前病毒所处的状
DTOJ 4781. 抗疫斗争
题意 新冠疫情爆发以来，病毒不断地扩散传播，而人类也在不断采取各种措施遏制病毒传播。于是我们可以为这场抗疫斗争建立一个数学模型，将病毒的不断传播和人类的不断采取措施抽象为一场双方轮流行动的博弈。我们认为人类与病毒的每轮行动都可以选择一个正整数作为行动值来评估。然而，出于各方面限制，双方的所有行动值总和必须等于一个数 m m m，且每次的行动值不能超过对方上轮的行动值。对人类来说，要遏制疫情，就
DTOJ 4749. 计数
题意 计数弱智题目 7 i n 1 7 in 1 7in1，就算你不是都会算也可以，本题根据你答对多少个问题来决定你得到多少分 第一类问题：求 n n n 个点构成的有标号无根树有多少种 第二类问题：求 n n n 个点构成的有标号有根树有多少种 第三类问题：求 n n n 个点构成的无标号无根树有多少种 第四类问题：求 n n n 个点构成的无标号有根树有多少种 第五类问题
DTOJ 4746. 我家钥匙放在哪了
题意 张士超是你在上海音乐学院的基友，关系非常好。你们在五角场附件合租了一间屋子。由于你那么有钱，一下买了 n n n 把相同的锁，并一下配了 N N N 把相同的钥匙。你用这些锁并联锁住你家的大门，需要同时插入 n n n 把钥匙才能打开。 一天晚上，张士超带着华师大的姑娘去了闵行。而且还把你们的 N N N 把钥匙全部藏在了一些奇怪的地方。 张士超有 M M M 个可能的地方来