cheeserish

题解

/ 注册

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

[CQOI2009]中位数图

QAQ，因为放在第三节习题题单里，搞得我以为需要二分！！！根据题意，中位数是一定在奇数序列里，所以从值b的k位置开始枚举；对于大于b的数1.小于b的数-1；以b位置左部分为求后缀和，后部分为前缀和。左右两部分相加为0的序列满足题意；对于奇偶判断：因为以k为起点，左边的值如果为-x，右边的值为x，（如...

2020-05-24

0 657

wyh的物品

和另一道一样，01分数规划+二分。 #include<bits/stdc++.h> using namespace std; #define ll long long const double esp=0.00000001; int main() { int t,n; c...

2020-05-23

0 786

小咪买东西

求单位最值，考虑01分数规划；x=∑a[i]/∑b[i]，所以∑a[i]-x*∑b[i]=0 ∑ ( a[i] - x * b[i] )枚举x，取k个物品，看代码： #include<bits/stdc++.h> using namespace std; #define ll long ...

2020-05-22

1 927

完全平方数

链接：https://ac.nowcoder.com/acm/problem/14733来源：牛客网题目描述多次查询[l,r]范围内的完全平方数个数定义整数x为完全平方数当且仅当可以找到整数y使得yy=x题目虽然标的二分吧，但是还是怎么简单怎么来；可以看出，对于lr之间的完全平方数，...

2020-05-22

0 1002

位数差

链接：https://ac.nowcoder.com/acm/problem/14380来源：牛客网题目描述 ** 给一个数组{a}，定义 h(a,b)为在十进制下 a + b 与 a 的位数差，求，0的位数为1。 ** 看到这道题，第一感觉数学问题；不过既然标签为二分，那就只能往二分靠；∑h...

2020-05-22

3 890

「土」巨石滚滚

看这题，就是贪心。贪心怎么贪？？就不误导了；分成两类，一种是b-a>=0的；另一种是b-a<0；对于第一种，显而易见，要按照a升序排列；对第二种，需要按照b降序排列，因为对于第二种，无论怎么排，m的值一定是减小的。所以先选b大的； #include<bits/stdc++.h>...

2020-05-20

0 595

铺地毯

简单暴力枚举； #include<bits/stdc++.h> using namespace std; struct node{ int a,b,g,k; }nod[110000];//分别记录四个顶点 int main() { int n; cin>&g...

2020-05-20

0 618

数学考试

注意数据范围；首先n^2超时，所以最少nlogn，但是看题目，感觉不需要数据结构优化；所以可能是n的复杂度，区间修改，前缀和。同时注意数据初始化； #include<bits/stdc++.h> using namespace std; #define int long long con...

2020-05-20

0 564

过河

看到L就知道，一定不能开个这么大的数组，且也不能按照这个1e9循环，一定超时；并且m石子数量只有100；所以，就需要用离散化进行化简。也就相当于，距离较远的石子用距离近的点代替； #include<bits/stdc++.h> #include<algorithm> usin...

2020-05-16

0 816

数码

https://ac.nowcoder.com/acm/problem/13221emm，数据范围1e9，顶多O（n）复杂度，但是看题可想而知，复杂度要小于O（n），跟数学有关系；再者，i|n形式，可以考虑考虑数论分块； #include<iostream> #include<al...

2020-05-05

0 632