• 「CF1242X」Codeforces Round #599 (Div. 1)

    「CF1242X」Codeforces Round #599 (Div. 1)

    A.TilePainting对n做因式分解,如果n有超过一个质因数t,则答案是1,否则答案是t。因为两个质因数求gcd以后是1,则ax+by可以把所有格子染上。[crayon-67020edee7cdf789228067/]B.0-1MST求补图的联通块个数,BZOJ1098原题。维护一个1-n的链表,表示有哪些点还没确定所在连通块。从1-n枚举点x,用bfs把与x同一连通块的点找出来,每次bfs只需要考虑还在链表里的点,这样每一条边要不然在原图中,要不然不在原图中使得某个点...

  • 「CF1229X」Codeforces Round #588

    「CF1229X」Codeforces Round #588

    A.MarcinandTrainingCamp若A觉得自己没有B强,B向A连边度数为0的点,是觉得自己比其它人都强的,把它们依此拓扑排序删除[crayon-67020edee8d4e166183760/]B.KamilandMakingaStream从一个点向上走,区间gcd单调下降,且最多变化log次可以用树上倍增维护区间gcd,枚举每个点往上二分跳,暴力统计答案更简单的做法是用vector维护一个点往上的不同gcd,以及它们贡献答案的次数,这个vector大小是logdfs暴力往儿子转移倍增:...

  • 「CF1220X」Codeforces Round #586

    「CF1220X」Codeforces Round #586

    A.Cards统计一下z和o的个数[crayon-67020edee928c607238551/]B.MultiplicationTable取第一行的gcd,则a1一定是gcd的约数再取一个M23,确定一下a1[crayon-67020edee9296212024159/]C.SubstringGameintheLesson先手可以直接转移到左边的最小字符[crayon-67020edee929b746106734/]D.AlexandJulian按每个数的2的因子数分类,只有2的因子数相同的才能共存选择最多数的一类[crayon-67020edee929f865990608/]E.Tourism按起...

  • 「CF685X」Codeforces Round #360 (Div. 1)

    「CF685X」Codeforces Round #360 (Div. 1)

    A.NP-HardProblem二分图染色[crayon-67020edee974d100465982/]B.RemaindersGame将K分解为a1^p1*a2^p2...an^pn则ai^pi要被c中的某个数整除[crayon-67020edee9757353726556/]C.TheValuesYouCanMake用f(i,j)表示容量i和j的背包能不能同时取得若f(x,K-x)则可以用K中的物品凑出X[crayon-67020edee975b183813036/] ...

  • 「CF623X」AIM Tech Round (Div. 1)

    「CF623X」AIM Tech Round (Div. 1)

    A.GraphandString题意n个点,每个点有a,b,c其中一种颜色,若两个点颜色的字母相邻则它们之间连边。给出图的连边情况,求一种可行的染色方案。题解如果有一个点和其它点都有连边,将其标号b。然后选择一个未被标号的点,标号为a,二分图染色。最后验证一下即可。[crayon-67020edee9b8b935108544/]B.ArrayGCD题意给定长为n的数列和两个操作,每个操作用一次1.移除数列的一个子串,代价是长度*a2.对于一些数字+1或者-1,每个数...

  • 「CF360X」Codeforces Round #210 (Div. 1)

    「CF360X」Codeforces Round #210 (Div. 1)

    A.LevkoandArrayRecovery求出每个位置初始值的最大值,然后check一下[crayon-67020edee9fed579118123/]B.LevkoandArray二分答案,f(i)表示前i个的最小修改次数,且i不修改,枚举上一个不修改的位置转移[crayon-67020edee9ff9877252260/]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

    UOJ Round #3

    http://vfleaking.blog.uoj.ac/blog/43「UR#3」核聚变反应强度[crayon-67020edeea7d7301003163/]「UR#3」铀仓库[crayon-67020edeea7e0636546559/]「UR#3」链式反应题目都不敢看。。。

  • 「topcoder」Single Round Match 652 – Round 1 Div2

    「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

    「codechef」February Lunchtime 2015

    懒得开多篇了LuckyFour 这题在逗我么[crayon-67020edeeb343252709815/]TheWarehouse发现实际上把一个东西移动到一个位置相当于不断做代价为1的交换所以只要枚举给3种字母赋权,求逆序对最小值即可[crayon-67020edeeb34b264223736/]Heavy-lightDecompositions设f[i][j]表示i为根的子树,后代到i经过轻边数量不超过j树形dp,要用到前缀后缀积/逆元。。。[crayon-67020edeeb352323438506/]  TheFirstCube 一眼分...

  • 「CF364D」Ghd

    「CF364D」Ghd

    JohnDoeofferedhissisterJaneDoefindthegcdofsomesetofnumbersa.Gcdisapositiveintegerg,suchthatallnumberfromthesetareevenlydivisiblebygandthereisn'tsuchg'(g' > g),thatallnumbersofthesetareevenlydivisiblebyg'.UnfortunatelyJanecouldn'tcopewiththetaskandJohnofferedhertofindtheghdofthesamesubsetofnumbers.Ghdisapositiveintegerg,suchthatatleasthalfofnumbersfromthesetareevenlydivisiblebygandthe...

  • 「codechef」January Challenge 2015

    「codechef」January Challenge 2015

    CHEFSTON[crayon-67020edf07bb1385393475/]GCDQgcd满足区间加法TAT,所以维护前缀和后缀和就好了[crayon-67020edf07bbb462858099/]SEAVOTE去掉所有0后若∑bi<tot或∑bi>=100+n则无解否则有解[crayon-67020edf07bc0162754376/]ONEKING按照右端点排序,选择第一个的右端点,删去覆盖其的线段。。。剩下的线段同理[crayon-67020edf07bc4856411751/]CLPERM答案根据第一个不能合成的数奇偶性得...

  • 「BZOJ2299」[HAOI2011] 向量

    「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,612最大公约数与最小公倍数
1 / 2 1 2 下一页 »