平凡的小白

题解

未归档(48)

/ 注册

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

国王的游戏来自专栏

思路：贪心+快排假设除了序列中相邻的两个大臣AB，其它大臣的位置都已经排好了。而AB的先后对前面和后面的结果都不会有影响，这里考虑A排前面最优的条件：左手数值用，右手数值用，表示AB前面大臣左手数值的乘积。1.A排前面时：,。2.B排前面时，,。3.。4.因为，所以不等式3需要满足，即。5.所以只要...

python 贪心

2020-05-29

5 1084

奇♂妙拆分来自专栏

题意：一个自然数最多可以分解成多少个不同的因子。思路：枚举题，主要在暴力的基础上减去不必要的枚举。1.因为n(1除外)一定存在一个小于的因子，所以枚举到因子枚举到就可以了。2.每找到一个因子就从n分离出来：3.当时，有两个一样的未出现的因子，那么只能把这两个因子合并为算作一个因子。4.当时，...

分解因子枚举数学

2020-05-29

4 672

数学考试来自专栏

戳我传送题意：思路求两个不连续的区间的最大和，很容易想到前缀和，[l,r]的区间和是sum[r]-sum[l-1]。朴素方法一个指针枚举左区间的起点，另一个指针枚举右区间的起点，两层循环复杂度（n^2）,应该会超时。枚举右区间的起点时，可以发现左区间的起点不需要从1开始找，此时的...

前缀和

2020-05-29

4 905

糖糖别胡说，我真的不是签到题目来自专栏

题意：n个糖糖排成一排，每个糖糖有一个能力值，第i秒第i个糖糖就会杀死前面能力比他小的人，进行m次区间加的操作，每次输入ci，表示第ci秒1~ci的糖糖能力值加一，输出最后有多少糖糖存活。思路： 1.前m次操作可以用前缀和模拟区间加，得到每个糖糖的新能力值后从后往前维护每个队伍的最大值，当前糖...

思维前缀和

2020-05-29

1 730

【每日一题】[CQOI2009]中位数图来自专栏

题目题目描述：给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。输入描述：第一行为两个正整数n和b ，第二行为1~n 的排列。对于 30% 的数据中，满足 n≤100；对于 60% 的数据中，满足 n≤1000；对于...

思维题前缀和

2020-05-27

3 1005

【每日一题】建筑抢修来自专栏

题意：有n个建筑，每个建筑有修复时间和截止时间，只有一个工人，建筑之间移动的时间不计，最多可以让多少个建筑在截止时间前修复好。思路：典型的“给程序留一个后悔机会”的贪心。贪心可以考虑下面三种种策略：1.我最先想到的是先修复修复时间短的建筑a，但是可能它的截止时间很晚，而有一件截止时间很早的建...

贪心可反悔的贪心

2020-05-27

1 634

【每日一题】货币系统来自专栏

题意：给n种货币，每个面值ai，数量无限，是否能去掉几种货币，使得原本这几种货币能组成的数仍能组成是否能去掉几种货币，问最后最少能剩下多少货币。思路： 1.打算化简一下货币系统，其实就是去掉几种货币，说明剩下的货币能表示被减去的货币。2.最小的不能去掉，因为其它的货币表示不了面值最小的货...

完全背包

2020-05-27

1 781

【每日一题】小AA的数列来自专栏

题意：给定一个数列，找出这个数列中长度为偶数的连续子列的异或和并且要求长度为偶数的同时满足在到之间最后结果思路：异或一般是是枚举每一个数每个二进制位的贡献1.这道题需要考虑的是一个连续子列，我们可以维护一个前缀和 cin>>a[i],a[i]^=a[i-1];2.那么枚举每个...

前缀和异或

2020-05-25

1 840

【每日一题】简单瞎搞题来自专栏

炸了啊，刚写完又没了！！$$ 一共个区间,每个区间任取一个数，设，求S的种类。思路：分组背包问题，&dp[i][j]&表示前i个区间里选i个数是否能表示j，我们要求最后能表示的数的种类数，其实就是。思路： 1.既然只有两种关系，我们这里就可以用bitset容器来保存每一个状态，...

bitset 多组背包

2020-05-25

1 835

牛客练习赛64

A、怪盗-1412 思路：对于单次出现的元素比如'4'，'2'，放在一起可以让序列1412的数量尽可能多，即被重复计算的次数多。而对于出现两次的元素'1'，分别设为考虑均值不等式，等于n，所以很明显，如果要最大，就应该使和尽可能平均分配。以样例1为例，合理的排布应当是：11144444444111...

打表规律数论图论容斥原理 dp 滚动数组

2020-05-22

1 631