下一页 »Current position : 首页 >> 最大公约数与最小公倍数
「CF1242X」Codeforces Round #599 (Div. 1)
A.TilePainting对n做因式分解，如果n有超过一个质因数t，则答案是1，否则答案是t。因为两个质因数求gcd以后是1，则ax+by可以把所有格子染上。[crayon-673fb4814b132889124499/]B.0-1MST求补图的联通块个数，BZOJ1098原题。维护一个1-n的链表，表示有哪些点还没确定所在连通块。从1-n枚举点x，用bfs把与x同一连通块的点找出来，每次bfs只需要考虑还在链表里的点，这样每一条边要不然在原图中，要不然不在原图中使得某个点...
「CF1229X」Codeforces Round #588
A.MarcinandTrainingCamp若A觉得自己没有B强，B向A连边度数为0的点，是觉得自己比其它人都强的，把它们依此拓扑排序删除[crayon-673fb4814c18f806155616/]B.KamilandMakingaStream从一个点向上走，区间gcd单调下降，且最多变化log次可以用树上倍增维护区间gcd，枚举每个点往上二分跳，暴力统计答案更简单的做法是用vector维护一个点往上的不同gcd，以及它们贡献答案的次数，这个vector大小是logdfs暴力往儿子转移倍增：...
「CF1220X」Codeforces Round #586
A.Cards统计一下z和o的个数[crayon-673fb4814c6b3371800601/]B.MultiplicationTable取第一行的gcd，则a1一定是gcd的约数再取一个M23，确定一下a1[crayon-673fb4814c6bd232359880/]C.SubstringGameintheLesson先手可以直接转移到左边的最小字符[crayon-673fb4814c6c2202369009/]D.AlexandJulian按每个数的2的因子数分类，只有2的因子数相同的才能共存选择最多数的一类[crayon-673fb4814c6c6213987051/]E.Tourism按起...
「CF685X」Codeforces Round #360 (Div. 1)
A.NP-HardProblem二分图染色[crayon-673fb4814cb8f218796894/]B.RemaindersGame将K分解为a1^p1*a2^p2...an^pn则ai^pi要被c中的某个数整除[crayon-673fb4814cb9f688267053/]C.TheValuesYouCanMake用f(i,j)表示容量i和j的背包能不能同时取得若f(x,K-x)则可以用K中的物品凑出X[crayon-673fb4814cba6008254066/] ...
「CF623X」AIM Tech Round (Div. 1)
A.GraphandString题意n个点，每个点有a,b,c其中一种颜色，若两个点颜色的字母相邻则它们之间连边。给出图的连边情况，求一种可行的染色方案。题解如果有一个点和其它点都有连边，将其标号b。然后选择一个未被标号的点，标号为a，二分图染色。最后验证一下即可。[crayon-673fb4814d040936208329/]B.ArrayGCD题意给定长为n的数列和两个操作，每个操作用一次1.移除数列的一个子串，代价是长度*a2.对于一些数字+1或者-1，每个数...
「CF360X」Codeforces Round #210 (Div. 1)
A.LevkoandArrayRecovery求出每个位置初始值的最大值，然后check一下[crayon-673fb4814d50e146420890/]B.LevkoandArray二分答案，f(i)表示前i个的最小修改次数，且i不修改，枚举上一个不修改的位置转移[crayon-673fb4814d51a048629618/]C.LevkoandStringsf(i,j)表示前i个字母，beauty值为j的合法方案，\(t_k=s_k\)(k>j)1.在第i位放一个比s[i]大的字母，枚举上一个位置i-k-1满足\(s_{i-k-1}!=t_{i-k-1}\)产生的新的bea...
UOJ Round #3
http://vfleaking.blog.uoj.ac/blog/43「UR#3」核聚变反应强度[crayon-673fb4814dc9b217454978/]「UR#3」铀仓库[crayon-673fb4814dca5576209880/]「UR#3」链式反应题目都不敢看。。。
「topcoder」Single Round Match 652 – Round 1 Div2
topcoder怎么会把客户端做成这样差评第一场只能打div2TAT250Youaregivenastringsconsistingoflowercaseletters.Weassigntheletters'a'to'z'valuesof1to26,respectively.WewilldenotethevalueassignedtotheletterXbyval[X].Forexample,val['a']=1andval['e']=5.Wedefinethevalueofthestringsasfollows.Foreachletters[i],letk[i]bethenumberoflettersinsthatarelessthanorequaltos[i],includings[i]itself.Then,thevalu...
「codechef」February Lunchtime 2015
懒得开多篇了LuckyFour 这题在逗我么[crayon-673fb4814e762551864874/]TheWarehouse发现实际上把一个东西移动到一个位置相当于不断做代价为1的交换所以只要枚举给3种字母赋权，求逆序对最小值即可[crayon-673fb4814e76c841348350/]Heavy-lightDecompositions设f[i][j]表示i为根的子树，后代到i经过轻边数量不超过j树形dp，要用到前缀后缀积/逆元。。。[crayon-673fb4814e772639674850/] TheFirstCube 一眼分...
「CF364D」Ghd
JohnDoeofferedhissisterJaneDoefindthegcdofsomesetofnumbersa.Gcdisapositiveintegerg,suchthatallnumberfromthesetareevenlydivisiblebygandthereisn'tsuchg'(g' > g),thatallnumbersofthesetareevenlydivisiblebyg'.UnfortunatelyJanecouldn'tcopewiththetaskandJohnofferedhertofindtheghdofthesamesubsetofnumbers.Ghdisapositiveintegerg,suchthatatleasthalfofnumbersfromthesetareevenlydivisiblebygandthe...
「codechef」January Challenge 2015
CHEFSTON[crayon-673fb4815da4d797535461/]GCDQgcd满足区间加法TAT，所以维护前缀和后缀和就好了[crayon-673fb4815da57024755103/]SEAVOTE去掉所有0后若∑bi<tot或∑bi>=100+n则无解否则有解[crayon-673fb4815da5c317948322/]ONEKING按照右端点排序，选择第一个的右端点，删去覆盖其的线段。。。剩下的线段同理[crayon-673fb4815da60589658621/]CLPERM答案根据第一个不能合成的数奇偶性得...
「BZOJ2299」[HAOI2011] 向量
Description给你一对数a,b，你可以任意使用(a,b),(a,-b),(-a,b),(-a,-b),(b,a),(b,-a),(-b,a),(-b,-a)这些向量，问你能不能拼出另一个向量(x,y)。说明：这里的拼就是使得你选出的向量之和为(x,y)Input第一行数组组数t，(t<=50000)接下来t行每行四个整数a,b,x,y (-2*109<=a,b,x,y<=2*109)Outputt行每行为Y或者为N，分别表示可以拼出来，不能拼出来SampleInput32133110110-23SampleOutputYNY题解orzwulala注意...
OI 课件=>
近期评论