ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共277篇）

3900: 交换茸角

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=3900 思路状态压缩，f[i]表示只包含i中的所有元素的最小代价所有元素排序后两两配对都不能满足，就是inf 其他的，一定小于等于元素个数-1 orz wxy 收获 1，知道自己啥...

DP 状态压缩

2019-02-26

0 516

CF767C 记录错误

链接 https://codeforces.com/contest/767/problem/C 思路之所以把这个题放进来，是因为要记录错误情况不止一种所以答案存储就是>=2了代码 #include <iostream> #include <cstdio>...

DP

2019-02-26

0 417

bzoj2086: [Poi2010]Blocks DP，单调栈

题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2086 思路这就有点妙了题目意思就是让你求平均数>=k的最长序列先求出a[i]-k的前缀和就是求sum[i]-sum[j]>=0的最大i-j 当\(j<=k&...

单调栈 DP

2019-02-24

0 482

bzoj1566: [NOI2009]管道取珠 DP

题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1566 思路 n个球，第i个球颜色为ai，对于颜色j，对答案的贡献为颜色为j的球的个数的平方 k^2=(1+1+1+..+1)*(1+1++1+..+1) for (i=1; i<...

DP 转化

2019-02-24

0 556

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