• 【小奇模拟赛】[bzoj3576]小奇的博弈2

    【小奇模拟赛】[bzoj3576]小奇的博弈2

    【题目背景】小奇和提比开脑洞又发明了新的游戏。【问题描述】给定一个数字F,游戏系统产生T组游戏。每组游戏包括n堆糖果,小奇和提比轮流操作。每次操作时,一方将某一堆数量不小于F的糖果分成M堆(M>=2且每次可以不同),要满足M堆中任意两堆糖果的差值不超过1,且不存在空堆。若一方不能操作,它就输了。假设提比和小奇都非常机智,小奇先手,请你预测一下游戏的结果。【输入格式】第一行有2个整数T,F接下来T行,每...

    02016年5月21日1,637博弈论,记忆化搜索
  • 【cf623X】AIM Tech Round (Div. 1)

    【cf623X】AIM Tech Round (Div. 1)

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

  • 【省选模拟赛】[hdu5171]小奇的集合

    【省选模拟赛】[hdu5171]小奇的集合

    注:原题没有考虑最大值为负数的情况【题目背景】小奇总是在数学课上思考奇怪的问题。【问题描述】有一个大小为n的可重集S,小奇每次操作可以加入一个数a+b(a,b均属于S),求k次操作后它可获得的S的和的最大值。(数据保证这个值为非负数)【输入格式】第一行有两个整数n,k表示初始元素数量和操作数,第二行包含n个整数表示初始时可重集的元素。【输出格式】输出一个整数,表示和的最大值。答案对10000007取模。【样例输入】2236...

    02015年11月22日1,675递推与动规,矩阵乘法
  • 【bzoj4173】数学

    【bzoj4173】数学

    Description Input 输入文件的第一行输入两个正整数。Output 如题SampleInput56SampleOutput240HINT N,M<=10^15题解贴个大爷的式子:http://blog.csdn.net/popoqqq/article/details/46820313[crayon-5a2facadcce45999834144/] ...

    32015年7月14日2,718欧拉函数
  • 【FJ2015集训】热身题

    【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日2,349快速幂,高斯消元,乘法逆元
  • NOI2013矩阵游戏

    NOI2013矩阵游戏

    Description婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的n行m列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质:若用F[i][j]来表示矩阵中第i行第j列的元素,则F[i][j]满足下面的递推式:F[1][1]=1F[i,j]=a*F[i][j-1]+b(j!=1)F[i,1]=c*F[i-1][m]+d(i!=1)递推式中a,b,c,d都是给定的常数。现在婷婷想知道F[n][m]的值是多少,请你帮助她。由于最终结果可能很大,你只需要输出F[n][m]除以1,00...

    52015年6月30日1,993矩阵乘法
  • 【cf261X】Codeforces Round #160 (Div. 1)

    【cf261X】Codeforces Round #160 (Div. 1)

    A.MaximandDiscounts挑要求最小的优惠方案啦,最贵的那几个显然要花钱买,赠品当然也是选最贵的。。。恩变成了子问题[crayon-5a2facadced87476952284/]B.MaximandRestaurantf(i,j,k)表示前i个人,选了j个,消耗为k的方案数然后枚举选的人数+组合数学,注意不重复统计答案[crayon-5a2facadced97543696964/]C.MaximandMatrix发现第m+1行的和就是2^(m二进制1的个数+1)则t是2的幂次才有解,求<=n的ans数量从大到小枚举每一...

  • 【cf286X】Codeforces Round #176 (Div. 1)

    【cf286X】Codeforces Round #176 (Div. 1)

    A.LuckyPermutation在第一位放一个2之后,可以得到12nn-1所以可以四个四个构造[crayon-5a2facae00e28142659749/]B.Shifting发现可以用队列来模拟。。。具体看代码[crayon-5a2facae00e3b344452066/]C.MainSequence从后往前贪心,尽量放左括号[crayon-5a2facae00e42241103423/]D.Tourists先把线段剖成一些不相交的区间(可以用set或者线段树)第二部英文题解讲的很清楚。。。大概就是,对于每个区间,出发时间在ti-ri之前是...

    22015年6月24日1,576STL,贪心,构造,调和级数
  • 【cf360X】Codeforces Round #210 (Div. 1)

    【cf360X】Codeforces Round #210 (Div. 1)

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

  • 【cf335X】MemSQL start[c]up Round 2 – online version

    【cf335X】MemSQL start[c]up Round 2 - online version

    A.Banana枚举sheet数,找到第一个不能用已有sticker凑出的[crayon-5a2facaddd2f3685056883/]B.Palindromef(i,j)表示末尾在i之前,长度为j的回文序列的最大头位置[crayon-5a2facaddd304007017541/]C.MoreReclamation用(len,x,y)表示一个游戏状态,2*len的完整格子,左端的状态为x,右端的状态为yx,y=0/1/2分别表示(完整),(左侧/右侧第一行第一格不可删),(左侧/右侧第二行第一格不可删)边界情况:len=0时sg值为0len=...

  • 【cf317X】Codeforces Round #188 (Div. 1)

    【cf317X】Codeforces Round #188 (Div. 1)

    A.PerfectPair每次把小的那个变成两个的和,注意考虑负数[crayon-5a2facae02994122815703/]B.Ants蚂蚁的活动范围不太大,所以依然是暴力QAQ[crayon-5a2facae029a3498107607/]C.Balance每次从缺水的地方出发,找一条能送水过来的路径a->b,要保证a是路径上符合要求的第一个容器运送量\(d=min(b_b-a_b,a_a-b_a)\),找n次若没有容量限制,每次从b到a扫,找当前水量超过d的往b方向运由于有容量限制,把d拆成d/2和d-d/2分两...

  • 【cf551X】Codeforces Round #307 (Div. 2)

    【cf551X】Codeforces Round #307 (Div. 2)

    A.GukiZandContest排序[crayon-5a2facae03a78001313486/]B.ZgukistringZ统计每个串每个字母的使用次数,枚举串b出现次数,计算c最大出现次数,更新答案我不知道为什么写太挫还能T[crayon-5a2facae03a89199370124/]C.GukiZhatesBoxes感受一下可以发现,比较远的箱子堆去的人越少越好所以二分答案后,从后往前贪心check即可[crayon-5a2facae03a94919713109/]D.GukiZandBinaryOperations按位考虑,给定K以后,每一位...

  • 【cf235X】Codeforces Round #146 (Div. 1)

    【cf235X】Codeforces Round #146 (Div. 1)

    A.LCMChallenge显然是在接近n数内找三个两两互质的,由于懒得推公式所以可以小范围暴力一下[crayon-5a2facadddf29224017737/]B.Let'sPlayOsu!计算出到每个位置的期望连续长度就可以得到如果该位置正确的期望得分,就可以dp辣[crayon-5a2facadddf39141932597/]C.CyclicalQuest一道很正经的后缀自动机建出s串的后缀自动机把xi复制一遍接在后面,然后在s串上匹配,就可以得出后缀自动机上贡献答案的结点[crayon-5a2facadd...