回归梦想

分类

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2) 题解(271)

/ 注册

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

16篇文章 978人学习

牛客每日一题

6篇文章 776人学习

0篇文章 0人学习

0篇文章 0人学习

0篇文章 0人学习

3篇文章 685人学习

ACwing寒假每日一题（提高组）

3篇文章 780人学习

13篇文章 912人学习

全部文章（共34篇）

[网络流24题]P3254圆桌问题

题目：假设有来自n 个不同单位的代表参加一次国际会议。每个单位的代表数分别为ri, i=1,2,...,n。会议餐厅共有m张餐桌，每张餐桌可容纳ci (i=1,2,...,m)个代表就餐。为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。...

ing *** 网络流

2021-01-16

0 623

NC213818 [网络流24题]魔术球问题

例2：NC213818 [网络流24题]魔术球问题题目： • 假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。（1）每次只能在某根柱子的最上面放球。（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。试设计一个算法，计算出在n根柱子上最多能放多少个球。例如...

匈牙利算法 *** 网络流

2021-01-15

0 762

NC50403 [ZJOI2004]嗅探器

NC50403 嗅探器题目： • 某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络，蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息，但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。现在需要你尽快...

*** tarjan 割点

2021-01-14

1 795

NC51272 棋盘覆盖

题目：给出一张n×n(n≤100) 的国际象棋棋盘，其中被删除了一些点，问可以使用多少1*2的多米诺骨牌进行掩盖。题解：先进行黑白染色，相邻的两个黑白就是一个骨牌，又因为一个格子不能放多个骨牌，所以相当于找每个格子的搭档（搭档即为相邻的点），使得搭档的数量足够多裸的二分图最大匹配代码：

二分图匹配 ***

2021-01-14

0 779

NC204871 求和

题目描述已知有 n 个节点，有 n−1 条边，形成一个树的结构。给定一个根节点 k，每个节点都有一个权值，节点i的权值为vi。给 m 个操作，操作有两种类型：1 a x ：表示将节点 aa 的权值加上 x2 a ：表示求 a 节点的子树上所有节点的和（包括 a 节点本身）题解：通过dfs序将...

树状数组 dfs序线段树 ***

2020-11-27

2 569

D - Take Your Seat

题意：飞机出发时有n个座位，一共n个人，Duha编号为1，每个人都有自己的编号，上飞机按照编号从小到大，Duha会随便选一个位置，后面的人如果发现自己的座位被选也会随机选其他座位，如果自己的座位没被选就会坐到自己的位置，问最后一个人做到自己座位的概率飞机回来时有m个座位，一共m个人，这次不按照顺序...

概率 *** 思维

2020-11-26

2 649

B - Rolling The Polygon

题意：一个n边型，给出n个顶点，在给你一个图形内部的一点x，然后n边型沿着边开始滚动，每个边只滚动一次，问x的运动距离题解：很好想，每次滚动都是弧形距离 = 弧度 * 半径距离求和就行弧度可以由角度得到角度可以由余弦定理得到但是我计算几何做的不多。。。求其弧度来及其费力代码： #includ...

计算几何 ***

2020-11-26

1 521

"Split Game" 与 "剪纸游戏" 的对比与分析

Split Game 是2020ICPC 江西省大学生程序设计竞赛的题剪纸游戏是acwing的一个博弈论题我们对比两个很相似但是不一样的博弈论问题题意： Split Game ：一张n * m的纸，两个人轮流操作，可以沿着一条直线切，当有人切出1 * 1的纸时即为输掉比赛，问最后谁赢剪纸游戏：一...

博弈论 ***

2020-11-21

2 878

高手过招 P2575

题目描述AKN玩游戏玩累了，于是他开始和同伴下棋了，玩的是跳棋！对手是wwx！这两位上古神遇在一起下棋，使得棋局变得玄幻莫测，高手过招，必有一赢，他们都将用最佳策略下棋，现在给你一个n*20的棋盘，以及棋盘上有若干个棋子，问谁赢？akn先手！游戏规则是这样的：对于一个棋子，能将它向右移动一格，如...

sg函数博弈论 *** 阶梯nim

2020-11-21

2 611

Split Game

题意：一张n * m的纸，两个人轮流操作，可以沿着一条直线切，当有人切出1 * 1的纸时即为输掉比赛，问最后谁赢题解：经典博弈论sg函数Sprague-Grundy定理：游戏和的SG函数等于各个游戏SG函数的Nim和（异或和）mex(minimal excludant)运算：这是一个针对集合...

sg函数博弈论 ***

2020-11-19

2 688