斩瑾

分类

题解(10)

/ 注册

全部文章（共10篇）

题解 | #最多数组数量#

一道前缀和的应用最快得到一个区间的和就用前缀和，其中暴力两次循环可以得到符合题目性质的解的数量，但肯定会超时，这时就需要考虑能不能优化成n的规模解决问题，根据前缀和单调递增的性质可以发现随着遍历i的取值j一定只会往后增大这时只要当每一次循环时找到符合要求的j的位置，如果符合当前i的位置的性质要求答...

2024-06-16

5 348

题解 | #异或症#

序列当中最大异或和其实与序列顺序无关（当时因为没想到序列顺序与最大和有什么关系就没有坚定答案错失良机）一个最大方案就是第一个数是1<<(log2(n)+1)-1第二个数与自身异或为零也就是答案是n*1<<(log2(n))+1)最后强调(一定要用long long 一定要用l...

2024-06-08

3 274

题解 | #[CQOI2009]中位数图#

题解：可以先找到需要的中位数的位置再从这个位置依次向两边寻找答案，因为是中位数所以可以将输入的数据转换成相对的大小比如大于该数就是1，小于就是-1.首先用sum记录当前的集合之和如果等于零代表了当前是一种答案，但这种只能看两边是否有答案，如果在该位置左右呢，那么就需要有一个数组记录左边每一个可能取...

C++ 数学

2024-01-10

0 283

题解 | #喷水装置#

思路：圆的半径小于等于W/2时，他会存在边角，使草坪不能有效覆盖，而当半径大于W/2时，他能覆盖的有效距离可以看成【L-sqrt(r^2-(W/2)^2，L+sqrt(r^2-(W/2)^2】再用区间覆盖判断是否最大可到达L #include <iostream> #include &l...

C++ 贪心

2023-06-18

0 361

题解 | #种树#

思路：贪心思想，要想尽可能地少种树，就要在之前已经种过，才会使此次种树量最少，那就是对右端点从小到大排序从后往前种树为最优解，至于按照上一区间的右端点大于这一去点的左端点会使答案可能变大比如1 6 2 与 2 3 1 这两组数据实际最小是两棵树但按照那个排序会是三棵树，具体代码如下 #include...

2023-06-13

0 475

题解 | #活动安排#

活动安排：贪心思想，区间合并的一种转换，首先你需要对左区间从小到大进行排序，当左区间相等时右区间从小到大排序为最优解，初始答案为1，左端点为最小的左端点，右端点为对应右端点，当右端点大于等于此时的左端点答案加一，更新此时的右端点为现在的右端点，当右端点大于此时的右端点此时答案不变但当前集合最优解为现...

C++ 贪心

2023-06-11

0 317

题解 | #一次交换#

思路：之前经过一次次的完善到了%80不理解哪里出错了，后来看了别人的题解发现有一块没有判断，那就是当两个字符串相等时，如果一个字符串其中的有个字母出现两次以上那么也可以交换一次输出YES,所以继续完善AC了这道题。首先输入两个字符串然后在用两个额外的字符串等于输入的字符串，对这两个字符串进行排序，如...

C++ 字符串

2023-05-26

0 406

题解 | #值周#

思路：区间问题，按照左端点从小到大排序，将可以合并的区间合并更新右端点在更新移除人数，将不可以合并的区间求差与原先人数相加在更新左右端点，最后总人数减移除人数加1，从零开始。由于排序之后，后一个的左端点肯定大于等于前一个，所以最先让比较的左右端点等于最开始的左右端点，再根据每次比较的右端点与此次的左...

C++ 贪心

2023-05-19

0 304

题解 |ranko的手表

思路：首先看见两个字符串还有其中有‘？’的不能直接从字符串一枚举到字符串二，就需要从0分钟枚举到1439分钟然后通过时间的进制分离小时和分钟，判断小时和分钟是否满足字符串一和二然后在将符合的分钟存进代表字符串一和二的数组，最后在枚举数组判断当字符串一数组小于字符串二数组值更新最大值和最小值 #inc...

C++ C 字符串枚举

2023-04-21

2 519

题解 | #[NOIP1999]回文数#

思路：当初以为只是单纯的将进制转换为十进制后调过来相加，没想到是不需要转换进制，在原进制下进行高精度的相加在判断 #include <cstdio> #include <string.h> using namespace std; char s[110]; int main(...

2023-04-17

0 622