Phecda_

未归档

/ 注册

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

LuoGu P3390 【模板】矩阵快速幂

板子传送门今天想去搞一下这个矩阵快速幂嘛（因为考试T2要用矩阵加速，不会QwQ所以来学一学）然后写成了这个样子： #include <iostream> #include <cstring> #include <cstdio> #define F(i,a,...

矩阵快速幂

2018-09-13

0 399

LuoGu P1352 没有上司的舞会

题目传送门这可能是最简单的树形Dp了吧对于每个人，要么他来，他的下属不来要么他不来，他的下属爱来不来于是设计状态： f[i][0/1]表示以i为根的子树中最大能达到的快乐值(i这个人选或者不选) 然后一遍dfs一遍转移就好了 #include <iostream> #inclu...

DP

2018-09-11

0 351

LuoGu P1541 乌龟棋

题目传送门乌龟棋我并不知道他为啥是个绿题0.0 总之感觉思维含量确实不太高（虽然我弱DP）（毛多弱火，体大弱门，肥胖弱菊，骑士弱梯，入侵**，沙华弱Dp）总之，设计出来状态这题就很简单了设 f[i][j][k][l] 表示第一种卡片用了 i 张，第二种用了 j 张，以此类推就好了（我太懒了啦）...

DP

2018-09-11

0 533

LuoGu P2783 有机化学之神偶尔会做作弊

题目传送门人生第一道黑题呢,虽然这题是黑题中的水题并且我调了一整节课,但是我还是很兴奋啊.毕竟人生第一道黑题啊这个题根据题意，先把整个图进行tarjan缩点，建出一棵树，对于每一组询问，两点之间的距离+1就是答案，求出他们的LCA，两点到LCA的距离之和就是两点之间的距离然后....LCA我采...

tarjan缩点 SCC 树链剖分

2018-09-11

0 471

LuoGu P1006 传纸条

题目传送门这题嘛...方格取数和这题一样一样的只不过这题是从左上到右下再回去罢了（来回一趟和来两趟有区别么？没有，那么这题和上题用一样的转移和状态就行了没什么好说的，说一下我的错误好了：人家图是nm的，我给存成了nn的（即使这样还是得了60分）读入对了后，转移的时候又成了n*n的...

DP

2018-09-06

0 329

LuoGu P1083 借教室

题目传送门借教室这个题有两种做法，差分+前缀和或者是线段树线段树维护区间最小值，因为能不能借教室使用是由这几天中可用教室最少的一天决定的其实这题是个很裸的线段树维护区间最小值，但有一点需要注意，区间最小值在进行加减修改时不能乘以区间长度很简单，不论区间长度怎么样，你整个区间-x，最小...

二分答案线段树差分前缀和

2018-09-06

0 478

LuoGu P1004 方格取数

题目传送门一开始这个题我是不会的(沙华弱DP啊QwQ)，后来考完试我一想，这东西怎么和数字三角形那题这么像啊？都是自上而下，只能向下或者向右，求一个max 那么...这不就是个走两遍的数字矩阵嘛转移方向都没换:对于(i,j)，只能由(i-1,j)或(i,j-1)转移过来转移解决了，那...

DP 网络流

2018-09-06

0 529

LuoGu P2735 电网 Electric Fences

题目传送门这个东西，本来我是用求出两条一次函数解析式然后判断在x坐标下的y坐标值来做的首先因为没考虑钝角三角形，WA了然后又因为精度处理不好又WA了一气之下，只能去网上查了查那个皮克定理首先用皮克定理需要知道：在(0,0)到(n,m)这条线段上的整点个数有gcd(n,m)+1个，...

计算几何皮克定理

2018-09-06

0 293

线段树【注意事项】

乘标记由于乘法分配律的存在，直接乘就好了但是，加标记，一定要记得乘上节点所管辖的区间长度！！！一定要记得乘上节点所管辖的区间长度！！！一定要记得乘上节点所管辖的区间长度！！！（重要的事情说三遍）就这些了...

线段树

2018-05-27

0 359