2015重庆集训题解

纯属流水账

【6.5】

弱省胡策Round3 HE人民送温暖系列

【6.6】

,Bstar复赛 >

抱着Tshirt走人的心态去打,结果被坑傻。
1001 枚举两条横边,竖边数一数就好,纯手速题。
1002 我不会弹吉他啊,读题读了半天。弦啊品啊啥的,其实就是暴力DP就好。
1003
1004 单调队列大裸题。出题人语文简直2333。
1005 递推一下。
1006 平衡大师,上下界网络流。

Looksery Cup >

A
B
C
H

【6.7】

SHTSC2012的题目。

T1 road

给定一个网格图和若干换乘站。只能在换乘站改变横纵方向,求两点最短路。
每行/列相邻点连边,Dijkstra。

T2 generator

不会做

T3 tree

裸的树链剖分,子树加,链求和。

【6.8】

省队交流

上午 >>

me >

SRM 613 Div1 900 Taro Checkers

CF Ping-Pong

线段树辅助维护并查集。每次查询时比较区间是否包含。
cts > 杉

T1

取对数后整体二分+半平面交

T2

高维循环模拟题

T3

不会做

下午 >>

hlq > 淇

T1 粗心的邮差

现在要你构造一个长度为n的数列{ai} 使得 |ai – i| <= 2 求方案数

矩阵加速优化DP

T2 推箱子

题意和题目大意差不多,只是可以旋转90度和一圈。分层图BFS

T3 旅行

裸的树链剖分,每次赋给整体一个权值或者加上一个等差数列或者以2为等比的数列。使劲写吧。

T4 水题

给你个图,N个点M条边,Q个询问,要求回答删去某条边后,有多少对点不能互相到达。

统计桥边就好。要是每次删除指定边数可以分治并查集。

T5 短信加密

K个互不重叠的长度为L的相同子串的代价为K * L,求最大化这个值。
后缀数组+二分+贪心。

T6 组织

gwy题的初版,每次加入的向量肯定与之前所有向量和同向,算出每一维的分量加到总向量即可。

T7 Hearth Stone

Catalan数。和APIO那两道题非常类似。

T8 循环排插

求一个点出入度都为1的N个点的图的环个数的k次方期望值。

T9 小Z的旅行路线

离线按w排序,维护直径

T10 覆盖半径

因为枚举一行后,每一列有贡献的点至多一个,斜率优化DP。
lxz >

djm

需要很麻烦的分类的DP题目。
syk > 堃

T1 ACU

将攻击药与回复药放在两行,可以看出这是一个比较巧妙的最短路模型。因为只有形成回路才能替换技能。所以转化为求一条边不能通过后两点间最短路。记录每个点的最短和次短路径即可。

T2 CF543E Listening Music

你是一个很喜欢听音乐的人,在之后的S天里面,你将会听有N首歌(编号)的音乐列表里面的M首歌,每首歌有一个品质值。在第天,你会选一个数字,这一天你会听编号为的歌,其中每有一首歌的品质值小于,你的不高兴值会增加1。请计算你之后S天每一天不高兴值的最小值。
, <= ,强制在线。

T3 tree

给出一棵含有N个节点的树,树之间的边边权为,有M个修改,每次修改一条边的边权。
输出未修改时和每次修改后,路径中边权的gcd为1的路径条数。

T4 CF343E Pumping Station

最小割树+贪心构造。
说下贪心构造,每次我们选择树上最小边分成两部分递归构造。
lrj > 杰

【6.9】

强省胡策Round4 >

T1 Message

分数规划+最大权闭合图

T2 Road

最小生成双连通图,不会。

T3 Express

老原题了。SHOI2005 树的双中心
可以用的大暴力来实现程序,具体的话,我们知道每次往代价最大的子树走,直到不能调整。因为树高有限,所以每次枚举一个点作为一个中心,将其他树上的相应信息更新,然后再从根节点寻找剩下的树的第二中心即可。

UR 8 >

A题

发现两维是独立的,直接算出最小段数相加求和。

B题

10pt 暴力模拟
30pt 线段树维护最大最小
50pt 线段树维护凸包

C题

10pt

【6.10】

nodgd租的题和造的题

T1 hamming

我是,B连傻逼题都不会捉。考场上脑抽一直减少不了未知数。其实可以把一个串全部变成0,因为每一位独立,所以这样四个串每一位共有7种情况。现在有6个已知条件,我们在依次枚举长度L,高斯消元。判定是否全是非负整数解即可。

T2 reverse

题目还是比较一眼。强行加了高精度。设表示放了的所有数,当前逆序对数为的方案数。直接Dp是三方的,前缀和优化一下就平方了。对于如何构造答案,还是老方法,逐位确定,枚举每一位放的是多少,去掉之后会使逆序对数减少,但是其实是原问题的子问题。

T3 spread

提交答案题,花了好多时间写了一个模拟器开始玩,发现能手玩的点并不多。
   Case # 1/2 手打
   Case # 3/5 贪心+随机化
   Case # 4 链DP
   Case # 6/7/8 树形DP
   Case # 9/10 A* + BFS估价

【6.11】

今天是弱省胡策Round 5。

T1

找规律/反演发现可以由组合数和的卷积表示。
直接直接上NTT就好。

T2 graph

