深度搜索 - Page 4

「BZOJ3206」[Apio2013] 道路费用
DescriptionInput你的程序必须从标准输入读入。第一行包含三个由空格隔开的整数N，M和K。接下来的 M行描述最开始的M 条道路。这M行中的第i行包含由空格隔开的整数ai，bi和ci，表示有一条在ai和bi之间，费用为ci的双向道路。接下来的K行描述新建的K条道路。这 K行中的第i行包含由空格隔开的整数 xi和yi，表示有一条连接城镇xi和yi新道路。最后一行包含N个由空格隔开的整数，其中的第j个为pj，表示从城镇j 前往城镇...
02015年4月27日6,394kruskal,深度搜索

「BZOJ1478」Sgu282 Isomorphism
Description给定一个N个结点的无向完全图（任意两个结点之间有一条边），现在你可以用M种颜色对这个图的每条边进行染色，每条边必须染一种颜色。若两个已染色的图，其中一个图可以通过结点重新编号而与另一个图完全相同，就称这两个染色方案相同。现在问你有多少种本质不同的染色方法，输出结果modP。P是一个大于N的质数。Input仅一行包含三个数，N、M、P。Output仅一行，为染色方法数modP的结果。SampleInput3497S...
32015年4月25日4,584深度搜索,置换,快速幂
「BZOJ3990」[SDOI2015] 排序
Description 小A有一个1-2^N的排列A[1..2^N],他希望将A数组从小到大排序,小A可以执行的操作有N种,每种操作最多可以执行一次,对于所有的i(1<=i<=N),第i中操作为将序列从左到右划分为2^{N-i+1}段,每段恰好包括2^{i-1}个数,然后整体交换其中两段.小A想知道可以将数组A从小到大排序的不同的操作序列有多少个,小A认为两个操作序列不同,当且仅当操作个数不同,或者至少一个操作不同(种类不同或者操作位置不同). 下面...
32015年4月23日5,517深度搜索
TCO 2015 Round 1A DIV1
250：枚举l-r的数，爆搜，统计数位，用map存一下TT实际上对于每个数小范围暴力即可TT[crayon-662b2066618c7300496599/]500：暴力走min(n^2,K)次，预处理出哪些不能同时取。。。再暴搜+快速幂算方案TAT结果有个点T了。。。正解假如k步之前在一起了，那么k步的时候一定在一起了所以如果我们能求出k步的状态，就可以用每个数出现的次数+1的乘积作为答案（可以选择任意数量的放，也可以不放）所以暴力求状态后乘起来就行了。。...
02015年4月15日33,208STL,深度搜索,二分图匹配
「CF534X」Codeforces Round #298 (Div. 2)
「cf534A」Examyy个奇怪的构造TT[crayon-662b20667fb1a296932851/]「cf534B」CoveredPathd很小，最大速度就很小，dp即可[crayon-662b20667fb25900488606/]「cf534C」Polycarpus'Dice对于每个骰子，得出其它骰子的和sum则它的最小值为A-sum，最大值为A-n+1[crayon-662b20667fb2b743761502/]「cf534D」Handshakes尽量大的能处理则处理[crayon-662b20667fb2f262688633/]「cf534E」BerlandLocalPositioningSystem非...
02015年4月13日3,179递推与动规,贪心,构造,深度搜索,状压动规
dancing link
其实感觉就是个搜索的优化我们只要知道一件事情就是双向链表中删除一个元素xl[r[x]]=l[x],r[l[x]]=r[x]这时候实际上x元素的左右指针没有被改变所以可以很容易地恢复回来然后看看代码应该就不难理解了贴一波代码hust1017fzu1686hdu2295hust1017精确覆盖应该没有更裸的了[crayon-662b20668021a358064198/]fzu1686裸重复覆盖实际上重复覆盖仅仅是在精确覆盖基础上略微改动一些主要是加入一个估价函数，即当前状态至少还需要的步数从左...
22015年4月1日4,226深度搜索,链表
「BC35」DZY Loves Balls
问题描述一个盒子里有n个黑球和m个白球。现在DZY每次随机从盒子里取走一个球，取了n+m次后，刚好取完。DZY用这种奇怪的方法生成了一个随机的01串S[1⋯(n+m)]。如果DZY第i次取出的球是黑色的，那么S[i]=1，如果是白色的，那么S[i]=0。DZY现在想知道，'01'在S串中出现的期望次数。输入描述输入有多组测试数据。(TestCase≤150)每行两个整数,n,m(1≤n,m≤12)输出描述对于每个测试数据，输出一行答案，格式为p/q(p,q...
12015年3月30日2,404深度搜索
「CF516B」Drazil and Tiles
Drazilcreatedafollowingproblemaboutputting1 × 2tilesintoann × mgrid:"Thereisagridwithsomecellsthatareemptyandsomecellsthatareoccupied.Youshoulduse1 × 2tilestocoverallemptycellsandnotwotilesshouldcovereachother.Andyoushouldprintasolutionabouthowtodoit."ButDrazildoesn'tliketowritespecialcheckingprogramforthistask.Hisfriend,Vardaadvisedhim:"howaboutaskingcontestantonlytoprintthesolut...
02015年2月25日2,769深度搜索,拓扑排序
「fjWC2015」当小威遇上玩具
「题目描述」么么哒的小威同学得到一个好玩的玩具。小威同学对它爱不释手。它包含若干根木棒,小威可以用这些木棒对称地摆成一个正九边形。愚人节到了,小威最好的朋(ji)友小斌同学决定捉弄一下么么哒的小威同学,就声称他带走了其中的若干根木棒。小威想先看看到底有没有少木棒,然后再考虑怎么整小斌。小威判断有没有少木棒的做法很简单,就是剩下的木棒能不能对称地摆成一个正九边形(木棒都要用上)。可是小威的智商比较捉急,他弄了半...
02015年2月4日3,196深度搜索
「POJ2362」Square
DescriptionGivenasetofsticksofvariouslengths,isitpossibletojointhemend-to-endtoformasquare?InputThefirstlineofinputcontainsN,thenumberoftestcases.Eachtestcasebeginswithaninteger4<=M<=20,thenumberofsticks.Mintegersfollow;eachgivesthelengthofastick-anintegerbetween1and10,000.OutputForeachcase,outputalinecontaining"yes"ifisispossibletoformasquare;otherwiseoutput"no".SampleInput[cray...
02015年1月22日2,437深度搜索
「codechef」December Challenge 2014
「codechefCAPPLE」ChefandAppleTrees其实我想练习打字，点开codechef随便做。。。后来发现这是在challenge，后来补了俩题[crayon-662b206682129163318998/]「codechefXORSUB」XORwithSubset求线性基，裸题[crayon-662b206682132568409703/]「codechefSANSKAR」Alok-nathandHisSanskars从大到小排序后优先用大的合成随便搜索一下TAT这样过了codechef但是似乎会被构造卡掉144151017161211020171945...
02015年1月9日2,874模拟,深度搜索,高斯消元
「泉七培训 – 刘定峰」链型网络
题意给定一张无重边，自环的无向图每次可以加边，或者询问有多少个点满足将该点删除后，原图的每个连通块都为一条链数据范围30%的数据n<=100m<=2n100%的数据n<=100000,m<=2n 题解30分很简单对于每次询问枚举删去每一个点，然后再用O（n）的时间在图上判环以及度数是否都小等于2 然后正解。。。考虑以下一些简单的情况原图为若干条链，则答案为点数N原图为单个简单环加若干条链，则答案为环大小原图中...
02014年12月26日4,368深度搜索,并查集