• 【省选模拟赛】小奇挖矿 3

    【省选模拟赛】小奇挖矿 3

    原题:【泉七培训-刘定峰】物流【题目背景】小奇在喵星系使用了无限非概率驱动的采矿机,以至于在所有星球上都采出了一些矿石,现在它准备建一些矿石仓库并把矿石运到各个仓库里。【问题描述】喵星系有n个星球,标号为1到n,星球以及星球间的航线形成一棵树。所有星球间的双向航线的长度都为1。小奇要在若干个星球建矿石仓库,设立每个仓库的费用为K。对于未设立矿石仓库的星球,设其到一个仓库的距离为i,则将矿石运回的费用为D...

  • 【NOIP模拟赛】[hdu5492]小奇的矩阵

    【NOIP模拟赛】[hdu5492]小奇的矩阵

    【题目背景】小奇总是在数学课上思考奇怪的问题。【问题描述】给定一个n*m的矩阵,矩阵中的每个元素aij为正整数。接下来规定1.合法的路径初始从矩阵左上角出发,每次只能向右或向下走,终点为右下角。2.路径经过的n+m-1个格子中的元素为A1,A2…A(n+m-1),Aavg为Ai的平均数,路径的V值为(n+m-1)*∑(Ai-Aavg)^2(1<=i<=n+m-1)求V值最小的合法路径,输出V值即可,有多组测试数据。【输入格式】第一行包含一个正整数T,...

    62015年10月5日1,270递推与动规,深度搜索
  • 【bzoj4207】【FJ2015集训】Can’t Stop

    【bzoj4207】【FJ2015集训】Can't Stop

    【题目描述】这个问题是源于一个在棋盘上玩的,由SidSackson设计的名叫Can'tstop的游戏的。这个问题与Can'tstop有一定的相似之处,但是不需要玩过Can'tstop。你在玩一个(非常大型的)棋盘游戏。在这个游戏里面,给出了一个长度为N的rollset的序列。每个rollset包括D个dieroll,每个dieroll是一个正整数。你需要找到序列中总长度最大的极好的区间。区间即为连续的一段rollset。如果存在k个数使某个区间内的所有rollset都至少...

    32015年7月6日1,056深度搜索
  • NOI2008假面舞会

    NOI2008假面舞会

    Description一年一度的假面舞会又开始了,栋栋也兴致勃勃的参加了今年的舞会。今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一个自己喜欢的面具。每个面具都有一个编号,主办方会把此编号告诉拿该面具的人。为了使舞会更有神秘感,主办方把面具分为k(k≥3)类,并使用特殊的技术将每个面具的编号标在了面具上,只有戴第i类面具的人才能看到戴第i+1类面具的人的编号,戴第k类面具的人能看到戴第1类面具的人的...

    22015年6月29日1,438深度搜索,并查集
  • 【cf261X】Codeforces Round #160 (Div. 1)

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

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

  • 【cf339X】Codeforces Round #197 (Div. 2)

    【cf339X】Codeforces Round #197 (Div. 2)

    A.HelpfulMaths排序[crayon-58d3667149771848965228/]B.XeniaandRingroad题意即题解[crayon-58d366714977a724794958/]C.XeniaandWeights搜索可过[crayon-58d366714977e905875949/]D.XeniaandBitOperations线段树模拟每次询问可以自底向上修改[crayon-58d3667149782781211487/]E.ThreeSwaps由于只有三次交换,所以数列最多被分成七段找到所有断点爆搜[crayon-58d3667149787837485829/]  ...

    12015年6月23日953模拟,深度搜索,线段树
  • 【cf317X】Codeforces Round #188 (Div. 1)

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

    A.PerfectPair每次把小的那个变成两个的和,注意考虑负数[crayon-58d3667149f18332280538/]B.Ants蚂蚁的活动范围不太大,所以依然是暴力QAQ[crayon-58d3667149f21511246384/]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分两...

  • 【cf241X】Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements)

    【cf241X】Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements)

    A.OldPeykan贪心,如果到某个城市油不够的话,说明一定要在之前的某个城市加油,当然是选它们之中c最大的啦[crayon-58d366715e577501747691/]B.Friends这种问题显然按位考虑,排序+乱搞。。。考虑到每一位时,对于前缀二进制相同的一段可以找到匹配的另一段,然后求两段之内两两xor和什么的看了半天卓神代码似懂非懂。。。[crayon-58d366715e582571445920/]C.MirrorBox枚举碰撞次数之后模拟[crayon-58d366715e587533008566...

    22015年6月19日1,184模拟,深度搜索,差分约束
  • 【cf325X】MemSQL start[c]up Round 1

    【cf325X】MemSQL start[c]up Round 1

    A.SquareandRectangles模拟题[crayon-58d366715ef67195866758/]B.StadiumandGames\[(2^k-1)m+m(m-1)/2=n\]枚举k二分得出m[crayon-58d366715ef70161344134/]C.MonstersandDiamonds此题比较恶心QAQ求最短用个类似dijkstra的东西,如果一种u->{v}的转移所有mn[v]都确定了,把这个转移放进堆或者是某个转移的代价被更新了求最长用记忆化搜索,走出环就是inf[crayon-58d366715ef75311850438/]D.Reclamation把图扩展成r...

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

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

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

  • 【cf293X】Croc Champ 2013 – Round 2

    【cf293X】Croc Champ 2013 - Round 2

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

  • 【cf263X】Codeforces Round #161 (Div. 2)

    【cf263X】Codeforces Round #161 (Div. 2)

    A.BeautifulMatrix模拟,求到中点的曼哈顿距离[crayon-58d36671600ea397725901/]B.Squares排序一下判断即可[crayon-58d36671600f6564481362/]C.CircleofNumbers如果一个点与俩个点都有连边,则它在这两个点的一侧所以dfs依次确定一下即可[crayon-58d36671600ff511546519/]D.CycleinGraph感受了一下,觉得随便从一个点开始深搜即可。。。找出过这个点的所有环判断一下[crayon-58d3667160109581801154/]E.Rhombus其实是...

    02015年6月5日897模拟,贪心,深度搜索
  • usaco 刷水。。。

    usaco 刷水。。。

    2017:[Usaco2009Nov]硬币游戏f(i,j)表示考虑最后i枚,前一次对手取j枚,自己的最大获益[crayon-58d36671605f0119865314/][Usaco2005Feb]RiggingtheBovineElection竞选划区爱怎么暴力怎么暴力[crayon-58d3667160613891316196/]1661:[Usaco2006Nov]BigSquare巨大正方形狗眼瞎了wa了n发。。。枚举一条边暴力即可[crayon-58d366716061a406030884/]1654:[Usaco2006Jan]TheCowProm奶牛舞会有向图强连通分量。。。[crayon...