Deep_Kevin的娱乐空间

正题 第一题：信仰圣光 精灵王国的每一名精灵都曾是圣光的信徒，在圣光的沐浴下歌颂祈福。 然而百年前的那场浩劫摧毁了 Bzeroth 大陆与神界的通道，同时将大陆打碎分散到了 不同的次元里。 百年后神界终于再次听到了精灵的祷告，找回了 Bzeroth大陆所在的次元。 经过了近百年的休养生息，精灵们终于在这片被抛弃的土地上重新建造了自己的文 明。现在的 Bzeroth大陆被...

正题 第一题：分则能成 这是之前写过的blog。 第二题：明辨是非 这题一开始想了很久，脑子里全是分块并查集，然后不断的把关系丢来丢去，很麻烦，其实只用考虑当前的一张关系图，有一些白边表示相等，有一些黑边表示不相等，首先我们可以把白边联通的点用并查集缩起来，然后考虑缩点之间的黑边，直接用set记录每一个联通块的黑出边就可以了，合并两个联通块的...

正题 第一题：Door Street 是一条繁华的街道，沿街一共有栋大楼，编号依次为 ，相邻两栋楼编号相邻。 现在你想在 Door Street 开一家咖啡厅，你可选址在任意一栋楼内。每栋楼都有一个消费指数 。若你 选址在第x号楼，则第i号楼的人在你的咖啡厅消费 ，你的收入是 n 栋大楼的 人的消费总和，即 。 对于每栋大楼，你想评估出你若选址在该大楼，你的收入分别是多少？ ...

专题测试 第一题：整数的 lqp 拆分整数拆分是个很有趣的问题。给你一个正整数 N，对于 N 的一个整数拆分就是满足任意 m>0, a1,a2,a3…am>0，且 a1+a2+a3+…+am=N 的一个有序集合。通过长时间的研究我们 发现了计算对于 N 的整数拆分的总数有一个很简单的递推式，但是因为这个递推式实在太 简单了，如果出这样的题目，大家会对比赛毫无兴趣的。 然后...

正题 第一题：有 n 个数字，a[1],a[2],…,a[n]。有一个集合，刚开始集合为空。然后有一种操作每次向 集合中加入一个数字或者删除一个数字。每次操作给出一个下标 x(1 ≤ x ≤ n)，如果 a[x]已 经在集合中，那么就删除 a[x],否则就加入 a[x]。 问每次操作之后集合中互质的数字有多少对。 注意，集合中可以有重复的数字，两个数字不同当且仅当他们的下标不同。 比...

综合测试 第一题：给出一个长度为 N 的序列 A[n]和 M 个操作，操作分为两种类型： 类型一，给出参数 l r k b 对于 l 到 r 之间(闭区间)的所有数 i ,令 A[i] = max(A[i],k*(i-l)+b ) 类型二，给出参数 l r, 求出 A[l] 到 A[r] 共(r-l+1)个数之中的最大值。 我们用线段树维护，每一个节点维护当前的直线，如...

综合模测 第一题：Alice和Bob是好朋友，她们经常喜欢在一起玩石子游戏。这一次他们想出了一个新 玩法：有若干堆石子，要求每次在一堆数量不为1的石子堆中取出石子，假设这堆石子 的个数是x，那么允许取的个数为正整数d，要求d|x且d ≠ x。如果没有办法再取石子了， 需要操作的那一方就输了。 游戏初始有m堆石子，每堆石子的个数均为1到n之间的正整数。Alice和Bob都是绝 对聪明的...

专题测试 第一题：大家都知道田忌赛马的故事，田忌和齐王又要赛马了，他们将各派出 N 匹马，每场比赛输 的一方需要给赢的一方 200 两黄金，平局的话双方都不比出钱，已知所有马的速度，且齐王 的出马顺序永远固定，求田忌的最大收益。 有一个很显然的贪心算法，就是将它们两个序列从大到小排序，比较当前齐王最大的和田忌最大的。如果田忌的比齐王的大，那么就拿出来比。如果田忌最小的比...

水法测试 第一题：小 M 培养了 n 个菌落。其中每个菌落有质量和颜色两种属性，颜色只可能为紫色或 红色。小 M 想把所有的菌落合并成一个菌落。 因为合并的过程非常费劲，小 M 每天只能进行一次合并，整个过程需要进行 n-1 天。 一次合并会将两个菌落变成一个菌落。如果原来两个菌落的颜色相同，两个菌落会进行融合， 新的菌落质量为原来两个菌落质量之和，颜色不变；如果原来两个菌落的颜色不...

综合测试 考试的前一天老师说今天的题比NOI稍微简单一些。 第一题，给你n，要你求。定义为其所有约数的异或和。. 这题还是比较简单的，直接数论分块，讨论那些为奇数就行了。 求前缀和的时候考虑相邻两个数（偶奇）的异或和为1.然后讨论一下情况就可以了。 #include<cmath> #include<cstdio> ...

专题测试 第一题：经典带修莫队：数颜色。 虽然打了出来但是证明复杂度也是刚才才会。 题意就是一开始给你一个序列，每次要么询问x到y中不同元素的个数，要么修改第x个元素为y。 假如我们按S把询问分块，一开始按第一关键字把l所在的块排序，按第二关键字把r所在的块排序，按第三关键字把t排序。 t就是这个询问之前的修改操作个数。 ...

专题测试 第一题：有一个序列，给出序列D满足对于，，现在已知，要你求。 我一开始做的就是推式子，然后发现我推出来的垃圾式子只能做的情况。后来想了想，这个里面没有二次项，所以，所以就直接二分的值，然后根据di算出来的值，又因为成比例变化，所以就可以直接二分了。 唯一要注意的一点就是一开始先算一算是正相关还是负相关。 #include<cstdio&...

专题测试 今天早上的题都是搜索。 第一题：给出n个开关，一个开关对应一个灯，灯与灯之间有连边，当摁下一个开关时，对应的灯和相邻的灯都会改变状态，问至少摁下多少开关，才可以把所有灯打开。 这道题很容易就可以想到一个结论：一个开关只会被打开一次，打开两次没有影响。 就可以直接爆搜拿到60分。满分也很简单，我们折半搜索，把第一次搜索的结果存在一个m...