回归梦想

题解

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)

/ 注册

全部文章 / 题解（共29篇）

D - Take Your Seat

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

概率 *** 思维

2020-11-26

2 642

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

Travel Expense

题意： n个点，m个边，两两之间可以到达我们要运送货物，如果量是x，运送第一天是x,第二天是x,第n天是x,运送几天取决于起点和终点的长度，长度=运送天数，问现在预算是budget，从s到t最多能运多少货物？题解：脑残了。。n<100,我们肯定要先求出任意两点的最短距离，还用什么spfa，...

二分最短路 ***

2020-11-19

2 535

CodeForces - 86D Powerful array

题意：求区间[l,r]内每个数出现次数的平方*这个数，然后求和是多少 num(i)为i出现的次数题解: 暴力固然不可行其实这个题不难看出有莫队的感觉，之前做过统计数字出现次数的题，就是用莫队，把那个add和del改一改就行不过这个题有点恶心，卡常我们一般块的大小时用sqrt(n)来决定，这个要...

优化 *** 莫队算法

2020-11-16

2 549

CodeForces - 514C Watto and Mechanism

题意：先给n个字符串(由a，b,c组成)，再给m个查询，问存不存在和n个中的某一个只差一个字符(0 ≤ n ≤ 3·10, 0 ≤ m ≤ 3·10) 题解： n和m都很大有两种做法：hash和字典树就是很暴力的做法把模板串整体哈希并记录值然后依次改变目标串的每一位，改成a~c，然后查看是否存储过...

字典树 *** hash

2020-11-16

1 668

二数

来源：牛客网：题目描述我们把十进制下每一位都是偶数的数字叫做“二数”。小埃表示自己很聪明，最近他不仅能够从小数到大：2,3,4,5....，也学会了从大数到小：100,99,98...，他想知道从一个数开始数最少的数就得到一个二数。但是聪明的小森已经偷偷在心里算好了小埃会数到哪个二数，请你求出...

构造思维模拟 ***

2020-11-16

2 797