- 博客(20)
- 收藏
- 关注
RSS订阅原创 [SDOI2016]征途
广告 ：博客食用更佳题目链接Solution方差=∑i=1m(xi−xˉ)2m\frac{\displaystyle\sum^{m}_{i=1}{{(x_i-\bar{x})^2}}}{m}mi=1∑m(xi−xˉ)2=∑i=1m(xi2+xˉ2−2∗xi∗xˉ)\displaystyle\sum^{m}_{i=1}{({x_i^2} + \bar{x}^2 - 2*x_i*\ba...
2019-08-19 16:59:16
126
原创 CodeForces 109B Lucky Probability ——概率
题目描述洛谷题目CF题目思路先算出在范围内（num[q - 1] < max(qr,vr)）所有的只包含4和7的数但要多算一个bool able = 1;inline void dfs(int li){ li为边界 int i,it = q; 记录该点的在num的位置 num[i]表示第i大的只含4,7的数 for(i = 0;i < ...
2019-07-01 11:42:41
223
原创 The Last Non-zero Digit
文章目录题意（beican）历程正解1正解2Code（正解2的）题意题目链接本题大意为 给定m,n求：PnmP^m_nPnm的最后一位非0的数（P在排列组合中就相当于A）（beican）历程看到题目 什么都不会的我一脸懵（洛谷的限制太水了vjudge上时限1s我们按严格的来）但仔细想了一下 我仍然只发现暴力是不可以的我暴力的思路是 乘起来但直接乘会爆 就留个9位吧（感觉...
2019-06-25 15:07:46
181
原创 Prosjecni——C++
描述o Slavko 很无聊，所以他把正整数填到 N N*N 的方阵中。如果他填出来的方阵满足以下条件，他会特别高兴：● 每行中的数字的平均值是一个位于同一行的整数。● 每列中的数字的平均值是一个位于同一列的整数。● 表中的所有数字都不同。帮助 o Slavko 找到一种会让他开心的填法。输入第一行输入包含整数 N N （1 1 ≤N N ≤ 100输出输出 N N 行...
2019-06-23 21:00:44
77
原创 Mag——C++
描述您将获得一棵由无向边连接的树，树上每个节点都分配了一个魔力值 X X i i 。路径的魔力值被定义为该路径上节点的魔力值的乘积除以该路径上节点的数量 。 例如 ， 路径上有两个点 ， 魔力值分别为 3 3 和 和 5 5 ， 那么这条路径的魔力值就为 为 7.5 （ 3*5/2 ）。在给定的树中，找到具有最小魔力值的路径并输出该路径的魔力值。输入第一行输入包含整数 N N （1...
2019-06-23 18:41:47
659
原创 Cezar——C++
描述Mirko有一组N个不同的单词，他想用替换密码加密。我们通过首先选择一个密钥（一种26个英语字母的排列）来加密使用替换密码的文本。然后我们用密钥的第一个字母替换所有出现的字母’a’，所有出现的字母’b’都替换为密钥的第二个字母，依此类推，直到字母’z’。除了这些词之外，Mirko还有一个数组A，它由1到N的数字组成，按照一定的顺序给出（换句话说，数组A是从1到N的一个排列）。Mirko想要...
2019-06-23 18:41:18
176
原创 初等数论初步
文章目录判断质数判断1~n范围内的质数整数的唯一分解最小公倍数和最大公约数（gcd&amp;&amp;lcm）$\forall$n的约数个数$\forall$n的约数之和同余欧拉函数初学数论学得十分肤浅判断质数for(i = 2;i * i &lt;= n;i++) if(n % i == 0) { able = 1; break; } 判...
2019-02-15 14:29:04
292
原创 Riv——树形DP
文章目录题目思路代码题目题目链接思路整道题看起来有很多要点要考虑最先想出的DP方程dp[i][j]表示第i个结点所在子树建j个伐木场的最小花费dp[i][j] = min(dp[v][k] + cost)看起来挺好的，时间复杂度也不高，但问题来了cost怎么算啊不知道剩余木材 不知道走的距离于是老师说 要三维\color{red}\text{要三维}要三维定义dp[i][...
2019-01-31 19:15:25
250
1
原创 Computer——树形DP
ComputerA school bought the first computer some time ago(so this computer’s id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled ea...
2019-01-30 21:18:10
197
原创 LCA——笔记
文章目录题目——[最近公共祖先](https://www.luogu.org/problemnew/show/P3379)TagjanAnother Way延伸题目——最近公共祖先Tagjan将所有的查询存起来然后一遍dfs，得出所有LCA非常奇妙主要依据于以下操作13 和 14 的 LCA 是7当dfs到7时 模拟\color{red}\text{模拟}模拟 断开 3 - 7...
2019-01-29 21:21:09
166
原创 迎春舞会之三人组舞——dp
文章目录题目思路code题目题目链接初看此题，难免想起这道题目但仔细想想，发现中间那个人的标记会很难搞于是便有了如下思路思路dp[i][j]表示在前i个人中分成j组的最小残疾程度便有如下状态转移方程dp[i][j] = min(dp[i-1][j],dp[i-2][j-1]+(num[i]-num[i-1])^2)但有以下要点当i - 1 >= j * 3时 dp...
2019-01-12 14:18:39
215
原创 平行四边形不等式优化DP——笔记
推很久推出方程后发现时间复杂度太大TLE是不是很沮丧优化方式及限定条件来道例题Post OfficeThere is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each village ...
2019-01-05 12:19:04
190
原创 笔记—树状数组&&线段树
那是一个春光明媚的下午我们被锁在机房里，被逼学树状数组邪恶的老师学懂了才能走！老师你看我核善的微笑然后于痛苦和绝望中我们学会了树状数组&amp;amp;amp;amp;&amp;amp;amp;amp;线段树（只是一点很肤浅的）然后，一道ban题文章目录现在谈谈树状数组先说说再谈谈现在谈谈树状数组学过的都知道也很轻松就能推出单点修改-区间查询区间修改-单点查询区间修改-区间查询，我就推不出来了orz(qw
2018-12-26 14:09:44
133
原创 考试总结
文章目录具体分析：现状努力方向目标编程社在毒瘤老师的带领下又迎来淘汰赛然而我却得了 333排名只有17具体分析：原因考试时的思路很快就有了，但有明显Bug，却未能发现代码实现后，过了样例，就匆忙地前往下一题（导致前面几道题往往拿不满）后面的题直接开始无脑爆搜（虽然有几道题的正解确实是爆搜）还有题意不能理解的于是乎便有了如下成绩第一次第二次第三次第...
2018-12-26 13:46:08
264
1
原创 Max Sum of Max-K-sub-sequence----单调队列
至于题是哪来的，老师BB出来的至于怎么BB的，请自己联想文章目录Max Sum of Max-K-sub-sequenceInputOutputSample InputSample Output这道题，可以这样做Max Sum of Max-K-sub-sequenceGiven a circle sequence A[1],A[2],A[3]…A[n]. Circle sequence ...
2018-12-12 13:18:51
457
原创 瑰丽华尔兹--单调队列
看到这道题，的标签说明啊，它可以用单调队列易推出dp[x][y][t] = max(dp[x`][y`][t - 1] + 1,dp[x][y][t]);然后看一下数据范围？？？n,m≤200，K≤200，T≤40000o(n^3)显然，TLE然后何老师讲了优化方案T可以换成K因为任一区间时间内，都只向一个方向走。。。然后就可以得到转移方程dp[x][y][k] = m...
2018-12-12 13:11:09
232
原创 笔记——单调队列&&单调栈优化DP
众所周知动态规划 的 题往往 推了a long time但是o(n^3)于是就自闭了所以我们有了单调队列和栈这种东西神奇的单调队列有这么一道题朴素 o(n^2)乱搞 o(nlog n)（线段树、RMQ）然后。。。单调队列o(n)对，你没有看错，就是一遍 其实是o(2n)?!单调队列用一个东西（栈、队列、数组。。。随君所好）然后，解释都在注释里#include...
2018-12-08 21:42:29
495
原创 HH的项链----树状数组
文章目录题目描述思路遍历i，当i所在位置贝壳前面没有时，update(i,1)code题目描述点这里思路某一段贝壳中，包含了多少种不同的贝壳？最开始看见这道题时，没有思路但再看看，可以非常明了的发现这是一个树状数组ban题设有一长为5的项链1 2 3 2 1然后 m = 31 52 51 3我的思路是这样，由于要求的是种类数 != 求l 到 r 的个数每种贝壳只能存一个...
2018-12-04 14:14:59
362
原创 解题报告————最长前缀 Longest Prefix
文章目录最易懂的题解题目描述做题时的垂死挣扎思路总结最易懂的题解题目描述题目描述做题时的垂死挣扎最先看到这道题，非常开心。哈哈一笑，暴力，然后快乐TLE请大家以我为戒，做题前先看标签。然后在看到DP后，我傻眼了。（我打的就是dp啊，怎么会错一个点）我盯着电脑，看着题，想了50多分钟无关的事后。。。我终于开始了打代码思路读入时需要注意一下字符串的技巧。然后你就暴力循环dp...
2018-12-01 12:10:36
632
原创 解题报告——（shuiti）对称二叉树
文章目录题目 对称二叉树题目描述思路检查是否符合对称条件信仰深搜找答案另外code总结题目 对称二叉树题目描述题目描述思路检查是否符合对称条件条件很简单——结构对称&amp;amp;&amp;amp;点权对称要做到点权对称其实也就顺便结构对称了于是条件可以简化为点权对称可以考虑并行搜索bool con(int l,int r) { if(l == -1&amp;amp;&amp;amp;r =
2018-11-29 23:17:57
148
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人