RVCake

题解

专题总结(1)

/ 注册

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

题解-[USACO 2010 Feb S]Chocolate Eating

解题思路二分枚举+检验的典型例题。首先考虑边界问题，最大的情况是 5e105e105e10 的快乐值，但是实际上可以在读入的时候就对巧克力的快乐值进行累计，这样得到的就是可能存在的最大解，因为每过一天快乐值都会减半所以最大值不会超过巧克力快乐值总数；其次是二分的写法问题，题卡了好几天换了好几...

C++ 二分查找

2022-03-15

2 415

题解-1014-[NOIP2006]明明的随机数

解题思路数据范围比较小，去重排序工作可以直接开一个涵盖所有可能值大小的数组，初始化清零，读到了就进行判断，如果已经有标记了那么直接 continuecontinuecontinue ，没有标记就置 111 ，count++count++count++ 记录下不重复的数据个数。 lastlastl...

C++ 数组

2022-03-14

0 241

题解-1016-[NOIP2011]铺地毯

解题思路贪心。用一个结构体数组来存每块地毯的左下右上坐标，判点在不在区域内可以用逆否命题（即判断的时候跳过超出区域边界值的点）。因为地毯是按输入的顺序铺开的，题目要求输出最上面的地毯那么只需要倒序遍历，第一个没被跳过的地毯就是覆盖在当前点最上层的地毯，输出编号 breakbreakbreak ...

C++ 贪心

2022-03-14

0 224

题解-1003-更相减损术

解题思路更相减损术的百度百科如下，更替相减的操作是重复且有尽头的，即本质可递归实现：第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用 222 约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等...

C++ 递归

2022-03-06

0 255

题解-1004-[NOIP2009]分数线划定

解题思路划定分数线的前提是数据的存储方式要有序，本题的“有序”有两个层次，首先是按照得分，得分高在前；另外是在得分相同的情况下，报名号小的在前；用结构体数组来存储数据，自己写 comparecomparecompare 函数，判断的优先级用一个 ififif 语句来限制。比较的部分结束之后是对...

C++ 有序集合

2022-03-05

0 494

题解-1002-小q的数列

解题思路题目中给的递推式的操作包含两项，前一项 f[n/2]f[n/2]f[n/2] 是对 n/2n/2n/2 后的递归操作， f[n%2]f[n\%2]f[n%2] 是对当前的 nnn 对 222 取余的操作，而 f[0]=0f[0] = 0f[0]=0 , f[1]=1f[1] = 1f[1...

C++ 二进制

2022-03-05

4 647

题解-1001-The Biggest Water Problem

解题思路就是很简单的递归，终止条件设置为当前数值小于10即可。写题解主要是因为提交的时候无法编译，报错信息是不是每一个分支都有返回值，于是把 dealdealdeal 函数的最后一行改为 returnreturnreturn deal(ans);deal(ans);deal(ans); 才通过。...

C++ 递归

2022-03-03

0 375

题解-1038-组队

解题思路首先是对团队中的人的能力值进行排序，然后用尺取法两个forforfor循环遍历一次能力值数组，时间复杂度为O(n)O(n)O(n)。一些需要注意的小细节: 1>多组数据输入，数组占用内存过大时定义成全局变量，读入前清零； 2>注意数据范围； 3>两次循环部分，外层的 ...

C++ 贪心

2022-03-02

3 354

题解-1035-数字计数

解题思路一开始的想法是读入之后直接sortsortsort排序，那么a[0]、a[1]、a[n−2]、a[n−1]a[0]、a[1]、a[n-2]、a[n-1]a[0]、a[1]、a[n−2]、a[n−1]就自然是最小次小次大最大，只过了50%的数据，错在是没考虑到数字重复的问题，最后是设置了四...

C++ 数组

2022-02-10

0 465