SSuryxin

分类

ACM个人赛题解(2) CF(1) dp(2) 图论(12) 数论(1) 笔记(5) 题解(29)

/ 注册

TA的专栏 3篇文章 0人订阅

3篇文章 1160人学习

全部文章（共52篇）

可达性

可达性题目描述：给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图，输出一个尽可能小的点集，使得从这些点出发能够到达任意一点，如果有多个这样的集合，输出这些集合升序排序后字典序最小的。 u1s1，这个题目描述讲的很难懂，你说是阅读理解都不为过，特别是最后一句，什么叫...

tarjan 缩点链式前向星拓扑排序

2021-08-13

0 764

Antenna Placement

Antenna Placement 题目描述： N * M的棋盘中，'o'代表障碍物，'*'代表空位，你可以使用1 * 2的多米诺骨牌放进空格，米牌可以重叠，也可以放在障碍物上，问最少使用多少牌使得放满所有空位思路：和上次那个棋盘问题很相似了，不过这次可以重叠了，那我们只需要计算出最大匹配...

匈牙利算法二分图最大匹配二分图二分图匹配

2021-08-09

1 505

题解 | #棋盘覆盖#

棋盘覆盖题目描述： N * N的棋盘，已知某些位置不能放东西，求最多能往棋盘上放多少块1 * 2的多米诺骨牌，可以横着放，也可以竖着放，且任意两张多米诺骨牌都不重叠思路：都不重叠，就有点像二分图左右两集合内没有边相连的那意思了有点绕其实，因为多米诺骨牌是1 * 2的，我们就将其看成一个...

匈牙利算法二分图最大匹配二分图二分图匹配

2021-08-07

0 701

题解 | #[ZJOI2007]矩阵游戏#

[ZJOI2007]矩阵游戏题目描述：给你一个N*N的矩阵，0代表白色，1代表黑色，你可以任意交换矩阵的两行或两列，问交换若干次能否使得方针的主对角线的颜色均为黑色思路：首先思考一下交换行和交换列的目的交换行，假设该行最终交换到了第 i 行，也就是代表该行的第 i 个元素必须是黑色，...

二分图最大匹配匈牙利算法二分图二分图匹配

2021-08-07

1 686

题解 | #Asteroids#

Asteroids 题目描述：给你一个n*n的地图，地图上有些点有外星生物，你有太空武器，一次可以杀死一行或一列的外星生物，问你最少需要几次攻击能杀死全部的外星生物？思路：感觉这个题见了很多次，但好像又没有写过？贪心是肯定不行的，举个例子：如果挑最多的一行或一列去贪心的选的话就会...

二分图最大匹配匈牙利算法二分图

2021-08-07

0 484

题解 | #Going Home#

Going Home 题目描述：给你一张n * m的地图，里面有若干个小人，用'm'表示，同样的，有相同数量的房子，用'H'表示，每个人可以进入任意一个房子，不过每个房子只能住一个人，现在你需要计算所有人住满房子最少需要走多少步思路：因为房子数量=人的数量，所以是在二分图的完美匹配的基础...

二分图匹配 KM算法二分图完美匹配

2021-08-07

1 578

题解 | #[ZJOI2009]假期的宿舍#

[ZJOI2009]假期的宿舍题目描述：学校放假了，有些同学放假回家了，有些同学不回家，而不回家的同学的非本校的朋友要到学校和他一起搞基，但是非本校的学生没有床位，这就需要进行床位转借，人总是会睡自己或自己认识的人的床，问能否存在一个方案使得所有不回家的学生和来和他们搞基的学生都有地方住思...

二分图匈牙利算法二分图最大匹配

2021-08-07

1 439

第十八届同济大学程序设计竞赛暨高校网络友谊赛（部分

自适应树游走协议题目描述：在计算机网络中，当多个站点试图通过同一个信道同时进行传输时，传输的数据会出现乱码，这称为冲突。自适应树游走协议（Adaptive Tree Walk Protocol**）是一种避免冲突的方法。它将所有使用同一个信道的站点使用一棵完全二叉树组织起来，每个叶子**代表一个...

2021-05-25

1 898

浅谈扩展欧几里得算法

什么是拓展欧几里得？简单的说，就是求关于x,y的方程 ax + by = gcd(a,b) 的所有整数解现在我们来解决四个问题什么是裴属定理，如何证明裴属定理？怎么用扩展欧几里得来求ax + by = gcd(a,b) 的特解？怎么求由特解推出其他的所有解？扩展欧几里得的...

扩展欧几里得数论

2021-05-20

1 537

分治

题目描述：给出一个表达式,其中运算符仅包含+,-,*,/,^（加减乘整除乘方）要求求出表达式的最终值数据可能会出现括号情况，还有可能出现多余括号情况数据可能会出现负数的情况思路：分治通过运算符将整个表达式一次次分割来计算根据优先度低的运算符来分割表达式，这样分治到最后进行...

递归表达式求值分治

2021-05-12

0 542