about 2 years ago

NOIP滚粗...
NOI滚粗...
WC滚粗...

今年还有ZJOI CTSC APIO.. 以及..NOI 感觉压力好大啊..

以下是滚粗狗的自我修养。



AIM Tech Round Div.1

这场表现不佳,B题卡了好久,最后能过system test真是万幸。
D题本来能出的,结果最后来不及了。
延续CF一路萎的传统,略微涨了点rating。

rating: 2170



  • 623A Graph and String

对于一个只包含a, b, c三种字母的字符串S1...Sn, 使用一种方法生成一个无向图G:

$$G包含n个点,从1到n标号。$$
$$对于任意两个不同的点i, j,它们之间有边当且仅S_i与S_j是相邻的字符。$$

现在给你一张图G,问是否存在一个字符串S可以生成G,并输出方案。

如果两个点之间没有边,说明肯定有一个是a,另一个是c。
对于一个度为n - 1的点来说,这个点肯定选b。
取G的补图,对于点数为1的联通块取b, 点数大于1的联通块进行二分染色判定是否合法,最后再枚举所有的边,判定一下方案是否合法。



  • 623B Array GCD

给定n个数,有两种操作:

  1. 删去一段数, 设长度为l, 则代价为a·l
  2. 将其中一些数+1或-1, 修改一个数的代价为b

每种操作最多只能进行一次。要使这些数的gcd不为1,求最小修改代价。

这题我刚一开始还没想到做法...
其实不难,观察发现数列的第一个数与最后一个数最后一定至少保留一个,这样就可以枚举a[1], a[n], a[1]±1, a[n]±1的因子,求最小代价即可。
就只要求将所有数修改为d的倍数的代价就好了, 先判断每个数是否一定要删除,然后枚举一下前缀后缀的修改区间,算一下代价就好了。


  • 623C Electric Charges

平面上有n个点,现在让你给每个点选定一个坐标轴(X轴或Y轴),然后把这个点投影到你选的这个轴上, 最后要使最远的两个点之间的距离最短。

这题其实还是比较思博的。
当时我看这题过的人少就没去看... 就狗带了。
首先对于一种方案,答案只跟X轴上最左端和最右端点的坐标,以及Y轴上最上面和最下面的点的坐标有关。
就可以二分答案d,先枚举X轴上最左端的点,假设它的绝对值大于等于X轴右端点的绝对值,那么X轴最右端的点就要满足两个条件,一个是不能超过d的距离,另外一个就是坐标不能大于左端点坐标的绝对值,显然取最右的符合条件的点最优,然后通过对Y轴坐标前缀和后缀的记录,就能算出答案了。再枚举X轴上最右端的点,假设它的绝对值大于等于左端点的绝对值,然后一样做就行了。


  • 623D Birthday

大家在玩捉迷藏,n个人躲了起来,每一轮你可以捉住一个人,其中捉住第i个人的概率是p[i], 由于你看不见他,所以你就要猜他是谁。游戏就这样一直进行下去..直到每个人都被你捉住并猜对至少一次。问最优策略下最少期望轮数。

每一轮贪心取能使得前i轮获胜概率尽可能增大的方案。
大概取到20w轮就差不多能达到精度了。
直观感觉是对的?
证明:待填

WARNING
此题精度要求较高


  • 623E Transforming Sequence

一个数列a[1] .. a[n], 定义一个变换P :

问有多少个不同的数列A, 使得A经过变换P之后单调增。答案对10^9 + 7 取模。

其实也是可以做的..就是比较麻烦
首先每个数可以拆成k位。然后列个dp式子:

发现这东西可以分治+FFT算出来
因为模数比较普通,所以可以通过做三遍NTT然后CRT将答案做出来


8VC Venture Cup 2016 - Elimination Round

  • 626A Robot Sequence

一个机器人只会往上下左右四个方向移动,现在给你一个机器人移动的序列(UPLR表示), 求有多少子串使得机器人能够回到原地。

n^2暴力即可


  • 626B Cards

有n张卡片, 有红绿蓝三种颜色。
有两种操作:

  1. 选择两张颜色相同的卡片,把它们合并成一张该颜色的卡片。
  2. 选择两张颜色不同的卡片,把它们合并成一张和这两种颜色均不同的卡片。

不断合并,直到只剩下一张卡片为止,问最后有可能剩下什么颜色的卡片。

首先如果所有卡片都是同一种颜色,那么显然最后只可能剩下这种颜色的卡片
对于剩下的情况,如果一种颜色的数量不等于n - 1, 那么肯定能拼成这种颜色


  • 626C Block Towers

