算法 - Page 32 - hzwer.com

「codechef」January Challenge 2015
CHEFSTON[crayon-6805076859199403255186/]GCDQgcd满足区间加法TAT，所以维护前缀和后缀和就好了[crayon-68050768591aa057859598/]SEAVOTE去掉所有0后若∑bi<tot或∑bi>=100+n则无解否则有解[crayon-68050768591b4925772078/]ONEKING按照右端点排序，选择第一个的右端点，删去覆盖其的线段。。。剩下的线段同理[crayon-68050768591bb728512542/]CLPERM答案根据第一个不能合成的数奇偶性得...
02015年1月12日6,595模拟,贪心,构造,数学,快速幂,随机化,容斥原理,最大公约数与最小公倍数

「点分治练习」[hdu4812] multik
「问题描述」给定一棵n个点的树,每个点有权值Vi问是否存在一条路径使得路径上所有点的权值乘积mod(10^6+3)为K输出路径的首尾标号,若有多解,输出字典序最小的解「输入格式」第一行两个数n,K第二行n个数,表示vi接下来n-1行每行两个数x,y表示一条边「输出格式」输出两个数a,b(a<b),无解输出”Nosolution”(不含引号)。「样例输入」5602523312132425「样例输出」34「数据规模与约定」对于100%的数据,有1≤n≤10^5,0≤K≤10^6+2...
62015年1月12日6,409点分治,乘法逆元
「点分治练习」不虚就是要AK
「问题描述」czy很火，因为又有人说他虚了为了证明他不虚,他决定要在这次比赛AK现在他正在和别人玩一个游戏:在一棵树上随机取两个点(两个点可以相同)如果这两个点的距离是4的倍数,那么算czy赢,否则对方赢现在czy想知道他能获胜的概率以即约分数形式输出这个概率(即”a/b”的形式,其中a和b必须互质。如果概率为1,输出”1/1”)「输入格式」多组数据,对于每组数据第一行一个数n,表示树上的节点个数接下来n-1条边a,b,c描述a到b有一条...
52015年1月10日6,206点分治
「点分治练习」boatherds
「问题描述」询问一颗树上距离为K的点对是否存在「输入格式」第一行两个整数n,m接下来n-1条边a,b,c描述a到b有一条长度为c的路径接下来m行每行询问一个K「输出格式」对于每个K每行输出一个答案存在输出”AYE”,否则输出”NYE”(不包含引号)「样例输入」2212112「样例输出」AYENYE「数据规模与约定」对于30%的数据,有1≤n≤100对于60%的数据,有1≤n≤10^31≤m≤50对于100%的数据,有1≤n≤10^4,1≤m≤100,1≤c≤1000,1...
12015年1月10日4,173STL,点分治
「CODEVS1515」跳
题目描述Description邪教喜欢在各种各样空间内跳。现在，邪教来到了一个二维平面。在这个平面内，如果邪教当前跳到了(x,y)，那么他下一步可以选择跳到以下4个点：(x-1,y),(x+1,y),(x,y-1),(x,y+1)。而每当邪教到达一个点，他需要耗费一些体力，假设到达(x,y)需要耗费的体力用C(x,y)表示。对于C(x,y)，有以下几个性质：1、若x=0或者y=0，则C(x,y)=1。2、若x>0且y>0，则C(x,y)=C(x,y-1)+C(x-1,y)。3、若x<0且y<0，...
72015年1月9日4,168贪心,快速幂,排列组合,乘法逆元
「BZOJ2151」种树
DescriptionA城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。园林部门得到指令后，初步规划出n个种树的位置，顺时针编号1到n。并且每个位置都有一个美观度Ai，如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤肥力欠佳，两棵树决不能种在相邻的位置（i号位置和i+1号位置叫相邻位置。值得注意的是1号和n号也算相邻位置！）。最终市政府给园林部门提供了m棵树苗并要求全部种上，...
02015年1月9日7,582STL,堆,贪心
「codechef」December Challenge 2014
「codechefCAPPLE」ChefandAppleTrees其实我想练习打字，点开codechef随便做。。。后来发现这是在challenge，后来补了俩题[crayon-680507685d62e065009073/]「codechefXORSUB」XORwithSubset求线性基，裸题[crayon-680507685d63b933132230/]「codechefSANSKAR」Alok-nathandHisSanskars从大到小排序后优先用大的合成随便搜索一下TAT这样过了codechef但是似乎会被构造卡掉144151017161211020171945...
02015年1月9日3,156模拟,深度搜索,高斯消元
「BZOJ2460」[BJ2011] 元素
Description 相传，在远古时期，位于西方大陆的MagicLand上，人们已经掌握了用魔法矿石炼制法杖的技术。那时人们就认识到，一个法杖的法力取决于使用的矿石。一般地，矿石越多则法力越强，但物极必反：有时，人们为了获取更强的法力而使用了很多矿石，却在炼制过程中发现魔法矿石全部消失了，从而无法炼制出法杖，这个现象被称为“魔法抵消”。特别地，如果在炼制过程中使用超过一块同一种矿石，那么一定会发生“魔法抵消”。后...
12015年1月8日5,715贪心,高斯消元
「BZOJ2738」矩阵乘法
Description　　给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。Input　　第一行两个数N,Q，表示矩阵大小和询问组数；接下来N行N列一共N*N个数，表示这个矩阵；再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。Output　　对于每组询问输出第K小的数。SampleInput2221341212111223SampleOutput13HINT　　矩阵中数...
02015年1月7日7,021二分法,树状数组
「BZOJ2527」[POI2011] Meteors
DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinanearbygalaxy.Theplanetisunsuitableforcolonisationduetostrangemeteorshowers,whichontheotherhandmakeitanexceptionallyinterestingobjectofstudy.ThememberstatesofBIUhavealreadyplacedspacestationsclosetotheplanet'sorbit.Thestations'goalistotakesamplesoftherocksflyingby.TheBIUCommissionhaspartitionedtheorbitinto...
42015年1月7日8,210二分法,树状数组
「codechefTADELIVE」Delivery Man
假设先都给x，然后再贪心选取一些给y[crayon-680507685f78c176212665/]
02015年1月6日2,581贪心
Fair Photography [Brian Dean, 2014]
http://218.5.5.242:9018/JudgeOnline/problem.php?id=1592题目描述FarmerJohn'sNcows(1<=N<=100,000)arestandingatvariouspositionsalongalongone-dimensionalfence. Theithcowisstandingatpositionx_i(anintegerintherange0...1,000,000,000)andhasbreedb_i(either'G'forGuernseyor'H'forHolstein). Notwocowsoccupythesameposition.FJwantstotakeaphotoofacontiguousintervalofcowsforthecountyfair,butw...
02015年1月5日2,859模拟