51nod 80分算法题
1537:见前几篇。
1627:题意:给定n,m的网格(10^5),初始状态为(1,1),你每次可以瞬移到右下方(不可以同行同列逗留)任何一个方格里,求移动到n,m的方案数。
一句话题解:首先很容易想到n^2的DP,不过实际上没必要,我们枚举走了几步,然后插板法看n和m分别分解为i个数的方案数,乘起来就好,也就是求这个式子(默认n小于m)
$ \sum\limits_{i = 1}^n {\left( \begin{array}{l}n - 1\\i - 1\end{array} \right)} \left( \begin{array}{l}m - 1\\i - 1\end{array} \right) $
1678:题意:给定一个序列(10^5),给定两个操作:单点修改和查询。查询时给定一个i,求出所有与i互质的下标对应的值的总和。
题解:正难则反,我们可以考虑求出不互质的总和,然后取补集,把每个数的值统计到自己的因子上,修改的时候改就可以了,查询的时候容斥一下,考虑到最多只有6 个不同的质因子,2^6完全可以接受。
1711:题意:给定序列(10^5),求出所有区间平均数中第k大的平均数。
题解:二分答案,然后统计有多少个区间满足,统计方法是:我们知道一个区间的平均数可以表示为 $ \frac{{sum[i] - sum[j]}}{{i - j}} $
我们要统计多少个i,j(j<i)满足 $ \frac{{sum[i] - sum[j]}}{{i - j}} \ge mid $
变形一下 $ sum[i] - mid * i \ge sum[j] - mid * j $
也就是每个位置都有一个值sum[i]-i*mid,把这个东西离散化之后我们实际上要求的就是逆序对个数,这个可以树状数组。
总复杂度O(nlognlogn)
1836:题意:m天n个东西,每天等概率选一个东西,求m天后个数期望。
题解:不知道说什么了。。简单dp
1766:传送门
1616:题意:给定n个数,他们属于一个集合,集合的性质为:若X,Y属于集合,那么gcd(X,Y)也属于这个集合。求集合最小个数。值域范围1e6
题解:对于每一个数我们求出对应的fi,fi定义为有多少个该数的倍数存在于集合当中。那么对于一个数,如果它的倍数中没有fi与自己的fi相等,说明这个数一定存在于集合中。统计出来即可。复杂度O(nln n)。
1476:题意:给定一个括号序列,其中有“?“”作为通配符,但是重定位会付出相应的代价,求最小代价使得序列合法。
题解:首先n^2dp很好想。但是可以更优。先强行把所有通配符定位成右括弧,然后左括弧为+1,右括弧为-1,算前缀和记为S,当前缀和为负数时,我们在前面的通配符中找一个代价最小的变为左括弧,同时S+=2。找最小可以用优先队列来实现。复杂度O(nlogn)。
1586:题意:有3个数组,a,b,c,a给定,b由a计算,c由b计算,计算规则为:某个下标的值为所有下标为其因数的数相加。有修改操作和查询操作,修改随机。范围1e5。
题解:既然是数据随机那么完全就可以乱搞了。。不赘述了
1463:题意:给定两个长度为n的数列A 、B,一个有m个元素的集合K,询问Q次,每次询问[l,r],输出区间内满足|Bi-Bj|∈K 的最大Ai+Aj
最新文章
- 深入.NET平台C#编程 测试题分析
- phpnow修改默认站点根目录的方法
- SQL 存储过程入门(事务)(四)
- 【Android学习】XML文本的三种解析方式(通过搭建本地的Web项目提供XML文件)
- 也谈闭包--小白的JS进阶之路
- django连接mysql自动同步生成数据表
- [老老实实学WCF] 第七篇 会话
- javax.management
- BroadcastReceiver的两种注册方式之------动态注册
- 洛谷 P1613 解题报告
- NIO(一)——缓冲区Buffer
- MySQL使用过程中的报错处理(持续更新)
- Yahoo Programming Contest 2019.D.Ears(DP)
- XML5个转义符:<;,>;,&;,”,&#169;;的转义字符分别如下: &;lt; &;gt;&;amp; &;quot; &;apos;
- 【Core】.NET Core 部署( Docker + CentOS)
- 洗礼灵魂,修炼python(48)--巩固篇—模块
- FAQ About WOYO PDR007 Dent Removal Heat Induction System
- (转)Python3异常-AttributeError: module &#39;sys&#39; has no attribute &#39;setdefaultencoding
- 洛谷P3966 单词 [TJOI2013] AC自动机
- P2880 [USACO07JAN]平衡的阵容Balanced Lineup
热门文章
- 2016.7.12 去除mybatis-generator生成的class里的注释
- Android的Framework分析---5 ActivityManager分析
- Android设计模式之中的一个个样例让你彻底明确装饰者模式(Decorator Pattern)
- vue2 axios 接口函数封装
- Activity 事件以及如何得到新打开Activity关闭后返回的数据
- VueJS组件之全局组件与局部组件
- SQL存在一个表而不在还有一个表中的数据
- EMI-CLK信号串电阻并电容
- 织梦在广告(myad)中使用css样式
- gulp 静态资源版本控制