小朋友们要搭建n座2个积木一层的塔和m座三个积木一层的塔,要求每座塔消耗的积木数量都不相同,求在此情况下耗费积木最少的塔所耗费的积木。

可以枚举答案进行判定, 对于一个答案s, 第一部分的塔优先使用能被2整除不能被3整除的方案,第二部分的塔优先使用被2整除不能被3整除的方案,最后把剩下的塔用能被6整除方案覆盖。


  • 626D Jerry's Protest

一个箱子里有n个球,每个球上有互不相同的数字。Andrew 和 Jerry 在玩游戏,每一轮每个人随机摸出一个球,然后比较它们的大小,摸到数字较大球的那个人获胜,然后把球放回箱子里。他们就这样进行3轮,求前两轮Andrew获胜,第三轮Jerry获胜,且Jerry三轮摸出的数字总和大于Andrew摸出的数字总和的概率。

n < 5000

枚举前两轮Andrew总和减去Jerry总和的值,用前缀和计算概率。
再枚举最后一轮两人取出的数,再用前缀和计算答案即可。


  • 626E Simple Skewness

有n个数,要求从其中挑选出一个子集,使得其平均数减去中位数尽可能大。

首先发现一个性质,如果子集大小为偶数,那么一定不会是最优方案, 因为当平均数大于中位数的时候,去掉中间的两个数中较大的那个数,一定不会让答案变小。
接着就可以枚举中位数,假设为a[x], 然后选取的区间一定是a[x - d .. x], a[n - d + 1 .. n], 可以证明平均数随着d的增长是一个单峰的函数,三分之。


  • 626F Group Projects

有n个数,要求把这些数分成若干组, 每组的不平衡度为该组中最大的数减去最小的数,求使得总平衡度不超过k的分组方案数。

n < 200 k < 1000.

考虑dp, 先将数字排序,然后从小到大一个一个数去安排分组。
f[i][j][k]表示目前已经考虑了i个数,有j个组目前仍未关闭,不平衡度为k的方案数。
这样对于一个数a[i], 可以单独分一组,关闭或不关闭它。 可以加入某一组,关闭或不关闭它。
发现总的不平衡度和一个数具体加入哪一组没有关系,只和这个组的关闭时刻有关。因此可以O(1)进行转移。


  • 626G Raffles

有n个抽奖池,每个抽奖池的奖品价值为p[i], 初始时有l[i]张抽奖劵, 现在你有t张抽奖劵,可以分配到这n个抽奖池中,但是在任意一个抽奖池中你不能分配超过该抽奖池总量一半的抽奖劵,也就是对于任意一个抽奖池,你的中奖概率最多为1/2. 要求合理分配这t张劵,使得期望收益最大。还有Q次修改操作,每次会将l[i]加1或减1,求修改后的期望收益。

n,Q < 10 ^ 5

对于没有修改的情况,可以发现对于一个抽奖池,期望收益的增加值是单调减的,因此可以贪心,用个堆去维护当前的决策集合,每次都选择最优决策进行。
对于有修改的情况,每个将l[i]加1或减1的操作,会让其在抽奖池中的决策顺位移动至多一个位置,因此最多会影响到一张劵的归属,对于将l[i]加一的操作,最多将其中的一张票取出,然后放到另外一个池中。对于将l[i]减一的操作,最多将另外一个池中的一张票取出,然后放到i中。用两个堆分别维护添加劵的最优决策和取出劵的最优决策,要注意随时保持每个池中劵数不超过一半。

WARNING
要注意在修改一个堆之后要对应去修改另外一个堆


Manthan, Codefest 16

rating: 2316



  • 633A Ebony and Ivory

求不定方程ax + by = c的非负整数解

数据范围很小,直接枚举x y即可。


  • 633B A Trivial Problem

求所有的n,满足n!末尾有恰好m个0

枚举n进行判断。


  • 633C Spy Syndrome 2

给你一个句子,把空格删掉,再给你一个字典,要求断句。

把字典建成一个trie,然后在句子上做dp, 在trie上去寻找下一个可行单词。


  • 633D Fibonacci-ish

给定n个数,在其中找出尽可能多的数,使其满足斐波那契数列的特征, 即每个数等于前两个数的和。

枚举第一个数和第二个数
数列长度为log(n)级别的
特判前两个数都为0的情况。


  • 633E Startup Funding

发现给你那个式子是有单调性的,这样就可以用单调队列/二分来求出每个l所对应的r,以及potential值
然后枚举子集的最小值,进行简单的概率计算即可。


  • 633F The Chocolate Spree

在一棵树上找两条不相交链,使它们权值和最大

