深度搜索 - Page 2

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

「CF261X」Codeforces Round #160 (Div. 1)
A.MaximandDiscounts挑要求最小的优惠方案啦，最贵的那几个显然要花钱买，赠品当然也是选最贵的。。。恩变成了子问题[crayon-6767f4b64d9d6739455544/]B.MaximandRestaurantf(i,j,k)表示前i个人，选了j个，消耗为k的方案数然后枚举选的人数+组合数学，注意不重复统计答案[crayon-6767f4b64d9df879604715/]C.MaximandMatrix发现第m+1行的和就是2^(m二进制1的个数+1)则t是2的幂次才有解，求<=n的ans数量从大到小枚举每一...
32015年6月25日4,269递推与动规,贪心,深度搜索,排列组合
「CF339X」Codeforces Round #197 (Div. 2)
A.HelpfulMaths排序[crayon-6767f4b64e28a623208570/]B.XeniaandRingroad题意即题解[crayon-6767f4b64e293453852577/]C.XeniaandWeights搜索可过[crayon-6767f4b64e298644020174/]D.XeniaandBitOperations线段树模拟每次询问可以自底向上修改[crayon-6767f4b64e29c297181449/]E.ThreeSwaps由于只有三次交换，所以数列最多被分成七段找到所有断点爆搜[crayon-6767f4b64e2a2495841031/] ...
12015年6月23日3,411模拟,深度搜索,线段树
「CF317X」Codeforces Round #188 (Div. 1)
A.PerfectPair每次把小的那个变成两个的和，注意考虑负数[crayon-6767f4b64eacc019822219/]B.Ants蚂蚁的活动范围不太大，所以依然是暴力QAQ[crayon-6767f4b64ead5224016259/]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分两...
12015年6月22日4,525构造,深度搜索,状压动规,博弈论
「CF241X」Bayan 2012 – 2013 Elimination Round(ACM ICPC Rules, English statements)
A.OldPeykan贪心，如果到某个城市油不够的话，说明一定要在之前的某个城市加油，当然是选它们之中c最大的啦[crayon-6767f4b64f314078791057/]B.Friends这种问题显然按位考虑，排序+乱搞。。。考虑到每一位时，对于前缀二进制相同的一段可以找到匹配的另一段，然后求两段之内两两xor和什么的看了半天卓神代码似懂非懂。。。[crayon-6767f4b64f321351299523/]C.MirrorBox枚举碰撞次数之后模拟[crayon-6767f4b64f32b790218227...
22015年6月19日4,267模拟,深度搜索,差分约束
「CF325X」MemSQL start[c] up Round 1
A.SquareandRectangles模拟题[crayon-6767f4b64fc2a383920168/]B.StadiumandGames\[(2^k-1)m+m(m-1)/2=n\]枚举k二分得出m[crayon-6767f4b64fc33544648136/]C.MonstersandDiamonds此题比较恶心QAQ求最短用个类似dijkstra的东西，如果一种u->{v}的转移所有mn[v]都确定了，把这个转移放进堆或者是某个转移的代价被更新了求最长用记忆化搜索，走出环就是inf[crayon-6767f4b64fc38368205522/]D.Reclamation把图扩展成r...
12015年6月16日3,799STL,深度搜索,并查集,二分法,记忆化搜索
「CF235X」Codeforces Round #146 (Div. 1)
A.LCMChallenge显然是在接近n数内找三个两两互质的，由于懒得推公式所以可以小范围暴力一下[crayon-6767f4b65053d738518716/]B.Let'sPlayOsu!计算出到每个位置的期望连续长度就可以得到如果该位置正确的期望得分，就可以dp辣[crayon-6767f4b650546130363536/]C.CyclicalQuest一道很正经的后缀自动机建出s串的后缀自动机把xi复制一遍接在后面，然后在s串上匹配，就可以得出后缀自动机上贡献答案的结点[crayon-6767f4b65...
02015年6月15日7,559深度搜索,广度搜索,后缀自动机,概率与期望,莫比乌斯反演
「CF293X」Croc Champ 2013 – Round 2
A.WeirdGame两个人都应该采取贪心策略根据规则，先取0而对方不取0则败，所以有1则取1，当然尽量取对方也是1的那些取0的时候同理，尽量取对方是1的那些我们模拟游戏进程得出两个人的最终序列比较即可[crayon-6767f4b650acf147876300/]B.DistinctPaths容易发现，n+m-1>K时是无解的，那么有解的棋盘就很小了，状压使用的颜色+dfs然而这样的状态还是太多，我们发现dfs到一个格子的时候，所有未在棋盘上出现的颜色并无差别，所...
22015年6月11日5,302贪心,深度搜索,点分治,数学,状压动规,概率与期望
「CF263X」Codeforces Round #161 (Div. 2)
A.BeautifulMatrix模拟，求到中点的曼哈顿距离[crayon-6767f4b66de2d889318549/]B.Squares排序一下判断即可[crayon-6767f4b66de37339887438/]C.CircleofNumbers如果一个点与俩个点都有连边，则它在这两个点的一侧所以dfs依次确定一下即可[crayon-6767f4b66de3b829341537/]D.CycleinGraph感受了一下，觉得随便从一个点开始深搜即可。。。找出过这个点的所有环判断一下[crayon-6767f4b66de41389841394/]E.Rhombus其实是...
02015年6月5日3,076模拟,贪心,深度搜索
usaco 刷水。。。
2017:[Usaco2009Nov]硬币游戏f(i,j)表示考虑最后i枚，前一次对手取j枚，自己的最大获益[crayon-6767f4b66e39a582074196/][Usaco2005Feb]RiggingtheBovineElection竞选划区爱怎么暴力怎么暴力[crayon-6767f4b66e3a5551557477/]1661:[Usaco2006Nov]BigSquare巨大正方形狗眼瞎了wa了n发。。。枚举一条边暴力即可[crayon-6767f4b66e3ab112349293/]1654:[Usaco2006Jan]TheCowProm奶牛舞会有向图强连通分量。。。[crayon...
02015年5月26日4,399递推与动规,深度搜索,图的连通
PKUSC 2013 #2
A:TheSettlersofCatan枚举起点dfs[crayon-6767f4b66e877378767861/]B:Nim傻逼记忆化搜索我竟然清空错数组QAQ[crayon-6767f4b66e880246214071/]C:TraditionalBINGO纯阅读题[crayon-6767f4b66e886321009627/]D:TraditionalBINGO排序后广搜更新每个点能到达的最高点。。。一通乱搞感觉并查集也可以就是很麻烦？[crayon-6767f4b66e88c035555378/] ...
02015年5月22日3,241深度搜索,广度搜索,博弈论,记忆化搜索
2015全国互测 1
计算给定n,m对于[1,n]不包含m作为其子串的数k求\(\sum_ke^{k/n}\)kmp预处理后数位dp。。。[crayon-6767f4b66ee1e210804715/]移动小x有n张卡片和n个卡槽，现在第i张卡片在ai卡槽中。小x每次可以把一个在a位置的卡片移动到b位置，消耗的代价为min(|a−b|,n−|a−b|)，每张卡片可以被移动多次。小x想使得每个卡槽有且仅有一张卡片，请你告诉他最少需要的代价是多少。环形分金币参加白书[crayon-6767f4b66ee2e598750046/]分离小x喜欢分...
02015年5月17日3,506KMP,深度搜索,数位动规