Nitrogens Xu-CSDN博客

原创 Training Log of Segmentation Fault

DateContestRankABCDEFGHIJKLM2019/04/032019/04/032019/04/032017-2018 ACM-ICPC East Central North America Regional Contest (ECNA 2017)12/13412/13412/134..OOOOOO.O...

2019-04-04 16:37:36 159

原创 2018 杭电多校 - 乱搞题目

2018 杭电多校 - 乱搞题目果然乱搞能力才是王道！1. HDU - 6299 - Balanced Sequence（贪心）题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6299题目来源：2018 HDU 多校第一场1.1 题意给你 n(1≤n≤105)n(1 \le n \le 10^5)n(1≤n≤105) 个括号串，每个括号...

2019-10-06 11:03:49 567

原创 2018 杭电多校 - 图论题目

2018 杭电多校 - 图论题目这些题是真的硬核啊！1. HDU - 6321 - Dynamic Graph Matching（状压 dp）题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6321题目来源：2018 HDU 多校第三场 - C 题出题人：Claris（%%%）1.1 题意给你一个 n(1≤n≤n,2∣n)n(1 \l...

2019-10-05 20:42:48 636

原创 CCPC-Wannafly Winter Camp - 数论（Div. 1）- 同余理论习题

CCPC-Wannafly Winter Camp - 数论（Div. 1）- 同余理论习题感谢 tangjz 的精彩讲解以及有趣的题单！本文中的题意全部来自原 Slideshow。1. Codeforces - 194B - Square（同余的性质）题目链接：https://codeforces.com/problemset/problem/194/B难度：130013001300...

2019-10-05 14:14:57 2131

原创 Codeforces - 图论题目（难度：2200）

Codeforces - 图论题目（难度：2200）AC 之后不写题解，赛前火葬场！！1. 507E - Breaking Good（最短路 + 松弛条件改造）题目链接：https://codeforces.com/contest/507/problem/E1.1 题意给你一个 n(2≤n≤105)n(2 \le n\le 10^5)n(2≤n≤105) 个点和 m(0≤m≤min⁡(n...

2019-10-03 21:03:42 1488

原创 CCPC-Wannafly Winter Camp - 数论（Div. 1）- 整除理论习题

CCPC-Wannafly Winter Camp - 数论（Div. 1）- 整除理论习题感谢 tangjz 的精彩讲解以及有趣的题单！本文中的题意全部来自原 Slideshow。1. Codeforces - 664A - Complicated GCD（最大公约数性质的应用）题目链接：https://codeforces.com/contest/664/problem/A难度：90...

2019-10-03 14:09:12 9967

原创 2-SAT 习题

2-SAT 习题1. Codeforces - 468B Two Sets1.1 题意给定 n(1≤n≤105)n(1 \le n \le 10^5)n(1≤n≤105) 个互不相同的数 pi(1≤pi≤109)p_i(1 \le p_i \le 10^9)pi(1≤pi≤109)，现在要将它们分成两个集合 AAA 和 BBB，并满足以下两个条件：如果 x∈Ax \in Ax∈A，...

2019-10-02 17:03:13 454

原创 Codeforces - 1102F - Elongated Matrix（建图 + 哈密顿通路）

题目链接：https://codeforces.com/problemset/problem/1102/F15.1 题意给你一个 n(1≤n≤16)n(1 \le n \le 16)n(1≤n≤16) 行 m(1≤m≤104)m(1 \le m \le 10^4)m(1≤m≤104) 列的矩阵 a(1≤ai,j≤109)a(1 \le a_{i,j} \le 10^9)a(1≤ai,j≤10...

2019-10-02 11:21:57 271

原创 Codeforces - 1027F - Session in BSU（建图 + 并查集）

题目链接：https://codeforces.com/contest/1027/problem/F14.1 题意有 n(1≤n≤106)n(1 \le n \le 10^6)n(1≤n≤106) 场考试，每场考试 iii 可以选择在第 aia_iai 天或者第 bib_ibi(1≤ai<bi≤1091 \le a_i < b_i \le 10^91≤ai<bi≤10...

2019-10-02 10:48:20 229

原创 Codeforces - 772C - Vulnerable Kerbals（同余 + 建图 + 拓扑排序）

题目链接：https://codeforces.com/problemset/problem/772/C13.1 题意给定一个整数 m(1≤m≤2⋅105)m(1 \le m \le 2 \cdot 10^5)m(1≤m≤2⋅105)，和 n(0≤n<m)n(0 \le n < m)n(0≤n<m) 个整数。现在需要构造出一种满足以下要求的序列：每个元素都在 [0,m−...

2019-10-02 10:47:15 400

原创 Codeforces - 732F - Tourist Reform（Tarjan + 贪心）

题目链接：https://codeforces.com/problemset/problem/732/F12.1 题意给定一个 n(2≤n≤4⋅105)n(2 \le n \le 4 \cdot 10^5)n(2≤n≤4⋅105) 个节点和 m(1≤m≤4⋅105)m(1 \le m \le 4 \cdot 10^5)m(1≤m≤4⋅105) 条边的无向连通图，保证没有自环和重边。现在要给每...

2019-10-02 10:46:13 298

原创 Codeforces - 825E - Minimal Labels（优先队列上的拓扑排序）

题目链接：https://codeforces.com/problemset/problem/825/E11.1 题意给出一个 n(2≤n≤105)n(2 \le n \le 10^5)n(2≤n≤105) 个节点和 m(1≤m≤105)m(1 \le m \le 10^5)m(1≤m≤105) 条边的有向无环图，保证没有自环和重边，但不保证图联通。现在要给每个点编号，范围为 [1,n][1...

2019-10-02 10:45:16 206

原创 Codeforces - 894E - Ralph and Mushrooms（Tarjan + 拓扑序 dp）

题目链接：https://codeforces.com/problemset/problem/894/E10.1 题意给定一个 n(1≤n≤106)n(1 \le n \le 10^6)n(1≤n≤106) 个点和 m(0≤m≤106)m(0 \le m \le 10^6)m(0≤m≤106) 条边的有向图，每条边 iii 的权值为 wi(0≤wi≤108)w_i(0 \le w_i \le ...

2019-10-02 10:43:33 224

原创 Codeforces - 1213F - Unstable String Sort（建图 + 拓扑序 dp）

题目链接：https://codeforces.com/problemset/problem/1213/F9.1 题意给你两个长度为 n(1≤n≤2⋅105)n(1 \le n \le 2 \cdot 10^5)n(1≤n≤2⋅105) 的排列 ppp 和 qqq，现在需要构造一个至少有 k(1≤k≤26)k(1 \le k \le 26)k(1≤k≤26) 个不同字母的字符串 sss，并且满...

2019-10-01 21:04:46 258

原创 Codeforces - 1038E - Maximum Matching（欧拉回路 + 建图）

题目链接：https://codeforces.com/contest/1038/problem/E8.1 题意有 n(1≤n≤100)n(1 \le n \le 100)n(1≤n≤100) 个条带，每个条带的格式为 [color1|value|color2]\texttt{[color1|value|color2]}[color1|value|color2](1≤color≤4,1≤val...

2019-10-01 19:27:34 264

原创 Codeforces - 845G - Shortest Path Problem?（DFS + 线性基）

题目链接：https://codeforces.com/contest/845/problem/G7.1 题意给定一个 n(1≤n≤105)n(1 \le n \le 10^5)n(1≤n≤105) 个节点和 m(n−1≤m≤105)m(n-1 \le m \le 10^5)m(n−1≤m≤105) 条边的无向连通图，定义一条路径的长度为这条路径上边权的异或和。问从 111 点到 nnn 点...

2019-10-01 16:53:11 228

原创 Codeforces - 962F - Simple Cycles Edges（Tarjan 求点双）

题目链接：https://codeforces.com/contest/962/problem/F6.1 题意给定一个 n(1≤n≤105)n(1 \le n\le 10^5)n(1≤n≤105) 个节点和 m(0≤m≤min⁡(n(n−1)2,105))m(0 \le m \le \min(\frac{n(n-1)}{2},10^5))m(0≤m≤min(2n(n−1),105)) 条边的...

2019-10-01 16:13:43 337

原创 Codeforces - 1005F - Berland and the Shortest Paths（BFS 建立分层图）

5.1 题意给你一个 n(2≤n≤2⋅105)n(2 \le n\le 2 \cdot 10^5)n(2≤n≤2⋅105) 个节点和 m(n−1≤m≤2⋅105)m(n-1\le m \le 2 \cdot 10^5)m(n−1≤m≤2⋅105) 条边的无向图，保证没有自环和重边。现在需要你构造一棵生成树，使得 111 号点经过生成树到达 [2,n][2,n][2,n] 各个节点的路径长度之和最...

2019-10-01 15:32:44 254

原创 Codeforces - 1042F - Leaf Sets（贪心 + 乱搞）

4.1 题意给定一棵 n(3≤n≤106)n(3 \le n \le 10^6)n(3≤n≤106) 个节点的无向树和一个整数 k(1≤k≤106)k(1 \le k \le 10^6)k(1≤k≤106)。定义一个叶子集合是 beautiful 的，当且仅当集合中任意一对叶子的距离都不超过 kkk。现在要将这棵树的叶子节点进行划分，问最少划分出几个集合，使得这些集合都是 beautiful...

2019-10-01 13:31:50 192

原创 Codeforces - 1120D - Power Tree（差分 + 建图 + 最小生成树）

题目链接：https://codeforces.com/contest/1120/problem/D3.1 题意给你一棵有 n(2≤n≤2⋅105)n(2 \le n \le 2 \cdot 10^5)n(2≤n≤2⋅105) 个节点的有根树，根为 111。每个节点 iii 都有一个价格 ci(0≤ci≤109)c_i(0 \le c_i \le 10^9)ci(0≤ci≤109)。Ar...

2019-10-01 12:13:41 313

原创 Codeforces - 160D - Edges in MST（最小生成树 + Tarjan）

题目链接：https://codeforces.com/contest/160/problem/D2.1 题意给定一个 n(2≤n≤105)n(2 \le n \le 10^5)n(2≤n≤105) 个点，m(n−1≤m≤min⁡(105,n(n−1)2))m(n-1 \le m \le \min(10^5,\frac{n(n-1)}{2}))m(n−1≤m≤min(105,2n(n−1))...

2019-10-01 11:32:38 331

原创 Codeforces - 1139E - Maximize Mex（建图 + 二分图匹配）

1.1 题意有 nnn 名学生和 m(1≤m≤n≤5000)m(1 \le m \le n \le 5000)m(1≤m≤n≤5000) 个分组，每个学生 iii 都有能力 pi(0≤pi<5000)p_i(0 \le p_i < 5000)pi(0≤pi<5000) 和其所在分组编号 ci(1≤ci≤m)c_i(1 \le c_i \le m)ci(1≤ci≤m)。...

2019-10-01 10:41:10 240

原创杜教筛和 min_25 筛基础习题

杜教筛和 min_25 筛基础习题这篇博客记录了自己最近几个月所刷的数论函数题目，所以有些题目可能不需要用到杜教筛或者 min_25 筛。某些题需要一些乱搞的技巧。感谢 tangjz 提供大量题目。1. HDU - 5608 function题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=56081.1 题意定义：n2−3n+2=∑d∣n...

2019-10-01 09:47:56 1505 1

原创 Codeforces - 图论题目（难度：2000）

欢迎访问本菜鸡的独立博客：CodechoSummary: 感觉只有 14\frac{1}{4}41 的题目比较硬核，能学到些东西；剩下的题目比较水，以 DFS 为主。463D - Gargari and Permutations (建图 + 拓扑序上dp)1. 题意给你 kkk 个长度为 nnn 的排列，问它们的最长公共子序列的长度。数据范围：1≤n≤103;2≤k≤51 \le n ...

2019-05-04 22:51:03 5454

原创莫比乌斯反演例题

UPDATED on Apr.22,2019\text{Apr}. 22, 2019Apr.22,2019.0. 套路(1)(1)(1) [n=1]=∑d∣nμ(d)\left[ n=1 \right] =\sum_{d|n}{\mu \left( d \right)}[n=1]=∑d∣nμ(d)(2)(2)(2) ∑i=1a∑j=1b[gcd(i,j)=d]=∑i=1⌊ad⌋∑j=...

2019-04-22 14:04:11 1072 3

原创 Codeforces Round #547 (Div. 3)（A、B、C、D、E、F1、F2、G）

欢迎访问本菜鸡的独立博客：Codecho比赛名称Codeforces Round #547 (Div. 3)比赛链接https://codeforces.com/contest/1141比赛情况解题数：4/84/84/8补题数：8/88/88/8排名：839839839比赛总结好久没打cf了，可是这场cf还是没有改变自己打cf场场崩的局面。已经自闭一个月了。A题签到，5mi...

2019-03-20 19:34:41 249

原创 Codeforces Round #544 (Div. 3)（A、B、C、D、E、F1、F2）

比赛名称Codeforces Round #544 (Div. 3)比赛链接https://codeforces.com/contest/1133比赛情况解题数：4/74/74/7补题数：7/77/77/7排名：968968968比赛总结自从自己上了 176817681768 分以来，打了很多场，状态都非常差，都很自闭，真的不知道为什么。也许是因为这种比赛有很多不确定性？？但...

2019-03-08 15:04:23 552

原创 Educational Codeforces Round 61 (Rated for Div. 2)（A、B、C、D、E、F）

比赛名称Educational Codeforces Round 61 (Rated for Div. 2)比赛链接https://codeforces.com/contest/1132比赛情况解题数：2/72/72/7补题数：5/75/75/7排名：139313931393比赛总结你是刚学ACM吗？？怎么才两道题？？怎么回事啊？？是不是这几天没训练啊？？等着回家挨揍！！...

2019-03-06 18:22:22 361 2

Nitrogens的博客