ComplexPug

未归档

做题记录(1)

/ 注册

全部文章 / 未归档（共273篇）

loj#2510. 「AHOI / HNOI2018」道路记忆化，dp

题目链接 https://loj.ac/problem/2510 思路 f[i][a][b]表示到i时，公路个数a,铁路个数b 记忆化复杂度=状态数=\(nlog^2n\) 代码 #include <bits/stdc++.h> #define ll long long us...

记忆化 DP

2019-02-24

0 642

[HNOI/AHOI2018]游戏

题目链接 https://loj.ac/problem/2508 https://www.lydsy.com/JudgeOnline/problem.php?id=5288 https://www.luogu.org/problemnew/show/P4436 思路离散化没啥好说的一堵墙 ...

拓扑排序乱搞暴力

2019-02-24

0 486

CF1131D tarjan，拓扑

题目链接 541div2 http://codeforces.com/contest/1131/problem/D 思路给出n序列和m序列的相对大小关系构造出最大值最小的序列缩点+拓扑小的向大的连边相等的连个环 tarjan缩点，判断环内是否ok 最后拓扑更新要这样 ans[v]...

CF tarjan 拓扑排序

2019-02-23

0 443

CF113D 高斯消元、dp

题目链接 https://codeforces.com/contest/113/problem/D 思路 \(k[i]=\frac{1-p[i]}{ru[i]}\) f[i][j]表示经过i和j的次数的期望=概率 \(f[i][j]=p[i]*p[j]*f[i][j]\) \(+k[i]*p[...

DP 数论-高斯消元

2019-02-22

0 459

bzoj4008: [HNOI2015]亚瑟王 dp

题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=4008 思路神仙啊 \(f[i][j]表示第i个点有j次机会(不管成功与否)\) \(f[i][j]=f[i-1][j]*(1-p[i-1])^p\) 第i-1个j次都失败 \(f[...

DP

2019-02-22

0 508

bozoj3131: [Sdoi2013]淘金数位dp

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=3131 思路 1. 函数值的素因子只有2、3、5、7 由他们组成的状态不多，爆搜的时候即使搜不对也没关系，我们只是缩小范围而已所以不要管呢么多，搜到几万就差不多了，包含有可能的就行 ...

数位DP DP

2019-02-21

0 402

hdu1358 Period kmp求循环节

链接 http://acm.hdu.edu.cn/showproblem.php?pid=1358 思路当初shenben学长暑假讲过，当初太笨了，noip前几天才理解过来、、我也没啥好说的代码 #include <iostream> #include <cstdi...

kmp

2019-02-21

0 440

cf213E 线段树维护hash

链接 https://codeforces.com/contest/213/problem/E 题目大意给出两个排列a、b，长度分别为n、m，你需要计算有多少个x，使得\(a_1 + x; a_2 + x; a_3 + x、、、 a_n + x\) 是b 的子序列(不连续的那种)。思路...

线段树 hash

2019-02-21

0 541

bzoj2298: [HAOI2011]problem a DP

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2298 思路把一个人的话转化为区间的线段，显然是\([a_{i},n-b_{i}]\) 然后找最大的不相交，不覆盖的最多线段数量注意是有重复的数字，所以不是单纯的线段覆盖 f[i]=m...

DP

2019-02-21

0 530

loj#2305. 「NOI2017」游戏 2-sat

链接 https://loj.ac/problem/2305 https://www.luogu.org/problemnew/show/P3825 思路 3-sat神马的就不要想了，NP问题除去x每个点只有两种可能，2-sat x只有8个，\(3^n\)暴力枚举哪个不选 2-sat是对称性...

2-sat 暴力

2019-02-21

0 578