题意是构造一个图使得任意两点最短路,且存在一对点对的最短路恰好等于
我们发现k=1就是完全图,k=n-1就是一个每个点都带自环的长度为n的环。对于,一个长度为k的环和若干长度为2的小环组成即可。

T3 dye

给N行M列的棋盘染色,要求任意两行本质不同。此处本质不同的定义是任意两行至少存在一种颜色的出现次数不同。
这题有两种做法:
法1
因为m比较小,所以我们爆搜出m的所有正整数划分,这一共有20W种。然后我们算出每种划分的本质不同的方案数和可以选择的颜色序列。具体就是因为划分后排列的方案数一定,在颜色方案中除掉相同大小的即可。之后DP一下,方程是表示考虑了前种划分,用了行的方案数。因为每行本质不同,所以最后还要乘上一个
法2
题解的做法我表示非常神奇。设表示放置i行j列的矩阵用k种颜色染色且每行至少强制d个k号颜色的方案数。转移很好写,。最后答案就是

【6.12】

今天是nodgd的题。

T1 照烧吃薯片

类似BJOI2011双端队列,因为只能取连续一段,所以贪心即可。

T2 照烧吃仙人掌

又是一道数数题。题目要求统计有标号仙人掌计数(每个点至多属于一个环内)。
不妨设表示i个点的仙人掌的数量,表示总共i个点组成k个基团的数量。枚举i号点的存在方式即可写出转移。这里说一说,我们枚举i号点所在仙人掌基团的点数,有转移方程:

T3 照烧吃键盘

提交答案,题目本家肯定是网络流啦。
 Case # 1    暴力枚举
 Case # 2    观察数据,全部取正数最优,Python
 Case # 3    二分图匹配
 Case # 4    最大权闭合图
 Case # 5 & 9  最大权闭合图
 Case # 6    随机化乱搞
 Case # 7 & 8  分块随机化乱搞
 Case # 10    树形DP

无意间拜到了dzy大毒瘤的胡策模拟题。

【6.13】

补6.12的提交答案题

这提交答案题神坑爹啊,完全是不正常人类才能拿到高分。
前5个点还好不吐槽了。
第9个点怎么跑网络流怎么都比标程好。12pt
第10个点dp最优值就是比标程好,就是不要你拿全。9pt
第6-8完全是秀逗啊,我退火退了一下午始终上不了6000,一直徘徊在4000左右。最后发现标程数组开销,(大雾

Bestcoder# 44

敦爷场
T1 模拟题拼手速
T2 建棵trie跑一跑咯
T3 只想出两个log的,最后没卡过
T4 据说是sy校内模拟赛,FFT+生成函数
打的很心酸啊

【6.14】

今天还是nodgd的题

擦与写

分解质因子后直接递推计算

拿与放

好厉害的题目
60pt很好拿,表示A取到前i个,B取到前j个是否可行,如果i和j的下一个元素都在相对的区间即可。

优与劣

World Final原题

【6.15】

今天是Gordon的生日,然而是我的模拟题。
听说民国风和数数题更配哟。

八辈子

其实只需要知道第i个填入的数在前i个数中的相对位置大小即可。

一梦千朝

只需要枚举剩下的点中有多少个点还需要向外连边,将还需要连入边的点和什么边都不连的点看作一类

呓语红尘

从小到大枚举,每次根据之前有多少个相邻的最大值数对就可以转移啦。

一直考到2点钟才考完,大家考的都还不错,nodgd 210,Gordon/lrj 130。生日buff真是厉害。

中午Gordon请了全省队(syk&hlq因为在中山所以缺席,noi再补)

下午回来补讲了上次的重庆集训课件。

【6.16】

今天是弱省互测#6

String

分别取模数后KMP一下,取a和b的Border数量的最大值

Tree

轻重链剖分+堆
再将每条重链的最优值维护一个set

Transport

因为不具备二分性质,所以直接枚举+set就好啦。

【6.17】

今天是Gordon的题目,是我有生以来题目描述版本最多的一次考试。

我并不能够回忆起题目的名称。

A

进位问题很讨厌:转化为两个数相加大于一个指定的数来做
归并+单调队列

B

组合数裂项相消+组合数取模
见BSOJ 礼物一题

C

因为起始点固定后,逆序对数为K的肯定是一段连续区间,而且随着起始端点的增大而单调不降。
有了这个性质就可以二分+前缀和来做啦。

【6.18】

今天是弱省互测#7

Magic

题意是求n个点n条边的带标号无向连通图计数
经典题目了,直接高精度压位。

I forget the name of the second problem

题意是求每次将一个宽度为1的矩形高度减一,然后求最大子矩阵
如果为0/1矩阵,直接线段树维护最大子段和。
然而拓宽到原题,其实是每一层维护一个可持久线段树就好,最后每一层的答案用个set维护。

TKD的神题

并不想看,还是zld巨神的提答题好评。

【6.19】

World Final 2015 重庆队模拟训练

分组后和10组队打。

A题 签到题,被多组数据坑了3次
C题 裸费用流,题意杀
D题 手动积分+二分 被01秒掉
L题 暴力枚举划分方案+Haffman编码 搞了好久的题

【6.20】

记人生第一次IPSC2015

我简直是猪队友,对全队贡献为-oo,就不丢队友的脸了

【6.21】

【6.22】

【6.24】

【6.25】

【6.27】

CF# 311
总算黄了,看来真不适合打CF。

【6.28】

【6.29】

【6.30】

nodgd的Round 16
T1
T2
T3