Yan2u's Blog

题目限制一览 题目 时间限制 空间限制 1. magician $1000$ MS $128$ MB 2. seq $1000$ MS $128$ MB 3. show $1000$ MS $128$ MB 1. 黑魔法师之门（magician.cpp）Description经过了 16 个工作日的紧张忙碌，未来的人类终于收集到了足够的能源。然而在与 Violet 星球的战争中，由于 Z 副官的愚蠢，地球的领袖 applepi 被邪恶的黑魔法师 Vani 囚禁在了 Violet 星球。为了重启 Nescafé这一宏伟的科技工程，人类派出了一支由 HQX 1人组成的精英队伍，穿越时空隧道，去往 Violet 星球拯救领袖 applepi。 applepi 被囚禁的地点只有一扇门，当地人称它为“黑魔法师之门”。这扇门上画着一张无向无权图，而打开这扇门的密码就是图中每个点的度数大于零且都是偶数的子图的个数 对 1000000009 取模的值。此处子图 (V, E) 定义为：点集 V和边集 E 都是原图的任意子集， 其中 E 中的边的端点都在 V中。 但是 V ...

题目限制一览 题目 时间限制 空间限制 1. buckets $1000$ MS $256$ MB 2. factory $1000$ MS $256$ MB 3. dining $1000$ MS $512$ MB 1. 救火（buckets.cpp）Description农场上起火了，奶牛们正在紧急赶去灭火！ 农场可以用一个像这样的10×10的字符方阵来描述： 12345678910................................B......................R.............................L.............. 字符’B’表示正着火的牛棚。字符’L’表示一个湖，而字符’R’表示农场上的一块巨大岩石。 奶牛们想要沿着一条湖到牛棚之间的路径组成一条“水桶传递队列”，这样她们就可以沿着这条路径传递水桶来帮助灭火。当两头奶牛在东南西北四个方向上相邻时水桶可以在她们之间传递。这对于湖边的奶牛也是对的——奶牛只能在紧挨着湖的时候才能用水桶从湖里取水。类似地，奶牛只能在紧挨着牛棚的时候才能用水去 ...

题目限制一览 题目 时间限制 空间限制 1. pudding $1000$ MS $256$ M 2. trouble $1000$ MS $256$ M 3. tree $1000$ MS $256$ M 1. 梦幻布丁（pudding.cpp）DescriptionN个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜色. Input第一行给出N,M表示布丁的个数和好友的操作次数.第二行N个数A1,A2…An表示第i个布丁的颜色从第三行起有M行,对于每个操作,若第一个数字是1表示要对颜色进行改变，其后的两个整数X,Y表示将所有颜色为X的变为Y，X可能等于Y.若第一个数字为2表示要进行询问当前有多少段颜色，这时你应该输出一个整数. Output针对第二类操作即询问，依次输出当前有多少段颜色. Sample Input123454 31 2 2 121 2 12 Sample Output1231 Hint1<=n,m<=100,000; ...

题目限制一览 题目 时间限制 内存限制 抓蛇 Snake $1000$ MS $256$ MB 分组行走 Walk $1000$ MS $512$ MB 谈笑风生 Talk $2000$ MS $512$ MB Problem#1. 抓蛇 SnakeDescription传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的3月17日，所以小明要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。小明装备了一个捕网，用来捕捉N组排成一行的蛇（1≤N≤400）。小明必须按照这些组在这一行中出现的顺序捕捉每一组的所有蛇。每当小明抓完一组蛇之后，她就会将蛇放在笼子里，然后带着空的捕网开始捕捉下一组。 一个大小为s的捕网意味着小明可以抓住任意包含g条的一组蛇，其中g≤s。然而，每当小明用大小为s的捕网抓住了一组g条蛇，就意味着浪费了s−g的空间。小明可以任意设定捕网的初始大小，并且她可以改变K次捕网大小（1≤K<N）。 请告诉小明她捕捉完所有组的蛇之后可以达到的总浪费空间的最小值。 Input输入的第一行包含N和K。第二 ...

二分图的最大匹配回顾首先，回顾一下什么是二分图： graph LR 1---4; 2---5;2---6 3---6 图中的点能被分成两个集合，使得每一条边两端的点均分属于两个集合，判断二分图可以用 染色法 来解决，例如图中就可以取：${1,\;4}\quad{2,5}\quad{3,\;6}$ 二分图的最大匹配二分图的匹配，故名思义，就是寻找二分图中的一些点对，使得这些点对分属于二分图的两个集合，最大匹配，就是寻找最多能选择的点对的数量，上图中，最大匹配为 3 解决最大匹配，可以用到 网络流 中的 费用流 ，建立源点 S 和 汇点 T 跑费用流，还有一种著名的算法就是 匈牙利算法 匈牙利算法算法演示 通过数代人的努力，你终于赶上了剩男剩女的大潮，假设你是一位光荣的新世纪媒人，在你的手上有N个剩男，M个剩女，每个人都可能对多名异性有好感（暂时不考虑特殊的性取向），如果一对男女互有好感，那么你就可以把这一对撮合在一起，现在让我们无视掉所有的单相思（好忧伤的感觉），你拥有的大概就是下面这样一张关系图，每一条连线都表示互有好感。 本着救人一命，胜造七级浮屠的原则，你想要尽可能地 ...

