• 「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,520贪心,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日1,170STL,贪心
  • [JSOI2010] 旅行

    [JSOI2010] 旅行

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

    22015年3月23日1,853STL,spfa
  • 「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日2,460STL,贪心
  • 「CF528A」Glass Carving

    「CF528A」Glass Carving

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

    12015年3月18日907STL,离线处理
  • 「CF521B」Cubes

    「CF521B」Cubes

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

    02015年3月14日1,197贪心,STL
  • 「BZOJ2796」[POI2012] Fibonacci Representation

    「BZOJ2796」[POI2012] Fibonacci Representation

    DescriptionFib数列0,1,1,2,3,5,8,13,21。给出一个数字,用FIB数列各项加加减减来得到。例如10=5+519=21-217=13+5-11070=987+89-5-1InputInthefirstlineofthestandardinputasinglepositiveintegerisgiven(1<=P<=10)thatdenotesthenumberofqueries.ThefollowinglinesholdasinglepositiveintegerKeach1<=K<=10^17.OutputForeachqueryyourprogramshouldprintonthestandardoutputtheminimumnumberofFibona...

    12015年3月12日2,040STL,记忆化搜索
  • 「BZOJ3728」PA2014Final Zarowki

    「BZOJ3728」PA2014Final Zarowki

    Description有n个房间和n盏灯,你需要在每个房间里放入一盏灯。每盏灯都有一定功率,每间房间都需要不少于一定功率的灯泡才可以完全照亮。你可以去附近的商店换新灯泡,商店里所有正整数功率的灯泡都有售。但由于背包空间有限,你至多只能换k个灯泡。你需要找到一个合理的方案使得每个房间都被完全照亮,并在这个前提下使得总功率尽可能小。Input第一行两个整数n,k(1<=k<=n<=500000)。第二行n个整数p[i](1<=p[i]<...

    02015年3月2日1,558STL,贪心
  • 「CF519X」Codeforces Round #294 (Div. 2)

    「CF519X」Codeforces Round #294 (Div. 2)

    「cf519A」AandBandChess模拟[crayon-5d35c831d51ab116749361/]「cf519B」AandBandCompilationErrors排序,双指针对比用个hash/map统计下元素出现次数[crayon-5d35c831d51b6055864936/]「cf519C」AandBandTeamTraining实际上答案是min(n,m,(m+n)/3)我分类讨论了TAT还是很好yy的[crayon-5d35c831d51bc653412322/]「cf519D」AandBandInterestingSubstringsa[i][j]表示前缀和为i,字母j为末尾的前缀数量每次查询...

  • 「BZOJ3544」[ONTAK2010] Creative Accounting

    「BZOJ3544」[ONTAK2010] Creative Accounting

    Description给定一个长度为N的数组a和M,求一个区间[l,r],使得(\sum_{i=l}^{r}{a_i})modM的值最大,求出这个值,注意这里的mod是数学上的modInput第一行两个整数N,M。第二行N个整数a_i。Output输出一行,表示答案。SampleInput5131095-57SampleOutput11HINT「数据范围」N<=200000,M,a_i<=10^18题解水水更健康维护前缀和,对于每个前缀和,用set找第一个其大的数,找不到就取set中最小的数,然后将当前...

    22015年2月28日1,684STL
  • 离大海最远点在哪里?

    离大海最远点在哪里?

    http://218.5.5.242:9014/problem.asp?id=1678题目描述遥远的海上有一座岛屿,这个岛屿的轮廓是一个凸多边形,把边视为岛屿的海岸线。当地的居民想要在岛屿上找一地点使其到大海的距离最远,这地点应在哪里?岛上居民们习惯地把岛上某个点到岛屿的各条海岸线(即各边)距离中最小者看成该点到大海的距离。如下图所示,点O到大海的距离为min{j,k,l,m,n}=j,其中j,k,l,m,n分别为O到AB,BC,CD,DE,EA的距离。现在,给您N...

    02015年2月3日2,620STL,链表,二分法,半平面交
  • 「fjWC2015」k个串 kstring

    「fjWC2015」k个串 kstring

    「题目描述」兔子们在玩k个串的游戏。首先,它们拿出了一个长度为n的数字序列,选出其中的一个连续子串,然后统计其子串中所有数字之和(注意这里重复出现的数字只被统计一次)。兔子们想知道,在这个数字序列所有连续的子串中,按照以上方式统计其所有数字之和,第k大的和是多少。「输入格式」第一行,两个整数n和k,分别表示长度为n的数字序列和想要统计的第k大的和接下里一行n个数a_i,表示这个数字序列「输出格式」一行一个整数...

    42015年2月3日3,331可持久化线段树,STL