ThinkofBlank

题解

未归档(4) 论文(10) 题单(1)

/ 注册

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

牛客练习赛61 A-E题解

一.闲话打了下比赛，把A-E做了后，看了下F，思考了一会儿，发现不可做，就来写题解辣，qwq 二.题解部分 A 打怪签到题，我的思路是先判断-1的情况（如果你可以一刀999秒掉小怪，由于你先手，那你就可以砍无数小怪了）然后，我们先计算出，砍完一只小怪，你扣的血，假设为x，这样，答案就是floo...

2020-04-10

2 986

二分图染色（弱化版）题解

乍看一下，此题貌似很简单，仔细一想，竟然完全不可做。。。然后，开始思考怎么搞这道题。。。首先，我们因为每个边都要染色，所以，我们不妨先给所有边都染上最没影响的颜色——绿色然后，我们只需考虑，将绿色的边改成红色或者蓝色即可~ 我们来推导一下如果既有蓝色，又有红色，尝试推导一下，发现情况太多，而...

数论

2020-04-10

3 911

题解 P4980 【【模板】Polya定理】

【模板】Polya定理题解提供一个新算法。。。首先,我们来分析一下题目: 给一个有n个点的环图n种颜色，问本质不同的方案数那么，很明显的，这是一个polya定理（废话，题目名说明了一切）我们先来看看这道题的“操作”，很明显的操作就是只有一个——平移（有人说旋转，但我个人更喜欢看成平移。。。...

数论优化研究

2019-09-23

1 626

题解 P4461 【[CQOI2018]九连环】

题解 P4461 【[CQOI2018]九连环】由于各位大佬已经用各种方法,将公式推得我这里便不再过多阐述,我们来谈谈本题的实现~ 首先,我们先来看公式:$\lfloor\frac{2^{n+1}}{3}\rfloor$ 我们知道,因为n<=1e5，所以$|2^{n+1}|...

研究优化高精题解

2019-03-18

1 712

题解CF785E Anton and Permutation

题解 CF785E 【Anton and Permutation】一.闲谈听说本题分块可以过而且吊打树套树？orz。。。我果然还是太菜了。。。二.分析 1.求逆序对简化题目:给出序列1-n，以及m个操作，每次交换两个数，求当前序列的逆序对数如果,交换的两...

题解数据结构主席树

2019-02-21

2 699

题解 USACO11OPEN玉米田迷宫Corn Maze

玉米田迷宫题解一.背景 x年x月x日，竞赛老师拿此题问我，然后我玄学过了，于是特来写此题。（谁说dijkstra不能过的？？）二.分析本题，我们先不考虑有传送阵的情况，发现，其实就是一个最短路(bfs)的模板题，随便弄下就能过，不过，这里多了个传送阵，于是我们就要考虑下...

题解图论研究

2019-02-19

0 605

题解 P3423 POI2005BAN-Bank Notes

本题有两个问，第一个是求最少硬币数，第二个则是求方案(翻译竟然没写。。。)。首先，我们来解决第一问。我们可以很容易想出，这是一个dp，我们设dp[i]表示凑出面值i最少需要多少个硬币，然后打个多重背包就好了。。。于是你就T了。。。对于多重背包，我们通常使用一种手段:二进制拆分...

题解优化动态规划

2019-01-21

0 562

题解 P3871 【[TJOI2010]中位数】

看到此题，顿时兴奋了，因为，我以前yy出了一种排序，叫做二分链表插入排序。详细板子代码见博客结果因为vector的insert太慢而被我GG了跑【模板】快速排序然后，看到此题，找中位数嘛，肯定是要在排好序的数列里面选出嘛。。。支持添加数字，嘛，二分一下就好了啊...

题解研究排序

2019-01-13

0 630

带修改的主席树 P2617 Dynamic Rankings

一:前置芝士: 1.树状数组(不会树状数组来打这个?(大雾 ) 2.主席树（不会主席树来打这个?(巨雾 ) 3.前缀和 (不会前缀和来打这个?(神雾） 4.权值线段树 (不会权值线段树来打这个?(仙雾) ) 5.看这篇文章的你需要用主席树将求区间kth练得比较熟，并且要理解其原理。二:分(che...

题解理解主席树

2019-01-13

1 737

题解USACO14DEC Piggyback_Silver

此题其实比较水的。。。首先我们来分析题目，我们假设，贝茜和艾尔西在i点相遇后贝西开始扛艾尔西，那么代价为多少呢？显然，代价=贝茜到i点的最小代价+艾尔西到i点的最小代价+贝茜和艾尔西一起到n点的最小代价。我们分开解决，首先贝茜到i点的最小代价=走的最少步数*b，而走的步数，我...

图论题解

2018-12-24

0 547