• pkusc 2014 #1

    pkusc 2014 #1

    A:unix纪元模拟[crayon-58d5b3929b1d3971469121/]B:连环锁真心不会格雷码QAQ[crayon-58d5b3929b1dc847642990/]C:Zhu'smultiset二分答案,得出每个数的增长开始时间[crayon-58d5b3929b1e3758279178/]D:TeamThemUp!二分图染色+dp[crayon-58d5b3929b1e7963081273/]F.Boatherds傻逼点分治[crayon-58d5b3929b1f0968537667/] ...

  • 【bzoj1095】[ZJOI2007]Hide 捉迷藏

    【bzoj1095】[ZJOI2007]Hide 捉迷藏

    Description捉迷藏Jiajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激...

  • 【bzoj3991】[Sdoi2015]寻宝游戏

    【bzoj3991】[Sdoi2015]寻宝游戏

    Description 小B最近正在玩一个寻宝游戏,这个游戏的地图中有N个村庄和N-1条道路,并且任何两个村庄之间有且仅有一条路径可达。游戏开始时,玩家可以任意选择一个村庄,瞬间转移到这个村庄,然后可以任意在地图的道路上行走,若走到某个村庄中有宝物,则视为找到该村庄内的宝物,直到找到所有宝物并返回到最初转移到的村庄为止。小B希望评测一下这个游戏的难度,因此他需要知道玩家找到所有宝物需要行走的最短路程。但是这个...

    82015年4月17日2,706虚树,dfs序,STL,最近公共祖先
  • 【bzoj2770】YY的Treap

    【bzoj2770】YY的Treap

    Description志向远大的YY小朋友在学完快速排序之后决定学习平衡树,左思右想再加上SY的教唆,YY决定学习Treap。友爱教教父SY如砍瓜切菜般教会了YY小朋友Treap(一种平衡树,通过对每个节点随机分配一个priority,同时保证这棵平衡树关于priority是一个小根堆以保证效率)。这时候不怎么友爱的510跑了出来,他问了YY小朋友一个极不和谐的问题:怎么求Treap中两个点之间的路径长度。YY秒了之后决定把这个问题交给你...

    02015年4月16日1,375STL,二分法,线段树
  • TCO 2015 Round 1A DIV1

    TCO 2015 Round 1A DIV1

    250:枚举l-r的数,爆搜,统计数位,用map存一下TT实际上对于每个数小范围暴力即可TT[crayon-58d5b392b0541589777296/]500:暴力走min(n^2,K)次,预处理出哪些不能同时取。。。再暴搜+快速幂算方案TAT结果有个点T了。。。正解假如k步之前在一起了,那么k步的时候一定在一起了所以如果我们能求出k步的状态,就可以用每个数出现的次数+1的乘积作为答案(可以选择任意数量的放,也可以不放)所以暴力求状态后乘起来就行了。。...

    02015年4月15日9,695STL,深度搜索,二分图匹配
  • 【bzoj3931】[CQOI2015]网络吞吐量

    【bzoj3931】[CQOI2015]网络吞吐量

    题意即题解最短路+网络流1A了赞233[crayon-58d5b392b0a10093621297/] 

    82015年4月7日1,669STL,dijkstra,最大流
  • 【East!_XVI】不祥之刃

    【East!_XVI】不祥之刃

    Background卡特琳娜又要怒拿五杀了,怎么办啊?某无良设计师伊泽瑞尔笑了笑:“基兰,断网,重赛!”Description卡特琳娜要从1到N依次通过这N个李青[小学僧/盲僧],并最终击杀第N+1个李青[Dopa僧]。对于[小学僧],卡特琳娜可以击杀他得到一点法强和数量等同于该[小学僧]权值的金币;对于[盲僧],如果卡特琳娜当前法强大于等于该[盲僧]的权值,就会被该[盲僧]击杀。现在卡特琳娜要击杀[Dopa僧],就必须得到大于等于其权值的法强。问卡特琳...

    02015年4月4日918贪心,STL
  • 【BC35】DZY Loves Topological Sorting

    【BC35】DZY Loves Topological Sorting

    问题描述一张有向图的拓扑序列是图中点的一个排列,满足对于图中的每条有向边(u→v)从u到v,都满足u在排列中出现在v之前。现在,DZY有一张有向无环图(DAG)。你要在最多删去k条边之后,求出字典序最大的拓扑序列。输入描述输入有多组数据。(TestCase≤5)第一行,三个正整数n,m,k(1≤n,m≤105,0≤k≤m).接下来m行,每行两个正整数u,v(u≠v,1≤u,v≤n),代表一条有向边(u→v).输出描述对于每组测试数据,输出一行字典序最大的拓...

    02015年3月30日1,016贪心,STL,拓扑排序
  • 【cf529B】Group Photo 2 (online mirror version)

    【cf529B】Group Photo 2 (online mirror version)

    Manyyearshavepassed,andnfriendsmetatapartyagain.Technologieshaveleapedforwardsincethelastmeeting,cameraswithtimerappearedandnowitisnotobligatoryforoneofthefriendstostandwithacamera,and,thus,beingabsentonthephoto.Simplyspeaking,theprocessofphotographingcanbedescribedasfollows.Eachfriendoccupiesarectangleofpixelsonthephoto:thei-thoftheminastandingstateoccupiesawipixelswideandahipixelshighrectang...

    02015年3月23日741STL,贪心
  • [jsoi2010]旅行

    [jsoi2010]旅行

    给定一张无向图,可以k次交换两条边边权,求1到n的最短路交换执行于求最短路之前,边权1<=c<=1000点数<=50边数<=150k<=20此题找不到题解求神犇留言做法我的想法。。。先求从1-n,无视i条边边权的最短路,然后在路径外找i条最短的加回去。。最后只对了5个点。。。[crayon-58d5b392b1b7a621011941/] ...

    12015年3月23日1,107spfa,STL
  • 【bzoj2590】[Usaco2012 Feb]Cow Coupons

    【bzoj2590】[Usaco2012 Feb]Cow Coupons

    DescriptionFarmerJohnneedsnewcows!ThereareNcowsforsale(1<=N<=50,000),andFJhastospendnomorethanhisbudgetofMunitsofmoney(1<=M<=10^14).CowicostsP_imoney(1<=P_i<=10^9),butFJhasKcoupons(1<=K<=N),andwhenheusesacoupononcowi,thecowcostsC_iinstead(1<=C_i<=P_i).FJcanonlyuseonecouponpercow,ofcourse.WhatisthemaximumnumberofcowsFJcanafford?PROBLEMN...

    12015年3月23日1,411STL,贪心
  • 【cf528A】Glass Carving

    【cf528A】Glass Carving

    Leonidwantstobecomeaglasscarver(thepersonwhocreatesbeautifulartworksbycuttingtheglass).Healreadyhasarectangularwmm × hmmsheetofglass,adiamondglasscutterandlotsofenthusiasm.Whathelacksisunderstandingofwhattocarveandhow.Inordernottowastetime,hedecidedtopracticethetechniqueofcarving.Todothis,hemakesverticalandhorizontalcutsthroughtheentiresheet.Thisprocessresultsinmakingsmallerrectangularfra...

    12015年3月18日903STL,离线处理
  • 【cf521B】Cubes

    【cf521B】Cubes

    OnceVasyaandPetyaassembledafigureofmcubes,eachofthemisassociatedwithanumberbetween0andm - 1(inclusive,eachnumberappearedexactlyonce).Let'sconsideracoordinatesystemsuchthattheOXistheground,andtheOYisdirectedupwards.Eachcubeisassociatedwiththecoordinatesofitslowerleftcorner,thesecoordinatesareintegersforeachcube.Thefigureturnedouttobestable.Thismeansthatforanycubethatisnotontheground,th...

    02015年3月14日801STL,贪心