威风镰鼬

题解

/ 注册

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

题解 | #[USACO 2006 Nov S]Round Numbers#

思路先说一下个人思路，由于时间原因我把这题跳了：区间[0,b]中的RN-区间[0,a-1]中的RN就是区间[a,b]中的RN,求所有小于k的RN的个数，可以先找出二进制中k的每一个1，然后在这些1之后的几位数字中填入n个1和m个0(m>=n)，那么这些组合数的结果相加就是小于k的RN个数，答...

数位DP 组合数学

2021-08-18

1 517

题解 | #[NOIP2013]火柴排队#

思路稍微用点群论的知识，我们可以感觉出它要我们求逆序对。于是我们可以先把a和b的数字和离散化结果记录下来，然后用x存储置换后的结果，然后套个归并排序的板子就OK啦。代码 #include<bits/stdc++.h> using namespace std; const int ma...

离散化归并排序 NOIP

2021-08-18

1 464

题解 | #Farey Sequence#

思路这是一道裸的欧拉函数题目，先线性预处理。对于所有n>2的欧拉函数进行前缀和，然后直接输出答案就可以了。代码 #include<stdio.h> typedef long long ll; const int maxn=1e6+7; int n,isn_pri[maxn],p...

2021-08-17

1 439

题解 | #Atlantis#

思路这道题是扫描线线段树的板子题，具体的处理方法：(1)每个矩形的上下边加入扫描线并标记，下边标记为1，上边标记为-1(2)让扫描线从从低到高排序，而矩形的左右边从小到大排序(3)考虑数据范围，我们进行离散化处理(3)建立线段树，那么区间可表示为区域的y1,y2，以及长度。(4)遍历所有相邻左右边...

线段树扫描线数据结构

2021-08-17

2 439

题解 | #Mayor's posters#

思路典型的区间染色问题。离散化区间端点（注意非连续区间中间要加点隔开），就可以建线段树了。倒序每一次询问，查看该区间是否被覆盖，如果没有就ans++,然后顺便把区间覆盖掉。代码 #include<iostream> #include<vector> #include<...

线段树数据结构

2021-08-17

1 487

题解 | #A Simple Problem with Integers#

思路线段树板子。代码 #include<iostream> #define pushup(x) (tree[x]=tree[x<<1]+tree[x<<1|1]) #define MID int mid=(start+end)>>1 using n...

数据结构线段树

2021-08-16

1 535

题解 | #[SDOI2011]计算器#

思路询问1：快速幂就可以了。询问2：可以转化为求解同余方程，使用扩展欧几里得就可以求解，在gcd(y,p)|z的时候有解。询问3：重点要讲的BSGS算法(我习惯叫北上广深)。我们要求满足同余式的最小非负数x，暴力枚举x在[0,p)的范围内，在p非常大的情况下是会爆的。可以令x=mi-j，那么式子转...

快速幂 BSGS 扩展欧几里得数论

2021-08-13

1 477

题解 | #间谍网络#

思路这道题中，图的遍历起点必然是可控制的，如果起点不可控制，答案肯定是NO,NO的情况只需要从1~n找到第一个没被遍历过的数输出就可以了。因此，我们记录下每个节点的入度，那么就相当于从图中所有入度为0（且可以控制）的点开始拓扑排序，并记录访问节点即可。但是题目不保证是有向无环图，因此我们需要对环进...

tarjan 图论缩点强连通分量

2021-08-13

1 0

题解 | #Visible Lattice Points#

思路没学过数论的同学估计一开始是不会想到欧拉函数的。那么我们怎么去联想到这东西呢。这道题，我们只需要计算y>x的点（上三角），然后答案就是2*ans+1了。(上三角+下三角+斜率为1的点)我们现在通过找规律来看看n不同时斜率的一个情况(y/x):n=1,ans=0;n=2,ans=1,k=1...

欧拉函数数论

2021-08-12

1 573

题解 | #[NOIP2017]棋盘#

思路没啥思考过程，照着题目跑bfs就过了。大概就是跑的时候记格子的花费和是否用过魔法。记录颜色时+1是因为比较方便区分白色。剪枝直接把同一格子花费大的剪掉就行了。正确性的大概考虑：若经过同一格子两次，用魔法的状态肯定是一样的，并且金币只会递增。（不知所云）代码 #include<bits/...

搜索 NOIP 普及组 bfs 最短路

2021-08-06

2 424