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) 杂(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)

/ 注册

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

洛谷P1017 进制转换

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

2019-01-01

0 450

洛谷P1005 矩阵取数游戏

最先很自然地想到贪心，而且确信贪心是对的，实际上太坑了，肯定是错的。反例：10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,8,8,8,8,8,9对于这个序列，按照贪心，先取右边的，最后取10，这样的话这么多大的8就被很小的幂浪费了，先取10的话，后面的8都被高效地利用了...

2018-12-22

0 393

洛谷P1417 烹调方案

https://www.luogu.org/problemnew/show/P1417 这道题不同于普通的01背包，不同的先选择的做菜策略会对之后产生不同的影响，即不满足“无后效性”。但是，考虑一种选择策略，假设有两个先后做的菜i和j，交换他们的顺序会产生什么影响呢？假设ij之前的时间为t ...

2018-12-21

0 328

洛谷P1282 多米诺骨牌

每个骨牌上下相差最多为6-1=5，1000个骨牌最多相差5000，考虑正负，偏移5000，可以开10000大小的数组存上下差值设f(i,j)：前i个骨牌，上比下多j-5000个对应的最少旋转次数。 f(0,5000)=0,f(0,j)=inf f(i,j)=min{f(i-1,j-(a[i]...

2018-12-19

0 342

洛谷 P1020 导弹拦截 & P1233 木棍加工

https://www.luogu.org/problemnew/show/P1020 第一问就是最长不上升子序列，第二问题解说用离散数学里的Dilworth定理，看不懂证明，它的结论是：将序列划分若干个为不上升子序列，使得划分的个数最小，那么这个个数等于序列的最长上升子序列的大小。 #inc...

2018-12-18

0 484

我的高精度模板

高中学的是vector<int>实现的高精度，很不好写。今天学习了字符串数组实现的高精度，直接用数组下标作为位移量，感觉比较自然。就拿它作为今后的模板了。该模板主要来自于大佬https://blog.csdn.net/u013615904/article/details/43373601...

2018-12-15

0 495

洛谷-----普及试炼场-----贪心 p1094纪念品分组 P1803 凌乱的yyy / 线段覆盖

P1803 凌乱的yyy / 线段覆盖对于每个开始时间，只能选择参加一次比赛或者不参加比赛，因此只考虑对于一个开始时间结束最早的比赛。设d（i）为i时间及其之后开始的最多参加的比赛数，则若i时间没有开始的比赛，d（i）=d（i+1），否则d（i）=max（d（i+1），d（i开始的结束时间）+1...

2018-12-06

0 374

洛谷P1309 瑞士轮

https://www.luogu.org/problemnew/show/P1309 看到题目，先想到每局sort一次，简单但一定会超时。然后想到，在一个2*n的有序数组里，每次只有n个元素+1，一定有高效的方法。想到如果用链表或者数组模拟链表，对于每局比赛，输的不管，赢得还保持原来的相对顺序，...

2018-12-06

0 504

广东工业大学2018新生杯决赛

题出的好！难度适中，覆盖知识点广，题目又着切合实际的背景，解法比较自然。给出题人点赞！然而我太菜了，只会8/13，差不多一半不会 A: 文远知行β 题目加粗，n个时刻速度均大于0. #include<cstdio> #include<iostream...

2018-12-02

0 592

洛谷试炼场-----普及-----模拟 P1067多项式输出 P1056 排座椅 P1023 税收与补贴问题 P1031 均分纸牌 P1042乒乓球 P1086 花生采摘 P1098 字符串的展开

P1067多项式输出小细节很多。 #include<iostream> using namespace std; int main() { int n,x; cin>>n; cin>>x; if(x) { if(x!=1&&...

2018-12-01

0 435