微澜尛雨

分类

题解(28)

/ 注册

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

32篇文章 993人学习

全部文章（共33篇）

题解 | #Quasi Binary# 来自专栏

题目考点：枚举题目分析：将数字用数量尽量少的01串表示，表示的结果是每一个01串相加后得到原数字即可；例如样例：103 需要用3个01串表示： 101 1 1 注意：100 1 1 1也可以表示，但是需要花费4个不是最优解还有就是本题输出的01串不唯一，但最少数量一定唯一代码： #inc...

枚举

2021-11-25

1 527

题解 | #毒瘤xor# 来自专栏

题目考点：前缀和、位运算题目大意：找到一个数X，使得X和数列区间内所有数字异或后，得到的值最大。题目分析：暴力解法O(d * 2e10)，其中d为区间长度、2e10为int正整数范围，用派蒙的脑子想想就知道不可取吧？换个想法来看，统计一下区间内的数字的第i位0的个数和1的个数：若第i位1的个数...

前缀和位运算

2021-11-25

1 523

题解 | #胖胖的牛牛# 来自专栏

题目考点：bfs or dfs or dijkstra(蒟蒻优先想到bfs，就先粘上bfs吧，日后有时间补上其他的) 题目大意：走迷宫起点到终点至少需要转90度弯共几次题目分析：优先队列按照转弯次数从小到大，基于贪心思想得到最优解。在bfs版子的基础上，在结点中多加一个该点是从哪个方向走来的即可。...

C++ C 深度优先搜索图 bfs dfs dijkstra

2021-11-19

1 519

题解 | #统计数字# 来自专栏

（截止2020-9-3题目有说是多组输入吗？？？？）题目考点：数位DP（小学奥数分情况讨论？）题目大意：统计0 ~ n中的所有数字中，0到9在每个数字的每一位上出现的次数。题目分析： 1、举例分析：统计数字2在（0 ~ n=324）的个位上出现的次数，个位有（32 * 1+1）次，在十位...

dp 数位dp

2021-09-03

6 657

题解 | #加边的无向图# 来自专栏

【路径压缩】【按秩合并】题目考点：并查集题目大意：求连通块个数题目分析：正常并查集代码，从前往后扫，遇到不在同一个连通块时ans++；题目数据无需优化，代码里贴上路径压缩+按秩合并代码，有兴趣的同学可以大概看看；代码： #include<iostream> #incl...

并查集

2021-08-11

0 449

题解 | #迷宫# 来自专栏

题目考点：bfs题目大意：从S走到E，其中W是墙壁不能走，D是门，必须找到钥匙K才能经过门，求能从S走到E所用的最少步数题目思路：bfs模板，找到钥匙前，走过的地方标记为D；找到钥匙后，走过的地方标记为W，这样能避免重复走，同时处理了有无钥匙的情况；代码： #include<iostream&...

bfs

2021-08-09

16 729

题解 | #Flip Game# 来自专栏

题目考点：位运算+01串枚举题目大意：n*m由'w'和'b'石子组成的矩阵，每次选择一个石子按一下，按下之后，该石子以及上下左右的5个石子都会翻转（'w'变成'b','b'变成'w'），问讲矩阵全变成'w'或全变成'b'最少需要按几次，若无解输出Impossible 题目分析：经分析得知，若第一行...

01串枚举枚举

2021-07-14

1 577

题解 | #矩阵消除游戏# 来自专栏

题目考点：01串枚举+贪心题目大意：从n*m的矩阵中进行k次选择，每次选择一整行或者一整列，得到这一行/列的和，每次选择过后，该行数字将会被消除；求k次选择能得到的最大和。题目分析：初步分析似乎是贪心，每次取最大和的一行或一列，但是很快能想出反例：举一个反例： 3 4 2 0 0 ...

01串枚举贪心

2021-07-14

1 716

题解 | #[NOIP2005]校门外的树# 来自专栏

考点：差分大意：在一个长区间内取走n和小区间，问取完后剩余的点数代码： #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 10...

差分前缀和

2021-07-09

0 401

题解 | #FBI树# 来自专栏

题目考点：分治（二分）题目内容：给出一个01串，将其不断二分成一颗二叉树，求后序遍历；遍历过程中，若某一节点儿子均为1，输出‘I’，若均为0，输出‘F’，否则输出‘F’；题目分析：如题目样例：3 10001011则有： #include<iostream> #include<...

2021-05-16

4 624