2-SAT 问题 $\mathtt{SAT=Satisfiability}$ 2-SAT 问题，就是求一类 在多个只有两个元素的集合里面选择元素，每个集合里面只能选一个，并满足给定的约束条件 的问题，处理这类约束条件的思路有点像 差分约束系统，即建立有向图来表示限制条件，这类问题的一般形式其实是 K-SAT 问题，即每个元素里面有 K 个元素，2-SAT 只是其中的一个情况 由于 2-SAT 问题不好系统地解释，下面用一个例题结合起来总结： CQYZOJ P2060.和平委员会Description 某国有n个党派，每个党派在议会中恰有2个代表。现在要成立和平委员会 ，该委员会必须满足： 　　1、每个党派在和平委员会中有且只有一个代表 。　　2、如果某两个代表不和，则他们不能都属于委员会 。 　　代表的编号从 1 到 2n，编号为 2a-1、2a 的代表属于第a个党派，求和平委员会是否能创立。若能，求一种构成方式。 　　PS：有n个组，第i个组里有两个节点Ai, Ai” 。需要从每个组中选出一个。而某些点不可以同时选出（称之为不相容）。任务是保证选出的n个点都能两两相容。这类型的 ...

Problem.#1：虫洞(wormhole.cpp/c/pas) While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ’s farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes. As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel ...

Description Each of Farmer John’s N (4 <= N <= 16) cows has a unique serial number S_i (1 <= S_i <= 25,000). The cows are so proud of it that each one now wears her number in a gangsta manner engraved in large letters on a gold plate hung around her ample bovine neck. Gangsta cows are rebellious and line up to be milked in an order called ‘Mixed Up’. A cow order is ‘Mixed Up’ if the sequence of serial numbers formed by their milking line is such that the serial numbers of ever ...

树链剖分树链剖分解决的主要是树上的区间修改，区间查询问题，其本质就相当于把线段树的操作从连续的序列移动到了一棵树上，当然操作的区间 $[L,\;R]$ 就变成了树上的点 $(u\,\;v)$ ，以下问题可以用树剖解决： 将树上两点 $(u,\;v)$ 之间的所有点权值加上 $\delta$ 询问 $\sum^{v}_{i=u}w[i]$，表示从 $u$ 到 $v$ 的唯一路径上的所有点权值之和 询问 $max\lbrace w[i]\;\;\; i\in\lbrace u,\;v \rbrace \rbrace$，表示询问 $u$ 到 $v$ 的唯一路径上的点权最大（最小亦同） 从上述问题中可以看出，树链剖分着力于树上的区间问题，常常是点区间问题（当然你也可以用去单点修改），因此，树链剖分需要配合线段树使用 但是普通的区间线段树针对的是连续的序列，对于一棵静态的树，需要把他的结点编排成有序的序列，使得每棵子树的根结点与他的所有儿子（直接儿子 & 隔代儿子）构成连续的序列关系，这就是树链剖分的工作所在了 概念在解剖一棵树前，需要做些准备工作 重儿子：结点的重儿子定 ...

点分治点分治，是树上的一种分治算法，是统计树上路径的一种优化算法 点分治的核心思想是，对于一棵无根树的一个结点 u ，把题目要求的特征路径分为只在 u 的子树上的路径数，和经过 u 的路径数，而求只在 u 的子树上的路径数可以通过递归求解 这里的 u 具有递归性质，那么应该考虑一个递归的入口，使得总的递归次数尽量小，也就是 u 连接的结点层数尽量小，符合要求的 u ，称之为：树的重心 树的重心求树的重心，对于优化点分治的时间复杂度很重要，而且求解数的重心的过程也是一个递归的过程，即这个“树”可能是递归时的子树，也就是说要对每一步走到的子树求重心，才能保证每一步都高效的分治求解 求解树的重心结点是一个树上 DP 的过程，把每个点延伸到的子树大小（这里要加上它自己的 1 个）求出来，取最小的结点即可，但是要注意无根树的性质，如下图： graph TD 1---2;2---3;1---4;4---5;2---6;4---7 此时，结点 4 的子树不仅包含 {5，7}，也包含它上面的一串点 {1，2，3，6}，但此时的 size() 里面是 2，那么 4 的另外一个子树大小应该是 ...