一只羊蝎子

题解

/ 注册

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

NC16783 拼数

容易跳坑的错误思路：将整数按字典序排序，比如把7，13，4，246排序成7，4，246，13，这样乍一看是对的，但多尝试几组数据以后可以发现会有类似98，9或者321，32这样的数据没法得到正确答案。正确的贪心思路：*假设数字均以字符串储存对于数字a, b, c, d，我们任意改变其中两个相邻数字...

贪心

2021-01-24

3 692

NC106350 POJ1753 Flip Game

题意：在4*4的棋盘里有16个可黑可白的棋，每轮游戏可以选择将一个棋及其上下左右相邻的棋的颜色取反（最多五个最少三个），所有棋面颜色相同时游戏结束，求最少进行几轮游戏后游戏结束思路：对任意的一个棋子进行两次翻转操作是无意义的，负负得正，因此一个棋最多只翻一次，可以采取枚举我们从上至下（当然你...

枚举位运算

2021-01-23

5 779

NC20241 SCOI2005 扫雷MINE

文中数组下标均从0开始地图上有两列，mine对应第一列，表示格子里的地雷数（0或1），map对应第二列，表示附近的地雷数根据map[0]的值，我们可以推断mine[0]和mine[1]地雷的存在情况，如：下标 mine map 0 1 2 1 1 2 2 ？ 2 3 ...

枚举

2021-01-22

15 765

NC207040 丢手绢

用双指针，从第一个小朋友开始一圈圈按顺时针方向遍历，到最后一个小朋友的那圈遍历完结束。因为题目定义两个小朋友的距离为沿着圆圈顺时针走或者逆时针走的最近距离，所以在计算最远距离时要让当前两个小朋友的距离小于圆圈周长的二分之一，不然最短距离就会变成从逆时针方向开始计算，这是一个小坑同时，计算的时候数组...

双指针

2021-01-22

3 927

NC18386 字符串

这题一看就可以用暴力，没什么好说的优化一下，用双指针，用一个26个元素的数组统计各字母在子串中出现过的次数判断是否符合题意即可 #include <iostream> #include <string> using namespace std; //用于判断是否符合题意...

双指针

2021-01-22

3 702

NC107658 POJ3061 Subsequence

题目要求找到长度最小的子串，使得字串和大于等于S既然是要长度最小，那我们就可以从长度为1开始遍历到长度为N，我们需要遍历次，当N非常大的时候耗时会特别长，所以可以稍微优化一下（双指针/尺取法）。如果是按长度从1到N遍历，那么我们每次都要从子串的头到尾重新计算一次子串和，对此我们可以做出这样的优化...

双指针

2021-01-22

3 748

NC20032 HNOI2003 激光炸弹

5001*5001，量太大了，直接用前缀和整一个5001*5001的二维数组来对应整个地图，数组中的元素表示当前坐标上目标的价值（无目标即为0）先很普通的用循环记录每个目标的坐标和价值，然后再循环计算前缀和。计算时，每个点[i][j]上记录的价值和为 [ i ][ j ]+[ i-1 ][ j ...

差分与前缀和

2021-01-21

3 683

NC16649 校门外的树

思路对于长度为L的马路，一开始共有L+1棵树如果直接声明长度为L+1的数组再根据输入的区间一个一个遍历把树移走的话，一个区间有n个数就要执行n次操作，太过复杂，耗费时间比较长，数据小还可以操作，数据大的话就不行了，所以这题可以考虑差分和前缀和有L+1棵树，为了方便操作，在数组最前面和最后面再加...

差分与前缀和

2021-01-21

2 805

NC16438 回文日期

题目要求统计回文日期，相当于回文字符串，可以考虑使用遍历如果固定年份，对月和日进行遍历再判断是否回文效率太低，可以直接遍历月和日，根据月和日构造回文的日期，这样最多只有366种可能。列出所有的回文日期以后再判断是否再输入的区间之内即可 #include<iostream> using ...

枚举

2021-01-20

12 864