P1712[NOI2016]区间我对尺取法并不敏感，所以感觉有点难度，我们想到按照区间长度排序加入使得满足单调性，直到有一个区间的覆盖次数达到了m就可以计算了，而这个就是尺取法，单调性使得我们答案总是最优的。覆盖次数就可以用线段树做，而且数据范围很大需要离散化，计算答案时注意把答案带

P1173[NOI2016]网格分讨+建图+点双分析一下替换个数的上界，发现最多为\(2\)，因为最坏情况下，也仍存在一个位置只有两个出去的方向（即边缘），堵住即可。那么现在答案就只有\(-1\)、\(0\)、\(1\)、\(2\)四种情况。分开讨论：\(-1\)：当图中只有一个跳蚤或者只有两只跳蚤连在一起时\(0

//Problem://P1712[NOI2016]区间////Contest:Luogu//URL:https://www.luogu.com.cn/problem/P1712//MemoryLimit:250MB//TimeLimit:1000ms////PoweredbyCPEditor(https://cpeditor.org)#include<iostream>#include<algorithm

[NOI2016]区间题目描述在数轴上有$n$个闭区间从$1$至$n$编号，第$i$个闭区间为$[l_i,r_i]$。现在要从中选出$m$个区间，使得这$m$个区间共同包含至少一个位置。换句话说，就是使得存在一个$x$，使得对于每一个被选中的区间$[l_i,r_i]$，都有$l_i\leqx\leqr_i$。对

题意给定\(n,m,k\)(\(1\len,m\le10^9\)，)问在\(k\)进制下有多少个分数值不同的\(\frac{x}{y}\)满足\(x\len,y\lem\)且其小数形式的循环节从小数点后第一位开始。sol因为要求不同分数值，我们只考虑既约分数。类比十进制，故要求\(gcd(y,k)=1\)。所以答案为：\[\sum_{i=1}

原文链接：[sol]P1587[NOI2016]循环之美-icyM3tra'sBlog此为备份。题目传送门0.前言提供一种式子较为简洁且不算难写的做法。以及介绍一种较为优秀的dp版杜教筛实现。1.式子推导我们知道纯循环小数一定可以写成分母形如\(k^a-1\)的分数。因此约分后的分母一定

很多套路糅合在一起的一道题。记\(len_i=r_i-l_i\)。则所求转化为一个有\(m\)个区间的集合\(S\)，满足：存在一个\(x\)，使得对于所有\(S\)中的区间\(i\)，有\(l_

链接：https://www.luogu.com.cn/problem/P1173题目描述：有一个\(n\timesm\)的棋盘，有\(c\)只蛐蛐，求再放置多少只蛐蛐可以使图中其他部分被分成两部分。题解：由于可以在这个

链接：https://www.luogu.com.cn/problem/P1587题目描述：求有多少个$\frac{a}{b}(1<=a<=n,1<=b<=m)$在$k$进制下是纯循环小数$(注意:相等的数只算一次)$。题解：可以发现$\f

P1587[NOI2016]循环之美这道题我推到后面推不下去了，最后还是看了题解。还是切不了这种题唉。前置知识：杜教筛开始时看不出什么，我们先用经验和手玩来找一下规律。我们

「NOI2016」网格题解前言感谢zqm学长提供调代码服务！本文中，所有没有特殊说明的连通都是指四连通，相邻都是指上下左右相邻。题目大意有一个$n\timesm$的网格，上

题面传送门首先我们发现，一定不会有低于\(h_1\)的参与操作的过程。然后考虑一个\(x\)与比它大的\(y<z\)，则发现一定是先\((x,y)\)，再\((\frac{x+y}{2},z)\)更好。因为这样