• 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,319矩阵乘法
  • 【cf261X】Codeforces Round #160 (Div. 1)

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

    A.MaximandDiscounts挑要求最小的优惠方案啦,最贵的那几个显然要花钱买,赠品当然也是选最贵的。。。恩变成了子问题[crayon-58d367c1b092a829063893/]B.MaximandRestaurantf(i,j,k)表示前i个人,选了j个,消耗为k的方案数然后枚举选的人数+组合数学,注意不重复统计答案[crayon-58d367c1b0933489101317/]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-58d367c1b115c769709479/]B.Shifting发现可以用队列来模拟。。。具体看代码[crayon-58d367c1b1164077256513/]C.MainSequence从后往前贪心,尽量放左括号[crayon-58d367c1b1168575231230/]D.Tourists先把线段剖成一些不相交的区间(可以用set或者线段树)第二部英文题解讲的很清楚。。。大概就是,对于每个区间,出发时间在ti-ri之前是...

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

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

    A.LevkoandArrayRecovery求出每个位置初始值的最大值,然后check一下[crayon-58d367c1b193f751063532/]B.LevkoandArray二分答案,f(i)表示前i个的最小修改次数,且i不修改,枚举上一个不修改的位置转移[crayon-58d367c1b1949122777194/]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-58d367c1b20d3147688651/]B.Palindromef(i,j)表示末尾在i之前,长度为j的回文序列的最大头位置[crayon-58d367c1b20dc604500888/]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-58d367c1b288f236098556/]B.Ants蚂蚁的活动范围不太大,所以依然是暴力QAQ[crayon-58d367c1b2898800594274/]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-58d367c1b2fef267111451/]B.ZgukistringZ统计每个串每个字母的使用次数,枚举串b出现次数,计算c最大出现次数,更新答案我不知道为什么写太挫还能T[crayon-58d367c1b2ff9506727088/]C.GukiZhatesBoxes感受一下可以发现,比较远的箱子堆去的人越少越好所以二分答案后,从后往前贪心check即可[crayon-58d367c1b2fff316148589/]D.GukiZandBinaryOperations按位考虑,给定K以后,每一位...

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

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

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

  • 【cf293X】Croc Champ 2013 – Round 2

    【cf293X】Croc Champ 2013 - Round 2

    A.WeirdGame两个人都应该采取贪心策略根据规则,先取0而对方不取0则败,所以有1则取1,当然尽量取对方也是1的那些取0的时候同理,尽量取对方是1的那些我们模拟游戏进程得出两个人的最终序列比较即可[crayon-58d367c1c6181027626762/]B.DistinctPaths容易发现,n+m-1>K时是无解的,那么有解的棋盘就很小了,状压使用的颜色+dfs然而这样的状态还是太多,我们发现dfs到一个格子的时候,所有未在棋盘上出现的颜色并无差别,所...

  • pkusc 2014 #2

    pkusc 2014 #2

    A:QuadTiling对于某一层来说,状态只有6种,所以手推下转移方程,矩阵乘法加速即可[crayon-58d367c1bb21b575115962/]B:Garden傻逼线段树[crayon-58d367c1bb226839398790/]D:One-movecheckmate枚举一下皇后能一步到达的位置,然后判一下是否将死注意细节较多具体见discuss[crayon-58d367c1bb231422600507/]E:ATP二分答案后,从比赛最后阶段往前考虑当然是每场给每个人分配一个可以打败的最NB的人。。。贪心判解的可行性...

  • 【cf546X】Codeforces Round #304 (Div. 2)

    【cf546X】Codeforces Round #304 (Div. 2)

    A.SoldierandBananas模拟[crayon-58d367c1c6a08396159727/]B.SoldierandBadges排序[crayon-58d367c1c6a10862507268/]C.SoldierandCards暴力模拟个一百万次。。。[crayon-58d367c1c6a14207472698/]D.SoldierandNumberGame用筛法得出每个数质因子个数前缀和即可[crayon-58d367c1c6a18153060170/]E.SoldierandTraveling我比较愚蠢写了网络流。。正解是什么我不知道[crayon-58d367c1c6a1d382417762/] ...

    52015年5月23日1,156模拟,筛法,网络流
  • pkusc 2013 #2

    pkusc 2013 #2

    A:TheSettlersofCatan枚举起点dfs[crayon-58d367c1c72e3150246723/]B:Nim傻逼记忆化搜索我竟然清空错数组QAQ[crayon-58d367c1c72ee818317979/]C:TraditionalBINGO纯阅读题[crayon-58d367c1c72f2345872420/]D:TraditionalBINGO排序后广搜更新每个点能到达的最高点。。。一通乱搞感觉并查集也可以就是很麻烦?[crayon-58d367c1c72f8609181593/] ...

  • poj训练记录4

    poj训练记录4

    1694.AnOldStoneGamef[x]表示x为根的树至少需要的石头,把子树按f排序后贪心即可[crayon-58d367c1c77c1286719095/]poj1738.AnoldStoneGame参见discuss的神算法,据说是knuth提出的?[crayon-58d367c1c77cc730807952/]1737.ConnectedGraph跪大爷http://blog.csdn.net/PoPoQQQ/article/details/43525019[crayon-58d367c1c77d2777788810/]1742.Coins二进制拆分+bitset竟然过不了...我被题解骗了突然一想这不是以前做过...