louhc

题解

未归档(78)

/ 注册

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

题解 - [JLOI2010]足彩投注

思路题目又臭又长,其实没有什么卵用....真正有用的只有那个式子.根据乘法原理,我们可以转换成这样: 于是设计状态表示当前进行到场,有场为 ,有场为 .因为都是级别的,所以总复杂度为 .最终结果可能会很大,最好不要用 double,用 long double...

期望概率动态规划

2019-12-01

1 773

题解 - Alice和Bob赌糖果

思路首先,我们可以忽略平局的情况.因为如果我们过滤掉平局的情况,最终结果仍然不变. 我们记Alice赢的概率为 ,输的概率为 , 当Alice手头有颗糖果时,最终获胜的概率是 . 然后我们就可以列出转移方程: 很明显这玩意不能直接转移,如果比较小的时候我们可以高斯消元解方程,但是这...

期望概率

2019-11-23

3 1184

题解 - 农村连接城市

思路首先,期望是线性的. 于是我们可以求出连接每一个农村所需长度的期望,然后全部加起来就OK了. 记表示第个城市, 表示第个农村, 表示与相连的概率, 表示与的距离. 那么现在我们依次处理每一个农村 . 先考虑城市的贡献.很明显只有离最近的城市才会有贡献. 对...

期望概率

2019-11-21

5 931

题解 | 信息学奥赛一本通不要 62

思路比较套路的一道数位DP题.按照套路转换成前缀和.先预处理出表示第位为,位为,位及之前不需要考虑(可以看做全是)满足条件的数的个数.我们枚举位到最高位与相同,位小于的答案.发现不满足条件记得及时退出.最后答案别忘+1.复杂度为. 代码 #include<bits/stdc++.h> ...

动态规划数位动态规划

2019-09-05

0 651

题解 | 信息学奥赛一本通恨7不成妻

思路设计状态表示不大于的数中,满足个位数之和模为,该数模为的数的平方和.最后一维为表示等于上界,为表示小于上界.很明显平方和不方便直接转移,因为,我们可以同时维护满足条件的数的个数以及和,然后我们就可以快乐地转移啦.我们在转移的同时去除那些有一位为的数,枚举下一位是啥转移即可.具体操作参考代码.时...

数位动态规划动态规划

2019-09-05

1 847

题解 | 信息学奥赛一本通 Windy 数

思路简单的数位DP题.预处理出表示位,最高位为的Windy数有多少.然后将范围转换为前缀和(这是有多套路qwq),从高位枚举到低位,加上选小于当前位的数的合法方案数,如果当前位到顶,继续枚举低位.然后别忘了最后答案+1.(一切都是多么经典qwq)算法复杂度为. 代码 #include<bit...

动态规划数位动态规划

2019-09-04

0 698

题解 | 信息学奥赛一本通Amount of Degrees

思路我们先用前缀和将问题转化为求范围内满足条件的数的个数-范围内满足条件的数个数.我们设当前我们在求范围内满足条件的数.我们可以考虑一棵二叉树,往左走表示第位为,往右走为.(表示深度;第位表示最高位,以此类推;这里是进制时).这样走到叶子节点都会得到一个数,我们的任务就是找出恰好往右走了次,结果得...

数位动态规划动态规划

2019-09-04

0 766

题解 | 信息学奥赛一本通股票交易

思路因为所有限制都是整数,中间过程参与运算的数字也肯定都是整数,而且数据范围允许,我们可以设计状态表示第天拥有支股票时相对初始状态最多有的钱.这天可以不买也不卖,所以的一种决策是.只有天前的状态有用,我们可以直接取的状态.(由于上一种转移,这肯定是最优的)然后这天要么买,要么卖,否则肯定不是最优的...

单调队列动态规划

2019-09-03

0 695

题解 | 信息学奥赛一本通取石子游戏

思路首先,函数什么的不怎么管用.(亏我想了好久)这题做法十分神奇.设表示在区间[l,r]的石子左边添加一堆L[i][j]的石子会导致先手必败,如果没有该种策略值为0.与此同理.易证决策不可能吧同时存在多个.预处理边界.因为相同的两堆会导致这样的情况:先手在一堆取多少,后手就在后一堆取多少,先手明显...

博弈论

2019-09-03

1 878

题解 | 信息学奥赛一本通取石子

思路不知道为什么好多大佬写的都是玄学的.这里介绍从某位神仙博客看来的神奇推理.过滤石子数为0的堆,我们把石子数为1的堆(以下称为单数堆)的个数记为,大于1的堆(以下称为复数堆)石子数总和+堆数-1记为.先手存在必胜策略当且仅当满足以下条件: 若,需要满足和至少有一个是奇数. 若,需要满足. 下...

博弈论

2019-09-02

1 840