ComplexPug

分类

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

/ 注册

全部文章（共277篇）

luoguP4072 [SDOI2016]征途

[SDOI2016]征途大体大概就是推推公式，发现很***的\(n^3\)DP get60 进一步我们发现状态不能入手，考虑优化转移套个斜率优化板子每一层转移来一次斜率优化思路先便便式子 \[s^2=m^{2}*\frac{\sum_{1}^{m}(a_{i}-\overline...

DP 斜率优化

2019-01-04

0 616

P2761 软件补丁问题

P2761 软件补丁问题思路貌似不用网络流，直接状态压缩用spfa跑最短路，直接判断是否能过位运算太渣了，WA了好几发代码 #include <bits/stdc++.h> using namespace std; const int N = 21, M = 101, ...

DP 状态压缩

2018-12-28

0 419

12.27 cf div3 解题报告

12.27 cf div3 解题报告 wxy.wxy,带上分拉，全场做了个无脑小白比赛场地 A： T1，跟着模拟就好了 B： sort一遍之后去除的数一定是a[1]或者a[n] 比较去除谁小就输出谁 C：他的二进制有多少个1 如果>k说明无解他的二进制位都放优先队列里 ...

CF

2018-12-28

0 518

网络流24题 P2754 [CTSC1999]家园

思路如图,建立分层图跑dinic 每次在残余网络里加边继续跑跑到ans>=k时候的i就是答案诶呀啊，忘记弄箭头了，最后一列是向上的箭头，不过聪明的你们应该没啥影响代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(i...

网络流最大流

2018-12-27

0 529

P3690 【模板】Link Cut Tree （动态树）

P3690 【模板】Link Cut Tree （动态树）思路 candy 不是太掌握也落落不太清楚自己学习吧 lmc讲的时候睡着了 #include<bits/stdc++.h> #define ls c[x][0] #define rs c[x][1] const int...

伸展树splay LCT

2018-12-26

0 528

P2147 [SDOI2008]洞穴勘测

P2147 [SDOI2008]洞穴勘测思路没办法，我就是喜欢板子都想发的人都是基础操作，不多说了代码 #include <bits/stdc++.h> #define ls ch[x][0] #define rs ch[x][1] #define FOR(i,a,b) ...

伸展树splay LCT

2018-12-26

0 521

P3203 [HNOI2010]弹飞绵羊

P3203 [HNOI2010]弹飞绵羊思路每个点都往后面连边所以肯定没有环超过n的算连向n+1 n+1个点，n条边，没有环，一定联通那就差不多是个树了然后就LCT模拟他的操作就行有比较简单的LCT做法，不过我还是喜欢无脑一点的错误 cut操作x写错i 代码 #inclu...

线段树 LCT 伸展树splay

2018-12-26

0 495

P4172 [WC2006]水管局长

P4172 [WC2006]水管局长前言 luogu数据太小去bzoj，他的数据大一些思路正着删不好维护那就倒着加，没了 LCT维护他的最小生成树MST 树上加一条边肯定会有一个环看看环上最大值和加边的大小然后选择加不加，改不改错误哇，恶心撒怼着题解都写不出来最后乱...

线段树 LCT 伸展树splay

2018-12-26

0 428

P3979 遥远的国度

P3979 遥远的国度思路一开始我用这个函数得到左端点 int get_l(int x,int y) { if(top[x]==top[y]) return son[x]; int last=top[x]; while(top[x]!=top[y]) { ...

线段树树链剖分

2018-12-26

0 453

P3128 [USACO15DEC]最大流Max Flow

思路这个题哪里有那么费脑筋我们可以树链剖分嘛LCT昨天学的时候睡着了，不是太会两遍dfs+一个5行的BIT 其实树链剖分学好了对倍增和LCT理解上都有好处一条路径上的修改由于一条剖出来的链是连续的，我们要选择数据结构维护不过这里不用维护太多东西，只是区间+1 我们可以选择常数小，好写的...

树状数组树链剖分

2018-12-26

0 517