留念处_灯火阑珊-CSDN博客

原创 Codeforces Round #397 Problem F. Souvenirs 解题报告

题目链接：Here！题目大意：给你一个数组，每次给定一个区间，求解题思路：由于只有询问，直接离线，按照左端点排序。然后建立一棵线段树，每一个节点维护一个set和当前的数的最小差值。从右到左依次更新（为什么是从右到左？因为这样的话每一次遇到的一定是没有处理的query中左端点最靠右的那个，从而可以避免不在query区间中的数对query产生影响），由于set内部有序，所以在set内部二分，比

2017-02-18 11:44:41 529

原创 Codeforces Round #397 Problem E. Tree Folding 解题报告

题目链接：Here! 题目大意：给你一种树的边的合成方式，问你经过数次合成之后，能否变成线性结构，如果可以，求出这个结构最短的长度。解题思路：按照拓扑排序的顺序，从度数为1的点开始“删去”，对于每一个节点用set保存从其他节点到这个节点的长度，如果有相同长度的就会自动“合并”。所以，只有两种情况是满足条件的： 1.有一个节点的set的大小是2，其余的都是1 2.全部节点的set的大小都是

2017-02-16 17:15:46 373

原创 Codeforces Round #397 Problem D. Artsem and Saunders 解题报告

题目链接：Here！题目大意：给你一个映射f，问是否存在两个映射g和h，使得，若存在，输出方案，若不存在，输出-1 解题思路：，显然，当时满足原等式，假如存在，若要满足原等式，则必有。根据以上推导判断构造映射即可。 #include #include #include #include #include #include #include #include #includ

2017-02-16 14:53:07 437

原创 Codeforces Round #383 (Div. 1) Problem A. Arpa's loud Owf and Mehrdad's evil plan 解题报告

题目链接：Here！题目大意：给你n个点之间的连接情况，问对于所有点，求一个最小的t，使得对于每一个点都有与之对应的点两点之间距离相等且为t的正整数倍。解题思路：由于n的范围比较小，我们可以直接用floyd求出每两个点之间的最短路径，然后暴力判断每个点是否合法即可。注意每次更新答案的时候都是取lcm，在这个过程中可能会爆int，所以我用的long long。 #include #inc

2016-12-08 17:48:33 302

原创 Codeforces Round #383 (Div. 1) Problem B.Arpa's weak amphitheater and Mehrdad's valuable Hoses 解题报告

题目链接：Here! 题目大意：一个人家里有一个剧场，但是这个剧场只能承受一定的重量。这个人想要邀请一些人到他家里玩，这些人中有一部分人相互是朋友，把相互是朋友的人看做一个集合，那么对于这个集合，要么邀请所有人，要么最多邀请一个人。每一个人有两个属性，颜值和重量。问在不超过剧场承受的重量的前提下，能邀请到的人的最大颜值和。解题思路：很明显的01背包。不过对于题目对于一个集合内只能邀请最多一个

2016-12-08 09:20:30 278

原创 HDU 5880 Family View 解题报告

题目链接：Here！题目大意：给你几个字符串再给你一段字符，让你把字符中所有出现的字符串都变成*，最后输出处理后的字符串题目思路：AC自动机直接处理出每个字符串的位置，直接替换即可。 #include #include #include #include #include #include #include #include #include #include #in

2016-09-17 17:53:29 299

原创 HDU 5828 Rikka with Sequence 解题报告

题目链接：Here！题目大意：给定一些数，对于这些数一共有三种操作：区间内所有的数加上一个数，区间内所有的数开根号向下取整，区间内所有的数求和。解题思路：对于第一个和第三个操作我们利用线段树就可以轻松完成，下面我们来讨论第二个操作。由于题目中的开根号操作是向下取整的，所以数的大小在一定的区间内开根号后的结果是一样的，并且对于一个数，开很少次的根号就可以让它等于1。结合前面的结论，很容易想到

2016-08-22 14:41:43 309

原创 HDU 5861 Road 解题报告

题目链接：Here! 题目大意：在一条路上有n座村庄，每天给定两个村庄之间的路必须是畅通的，开启道路的费用就是路的权值，每条道路只能开，关各一次，问从开始到每一天的费用最小是多少。题目思路：利用线段树处理出每一条路开启的时间段，将所有的开启日期和关闭日期混合在一起排序，然后从1-m枚举日期，如果当前日期是某一条线段的开启日期，则答案加上该线段的权值，若当前日期是某一条线段的关闭日期，则答案减

2016-08-22 10:07:05 363

原创 HDU 5862 Counting Intersections 解题报告

题目链接：Here！题目大意：给定一些水平或竖直的线段，求它们的交点数。解题思路：首先想到的方法是暴力枚举线段然后判断是否相交，但是时间复杂度显然过大，所以我们要采取其他的办法。我们把所有水平的线段的两个端点的两个权值分别置为-1和1，然后再按x坐标排序，那么我们只需要面对一个方向上的线段了，这个时候我们就可以将所有竖直的线段按横坐标排序，离散化纵坐标然后按横坐标从小到大依次枚举水平线段的

2016-08-21 20:53:08 348

原创 Codeforces Round #365 (Div. 2) Problem D.Mishka and Interesting sum 解题报告

题目链接：Here！题目大意：给你n个数，然后m次查询，每一次查询输出所有在给定区间内出现偶数次数的数的异或值，如果只有一个出现偶数次数的数，则直接输出该数，如果没有出现偶数次数的数，则输出0。解题思路：看到区间查询，第一反应是线段树，但是用线段树来统计区间内出现次数为偶数次数的数并且保存这些数的异或值比较麻烦。本题的1 ≤ n ≤ 1 000 000，莫队的时间复杂度为O(n^1.5)显

2016-08-05 16:30:15 474

原创线段树的一点总结

线段树，顾名思义，是根据线段建成的树。每一个节点都可以是线段。对于单点查询，区间查询，单点更新，区间更新都是O(logn)级别的，所以对于大多数区间操作比较大的题，都可以用线段树解决。 0.性质对于每一个非叶子节点下标为i的节点，它的左儿子的下标必定为I 1.定义 const int MAXN = 100005;//线段最大长度 struct Node{ int l;//区间的左

2016-07-28 19:37:31 378

一步步成长