AFreeMan

分类

BFS(1) CDQ分治和整体二分(1) Codeforces(15) DFS(4) GDUT训练(8) KMP(1) MST(1) RMQ(2) Trie(1) 二分(3) 几何(2) 区间型DP(5) 单调栈(3) 容斥原理(2) 尺取(1) 差分(1) 广工新生赛题解(1) 序列型DP(1) 思维(1) 拓扑排序(1) 排序(3) 搜索(2) 数位DP(5) 数论(9) 无向图双连通分量(1) 最短路(8) 未归档(95) 杂(5) 栈/(优先)队列/链表(1) 树形DP(2) 树链剖分(2) 棋盘型DP(4) 概率/期望DP(3) 模拟退火(1) 物理(1) 状压型DP(9) 矩阵快速幂(2) 线性DP(4) 线段树/树状数组(8) 组合数学(1) 缩点(不仅SCC)(1) 网络流(4) 背包型DP(4) 莫队算法(2) 贪心(3) 题解(3)

/ 注册

全部文章（共238篇）

洛谷P1080 国王游戏

https://www.luogu.org/problemnew/show/P1080 这道题要获奖赏最多的大臣所获奖赏尽量低，但是是不能二分的，因为不能根据一个最多获奖赏数额来确定最优排序。考虑一个已经排好序的序列，看第i-1和i个大臣，设前i-2个大臣的左手之积是x，第i-1个大臣左ai-...

2019-01-05

0 491

洛谷P1074 靶形数独

https://www.luogu.org/problemnew/show/P1074 这道题单独以每个位置递归纯暴力搜索的话，复杂度9^81，考虑剪枝，和八皇后类似，在同一行同一列同一宫则不能放。另外，想象解答树，先搜索情况少的位置和先搜索情况多的位置总结点数是一样的，不一样的地方在于先搜情况少...

2019-01-04

0 466

洛谷P1092 虫食算

https://www.luogu.org/problemnew/show/P1092 这题如果直接暴力枚举的话，复杂度(26!)=4.0329146112661e+26. 然后用科学的剪枝居然玄学地下降到不足1e+8？？？剪枝1：若加数最高位加起来大于n，则剪掉，因为最高位不能进位。剪...

2019-01-02

0 448

洛谷P1040 加分二叉树

https://www.luogu.org/problemnew/show/P1040 这道题看上去是二叉树，实际上就是一个简单的区间DP，因为其中序遍历是1~n，可按区间dp的方法做。设f(i,j):编号i~j的子树的最大分数。则以树根划分，f(i,j)=max{f(i,k-1)*f(k...

2019-01-02

0 419

洛谷P1019 单词接龙

https://www.luogu.org/problemnew/show/P1019 先预处理任意两个单词是否能相连及重叠长度，注意重叠长度必须小于两个字符串的长度。然后跑一遍dfs就好了。 #include<iostream> #include<cstdio> ...

2019-01-02

0 460

洛谷P1045 麦森数

https://www.luogu.org/problemnew/show/P1045 第一问：2^p-1的位数，就是log10(2^p-1)+1向下取整第二问：(2^p-1)%(10^500).需要用高精度快速幂，暴力会超时。保留后500位在高精度里实现就好了。快速幂非递归：利用 ...

2019-01-01

0 508

洛谷P1017 进制转换

https://www.luogu.org/problemnew/show/P1017 在正进制中，既有负数又有正数，但在负进制中，基数的幂次方偶正奇负，因此负进制下只有正数。转换方法和正进制差不多，都是除k取余法，利用了秦九韶算法的思想。但是，举个例子，要把325转为-10进制， 32...

2019-01-01

0 450

Windows & Linux 对拍

这个内容直接从我的老blog搬过来。 1.首先，暴力程序 baoli.cpp #include<iostream> using namespace std; int main() { int a,b; c...

2018-12-23

0 425

洛谷P1026 统计单词个数

https://www.luogu.org/problemnew/show/P1026 对这句话“当选用一个单词之后，其第一个字母不能再用”需要特殊处理一下，贪心，如果包含this，th，t则等价于只包含t，即几个单词开头相等并且有完全包含关系，则保留最短的那个即可，针对上述3个单词给个例子：th...

2018-12-23

0 563

洛谷 P1541 乌龟棋

https://www.luogu.org/problemnew/show/P1541 2年前做过这道题，不过早就忘了怎么做的了。看到题，先想到用f(p,i,j,k,l)表示当前在位置p，手中有i,j,k,l张四种面值的卡片，已经得到的分数，则f(p,i,j,k,l)=max{f(p-1,...

2018-12-23

0 469