monkeycpp
monkeycpp
全部文章
分类
每日一题(20)
归档
标签
去牛客网
登录
/
注册
monkeycpp的博客
全部文章
(共20篇)
[每日一题] [NC19798] 区间权值
题目大意:一个长度为N(<=3E5)的数组,考虑每一个长度为L的区间,给予权重w_L。计算没个区间的总和乘以权重的和。 https://ac.nowcoder.com/acm/problem/19798 反过来考虑没个权重w_L的系数,为所有长度为L的区间的总和之和。长度为1的区间和为a1+....
2020-07-20
0
786
[每日一题] [NC20272] 生日快乐
题目大意:有N(<=10)个人,需要把X*Y的蛋糕切成N等份,每次只能横/竖切一刀。求最大的长宽比的最小值。其中矩形的长宽比为长边与短边的比值。 https://ac.nowcoder.com/acm/problem/20272 数据比较小,N只有10,直接用了个dfs就解决了。考虑XY的蛋糕...
2020-07-14
0
623
[每日一题] [NC16645] 矩阵取数游戏
题目大意:有一个矩阵,每行独立玩一个游戏,每次可以从头/尾取一个数并乘以2^i,希望总和最大。要求每行的总和最大值的和。矩阵很小(n,m <= 100)。 https://ac.nowcoder.com/acm/problem/16645 其实很简单,就是区间DP,每行单独做即可。考虑这一行第...
2020-07-09
0
587
[每日一题] [NC18979] 毒瘤xor
题目大意:有一个数组,每次询问数组的第L个到第R个数和某个数x的xor的总和最大的那个x。 https://ac.nowcoder.com/acm/problem/18979 其实很简单,没个bit可以分开,那么就是要么这个bit不变,要么全部flip,问哪种剩下的1个数多,只要能飞快地知道这一位0...
2020-07-02
0
729
[每日一题] [NC14522] 珂朵莉的数列
题目大意:给定一个数组,有N*(N+1)/2个子序列,这些子序列总共有多少个逆序对? 对于没个arr[i] > arr[j], i < j,在总个数的贡献是(i + 1) * (N - j)。所以基本就跟算逆序对个数这个问题是一样的,无非就是在merge的时候不是算个数的总和而是算(N ...
2020-07-02
0
511
[每日一题] [NC23413] 小A买彩票
https://ac.nowcoder.com/acm/problem/23413 题目大意:N次独立的赌博,每次要花3元,等可能赚1,2,3,4,问保本概率。 比较简单的技术DP,只需要知道每种总和的选法即可。状态转移也比较直接。 //Pr[X1+...Xn>=3*n] #include &...
2020-06-23
0
679
[每日一题] [NC20241] 扫雷MINE
题目大意:Nx2列的扫雷,第二列没有雷,并且第二列每个数代表周围八个里面有多少雷。给定第二列的数,问有几种排法。 https://ac.nowcoder.com/acm/problem/20241 很经典的状态压缩DP。可以认为有一个01数组,然后知道每连续三位的总和。问有多少种方法。 ==== 仔...
2020-06-19
0
690
[每日一题] [NC18386] 字符串
https://ac.nowcoder.com/acm/problem/18386 题目大意:选取字符串最长的包含所有小写字母的substring的长度。 比较简单,用sliding window即可,维护一个left和right区间,每次right尽量伸长,left再减少一位。 #define M...
2020-06-16
0
504
[每日一题] [NC50995] Supermarket
题目大意:有很多物品,每个物品有一个价值和deadline,放入每个物品需要1 unit time,最多可以购买多少总价值。 https://ac.nowcoder.com/acm/problem/50995 看了一下我的做法似乎和大家的不太一样,原来和之前某一道题类似是带反悔的贪心。 我的做法,就...
2020-06-14
0
509
[每日一题] [NC13884] Paint Box
题目大意:有n个盒子,总共有m中可能颜色,问有多少种染色方式,使得相邻的盒子不相邻,且恰好有k中颜色。数据范围n和m都非常大,k不超过1E6。 https://ac.nowcoder.com/acm/problem/13884 如果n和m的范围不大,这题可以用一个DP来完成,即考虑前i个盒子恰好k种...
2020-06-11
0
671
首页
上一页
1
2
下一页
末页