开开心心写

ACM题解

ACM - dp(1) ACM - 二分(8) ACM - 数学(1) ACM - 矩阵(1) ACM-线段树(1) Android(3) angr(3) Crypto(5) CTF之旅(84) Linux(8) pwn(1) python(6) reverse(3) ubuntu(1) Windows(4) 大作业(1) 恶意代码分析实战(43) 数学(4) 数据结构专题班(15) 未归档(4)

/ 注册

全部文章 / ACM题解（共245篇）

codeforces 348A Mafia

先贴一个有数学公式的题解题解题意： n个人，其中每个人最少参加Ai次比赛。比赛是这样定义的：n个人之中出1个裁判，其中n-1个人参加问：最少需要多少场比赛可以满足题目要求？看到最少，然后 sum { A【i】} 是肯定可以的，0是肯定不行的。想到了什么？二分答案。...

2020-05-03

0 487

codeforces 348B B. Apple Tree(dfs+数论)

这个题我一开始是当作树形dp搞的题解：戳我其实树上的dfs想成了树形dp，也是没走太多弯路的但是为什么处理错了？因为维护的方向和数值不对维护的方向应该是从父亲的方向推到儿子的方向，但是基本树形dp都是从儿子维护到父亲想想：如果当前节点u，有三个孩子，每个孩子有a...

2020-05-03

0 488

POJ 3132 Sum of Different Primes 【01背包】

背包题还是太难太难，不是公式难，是理解公式运用公式太难把n拆分成k个不同素数的和，有多少种方法。n不超过1120，k不超过14，一看就是个打表的题首先把所有素数打表出来然后，打表dp【i】【j】：把i拆分成j个不同的素数的和的方案数是多少这个不同怎么来理解？用01背包来理解...

2020-05-03

0 432

HDOJ 5952 Counting Cliques【2016沈阳现场赛】【暴力】

暴力姿势永远学不会的姿势先说题意：n点m条边，问图中有多少种情况是：有s个点两两相连（问子图的独立团，其中点数为s）看到数据量其实并不大，n是100，m是1000，s最大为10 还有一句话：It is guaranteed that the maximum degree of th...

2020-05-03

0 334

HDOJ 5943 Kingdom of Obsession【2016杭州现场赛】【二分图匹配暴力】

现场赛的铜牌题，没有搞出来挺遗憾的题意：如果i%j==0，那么说（i，j）是可以匹配的题目问：（s+1，s+2，……，s+n），（1，2，……，n）这两个数组能否找到某种对应方式，使得完全匹配（也就是说等于n）一开始的思路是：素数是很特殊的数，当值很大的时候，（s+1，s+2，...

2020-05-03

0 382

POJ 2186 Popular Cows【强连通】

因为杭州B题是个强联通，而且90+队伍会，弱不会，所以来学一学这个专题从最简单的模板题应用开始 n个人，m条边。（A，B）的边意味着A认为B是好人，这种关系具有传递性，即如果有（A，B）和（B，C）边在图中，那么A认为C是好人给定n个人和m条边问：图中有多少个人，他们被所有的人都认...

2020-05-03

0 460

HDOJ 5934 Bomb【2016杭州现场赛】【强连通】

全场90+个队伍过的图论模板题，自己太弱想当成网络流建图来补完强连通的算法之后，发现：就是模板题题意：题中有n个炸弹，其中每个炸弹有4个数据，坐标位置（x，y），引爆炸弹需要的费用c，引爆之后可以影响的范围半径r 问，我最少需要多少费用，才能把这些炸弹全部引爆！这个题比POJ...

2020-05-03

0 337

codeforces #378 Div2 ABCD题解

做了几场CF的Div2级别的比赛，终于从这一场知道怎么上分了（因为自己很菜，还是1500+，所以上分很简单。。。）先说说做题的心态： A题B题，看完样例，看完特判，直接求手速，一般不会卡太多太难的数据只需要保证：如果题目中有Hint好好看看，题目中有无法达成目标，然后需要输出-1或者无解信...

2020-05-03

0 373

HDOJ 4635: Strongly connected 【强连通】

题意：图中有n个点，m条有向边。保证不含有自环和重边问：我们最多可以添加多少条边，使得原图不是强连通的首先：去掉不是强连通的条件：我们可以添加的总边数为：n*（n-1）-m 所以：如果原图已经是强连通了：那么答案为-1 需要特判吗？不需要！那么该题第一步就是用模板，缩点强连通...

2020-05-03

0 537

POJ 1236 Network of Schools【强连通缩点】

两边dfs还是好想好实现，就是不跟大众走，不用Tarjan 题意：有n个点，输入的时候比较奇怪，给的是第n个点与那些边相连，以0为结束符号，都是有向边需要求两个值第一个：我们要保证所有的点都能够得到消息，那么最少需要选取几个点来初始传送第二个：我们想让任何一个点都能作为起点（那么...

2020-05-03

0 487