• avatar just_sort 2016-09-07 22:30:46

    Codeforces Round #332 (Div. 2) B. Spongebob and Joke(水题,构造)

    B. Spongebob and Joke time limit per test 2 seconds memory limit per test 256 megabytes

    来自 just_sort
    00
  • avatar just_sort 2016-09-07 21:59:07

    Educational Codeforces Round 4 D. Array GCD

    D. The Union of k-Segments time limit per test 4 seconds memory limit per test 256 megabytes input standa

    来自 just_sort
    00
  • avatar just_sort 2016-09-07 21:05:00

    AIM Tech Round (Div. 2) D. Array GCD(dp,two pointers)

    D. Array GCD time limit per test 3 seconds memory limit per test 256 megabytes

    来自 just_sort
    00
  • avatar just_sort 2016-09-07 18:54:58

    AIM Tech Round (Div. 2) C. Graph and String

    C. Graph and String time limit per test 2 seconds memory limit per test 256 megabytes

    来自 just_sort
    00
  • avatar just_sort 2016-09-06 21:12:30

    BNUOJ 51280 组队活动

    【题目】https://www.bnuoj.com/v3/problem_show.php?pid=51280 【题意】中文题目! 【解题方法】dp[i],i个人的组队方案数。dp【0】=1,dp【i】=sigma(C(i-1,j)*dp[i-1-j])。这个方程怎么来的呢?考虑一下第i个人,在

    来自 just_sort
    00
  • avatar just_sort 2016-09-06 20:10:06

    Codeforces Round #287 (Div. 2) E. Breaking Good(最短路、dp)

    【题意】             N<=10^5个城市,M<=10^5条边,保证无向联通并且没有自环和重边。边分成两种,一种是被毁坏的,用0表示,一种是没被毁坏的用1表示。现在要修1-n的最短路,并且使得这条路的影响值最小,一条道路的影响值定义为:最短路上的毁坏边数+不在最短路上的正常

    来自 just_sort
    00
  • avatar just_sort 2016-09-06 18:42:52

    Hihocoder 1270 建造基地(完全背包)

    描述 在遥远的未来,小Hi成为了地球联邦外空间联合开发工作组的一员,前往一颗新发现的星球开发当地的重金属资源。 为了能够在当地生存下来,小Hi首先要建立一个基地。建立基地的材料可以直接使用当地的石材和富裕的重金属资源。基地建设分为N级,每一级都需要达成K的建设值后才能够完成建设,当前级别的建

    来自 just_sort
    00
  • avatar just_sort 2016-09-06 10:49:38

    Gym 100685G Gadget Hackwrench (LCA)

    【题意】给了一颗V<=100000的有向的,但是忽略方向的一颗树,每次查询(u,v)是否可以到达? 【解题方法】随便一个点当成根,那么边有两种,一种是向上一种向下。我们可以预处理dp[u]表示u向上或者下的边的条数,有了这个就可以快速算出u向上或者向下的边的条数。当询问(u,v)是否可以到达

    来自 just_sort
    00
  • avatar just_sort 2016-09-06 10:06:48

    UESTC 92 Journey(LCA 裸题)

    【题意】给了一颗树,问加一条边可以为两点节省多少距离? 【解题方法】知道dp[u,v]=dp[u]+dp[v]-2*dp[lca(u,v)]就没问题啦。 【AC 代码】 #include <cstdio> #include <cstring> #include <

    来自 just_sort
    00
  • avatar just_sort 2016-09-06 09:33:48

    UVALive 6837 There is No Alternative (MST+暴力LCA)

    【题意】给定一个联通图,求这个图的最小生成树的不可替代边有哪些,并计算这些边的总权值。 【分析】先任意求出一颗生成树,然后标记树边和非树边。然后枚举一下非树边,对于每条边u,v,去找MST上从u到v的路径上是否存在某条边的权值等于这条边的权值。如果有,说明是可替代的。这里直接暴力u,v之间的路径或

    来自 just_sort
    00
  • avatar just_sort 2016-09-05 11:20:09

    Codeforces Round #326 (Div. 2) E. Duff in the Army

    E. Duff in the Army time limit per test 4 seconds memory limit per test 512 megabytes

    来自 just_sort
    00
  • avatar just_sort 2016-09-04 15:27:58

    POJ 2763 Housewife Wind 两种解法

    Housewife Wind Time Limit: 4000MS   Memory Limit: 65536K Total Submissions: 9637   Accepted: 2642

    来自 just_sort
    00
  • avatar just_sort 2016-09-04 12:53:00

    湖南省第十一届大学生计算机程序设计竞赛 部分题解 待续

    【PS】由于这些题应该找不到题解,所以只能把我能做出来的先放在这里,其他的等出题解了补上。 【B - 大还是小?】http://acm.hust.edu.cn/vjudge/contest/130626#problem/B 【题意】中文题目。 【解题方法】水题。 【AC 代码】 #in

    来自 just_sort
    00
  • avatar just_sort 2016-09-04 12:34:49

    2015 ACM/ICPC 长春现场赛 部分题解

    昨天全队做了这个比赛,做一个小小的总结,写一写部分题的题解。 【E - Rebuild】https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&am

    来自 just_sort
    00
  • avatar just_sort 2016-09-02 18:51:25

    POJ 1265 Area

    Area Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 6324   Accepted: 2774

    来自 just_sort
    00
  • avatar just_sort 2016-09-02 16:46:07

    POJ 3695 Rectangles(矩形切割)

    Rectangles Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 3927   Accepted: 1150

    来自 just_sort
    00
  • avatar just_sort 2016-09-02 15:38:46

    POJ 3277 City Horizon 矩形切割

    City Horizon Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 18556   Accepted: 5115

    来自 just_sort
    00
  • avatar just_sort 2016-09-02 14:45:11

    POJ 1151 矩形切割

    【题目】http://poj.org/problem?id=1151 【题意】求矩形面积并。 【解题方法】可以线段树扫描线,当然这里我是来试一试矩形切割的。 【AC 代码】在POJ和HDU均测试通过。 #include <cstdio> #include <cstri

    来自 just_sort
    00
  • avatar just_sort 2016-09-02 14:42:06

    线段切割&&矩形切割

    【参考BOLG】http://blog.csdn.net/acdreamers/article/details/8778225 【解释】直接沿用acdreamers大神的解释啦。 【题目】http://poj.org/problem?id=2528 【解题方法】线段树写过了,不说,这里学习另外

    来自 just_sort
    00
  • avatar just_sort 2016-09-01 20:44:42

    Codeforces Beta Round #1 C. Ancient Berland Circus

    C. Ancient Berland Circus time limit per test 2 seconds memory limit per test 64 megabytes input standard

    来自 just_sort
    00
  • avatar just_sort 2016-09-01 12:24:18

    HDU 4082 Hou Yi's secret

    Hou Yi's secret Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4384    Accepted Submission(

    来自 just_sort
    00
  • avatar just_sort 2016-08-30 20:44:10

    Codeforces Round #369 (Div. 2) 题解

    【A. Bus to Udayland】http://www.codeforces.com/contest/711/problem/A 【题意】公交车上有些位置能做,有些不能坐,问是否有两个相邻的位置。 【解题方法】找到并排的2个0就行了。 【AC代码】 #include <bits

    来自 just_sort
    00
  • avatar just_sort 2016-08-29 08:57:17

    HDU 3487 Play with Chain(Splay 经典操作)

    Play with Chain Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5770    Accepted Submission(

    来自 just_sort
    00
  • avatar just_sort 2016-08-28 19:39:51

    HDU 3436 Queue-jumpers(Splay)

    Queue-jumpers Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3545    Accepted Submission(s

    来自 just_sort
    00
  • avatar just_sort 2016-08-28 16:04:33

    计算几何

    这两天在学习计算几何,随便说说自己的学习过程吧。   基本的叉积、点积和凸包等东西就不多说什么了,网上一搜一大堆,切一些题目基本熟悉了就差不多了。   一些基本的题目可以自己搜索,比如这个blog:http://blog.sina.com.cn/s/blog_49c5866c0100f3om

    来自 just_sort
    00
  • avatar just_sort 2016-08-28 15:27:51

    POJ 3417 Network(dp+tarjian LCA)

    Network Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 4929   Accepted: 1413

    来自 just_sort
    00
  • avatar just_sort 2016-08-28 14:27:16

    UVA 11354 Bond(MST+倍增)

    【题意】给定N<=5*10^4,M<=1*10^5的图,Q<=5*10^4个询问,(u,v)选择一条路径使得最大的边权最小。 【解题方法】找最小,显然先MST。然后用倍增搞一搞就行了,熟练剖分也可以,算是树剖入门题了,我这里用倍增来搞一下。 【AC 代码】 #include

    来自 just_sort
    00
  • avatar just_sort 2016-08-28 10:38:05

    Regionals 2015 :: Asia - Taipei 部分题解

    【第3次区域赛训练赛】最终做了6题,完全是因为这场比赛水的缘故。。。赛后又补了个题,现在来写一下这7题的题解,总结一下。 【A - Parentheses】https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&

    来自 just_sort
    00
  • avatar just_sort 2016-08-27 10:31:09

    UVALive 4960 Sensor network(MST+LCA)

    【题目】http://acm.hust.edu.cn/vjudge/problem/16412 【题意】给了N<=350个点的一个图,求所有的MST的最大边减去最小边的最大值。 【解题方法】这道题曾经有一个小数据版本,uva1395,那道题可以通过枚举最小边,算最小生成树,暴力算出最大减去

    来自 just_sort
    00
  • avatar just_sort 2016-08-26 22:01:28

    2016暑假集训小结

                                                               小结    暑假集训之前,有很多事情在忙,什么考试,**之类。集训开始的时候还回了一趟家,这趟回家也发生了对我影响最大的事,之后想了很久,觉得也还是有必要继续走下去,因为我还是很爱

    来自 just_sort
    00
  • avatar just_sort 2016-09-02 20:55:28

    HDU 2874 Connections between cities

    Connections between cities Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 9785    Accepted

    来自 just_sort
    00
  • avatar just_sort 2016-08-26 21:31:33

    SPOJ Query on a tree II (倍增LCA)

    Query on a tree II Time Limit: 433MS   Memory Limit: 1572864KB   64bit IO Format: %lld & %llu Su

    来自 just_sort
    00
  • avatar just_sort 2016-08-26 17:06:44

    LCA 总结

    【转载地址】点击打开链接 LCA: 什么是LCA? Lowest Common Ancestor, 指的是树上两点的最近公共祖先。 有了它, 我们可以高效地求解树上两点间的距离、最大权值边等信息。 的时间复杂度: 暴力 O(n+m+qn) 倍增法O(n+m+nlogn+qlogn) 欧拉序列与

    来自 just_sort
    00
  • avatar just_sort 2016-08-26 16:15:51

    HDU 1890 Robotic Sort(Splay 区间翻转)

    Robotic Sort Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3741    Accepted Submission(s):

    来自 just_sort
    00
  • avatar just_sort 2016-08-25 22:45:41

    POJ 3468 Splay 做法

    A Simple Problem with Integers Time Limit: 5000MS   Memory Limit: 131072K Total Submissions: 96635  

    来自 just_sort
    00
  • avatar just_sort 2016-08-25 19:42:12

    HNOI 2002 (Splay入门题,无更新操作)

    1588: [HNOI2002]营业额统计 Time Limit: 5 Sec   Memory Limit: 162 MB Submit: 13618   Solved: 5062 [ Submit][ Status][ Discuss] Description

    来自 just_sort
    00
  • avatar just_sort 2016-08-25 19:29:58

    伸展树(Splay tree)学习小结

    转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents           by---cxlove 总结一下最近学习的Splay tree。万事开头难啊,像这种神一样的数据结构,刚学是很痛苦的,建议之前要把平衡树,SBT之类的数据结

    来自 just_sort
    00
  • avatar just_sort 2016-08-24 21:10:27

    HDU 3065 (AC自动机水题)

    病毒侵袭持续中 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11454    Accepted Submission(s): 401

    来自 just_sort
    00
  • avatar just_sort 2016-08-24 20:10:56

    POJ 1056 IMMEDIATE DECODABILITY(字典树 水题)

    IMMEDIATE DECODABILITY Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 13014   Accepted

    来自 just_sort
    00
  • avatar just_sort 2016-08-24 18:41:48

    HDU 4099 Revenge of Fibonacci

    Revenge of Fibonacci Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 204800/204800 K (Java/Others) Total Submission(s): 2895    Accepted Sub

    来自 just_sort
    00
  • avatar just_sort 2016-08-24 15:38:59

    HDU 3695 Computer Virus on Planet Pandora

    【题意】 给n个病毒字符串和一个程序字符串,若程序字符串包含某个病毒字符串或者它的反串,则包含这个病毒,问所给程序字符串包含多少个病毒? 【解题方法】 用病毒串和反串建立AC自动机,然后求包含多少病毒,但同一个病毒可能会被计算2次(如果病毒和它的反串都出现在程序中),对于每个病毒,它在自动机中

    来自 just_sort
    00
  • avatar just_sort 2016-08-24 11:45:39

    SWUST 2489 上决欺负HZF

    【题意】 由于HZF长得太帅,被各种人调戏是绝对的啦!今天上决十分的无聊,于是就去欺负HZF不会数据结构,嘻嘻。来点简单的嘛,免得峰哥报复,那就……HZF嘿嘿一笑:看我无敌版函数式平衡逆天启发式线段树! Input  多组。 第一排两

    来自 just_sort
    00
  • avatar just_sort 2016-08-24 11:16:20

    SWUST OJ 2285

    【解题方法】线段树区间合并典型题,维护区间左端点开始最大值,右端点结束最大值,以及整体最大值,还需要维护一下区间左端点和右端点的值,这样合并就方便了。 【我的这份代码还是比较快的,在本oj跑到了第一名】 【AC 代码】 #include <cstdio> #include <

    来自 just_sort
    00
  • avatar just_sort 2016-08-24 09:45:21

    2015-2016 ACM-ICPC Northeastern European Regional Contest (NEERC 15)

    【题目传送门】http://7xjob4.com1.z0.glb.clouddn.com/30a7f1a788b43f34819586f3593d670a 【Problem A. Adjustment Office 】 【题意】 给了一个N*N的矩阵,矩阵中每个坐标为x,y的格子的值为x+y。有Q个

    来自 just_sort
    00
  • avatar just_sort 2016-08-22 15:54:23

    2015 北京区域赛现场赛 部分题解

    【前言】这场比赛是昨天的训练赛,弱队最终做了4题,好像去年是铜牌滚粗。,太弱啦。现在写一下部分题解。 【A Xiongnu's Land 】 http://7xjob4.com1.z0.glb.clouddn.com/3e76f5f069daf5f6fa79969c155e4e14 【题意】W

    来自 just_sort
    00
  • avatar just_sort 2016-08-22 10:25:19

    Bzoj 1901 Dynamic Rankings

    【题意】 Description 给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还

    来自 just_sort
    00
  • avatar just_sort 2016-08-21 10:01:20

    Codeforences #368 部分题解

    【A】 A. Brain's Photos time limit per test 2 seconds memory limit per test 256 megabytes

    来自 just_sort
    00
  • avatar just_sort 2016-08-20 17:03:22

    主席树的读书笔记

    ***********************************************声明************************************************  原创作品,出自 “晓风残月xj” 博客,欢迎转载,转载时请务必注明出处(http://blog.c

    来自 just_sort
    00
  • avatar just_sort 2016-08-20 16:46:44

    UVA 11019 Matrix Matcher

    【题意】 给出一个n*m的字母矩阵T和一个x*y的字母矩阵S。求S在T中出现了多少次? 【解题方法】 具体见白书218页,前面写的AC 自动机,都是没有加last优化的,但是我写这个题的时候,发现不加last巨难写,好吧我太菜了。所以我选择了这种last优化(好像并没有优化?)的版本,作为

    来自 just_sort
    00
  • avatar just_sort 2016-08-20 14:57:11

    UVA 11468 Substring AC 自动机套DP

    【题意】 【解题方法】 详细可见白书P 218 构造完改造后的AC自动机后,每随机生成一个字母,相当于在AC自动机中随机走一步。所以有单词的节点标记为"禁止"。则本题就是求从节点0开始走L步,不进入任何禁止节点的概率。         令d[i][j]表示当前在i节点

    来自 just_sort
    00
  • avatar just_sort 2016-08-20 13:26:58

    UVA 4670 Dominating Patterns

    【题意】 【分析】 题目给出一个文本串多个模板串,要求出现最多的模板串。这恰好可以用AC自动机解决,只不过需要将print修改为cnt[val]++ 统计标号为val的模板串出现的次数。  原理:在文本串不同位置出现的模板都可以通过自动机匹配找到。  注意:为什么模板要开始从1标号?

    来自 just_sort
    00
  • avatar just_sort 2016-08-20 10:05:19

    HDU 2222 Keywords Search (AC 自动机)

    【题意】多模式串匹配母串,求模式串出现的次数。 【解题方法】AC 自动机裸题。 【AC自动机学习】 可以参考这篇blog,写得很好。点击打开链接 【AC 代码】 // //Created By just_sort 2016/8/20 //All Rights Reserved // #in

    来自 just_sort
    00
  • avatar just_sort 2016-08-19 20:39:14

    BZOJ 4653: [Noi2016]区间

    Description 在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间,使得这 m个区间共同包含至少一个位置。换句话说,就是使得存在一个 x,使得对于每一个被选中的区间 [li,ri],都有 li≤x≤ri。 对

    来自 just_sort
    00
  • avatar just_sort 2016-08-19 18:53:09

    BZOJ 4668 冷战

    Description 1946 年 3 月 5 日,英国前首相温斯顿·丘吉尔在美国富尔顿发表“铁 幕演说”,正式拉开了冷战序幕。 美国和苏联同为世界上的“超级大国”,为了争夺世界霸权,两国及其 盟国展开了数十年的斗争。在这段时期,虽然分歧和冲

    来自 just_sort
    00
  • avatar just_sort 2016-08-19 18:09:39

    多校联合训练10&&HDU 5861 Road

    【题意】             给你n个村庄,每两个相邻的村庄有一条路,m个操作,每次都要从一个村庄走到另外一个村庄,每一条路每次都有一个维修的费用,每条路一开始是关闭的,你可以打开一次,关闭一次。问你最少的费用是多少。 【解题方法】            copy一遍题解:为了使得花费最小

    来自 just_sort
    00
  • avatar just_sort 2016-08-19 15:50:32

    2016多校联合训练10&&HDU5857 Median

    Problem Description There is a sorted sequence A of length n. Give you m queries, each one contains four integers, l1, r1, l2, r2. You should use

    来自 just_sort
    00
  • avatar just_sort 2016-08-19 11:27:22

    POJ 3074 DLX精确覆盖求解数独问题

    【解题方法】             DLX解决9*9的数独问题,转化为729*324的精确覆盖问题             行:                   一共9 * 9 * 9 == 729行。一共9 * 9小格,每一格有9种可能性(1 - 9),每一种可能都对应着一行。   

    来自 just_sort
    00
  • avatar just_sort 2016-08-18 21:20:18

    多校训练10&&HDU5862 Counting Intersections

    【题意】真水的题。。不知道我们队干了什么,卡在A题这个水题几个小时,太悲哀了。 【解题方法】这不好说,去偷一份我同学的解题方法吧,思路大概都是这样,扫描线的基础题了,BIT维护信息,扫描线扫过去就完了。 因为题目已经说明所有的线段都是平行于坐标轴的 那么,线段无外乎两种:①平行于x轴;②平行于

    来自 just_sort
    00
  • avatar just_sort 2016-08-18 10:16:31

    FZU 1686 神龙的难题(DLX 重复覆盖)

    【题意】 Description 这是个剑与魔法的世界.英雄和魔物同在,动荡和安定并存.但总的来说,库尔特王国是个安宁的国家,人民安居乐业,魔物也比较少.但是.总有一些魔物不时会进入城市附近,干扰人民的生活.就要有一些人出来守护居民们不被魔物侵害.魔法使艾米莉就是

    来自 just_sort
    00
  • avatar just_sort 2016-08-18 09:25:20

    HDU 2295 Radar(二分加DLX)

    【题意】        有n个城市,m个雷达,k个操作员,要求确定最小的半径,使得所有城市都能被覆盖。首先,解空间应该是一组数,也就是任意一个雷达和城市的距离的集合,答案必然是其中的一个,所以排好序,二分查找。每次判断某个半径能不能做到覆盖就可以了。至于覆盖问题,马上想到Dancingl  ink

    来自 just_sort
    00
  • avatar just_sort 2016-08-17 20:43:57

    POJ 1155 TELE(树形DP 水)

    【题意】 电视台发送信号给很多用户,每个用户有愿意出的钱,电视台经过的路线都有一定费用,求电视台不损失的情况下最多给多少用户发送信号。【解题方法】 裸的树形DP了。 dp[i][j]代表i节点为根节点的子树j个用户的时候最大剩余费用。则dp[i][j] = max(dp[i][j],

    来自 just_sort
    00
  • avatar just_sort 2016-08-17 19:42:35

    POJ 1741 树分治

    【题意】求树上距离小于等于K的点对有多少个? 【解题方法】不愧是男人8题,从TLE写带WA,最后过了,经历了10+次。 一个重要的问题是,为了防止退化,所以每次都要找到树的重心然后分治下去,所谓重心,就是删掉此结点后,剩下的结点最多的树结点个数最小。 每次分治,我们首先算出重心,为了计算重心,

    来自 just_sort
    00
  • avatar just_sort 2016-08-17 09:59:29

    URAL - 1018 (树形dp 水题)

    【题意】 Description Let's imagine how apple tree looks in binary computer world. You're right, it looks just like a binary tree, i.

    来自 just_sort
    00
  • avatar just_sort 2016-08-17 09:09:21

    bzoj 2427 && codevs 1866 tarjian缩点+树形dp

    【题意】 2427: [HAOI2010]软件安装 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 929  Solved: 371 [ Submit][ Status][ Discuss] Description

    来自 just_sort
    00
  • avatar just_sort 2016-08-16 10:38:45

    有向图强连通分量的Tarjian算法

    【转载地址】点击打开链接 [有向图强连通分量] 在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected

    来自 just_sort
    00
  • avatar just_sort 2016-08-16 09:47:00

    NKOI 1469 通向自由的钥匙(树形dp)

    【题意】 通向自由的钥匙 Time Limit:10000MS  Memory Limit:65536K Total Submit:96 Accepted:39 Case Time Limit:1000MS Description 通向自由的钥匙被放n个房间里,这n个房间由n-1条走廊连

    来自 just_sort
    00
  • avatar just_sort 2016-08-16 09:23:22

    Codevs 1378 选课(树形dp)

    【题意】 学校实行学分制。每门的必修课都有固定的学分,同时还必须获得相应的选修课程学分。学校开设了N(N<300)门的选修课程,每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。   在选修课程中,有些课程可以直接选修,有些课程需要一定的基础知识,

    来自 just_sort
    00
  • avatar just_sort 2016-08-15 20:39:52

    HDU1561 树形dp,泛化背包

    【题意】 The more, The Better Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7476    Accepte

    来自 just_sort
    00
  • avatar just_sort 2016-08-15 17:06:02

    POJ 1655 (树dp or 树重心)

    【题意】不解释了。 【解题方法】其实这题就是一个树的重心,我用两种方法写的,水题。 【AC 代码 1】 //树的重心 #include <cstdio> #include <cstring> #include <iostream> #include <

    来自 just_sort
    00
  • avatar just_sort 2016-08-15 15:11:09

    HDU 5839 Special Tetrahedron(计算几何)

    【参考BLOG】点击打开链接 【题意】<big>在三维空间中给出N个点,找有多少个满足条件的四面体.</big> 四面体至少有四条边相等 <big>若恰好四条边相等,那么剩下的两边不相邻.</big> 【解题方法】 <big&g

    来自 just_sort
    00
  • avatar just_sort 2016-08-14 21:43:08

    HDU 5833

    【题意】给出n个整数,从中选出1个或者多个,使得选出的整数乘积是完全平方数。一共有多少种选法? 【解题方法】高斯消元,不得不吐槽这场网络赛,这道题是白书的原题,可惜没有发现,最后队友们还是做出来的。参考白书p160 【AC 代码】 #include <cstdio> #inclu

    来自 just_sort
    00
  • avatar just_sort 2016-08-14 09:43:54

    HUST 1017 Exact cover(舞蹈链 入门题)(模板记录)

    【题意】不解释了,就是裸的DLX模板题,先记录一下DLX的板子,看了半天总算理解了一些。 【DLX学习】参考这篇博客:点击打开链接 写得非常清楚,顺便赞一句,DLX真的是太神奇了。orz。 【AC 代码 DLX 模板】 /********************/ //Created by

    来自 just_sort
    00
  • avatar just_sort 2016-08-13 20:11:10

    SPOJ BALNUM (数位DP)

    【题意】求出现的数字,所有偶数出现奇数次,所有奇数出现偶数次的个数。 【解题方法】用一个三进制表示每个数字出现的状态,1表示出现过奇数次,0表示从未出现过,1表示出现过偶数次。dp[l][s]长度为i,s代表当前状态。接下来就是数位DP经典套路了。 【AC 代码】 #include <

    来自 just_sort
    00
  • avatar just_sort 2016-08-13 14:58:35

    HDU 5493 Queue (线段树)2015合肥赛区网络赛

    【参考BLOG】 点击打开链接 【题意】 给定N<105个人的序列,N个(height,k)二元组描述这个序列 height:=这个人的身高,k:=这个人的左边或者右边有k个人比他高 构造一个字典序最小的序列满足这些条件 【解题方法】 从高到低放或者从低到高放都可以,由于

    来自 just_sort
    00
  • avatar just_sort 2016-08-13 14:13:10

    HDU 4614 二分加线段树

    【题意】初始有n个空花瓶,然后有q个操作,1 x y,从x开始插花,插够k个即可。2 x y,把x,y区间有有花的花瓶全部清空。 【解题方法】 线段树维护剩余空花瓶的个数 第一种操作二分≥1的最左边的位置,二分≥k的最左边位置第二种直接更新就好啦复杂度是O(n+mlog2n) 【AC代

    来自 just_sort
    00
  • avatar just_sort 2016-08-13 09:37:40

    HDU 5634 Rikka with Phi

    【题意】有一个序列,有3种操作,一种是把区间里面所有的数变成他的欧拉函数值,第二种是把整个区间的数变成某一个值,第三种是查询区间的和。 【解题方法】 这道题其实用线段树来维护就完全可以了,只有当区间的setv存在时,我们更新下去。具体细节见代码。 【AC 代码】 #include &l

    来自 just_sort
    00
  • avatar just_sort 2016-08-12 21:32:02

    HDU 3652 裸数位DP

    【题意】【1,n】里面还有数字13并且是13的倍数的数字的个数。 【解题方法】数位DP裸题。 dp[l][mod][iso][has] :l为数字长度,(mod为当前数字对13的取余值,iso为是否存在, has为最后一位是否为数字1。 int dfs(int l,int mod,bool

    来自 just_sort
    00
  • avatar just_sort 2016-08-11 21:31:03

    多校联合训练8&&HDU 5828

    【题意】给了一个序列,3个操作,1是给区间[l,r]加上一个数,2是给区间[l,r]里每个数开平方,3是查询[l,r]的和。 【解题方法】 其实这道题线段树就完全可以维护了,平衡树不会,线段树节点里面保存了两个标记,一个是add(区间加),一个是区间里面元素是否相同,接下来很重要的主要是pu

    来自 just_sort
    00
  • avatar just_sort 2016-08-11 19:21:56

    多校第8场&&HDU 5821

    【题意】题目给了两个代表颜色的序列,然后给了q个操作,每个操作有个[l,r]区间,表示你可以把[l,r]区间里面所有的数任意排列,问最后能否利用这些操作使得a变到b数组。 【解题方法】 【AC 代码】 #include <bits/stdc++.h> using names

    来自 just_sort
    00
  • avatar just_sort 2016-08-11 10:40:55

    HDU 5623 KK's Number(博弈dp)

    【题意】两个人轮番从n个数中每次选择任意个数, 每次获得的分数是所选数种最小的,两人采取的策略都是使得自己的分数减去对方的分数尽量大, 求最终第一个人的得分。 【解题方法】由于每个人都是从大往小拿,先将序列排序。由于得分是最小值,我们不妨反向思考,f[i]:=剩余i个数,先手得分−后手得分的最大值

    来自 just_sort
    00
  • avatar just_sort 2016-08-11 10:09:53

    HDU5497 (梳状数组套two pointers)

    【题意】 N<=105的序列,求删去一个M<N的连续子序列后,剩余序列的最小逆序对数 【解题方法】 求逆序对当然要BIT辣,然后维护删去固定大小的序列可以用two pointers 开两个BIT,b[]维护连续M子序列前面的,c[]维护后面的 删去ai+m,影响就是少了后面所有比它

    来自 just_sort
    00
  • avatar just_sort 2016-08-10 20:47:46

    Codeforences #287 div2 D. The Maths Lecture

    【题意】N<=1000位数字,要我们构造一个N位数,使得这个数存在一个后缀,并且这个后缀可以整除K。 【解题方法】裸数位DP了。dp[i][mod][ok]表示从第n位到第i位,模数为mod,是否含有后缀大于0并且mod=0的数字数。添加一个数的时候是(d*10^i+mod)%k,这里需要注

    来自 just_sort
    00
  • avatar just_sort 2016-08-10 19:49:04

    Codeforces Round #223 (Div. 2) E Sereja and Brackets

    【题意】给一个括号字符串,然后m个查询,查询【L,R】区间里最大的括号匹配数。 【解题方法】虽然是E题,但我不得不说这是个很水的题。我们只需要考虑一下每个区间没匹配左括号的个数,没匹配的右括号的个数,以及匹配的括号数即可。接下来就是区间合并的典型套路了。 【AC 代码】 #include &

    来自 just_sort
    00
  • avatar just_sort 2016-08-10 15:50:32

    HDU 2089 不要62 && HDU 3555 Bomb (数位DP)

    【题意】【L,R】中不含4或62的数字的个数。 【解题方法】数位DP,板子题。 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using

    来自 just_sort
    00
  • avatar just_sort 2016-08-10 15:23:17

    HDU 4352 XHXJ's LIS(数位DP)

    【题意】 问区间[L, R]里面满足 LIS == k的数字个数。 【解题方法】 LIS运用动态规划可以在nlogn的时间复杂度解决,此略。 因为最多只有0-9十个数字,因此可以预处理。 .sta为LIS 的状态,siz[sta]中保存LIS 的长度(即二进制中1的个数),nex[sta][i

    来自 just_sort
    00
  • avatar just_sort 2016-08-10 11:28:16

    数位DP学习 数位DP板子理解 CF55D解题报告

    【题意】先理解一下数位DP的模板,下面解释的非常清楚了。 // pos = 当前处理的位置(一般从高位到低位) // pre = 上一个位的数字(更高的那一位) // status = 要达到的状态,如果为1则可以认为找到了答案,到时候用来返回, //

    来自 just_sort
    00
  • avatar just_sort 2016-08-10 10:24:09

    Codeforces 629C Famil Door and Brackets (DP)

    【题意】 定义一个合法串: (1),'('的总数 == ')'的总数。 (2), 串中所有前缀 满足 '('的个数 >= ')'的个数。 题意:给定一个合法串的长度n和一个长度为m的中间串s,要求你找到一个p串和q串,使得p + s + q是一个合法串且长度为n。问有多少种不同的方案数

    来自 just_sort
    00
  • avatar just_sort 2016-08-10 09:40:15

    Manthan, Codefest 16 C. Spy Syndrome 2(Trie树套DP)

    【题意】给你m个单词的词典和一句话,这句话中的每个单词都来自字典,字典中的每一个单词重复可用,把这句话所有大写字母变成小写字母,然后反转单词去掉空格,要求你恢复这句话。 【解题方法】Trie+dp.dp[i]=:以i结尾的字符串是否可以解密,为记录答案直接存长度就可以了。复杂度O(n*1000)

    来自 just_sort
    00
  • avatar just_sort 2016-08-10 08:46:58

    2016多校联合训练7&&HDU5816

    【题意】一个怪初始有P的血量,并且这个人初始有n次抽牌机会,并且这个抽牌是可以换两次抽牌机会的,还有M张攻击牌,问用这些攻击牌和N次抽牌机会杀死怪物的概率。 【解题方法】状压DP+动态内存分配,这道题如果静态开会无线MLE。 【AC 代码】 #include <cstdio> #

    来自 just_sort
    00
  • avatar just_sort 2016-08-09 19:58:16

    多校联合训练7&&HDU 5810

    【解题方法】 【AC 代码】 #include <bits/stdc++.h> using namespace std; #define ll long long int main(){ ll n,m; while(scanf("%I64d%I64d

    来自 just_sort
    00
  • avatar just_sort 2016-08-09 19:35:24

    多校联合训练7&&HDU5813

    【题意】给定一个DAG上每个点和多少个点间接连接,然后要让我们自己搞一个图,满足这个条件。 【解题方法】贪心水题。将顶点按能到达的点数从小到大排序,排好序之后每个点只能往前面的点连边. 因而如果存在一个排在第i位的点,要求到达的点数大于i-1,则不可行;否则就可以按照上述方法构造出图. 复杂度O(

    来自 just_sort
    00
  • avatar just_sort 2016-08-09 19:27:49

    2016多校联合训练7&&HDU5818

    【题意】给出两个栈A B(初始时为空),有三种操作:push、pop、merge.其中merge是按照A B中元素进栈的相对顺序来重排的. 【解题方法】模拟水题,优先队列模拟即可。 【AC 代码】 #include <bits/stdc++.h> using namespace

    来自 just_sort
    00
  • avatar just_sort 2016-08-09 10:52:27

    HDU 4604 Deque(LCS DP)

    【题意】给定N≤105的一个序列,现在有一个deque唯一的要求是deque里的数必须是不降的,求deque里的最多元素个数是多少 【解题方法】 【AC 代码】 #include <bits/stdc++.h> using namespace std; const int i

    来自 just_sort
    00
  • avatar just_sort 2016-08-09 10:13:28

    HDU 4616 Game(树形DP)

    【题意】一颗有n个节点的树,每个节点有val值和c(有无陷阱)值,给出最大可踩陷阱数m。在树中任取一点作为起点,经过某点就取得该点的val值,踩到第m个陷阱后马上停止,而且不能走已走过的点,求所能获得的最大val总值。 【解题方法】树形dp,经典题,虽然我不会。 dp[u][i][0/1]:=以u

    来自 just_sort
    00
  • avatar just_sort 2016-08-09 08:59:20

    Codeforces Round #343 (Div. 2) D. Babaei and Birthday Cake(dp + BIT)

    【题意】给定N≤105个蛋糕,编号为1∼N,每个都有体积Vi ,任意一个蛋糕都可以放在桌子上,对于蛋糕对(i,j),i可以放在j上,当且仅当i>j且Vi≥Vj ,求能摆放的蛋糕的最大体积? 【解题方法】                    dp[i]表示第i个蛋糕在最上面的最大体积和  

    来自 just_sort
    00
  • avatar just_sort 2016-08-08 16:27:50

    SWUST 2268 SB_cyh and his BST two (Treap名次树)

    Input 多组数据(整个文件以输入 -1 结束) 对于每组数据,有若干行(最多100000行),表示的意义如下: 【A】 insert x 【B】 delete x 【C】 predecessor x 【D】 successor x 【E】 Kth x 【F】 rank x

    来自 just_sort
    00
  • avatar just_sort 2016-08-08 15:58:11

    BZOJ 3809 Gty的二逼妹子序列

    【题意】莫队加树状数组的做法很显然,解法借鉴HZWER大牛,这道题可以这样做,考虑对权值分块,这样使得每次查询复杂度变为√n,而修改的复杂度变为O1 总复杂度降为m√n,其实我自己一直没怎么想懂这个问题,感觉这个复杂度确实没优化多少。 【AC 代码】 #include <mat

    来自 just_sort
    00
  • avatar just_sort 2016-08-08 11:34:36

    SPOJ 3273 Treap

    【题意】给定n个操作,I,D,K,C,分别代表插入,删除,找第K大元素,找小于x的元素个数。 【解题方法】基本的Treap操作了,考虑如果一个数没在Treap里面,那么先插入Treap然后查排名,然后删除这个数。 【AC 代码】 #include <iostream> #incl

    来自 just_sort
    00
  • avatar just_sort 2016-08-08 11:14:32

    POJ 1442 (Treap 板子记录)

    【题意】给一个序列,然后给出m个查询,每次查询输入一个数x,对于第i次查询,输出前x个数中第i大的关键字的值。 【解题方法】就是裸Treap板子了,先介绍一下Treap。 Treap是一棵二叉搜索树,只是每个节点多了一个优先级fix,对于每个节点,该节点的优先级小于等于其所有孩子的优先级。 当

    来自 just_sort
    00
  • avatar just_sort 2016-08-07 19:52:57

    Codeforces483D 线段树上的位操作

    【题目】点击打开链接 【题意】 给出若干个条件,让一个序列满足从第Li个数到第Ri个数的&和为Qi;问是否存在这个序列,若存在,输出YES,并输出这个序列,否则输出NO. 思路:线段树区间覆盖,对于每一个条件,对这个区间上的每一个数都|上询问的数。操作完之后,在检查每个询问是否成立。

    来自 just_sort
    00