• 【省选模拟赛】小奇的花园

    【省选模拟赛】小奇的花园

    原题:【泉七培训-刘定峰】花园【题目背景】小奇在家中的花园漫步时,总是会思考一些奇怪的问题。【问题描述】小奇的花园有n个温室,标号为1到n,温室以及以及温室间的双向道路形成一棵树。每个温室都种植着一种花,随着季节的变换,温室里的花的种类也在不断发生着变化。小奇想知道从温室x走到温室y的路径中(包括两个端点),第t种花出现的次数。【输入格式】第一行为两个整数n,q,表示温室的数目和操作的数目。第二行有n个整数T1...

    32015年12月19日4,204STL,树套树,treap,线段树,树链剖分
  • 【省选模拟赛】[bzoj1556]小奇走迷宫

    【省选模拟赛】[bzoj1556]小奇走迷宫

    原题:【bzoj1556】墓地秘密【题目背景】小奇驾驶G-1500机器人探险时落入了一个有魔法的迷宫,一旁的木牌上写着:“你可以回头,但你永远无法离去。”【问题描述】木牌下方有一行小字:“撞击所有机关墙”。G-1500机器人每次可以朝着前方光速移动,质量、动能无穷大,可以选择自己在行进中停下来或者撞墙后停下来,移动时只有转向需要花费时间。真是个诡异的迷宫,不过,小奇的眼前已经出现了迷宫的地图,它想尽早离开这里,请你...

    22015年12月19日2,821spfa,状压动规
  • 【FJ2015集训】贪吃蛇

    【FJ2015集训】贪吃蛇

    最近lwher迷上了贪吃蛇游戏,在玩了几天却从未占满全地图的情况下,他不得不承认自己是一个弱菜,只能改去开发一款更弱的贪吃蛇游戏。在开发的过程中,lwher脑洞大开,搞了一个多条蛇的模式。但由于这种模式太难操作,于是他只好改变游戏的玩法,稍微变化一下游戏目标。新的游戏是这样的:一些蛇覆盖了一个网格。每个格子要么是一个障碍物,要么是蛇的一部分。每条蛇占据了一条折线(拐角处只能水平和竖直连接),且只是占据两个格子...

  • 【bzoj4205】【FJ2015集训】卡牌配对

    【bzoj4205】【FJ2015集训】卡牌配对

    卡牌配对【问题描述】现在有一种卡牌游戏,每张卡牌上有三个属性值:A,B,C。把卡牌分为X,Y两类,分别有n1,n2张。两张卡牌能够配对,当且仅当,存在至多一项属性值使得两张卡牌该项属性值互质,且两张卡牌类别不同。比如一张X类卡牌属性值分别是225,233,101,一张Y类卡牌属性值分别为115,466,99。那么这两张牌是可以配对的,因为只有101和99一组属性互质。游戏的目的是最大化匹配上的卡牌组数,当然每张卡牌只能用一次。【输...

    32015年7月5日2,475二分图匹配,网络流
  • 【bzoj2118】墨墨的等式

    【bzoj2118】墨墨的等式

    Description墨墨突然对等式很感兴趣,他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件,他要求你编写一个程序,给定N、{an}、以及B的取值范围,求出有多少B可以使等式存在非负整数解。Input输入的第一行包含3个正整数,分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数,即数列{an}的值。Output输出一个整数,表示有多少b可以使等式存在非负整数解。SampleInput251035S...

    02015年7月5日3,004STL,,dijkstra
  • 【bzoj1180】[CROATIAN2009]OTOCI

    【bzoj1180】[CROATIAN2009]OTOCI

    Description给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作:1、bridgeAB:询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”,并且在结点A和结点B之间连一条无向边。2、penguinsAX:将结点A对应的权值wA修改为X。3、excursionAB:如果结点A和结点B不连通,则输出“impossible”。否则输出结点A到结点B的路径上的点对应的权值的和。给出q个操作,要求在线处理所有...

    62015年7月1日2,530link cut tree
  • NOI2008假面舞会

    NOI2008假面舞会

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

    12015年6月29日1,949深度搜索,并查集
  • NOI2009变换序列

    NOI2009变换序列

    DescriptionInputOutputSampleInput511221SampleOutput12403HINT30%的数据中N≤50;60%的数据中N≤500;100%的数据中N≤10000。题解byvoid大神:https://www.byvoid.com/blog/noi-2009-transform/[crayon-59e5ccff194a9769865145/]...

    02015年6月29日1,753二分图匹配
  • 【cf360X】Codeforces Round #210 (Div. 1)

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

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

  • 【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-59e5ccff1afc7298993902/]B.Friends这种问题显然按位考虑,排序+乱搞。。。考虑到每一位时,对于前缀二进制相同的一段可以找到匹配的另一段,然后求两段之内两两xor和什么的看了半天卓神代码似懂非懂。。。[crayon-59e5ccff1afd2817140620/]C.MirrorBox枚举碰撞次数之后模拟[crayon-59e5ccff1afd8564862566...

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

    【cf325X】MemSQL start[c]up Round 1

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

  • 【cf293X】Croc Champ 2013 – Round 2

    【cf293X】Croc Champ 2013 - Round 2

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

  • 【bzoj3308】九月的咖啡店

    【bzoj3308】九月的咖啡店

    Description深绘里在九份开了一家咖啡让,如何调配咖啡民了她每天的头等大事我们假设她有N种原料,第i种原料编号为i,调配一杯咖啡则需要在这里若干种兑在一起。不过有些原料不能同时在一杯中,如果两个编号为i,j的原料,当且仅当i与j互质时,才能兑在同一杯中。现在想知道,如果用这N种原料来调同一杯咖啡,使用的原料编号之和最大可为多少。Input一个数字NOutput如题SampleInput10SampleOutput30HINT1<=N<=2...

    62015年6月2日2,877费用流