hzwer.com - Page 35

「POJ1637」Sightseeing tour
DescriptionThecityexecutiveboardinLundwantstoconstructasightseeingtourbybusinLund,sothattouristscanseeeverycornerofthebeautifulcity.Theywanttoconstructthetoursothateverystreetinthecityisvisitedexactlyonce.Thebusshouldalsostartandendatthesamejunction.Asinanycity,thestreetsareeitherone-wayortwo-way,trafficrulesthatmustbeobeyedbythetourbus.Helptheexecutiveboardanddetermineifit'spossibletocons...
12014年12月29日5,384最大流,欧拉图

「POJ1284」Primitive Roots
DescriptionWesaythatintegerx,0<x<p,isaprimitiverootmodulooddprimepifandonlyiftheset{(ximodp)|1<=i<=p-1}isequalto{1,...,p-1}.Forexample,theconsecutivepowersof3modulo7are3,2,6,4,5,1,andthus3isaprimitiverootmodulo7.Writeaprogramwhichgivenanyoddprime3<=p<65536outputsthenumberofprimitiverootsmodulop.InputEachlineoftheinputcontainsanoddprimenumbersp.Inputisterminatedbytheend-of-...
02014年12月29日4,331筛法,欧拉函数
「BZOJ2186」[SDOI2008] 沙拉公主的困惑
Description　　大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对R取模后的答案即可。R是一个质数。Input第一行为两个整数T，R。R<=10^9+10，T<=10000，表示该组中测试数据数目，R...
62014年12月28日8,943筛法,欧拉函数,乘法逆元
「codechefTASTRMAT」String Matching
其实我没有参赛。。。在比赛时间被人拉去做了这一道。。。你们就坑我吧设L=n-m对于B的第1个字符，其匹配的是A的一个区间1到1+L若其与A[1]不同，则hash值增加100001^m与A[1+K]不同，则hash值增加100001^(n-K)用数据结构支持查询1到1+L对hash值的贡献即第K位与B的第1个字符不同则hash值增加100001^(n-K)，相同增加0用个线段树or树状数组（实际上前缀和就行）接着考虑对于B的第2个字符，其匹配的是A的一个区间2到2+L若...
02014年12月28日2,967线段树,乘法逆元
「zoj2760」How Many Shortest Path
Givenaweighteddirectedgraph,wedefinetheshortestpathasthepathwhohasthesmallestlengthamongallthepathconnectingthesourcevertextothetargetvertex.Andiftwopathissaidtobenon-overlapping,itmeansthatthetwopathhasnocommonedge.So,givenaweighteddirectedgraph,asourcevertexandatargetvertex,weareinterestedinhowmanynon-overlappingshortestpathcouldwefindoutatmost.InputInputconsistsofmultipletestcases.Thefirs...
02014年12月27日3,626最大流,floyd
「BZOJ2400」SPOJ 839 Optimal Marks
Description定义无向图中的一条边的值为：这条边连接的两个点的值的异或值。定义一个无向图的值为：这个无向图所有边的值的和。给你一个有n个结点m条边的无向图。其中的一些点的值是给定的，而其余的点的值由你决定（但要求均为非负数），使得这个无向图的值最小。在无向图的值最小的前提下，使得无向图中所有点的值的和最小。Input第一行，两个数n，m，表示图的点数和边数。接下来n行，每行一个数，按编号给出每个点的值（若为负...
22014年12月27日5,781最小割
「网络流24题」最长递增子序列问题
题意有些奇怪任务（2）是取出。。。且题中递增是非严格递增我的代码任务3若能取出无限多的序列，则输出-1输入41324输出3 1 2样例2输入43625输出2 2 -1搬运byvoid神犇题解「问题分析」第一问是LIS，动态规划求解，第二问和第三问用网络最大流解决。「建模方法」首先动态规划求出F[i]，表示以第i位为开头的最长上升序列的长度，求出最长上升序列长度K。1、把序列每位i拆成两个点<i.a>和<i.b>，从<i.a>到&...
52014年12月27日6,580最大流
「网络流24题」最长k可重区间集问题
搬运byvoid的题解「问题分析」最大权不相交路径问题，可以用最大费用最大流解决。「建模方法」方法1按左端点排序所有区间，把每个区间拆分看做两个顶点<i.a><i.b>，建立附加源S汇T，以及附加顶点S'。1、连接S到S'一条容量为K，费用为0的有向边。2、从S'到每个<i.a>连接一条容量为1，费用为0的有向边。3、从每个<i.b>到T连接一条容量为1，费用为0的有向边。4、从每个顶点<i.a>到<i.b>连...
22014年12月27日5,967费用流
「POJ1149」PIGS
DescriptionMirkoworksonapigfarmthatconsistsofMlockedpig-housesandMirkocan'tunlockanypighousebecausehedoesn'thavethekeys.Customerscometothefarmoneafteranother.Eachofthemhaskeystosomepig-housesandwantstobuyacertainnumberofpigs.AlldataconcerningcustomersplanningtovisitthefarmonthatparticulardayareavailabletoMirkoearlyinthemorningsothathecanmakeasales-planinordertomaximizethenumberofpigssold.M...
02014年12月27日5,836最大流
「泉七培训 – 杨国烨」图
「题目描述」给一张联通无向图，定义Dist[i][j]表示点i到点j之间的最短路。当前已经有了若干条的边，再给定N个A[i]，要求添加若干条无向边，使得Σ(a[i]-Dist[1][i])^2最小。输出最小的答案。「输入格式」第一行是整数N，表示节点数。接下来是N*N的矩阵，mat[i][j]=‘Y’表示i和j之间有一条无向边。保证mat[i][j]=mat[j][i]。接下来N个数，表示A[i]。「输出格式」求答案。「样例输入」4NYNNYNYNNYNYNNYN...
02014年12月26日4,399最小割
「泉七培训 – 刘定峰」链型网络
题意给定一张无重边，自环的无向图每次可以加边，或者询问有多少个点满足将该点删除后，原图的每个连通块都为一条链数据范围30%的数据n<=100m<=2n100%的数据n<=100000,m<=2n 题解30分很简单对于每次询问枚举删去每一个点，然后再用O（n）的时间在图上判环以及度数是否都小等于2 然后正解。。。考虑以下一些简单的情况原图为若干条链，则答案为点数N原图为单个简单环加若干条链，则答案为环大小原图中...
02014年12月26日4,831深度搜索,并查集
「泉七培训 – 杨国烨」出纳员zgg
「题目描述」zgg去当出纳员了！zgg所在的公司的工资是按年发放的。在每年的元旦，每个员工的工资额会被修改为0元；在每年的除夕，员工按工资额领取相应的工资。zgg的上司是一位和蔼可亲的老爷爷，他经常给员工们提升工资。而zgg的工作，就是帮助所有员工统计最后的工资额。老爷爷只会用以下两种指令给员工们提升工资：1.让某个员工的工资额提升X元；2.让所有员工的工资额变成原来的X倍。然则，由于老爷爷实在是太和蔼了，以至于提...
02014年12月26日3,390树形动规