无脑树形dp, f[i][j][0/1] 代表以i为根的子树中,找了j条链,i是否能再向上延伸。
转移要分好几种情况讨论,注意细节


  • 633G Yash And Trees

把子树问题转化成序列问题,用线段树去搞
看到m只有1000,可以用在线段树上套个bitset来维护
区间加操作就把对应节点的bitset给rotate一下
区间询问就把区间内的bitset给or起来,再去and一个m以内质数的bitset就能得到答案了。


  • 633H Fibonacci-ish II

莫队大法好
插入或删除用线段树去维护,每个节点维护一个2*2的矩阵就好了


8VC Venture Cup 2016 - Final Round

  • 627A XOR Equation

从低位到高位依次确定,记录一下目前的进位即可。


  • 627B Factory Repairs

问题相当于单点修改,询问[1, l] min(b, x[i]) + [r, n] min(a, x[i])
用个线段树去维护就好了


  • 627C Package Delivery

经典问题了,贪心
对于一个位置,先往后找距离它最近的,油价比它低的点,如果能开到那里,就把油加到恰好能开到那里,因为在后面加油肯定比在这里加油划算。
如果开不到这样的点,就在这里把油加满,然后去找能开到的地方中油价最低的地方,开到那里。


  • 627D Preorder Test

给你一棵带点权的无根树,你可以任意确定这棵树的根以及每条边的顺序,要使这棵树dfs序前k个节点中权值最小的权值尽可能小。

首先二分答案,点权都变成了01,判断是否能把一棵树的dfs序的前k个点都弄成1。
假设已经确定了根,那么如何使它dfs序前面尽可能多的点弄成1呢,首先肯定把它全是1的子树给挪到最前面,然后再剩下的子树中去找答案最大的子树。子树的答案就是一个子问题,可以递归下去解决。

这样我们就可以做两次tree dp,先随意确定一个根,做一次dp,把每个点作为根的情况下的dp值求出来,然后再遍历一遍子树,用父亲节点的信息去更新当前点的dp值,这样就能求出最优方案了。


Codeforces Round #345 (Div. 1)

unrated爽


  • 650A Watchmen

在平面上给你n个点,要求两两之间曼哈顿距离等于欧几里得距离的点对数目。

这种情况只发生在x坐标相等或y坐标相等的时候,拿个set记录一下就好了。注意处理两维坐标都相等的情况。


  • 650B Image Preview

枚举右边看的照片数量,左边看的照片是单调减的.. 这样O(n)就可以解决了。
注意要判断一下是先看左边还是先看右边。


  • 650C Table Compression

按照每一行每一列的限制建出一个DAG,搞拓扑排序就好了。

开黑一时爽


  • 650D Zip-line

这个题的主要瓶颈在于确定一个数是否一定在LIS上
有两种方法:

  1. 先正着做一遍LIS,这样得到了一个字典序最大的LIS, 接着倒着做一个LIS, 就得到了一个字典序最小的LIS,如果i一定在LIS上,则它在一定都出现在两个序列的相同位置上。
  2. 计算出经过每个i的LIS的数量,对一个大质数取模,跟总数比较,如果相等,则说明i一定在LIS上。

  • 650E Clockwork Bomb

LCT就好了..简单无脑..魔法森林交上去就好了..


  • 653A Bear and Three Balls

枚举


  • 653B Bear and Compressing

直接dfs所有可能的答案,然后判定是否可行。


  • 653C Bear and Up-Down

如果不合法的位置太多了,那么答案肯定就是0.
不然就暴力枚举每个不合法位置和其他所有位置交换,然后暴力判断每个不合法位置以及交换的位置附近是否合法。


  • 653D Delivery Bears

二分答案,最大流。

WARNING
可能会爆int!!要注意


  • 653E Bear and Forgotten Tree 2

一个图合法当且仅当:

  1. 原图删去1之后形成了不超过k个联通块
  2. 1的度数大于等于k
  3. 对于每个联通块都有边连向1

难点就在于寻找原图删去1之后的联通块。这个只要对于每个点dfs一遍,dfs经过的点就从点集中删掉。
这样就能保证每个点最多被dfs到一次。


  • 653F Paper task

SAM套上数据结构。


  • 666A Reberland Linguistics

直接暴力判断每一个子串是否合法即可,判断子串合法可以用dp。

WA了几发之后发现忘记去重了。


  • 666B World Tour

先bfs把两两之间最短路给求出来,然后把从每个点出发的距离排序,到每个点结束的距离排序。枚举中间两个点,然后直接选取最大的两个值即可,然而因为4个点不能重复,因此每一侧都要枚举4个最远的点。


  • 666C Codeword

vp的时候sb了,这题居然不会做

