状压动规 - Page 2

「CF534X」Codeforces Round #298 (Div. 2)
「cf534A」Examyy个奇怪的构造TT[crayon-6a1d33d17803b651153144/]「cf534B」CoveredPathd很小，最大速度就很小，dp即可[crayon-6a1d33d178044057756890/]「cf534C」Polycarpus'Dice对于每个骰子，得出其它骰子的和sum则它的最小值为A-sum，最大值为A-n+1[crayon-6a1d33d178049081313369/]「cf534D」Handshakes尽量大的能处理则处理[crayon-6a1d33d17804e224828459/]「cf534E」BerlandLocalPositioningSystem非...
02015年4月13日4,152递推与动规,贪心,深度搜索,构造,状压动规

「codechef」January Lunchtime 2015
Pieceofcake 统计每个字母出现次数，取最大值，判断其是否等于l/2[crayon-6a1d33d178780998754144/]Justmultiply 乘法快速乘即可，但乘方由于M过大。。使用欧拉函数降幂比较麻烦。。发现a^(10b+c)=(a^b)^10*a^c然后就能On算出表达式了^10可以看做常数[crayon-6a1d33d17878a132612247/]Candidatewalk状压一下，转移显然[crayon-6a1d33d17878f498592849/]Manybananas这一题比较有意思将宗族大小分为<=300和>300用数组统...
02015年3月1日4,561模拟,状压动规,树状数组,快速幂
「fjWC2015」三视图
「题目描述」史蒂夫想在minecraft里盖一座房子，众所周知，minecraft世界主要是由各式各样的立方体组成的。可惜的是，现在史蒂夫只拿到了建筑图纸的左视图和正视图（如下所示）。请问可能有多少种建筑符合给定的左视图和正视图，答案对10^9+9取模。方块不能悬空摆放。「输入格式」第一行一个整数n，表示正视图的列数。第二行n个整数，表示每列能看到的最高的立方体柱的高度。第三行一个整数m，表示左视图的列数。第四行m个整数，表...
12015年2月4日5,447状压动规
「BZOJ2004」[HNOI2010] Bus 公交线路
Description小Z所在的城市有N个公交车站，排列在一条长(N-1)km的直线上，从左到右依次编号为1到N，相邻公交车站间的距离均为1km。作为公交车线路的规划者，小Z调查了市民的需求，决定按下述规则设计线路：1．设共K辆公交车，则1到K号站作为始发站，N-K+1到N号台作为终点站。2．每个车站必须被一辆且仅一辆公交车经过（始发站和终点站也算被经过）。3．公交车只能从编号较小的站台驶往编号较大的站台。4．一辆公交车经过...
02015年1月31日5,218状压动规
「BZOJ2073」[POI2004] PRZ
Description一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥.桥已经很旧了,所以它不能承受太重的东西.任何时候队伍在桥上的人都不能超过一定的限制.所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过.队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,我们想知道如何分批过桥能使总时间最少.Input第一行两个数:w–桥能承受的最大重量(...
02015年1月22日4,650状压动规
「POJ2404」Jogging Trails
DescriptionGordistrainingforamarathon.Behindhishouseisaparkwithalargenetworkofjoggingtrailsconnectingwaterstations.Gordwantstofindtheshortestjoggingroutethattravelsalongeverytrailatleastonce.InputInputconsistsofseveraltestcases.Thefirstlineofinputforeachcasecontainstwopositiveintegers:n<=15,thenumberofwaterstations,andm<1000,thenumberoftrails.Foreachtrail,thereisonesubsequentlineofin...
02015年1月2日5,450floyd,状压动规
「BZOJ2595」[Wc2008] 游览计划
DescriptionInput第一行有两个整数，N和M，描述方块的数目。接下来N行，每行有M个非负整数，如果该整数为0，则该方块为一个景点；否则表示控制该方块至少需要的志愿者数目。相邻的整数用（若干个）空格隔开，行首行末也可能有多余的空格。Output由N+1行组成。第一行为一个整数，表示你所给出的方案中安排的志愿者总数目。接下来N行，每行M个字符，描述方案中相应方块的情况：z ‘_’（下划线）表示该方块没有安排志愿者...
42014年12月20日7,523状压动规
「BZOJ1226」[SDOI2009] 学校食堂Dining
Description小F的学校在城市的一个偏僻角落，所有学生都只好在学校吃饭。学校有一个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴。当然，不同的人口味也不一定相同，但每个人的口味都可以用一个非负整数表示。由于人手不够，食堂每次只能为一个人做菜。做每道菜所需的时间是和前一道菜有关的，若前一道菜的对应的口味是a，这一道为b，则做这道菜所需的时间为（aorb）-（aandb），而做第一道菜是不需要计算时间的。其中...
12014年12月13日6,639状压动规
「BZOJ2734」[HNOI2012] 集合选数
Description《集合论与图论》这门课程有一道作业题，要求同学们求出{1,2,3,4,5}的所有满足以下条件的子集：若x在该子集中，则2x和3x不能在该子集中。同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数n≤100000，如何求出{1,2,...,n}的满足上述约束条件的子集的个数（只需输出对1,000,000,001取模的结果），现在这个问题就交给你了。Input 只有一行，其中有一个正整数n，30%的数据满足n≤20。O...
62014年11月13日7,220状压动规
「NOIP模拟赛」篮球比赛2
由于Czhou举行了众多NOIP模拟赛，也导致放学后篮球比赛次数急剧增加。神牛们身体素质突飞猛进，并且球技不断精进。这引起了体育老师彩哥的注意，为了给校篮球队找到势均力敌的对手，彩哥找到了Czhou神，想要和机房篮球队进行多场友谊赛。Czhou为了顾全校篮球队面子，决定派出配合默契又不至于吊打校篮球队的阵容。而机房神牛的能力值受到游戏时长，训练时长，个人基础值得影响，可能会不断变化。所以Czhou想根据神牛当...
12014年11月5日5,830背包动规,深度搜索,状压动规
「NOIP模拟赛」班服
题目描述：要开运动会了，神犇学校的n个班级要选班服，班服共有100种样式，编号1~100。现在每个班都挑出了一些样式待选，每个班最多有100个待选的样式。要求每个班最终选定一种样式作为班服，且该班的样式不能与其他班级的相同，求所有可能方案的总数，由于方案总数可能很大，所以要求输出mod1000000007后的答案。输入描述：共有T组数据。对于每组数据，第一行为一个整数n，表示有n个班级。2~n+1行，每行有最多100个数字，表示第i...
02014年10月25日4,257状压动规
「BZOJ1097」[POI2007] 旅游景点atr
DescriptionFGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景，品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的，比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山，而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的，他可以在某些旅行方案之间进行选择。由于FGD非常讨厌乘车的颠簸，他希望在满足他的要求的情况下，旅行的距离尽量短，这样他就有足...
02014年10月19日6,052dijkstra,状压动规