最大公约数与最小公倍数

「CF1242X」Codeforces Round #599 (Div. 1)
A.TilePainting对n做因式分解，如果n有超过一个质因数t，则答案是1，否则答案是t。因为两个质因数求gcd以后是1，则ax+by可以把所有格子染上。[crayon-696700813eef7370634085/]B.0-1MST求补图的联通块个数，BZOJ1098原题。维护一个1-n的链表，表示有哪些点还没确定所在连通块。从1-n枚举点x，用bfs把与x同一连通块的点找出来，每次bfs只需要考虑还在链表里的点，这样每一条边要不然在原图中，要不然不在原图中使得某个点...
02019年11月8日4,692广度搜索,状压动规,最大公约数与最小公倍数

「CF1229X」Codeforces Round #588
A.MarcinandTrainingCamp若A觉得自己没有B强，B向A连边度数为0的点，是觉得自己比其它人都强的，把它们依此拓扑排序删除[crayon-6967008140ba2736784179/]B.KamilandMakingaStream从一个点向上走，区间gcd单调下降，且最多变化log次可以用树上倍增维护区间gcd，枚举每个点往上二分跳，暴力统计答案更简单的做法是用vector维护一个点往上的不同gcd，以及它们贡献答案的次数，这个vector大小是logdfs暴力往儿子转移倍增：...
02019年10月3日4,706树上倍增,拓扑排序,最大公约数与最小公倍数
「CF1220X」Codeforces Round #586
A.Cards统计一下z和o的个数[crayon-6967008141460873143435/]B.MultiplicationTable取第一行的gcd，则a1一定是gcd的约数再取一个M23，确定一下a1[crayon-696700814146f091018671/]C.SubstringGameintheLesson先手可以直接转移到左边的最小字符[crayon-6967008141479643677315/]D.AlexandJulian按每个数的2的因子数分类，只有2的因子数相同的才能共存选择最多数的一类[crayon-6967008141480459139363/]E.Tourism按起...
02019年9月24日4,339贪心,树形动规,博弈论,最大公约数与最小公倍数
「CF685X」Codeforces Round #360 (Div. 1)
A.NP-HardProblem二分图染色[crayon-6967008141b89348974319/]B.RemaindersGame将K分解为a1^p1*a2^p2...an^pn则ai^pi要被c中的某个数整除[crayon-6967008141b9a050603661/]C.TheValuesYouCanMake用f(i,j)表示容量i和j的背包能不能同时取得若f(x,K-x)则可以用K中的物品凑出X[crayon-6967008141ba3489555998/] ...
02016年6月30日2,461背包动规,二分图染色,最大公约数与最小公倍数
「CF623X」AIM Tech Round (Div. 1)
A.GraphandString题意n个点，每个点有a,b,c其中一种颜色，若两个点颜色的字母相邻则它们之间连边。给出图的连边情况，求一种可行的染色方案。题解如果有一个点和其它点都有连边，将其标号b。然后选择一个未被标号的点，标号为a，二分图染色。最后验证一下即可。[crayon-6967008142230661525807/]B.ArrayGCD题意给定长为n的数列和两个操作，每个操作用一次1.移除数列的一个子串，代价是长度*a2.对于一些数字+1或者-1，每个数...
02016年3月6日5,007构造,二分图染色,最大公约数与最小公倍数
「CF360X」Codeforces Round #210 (Div. 1)
A.LevkoandArrayRecovery求出每个位置初始值的最大值，然后check一下[crayon-69670081429b0262612942/]B.LevkoandArray二分答案，f(i)表示前i个的最小修改次数，且i不修改，枚举上一个不修改的位置转移[crayon-69670081429c2398301576/]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...
12015年6月23日5,789递推与动规,spfa,贪心,二分法,最大公约数与最小公倍数
UOJ Round #3
http://vfleaking.blog.uoj.ac/blog/43「UR#3」核聚变反应强度[crayon-6967008143561710542835/]「UR#3」铀仓库[crayon-696700814356b553531419/]「UR#3」链式反应题目都不敢看。。。
02015年4月19日3,160二分法,最大公约数与最小公倍数
「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...
12015年3月10日4,839模拟,凸包,最大公约数与最小公倍数
「codechef」February Lunchtime 2015
懒得开多篇了LuckyFour 这题在逗我么[crayon-696700814454a832945704/]TheWarehouse发现实际上把一个东西移动到一个位置相当于不断做代价为1的交换所以只要枚举给3种字母赋权，求逆序对最小值即可[crayon-6967008144557067684240/]Heavy-lightDecompositions设f[i][j]表示i为根的子树，后代到i经过轻边数量不超过j树形dp，要用到前缀后缀积/逆元。。。[crayon-6967008144563223508442/] TheFirstCube 一眼分...
02015年2月23日3,983模拟,树形动规,素数测试,最大公约数与最小公倍数
「CF364D」Ghd
JohnDoeofferedhissisterJaneDoefindthegcdofsomesetofnumbersa.Gcdisapositiveintegerg,suchthatallnumberfromthesetareevenlydivisiblebygandthereisn'tsuchg'(g' > g),thatallnumbersofthesetareevenlydivisiblebyg'.UnfortunatelyJanecouldn'tcopewiththetaskandJohnofferedhertofindtheghdofthesamesubsetofnumbers.Ghdisapositiveintegerg,suchthatatleasthalfofnumbersfromthesetareevenlydivisiblebygandthe...
02015年1月20日4,116随机化,最大公约数与最小公倍数
「codechef」January Challenge 2015
CHEFSTON[crayon-696700815b615964679585/]GCDQgcd满足区间加法TAT，所以维护前缀和后缀和就好了[crayon-696700815b623795478212/]SEAVOTE去掉所有0后若∑bi<tot或∑bi>=100+n则无解否则有解[crayon-696700815b62e477180653/]ONEKING按照右端点排序，选择第一个的右端点，删去覆盖其的线段。。。剩下的线段同理[crayon-696700815b636094903081/]CLPERM答案根据第一个不能合成的数奇偶性得...
02015年1月12日7,276模拟,贪心,构造,数学,快速幂,随机化,容斥原理,最大公约数与最小公倍数
「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注意...
22014年12月17日4,958最大公约数与最小公倍数