观察发现对于长度相同的模式串,答案都是一样的,因此只有n和m的取值有意义。

对于给定的n, m, 答案可以这么计算

可以把提到外面去,这样给定一个m,就可以求出所有n的答案。

由于m的总和不超过n, 因此不相同的m是级别的,总的复杂度就是


  • 666E Forensic Examination

直接把后缀xxx和区间众数嵌套了起来。

直接把所有串接起来直接件后缀树,两个后缀的LCP就是它们的LCA,这样询问就相当于在一段区间内找权值范围在[l, r]之中出现次数最多的权值。莫队 + 线段树就好了,注意把所有串接起来的时候在串和串之间要加上分割符,也要注意开够空间。


  • 663A Rebus

先把符号为正的项和符号为负的项给分开,发现这两部分的取值都是一个区间。

那么只要暴力地枚举一个部分的取值,判断一下另外一个部分是否合法即可。


  • 663B International Olympiad

先暴力把比较靠前年份的答案算出来,后面的年份都是有规律的

要么缩写就是自己本身,要么就是在自己前面加一个1, 分界线在哪里呢..打个表找规律发现分界线都形如3099, 13099,113099, 1113099...

这样就可以直接搞了。


  • 663C Graph Coloring

每个联通块分开来考虑,对于一个联通块,只要任意确定一个点是否选,那么其他点的状态就确定了。


  • 663D To Hack or not to Hack

一道逗比题,首先枚举每道题目的分数,这样就知道每道题要hack几个人了。

之后就要决定要hack哪些人,这样直接做复杂度是的。 发现每hack一个人可以加入100分,也就是如果能hack的人数超过90,那么不管怎么hack肯定都rank1了。 于是n的范围就缩小为90了,暴力dp就好了。


  • 663E Binary Table

预处理出0~2^n-1每个数的贡献,然后FWT一波就好了。


  • 668A Little Artem and Matrix

一开始naive了,以为只要记录每一行每一列shift了几次就能做了,后来发现每次需要遍历操作列表,然后就能找到对应的位置了。


  • 668B Little Artem and Dance

只要对每次起点位置的奇偶性和2操作数量的奇偶性进行讨论就可以了


  • 668C Little Artem and Random Variable

对于每个Xi, Yi都可以列出一个二次方程组来,只要依次解出来就可以了。

WARNING
对实数开根号的时候要对0取max,不然由于浮点误差,被开方数可能为负数。


  • 668D Little Artem and Time Machine

这题非常sb,只要对每个元素动态地开一个线段树就行了


  • 668E Little Artem and 2-SAT

首先判断两个2-SAT是否一个有解一个无解

枚举其中一个2-SAT的一条边,看在另一个2-SAT当中这两个点是否冲突,若不冲突则找到了一组解。


  • 668F Little Artem and Graph

还不会 坑着。


  • 671A Recycling Bottle

简单题,排序一下选最小的就好了。


  • 671B Robin Hood

首先看看解是否为1或0(也就是土匀匀的)
如果不是土匀匀的,就枚举一下最大的位置和最小的位置,算一下答案就好了。


  • 671C Ultimate Weirdness of an Array

枚举一下GCD,然后发现GCD能取到它的区间能被划成三段。
排个序搞一搞就变成区间取max,区间求和了..segmentbeats一波就好了。


  • 671D Roads in Yusland

的dp比较简单的,用map维护一下状态,启发式合并更新一下。


  • 555A Case of Matryoshkas

题目看错了一发,如果要套进去的话,外层只能有一个套娃,不能好多个一起。


  • 555B Case of Fugitive

一个简单的贪心,把所有区间按右端点排序。然后每个区间取最左边能取的长度。用个set就好了。


  • 555C Case of Chocolate

动态开两个线段树就好了。


  • 555D Case of a Top Secret

直接模拟绳子的位置和长度,这样做的瓶颈在于绳子可能会转很多圈,只要在能取模的时候把绳子长度取模就可以了。因为取模一次之后绳子长度至少减少了2。


  • 555E Case of Computer Network

先把边双树给建出来,然后在树上取覆盖边就好了,用个并查集维护就行了。


  • 555A Glass Carving

用一个set维护两个方向间隔的长度。


  • 555B Clique Problem

把式子列一下,发现要求的就是区间图最大独立集,经典的贪心。


  • 555C Data Center Drama

先把奇度的点两两连起来,如果总边数为奇数,就随便连一个自环,然后跑一个欧拉回路就好了。


  • 555D Fuzzy Search

把AGCT四个分开来做,这是一个经典的通配符匹配,FFT。


  • 506C Mr. Kitayuta vs. Bamboos

