151017模拟 动态规划 杂题

151017模拟

今天考的题比较简单,一个半小时AK了。但是后来机房突然停电.....幸好代码早早就交了= = T1 表达式 感觉好久没做这种类型的题了,题目给的信息非常准确严谨。首先空格不能直接吃掉,而是应该当作一个正常字符来处理。然后就可以把所有连续的数所在区间设为合法区间,最后DP一下即可。 [crayon-5···
141017模拟 动态规划 杂题

141017模拟

T2 喝喝喝 思路非常好,就是先把取模的式子变形,化为a[x]-mod=k*a[y],这样可以知道,满足要求的数对就是前面的数减去mod后是后面的数的倍数的数字。那么,我们有两种思路,一是从前往后枚举,每次更新以当前点为右端点,最左能到达哪里,但是这样需要枚举当前数的倍数,如果不加优化或者分块的话时···
101017模拟 动态规划 杂题

101017模拟

虽然今天考试又翻车了(暴力分都没拿全),但是这套题还是非常值得总结的。 T1 小奇挖矿2 考试的时候注意到+4+7很奇怪,也试着凑了几个数,但是因为写错了没找到规律,乖乖打了暴力(然而处理重复没搞好)。实际上,如果认真把4和7能凑出来的数写出来的话,可以发现,4和7可以凑出{4,7,8,11,12,···
071017模拟 杂题

071017模拟

T1 排队(line) 想清楚了非常水,十几行搞定。其实就是最后所有男生都会到最后,而越靠后的男生越早到达,所以最晚的永远是最前面的男生,我们关注的也只是最前面的男生。一个男生到达后面的最早时间是后面女生的数量,且中途可能被后面相邻的男生卡住。但是,相邻两男之间的女生可以“缓冲”掉一定的“浪费时间”···
BZOJ4007 [JLOI2015]战争调度 DP+DFS 动态规划 搜索

BZOJ4007 [JLOI2015]战争调度 DP+DFS

考试的时候先想到的是确定了最下面一排的选择情况后,上面的点只要扫一遍就一定能确定了,之后去打了状压暴力。。。 实际上,如果反着想,如果上面的点确定后,下面的点选择情况也一定能确定,因为最下面每个点产生的贡献只与它的所有祖先节点有关。接着,如果我们已经确定了当前枚举到的一个点,并且该点上方所有祖先节点···
BZOJ4000 [TJOI2015]棋盘 状压DP+矩阵乘优化 动态规划

BZOJ4000 [TJOI2015]棋盘 状压DP+矩阵乘优化

题目描述不是很清楚,实际上就是给你一个矩阵表示每个点的攻击范围,若下标均从1开始,点在第2行第p+1列,求放棋子的可行方案。 实际上是状压DP的水题,枚举行,枚举上一行状态,枚举本行状态即可,但是这题的行数开的比较大,实测普通的DP只能得70分,观察式子发现,合法的状态并不多,每行撑死也就64种,而···
Evensgn剪树枝(tree.*) 树形DP 动态规划 图论

Evensgn剪树枝(tree.*) 树形DP

又是一道树形DP,考试打暴力期望60,然而只骗到了30。思路非常不显然,至今懵逼。设f[i][0]表示i点上方的连通块中不包含黑点,在i的子树中的方案数;f[i][1]相反。这样设计状态,可以考虑砍i点的父边。 设当前考虑的是u点,先不考虑u点的颜色,递归处理u的子树,递归完成后,再考虑f[u]的取···
BZOJ1076 奖励关 期望概率+状压DP 动态规划 期望概率

BZOJ1076 奖励关 期望概率+状压DP

看数据范围,是期望+状压,状态转移也很好想,但是这道题如果正向转移会比较麻烦,因为处理无效状态转移到有效状态会比较麻烦。但是,如果逆向思考,就会容易一些。设f[i][j]表示前i次选到了状态为j的最优解。倒序枚举每一次,枚举状态,枚举该次选到的物品,若当前状态允许选择该物品,则该物品可以选或不选,由···
GDOI2014 拯救莫莉斯 状压DP 动态规划

GDOI2014 拯救莫莉斯 状压DP

注意题目是“n*m<=50”,最坏情况应该是7x7的矩阵,显然不能直接暴搜,那么只能用状压DP来做。因为当前一行的状态选择只与其上下两行有关(第一行和最后一行例外),所以设f[i][j][k]表示前i行,i-1行状态为j,i行状态为k时的最优解。枚举行数、i-1行状态、i行状态、i+1行状态,···