hzwer.com - Page 12

「BZOJ3535」[Usaco2014 Open] Fair Photography
DescriptionFJ'sNcows(1<=N<=100,000)arestandingatvariouspositionsalongalongone-dimensionalfence.Theithcowisstandingatpositionx_i(anintegerintherange0...1,000,000,000)andhasbreedb_i(anintegerintherange1..8).Notwocowsoccupythesameposition.FJwantstotakeaphotoofacontiguousintervalofcowsforthecountyfair,butwewantsallofhisbreedstobefairlyrepresentedinthephoto.Therefore,hewantstoensurethat...
12015年7月12日5,002哈希表

「FJ2015集训」热身题
「问题描述」定义F：F(1)=1,F(2)=2,F(n)=F(n-1)+F(n-2)(n>=3)定义p：p(i)=a1*F(1)^i+a2*F(2)^i+…+ak*F(k)^i其中k和a1…ak为常数。现在已知k,p(1),p(2),…,p(k)，求p(k+1)。为了避免高精度，所有运算都模掉M。保证F(1),…,F(n)在模质数M下两两不同，保证有唯一解。「输入格式」第一行，两个整数k,M。第二行，p(1),p(2),...,p(k)模M。「输出格式」输出p(k+1)模M。「样例输入1」310151129「样例输出1」83「样例输...
12015年7月12日4,777快速幂,高斯消元,乘法逆元
「FJ2015集训」签到题
「问题描述」给定一个n个点的严格凸多边形（各个内角<180°），现在要切出两个非退化三角形（三点不共线），要求两个三角形顶点必须是凸多边形的顶点，且三角形不可相交（但是点或边可以重合）。求两个三角形面积之差的最大值。「输入格式」第一行，一个整数N。第二到N+1行，每行两个整数xi,yi，表示多边形的一个点，保证顶点按顺时针或逆时针顺序给出。「输出格式」输出答案，精确到小数点后1位。「样例输入1」400011210「样...
12015年7月12日3,675旋转卡壳
「BZOJ3600」没有人的算术
http://pan.baidu.com/s/1B0JNovfk大大的题好厉害QAQWJMZBMR在论文中也有提到平衡树的这种用法《重量平衡树和后缀平衡树在信息学奥赛中的应用》大概就是用平衡树维护这些数，给每个数一个实数值表示其大小生成一个数(a,b)的时候，由于a,b都是之前出现过的数，所以我们可以直接在平衡树上插入，返回代表它的实数值用线段树求区间最大值[crayon-664b90fd9c2e1203331653/] ...
32015年7月11日7,901替罪羊树,线段树
「BZOJ1229」[USACO2008 Nov] toy 玩具
Description玩具[ChenHu,2006]Bessie的生日快到了,她希望用D(1<=D<=100,000;70%的测试数据都满足1<=D<=500)天来庆祝.奶牛们的注意力不会太集中,因此Bessie想通过提供玩具的方式来使它们高兴.她已经计算出了第i天需要的玩具数T_i(1<=T_i<=50).Bessie的幼儿园提供了许多服务给它们的奶牛程序员们,包括一个每天以Tc(1<=Tc<=60)美元卖出商品的玩具店.Bessie想尽可能的节省钱,但是FarmerJohn担...
22015年7月11日5,862贪心,三分法
「BZOJ3230」相似子串
DescriptionInput输入第1行，包含3个整数N，Q。Q代表询问组数。第2行是字符串S。接下来Q行，每行两个整数i和j。（1≤i≤j）。Output输出共Q行，每行一个数表示每组询问的答案。如果不存在第i个子串或第j个子串，则输出-1。SampleInput53ababa3559810SampleOutput1816-1HINT样例解释第1组询问：两个子串是“aba”,“ababa”。f=32+32=18。第2组询问：两个子串是“ababa”,“baba”。f=02+42=16。第3组询问：不存在...
12015年7月9日5,958后缀数组
「BZOJ3483 / 4212」SGU505 Prefixes and suffixes(询问在线版)
DescriptionGAL发现了N个特殊的字母序列，由小写字母组成。小L认为，对于两个字符串s1,s2，若s1是某个特殊序列的前缀，s2是该特殊序列的后缀，则称s1,s2被这个序列拥有。现在小L给出M对s1,s2，对于每对字符串，问它们被几个特殊序列拥有。Input第1行一个整数N。接下来N行，每行一个字符串，代表N个特殊序列。第N+2行一个整数M。接下来M行每行一对s1,s2用空格隔开。S1,s2是经过加密的。设上一问的答案为lastans。解...
32015年7月7日3,702STL,哈希表
「BZOJ4207」「FJ2015集训」Can’t Stop
「题目描述」这个问题是源于一个在棋盘上玩的，由SidSackson设计的名叫Can'tstop的游戏的。这个问题与Can'tstop有一定的相似之处，但是不需要玩过Can'tstop。你在玩一个（非常大型的）棋盘游戏。在这个游戏里面，给出了一个长度为N的rollset的序列。每个rollset包括D个dieroll，每个dieroll是一个正整数。你需要找到序列中总长度最大的极好的区间。区间即为连续的一段rollset。如果存在k个数使某个区间内的所有rollset都至少...
22015年7月6日4,758深度搜索
「CF305X」Codeforces Round #184 (Div. 2)
A.StrangeAddition考虑0的个数，是否存在100，是否同时存在X0和0X[crayon-664b90fd9e659306738428/]B.ContinuedFractionshttp://www.cnblogs.com/scau20110726/archive/2013/06/09/3130198.html[crayon-664b90fd9e663034249420/]C.IvanandPowersofTwo感觉就是个模拟题0。0，每个数字再往后若干位开始一定就会是连续一段0用map机智的暴力[crayon-664b90fd9e668079861264/]D.OlyaandGraph性质1：从i到i+1的边一定要存...
02015年7月6日3,909模拟,STL
「CF268D」Wall Bars
Manaoisworkingforaconstructioncompany.Recently,anordercametobuildwallbarsinachildren'spark.Manaowascommissionedtodevelopaplanofconstruction,whichwillenablethecompanytosavethemostmoney.Afterreviewingtheformalspecificationsforthewallbars,Manaodiscoveredanumberofcontroversialrequirementsanddecidedtotreatthemtothecompany'sadvantage.Hisresultingdesigncanbedescribedasfollows:Let'sintroducesomeuni...
22015年7月6日3,886递推与动规
「CF316D3」PE Lesson
SmartBeaverdecidedtobenotonlysmart,butalsoahealthybeaver!AndsohebegantoattendphysicaleducationclassesatschoolX.Inthisschool,physicaleducationhasaverycreativeteacher.Oneofhisfavoritewarm-upexercisesisthrowingballs.Studentslineup.Eachonegetsasingleballinthebeginning.Theballsarenumberedfrom1ton(bythedemandoftheinventorycommission).Figure1.Theinitialpositionforn = 5.Afterreceivingtheball...
02015年7月5日2,687递推与动规
「BZOJ4205」「FJ2015集训」卡牌配对
卡牌配对「问题描述」现在有一种卡牌游戏，每张卡牌上有三个属性值：A,B,C。把卡牌分为X,Y两类，分别有n1,n2张。两张卡牌能够配对，当且仅当，存在至多一项属性值使得两张卡牌该项属性值互质，且两张卡牌类别不同。比如一张X类卡牌属性值分别是225,233,101，一张Y类卡牌属性值分别为115,466,99。那么这两张牌是可以配对的，因为只有101和99一组属性互质。游戏的目的是最大化匹配上的卡牌组数，当然每张卡牌只能用一次。「输...
32015年7月5日5,391二分图匹配,网络流