有n个竹子,每棵竹子初始长度为hi, 生长速度为ai, 有m天,每一天每棵竹子都会生长ai的长度。现在你有一把斧头,每一天你都可以砍k下..每一下可以让一棵竹子变短p。问最后最长的竹子最短是多少。

这个题还是不错的.. 和UOJ goodbye yiwei的那个题比较像.. 用了一个逆向思维。首先二分答案,然后考虑有n个长度为x的竹子,每天都会变短,你每天可以让竹子变长k次每次p,竹子在中间的时候长度不能变成负的。 这样就把竹子长度非负的限制巧妙转化了一下。发现k的值非常小,就可以把每棵竹子一定要被变长的时间节点给算出来,然后贪心就好了。


  • 484C Strange Sorting

这个题是这场最难的题目
发现操作可以分解成两个部分..对前k个数进行重新排列,把数列循环左移。
这两个操作都可以看成一个置换,那么用快速幂去做这个置换就好了。


  • 480E Parking Lot

有n*n的网格,k次操作,每一次把一个空地变成障碍,每次操作完问最大空白的正方形的边长。

n, k < 2000

把空地变成障碍不如把障碍变成空地好处理,就可以把操作序列倒过来。
这题我是用线段树做的,对于每一个位置记录它向上的空白格子个数,记为Hi,每一行开一个线段树去维护。
每次修改都会改变O(n)个位置Hi的值。询问的时候枚举正方形的底边,查询最长的一段连续区间,每个Hi都大于等于K.


  • 494D Birthday

一棵n个点的树,q次询问,每次询问一个点到一棵子树内所有点距离的平方和。

考虑将询问离线。DFS这棵树,用维护每个点到当前点的距离。每次走一步一定对一个子树内所有距离都减1,对其他点的距离+1,这样就可以将DFS序建线段树来维护距离了。


  • 461E Appleman and a Game

用一个字符串A去覆盖另一个字符串B定义为:每次取出A中的一个子串,依次不重叠地覆盖串B

给定串A,求长度为n的串B使得最少需要的覆盖次数尽可能多

假设已经知道了B,计算答案就是一个贪心的过程.. 每次取出长度最长的B的前缀使得其为A的子串。
考虑dp[i][j]为被覆盖了i次且当前未覆盖首字母为j的串的最小长度.
如果能求出这个,那么只需要二分一下答案就能求出最大的覆盖次数了。
考虑这个dp怎么转移. 每次只要将一个开头为j,末尾为k且不出现在A中的串接到B后面,就能得到一个答案起码为i+1的串。
这样就可以倍增去做这个dp了..


  • 512C Fox And Dinner

把n个数分成若干组,使得每个组都是都能围成一个环,满足任意相邻元素的和为质数。

n <= 200

发现质数一定都是奇质数,因此把所有数按照奇偶性分开。
问题就变成了,在一张二分图上找出若干个环覆盖所有的点,每个点仅在一个环上。
这个问题的充要条件是每个点的度数都为2.
这就变成了一个经典的网络流问题了。


  • 338D Fox and Perfect Sets

求出0~n所组成的二进制加法子群个数。

考虑枚举这个群的基,每一位就有两种填法..要么是新开一维,这样这一位就只放这么一个1,要么就不增加维数,放奇数或者偶数个1,这个可以用组合数预处理出方案。 然后数位dp就行了。


  • 348C Subset Sums

n个数,m个集合。每次给一个集合中所有元素加上一个值,或者询问一个集合的元素之和。

对于集合分类,大于根号n的集合作为大集合,小于根号n的结合作为小集合。
预处理出每个大集合和其他集合交集的大小。
这样对于一个集合修改和查询的时候就能枚举所有大集合通过交集大小来更新答案了。
对于小集合的修改..只要暴力枚举元素去修改对应元素的值就好了。


  • 348E Pilgrims

开始的时候一直在想如果枚举断点来计算答案,后来发现十分繁琐无法计算。
实际上可以对于每个关键点计算合法的断点。发现如果一个关键点存在合法的断点,那么这些断点肯定在一条链上。
只要通过DFS找出这条链,然后套上数据结构就好了。


  • 687E TOF

给定一张有向图。给每个点指定一条出边,使得在环上的点最少。

首先求一个SCC,然后发现如果一个SCC不在DAG的叶子上,那么它一定可以被拆成链。只有处在叶子的SCC可能贡献环。
这样就对这些SCC求一个最小环就行了。 有向图最小环的求法很简单,只要BFS就行了。

← 滚粗狗的自我修养之TOPCODER练习 SRM 558 弱鸡题解 →
 
comments powered by Disqus