Potassium

未归档

题解(1)

/ 注册

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

P2731 骑马修栅栏 Riding the Fences 题解（欧拉回路）

题目链接 P2731 骑马修栅栏 Riding the Fences 解题思路存图+简单\(DFS\)。坑点在于两种不同的输出方式。 #include<stdio.h> #define N 1030 int n,g[N][N],deg[N],m=1024,M=-1; voi...

2019-03-09

0 667

P4847 银河英雄传说V2 题解（Splay）

题目链接 P4847 银河英雄传说V2 解题思路我天哪！！！\(splay\)在\(rotate\)的时候先\(upd(y)\)再\(upd(x)\)！！以后不能再因为这个\(WA\)一晚上了！！！ AC代码 #include<stdio.h> #define ls t[x]...

2019-03-06

0 689

P3160 [CQOI2012]局部极小值题解（状压DP+容斥）

题目链接 P3160 [CQOI2012]局部极小值双倍经验，双倍快乐解题思路存下来每个坑（极小值点）的位置，以这个序号进行状态压缩。显然，\(4*7\)的数据范围让极小值点在8个以内（以下示意） X . X . X . X . . . . . . . . . X . X ...

2019-03-03

0 594

P1092 虫食算题解（搜索）

题目链接 P1092 虫食算解题思路好题啊！这个搜索好难写...... 大概是要考虑进位和考虑使用过某个数字这两个东西，但就很容易出错...... 首先这个从后往前搜比较好想，按照从后往前出现的顺序搜，在这个剪枝条件下速度会快很多。比如样例， 5 ABCED BDACE E...

2019-03-02

0 740

P3387 【模板】缩点题解（Tarjan）

题目链接 P3387 【模板】缩点解题思路这几天搞图论，好有趣hhh，多写几篇博客。上次学\(Tarjan\)求割点，这次缩点。思路大概是多一个栈和染色的步骤，每次\(Tarjan\)的时候把点入栈，如果某个点（比较像割点但不完全是）的\(DFS\)子树都搜不到它祖宗，那么接下来进...

2019-02-27

0 673

P3388 【模板】割点（割顶）题解（Tarjan）

题目链接 P3388 【模板】割点（割顶）解题思路最近学的东西太杂了，多写点博客免得自己糊里糊涂的过去了。这个题求割点，感觉这篇文章写得挺好。割点是啥？如果去掉这个点之后连通图变成多个不连通图了，那这个点就是割点。那我们如何求割点呢？显然，我们可以无视复杂度枚举一下每个点然后\...

2019-02-26

0 772

BuaacodingT141 microhhh的回城题解（模拟）

题目链接 microhhh的回城解题思路这题挺有意思的。本来寻思放在\(DS\)第一次练习赛应该不会很难吧，结果愣是卡在数据范围上写不出来。然后暴力过掉了,但是用了\(1019ms\)。感觉可以继续优化。（放一下暴力代码，不解释了） #include<stdio.h> #...

2019-02-26

0 567

P2055 [ZJOI2009]假期的宿舍题解（二分图）

题目链接 P2055 [ZJOI2009]假期的宿舍解题思路因为懒，提供一种不连边，直接根据题目给出的邻接矩阵进行匈牙利算法的思路。 \(a[i][j]\)表示\(i\)能不能睡\(j\)的床，需要根据具体情况在读入的时候适当调整。 \(inv[i]\)表示第\(i\)个需要在学校睡觉...

2019-02-26

0 661

2019.2-2019.3 TO-DO LIST

DP P2723 丑数 Humble Numbers（完成时间：2019.3.1） P2725 邮票 Stamps（完成时间：2019.3.1） P1021 邮票面值设计（完成时间：2019.3.1） P1070 道路游戏（完成时间：2019.3.2） P2558 [AHOI2002]网络传输（完...

2019-01-31

0 1198

P3369 【模板】普通平衡树题解（Splay/FHQ）

题目链接 P3369 【模板】普通平衡树解题思路1：Splay 注意查询的时候大于小于等于号千万不要搞错了；注意适时伸展 AC代码1 #include<stdio.h> #define root t[0].s[1] struct Tree{ int s[2];//so...

2019-01-28

0 608