A-小杜要迟到了！ 题解 比较(n-1)*a和 (n+k-2)*b的大小，按要求输出结果即可。 时间复杂度O(1) 参考代码 #include<bits/stdc++.h> #define ll long long #define L(i,j,k) for(ll i=(j);i<=(k);++i) #define R(i,j,k) for(ll i=(j);i>=(k);--i) #define inf 2e9 #define fi first #define se second #define pb push_back #define mkp make_pair #d...

HDU多校4 赛中5题（都是队友过的 1004 题意：给一个边长为n的大正三角形，由许多边长为1的小正三角形组成。在所有小三角形的每个顶点中填写0,1或2，满足大三角形的左侧不应出现0。大三角形的右侧不应出现1。大三角形的底侧不应出现2。对于每个小三角形，三个顶点的总和不应是3的倍数。询问是否可以填写出这样的大三角形。 （想了半天硬是没推出一个Yes的，一看榜单过了好多人，猜一手结论不存在这样的大三角形） 思路：输出No即可。具体证明过程见官方题解。 1006 题意：DLee按顺序买了n张票，如果之前花费的总票价≥100，之后的票打8折；如果之前花费的总票价≥200，之后的票打5折。但是DLe...

HDU多校3 赛中3题，菜… 1003 签到题，将每个单词压缩成大写的首字母 1012 题意：给定两个长度都为n的排列P、Q以及一个一开始为空的序列R，每次操作你可以从P或Q中弹出最左边的一个数字放入R的最右边。给定R，求有多少种操作方式能生成序列R。 思路：动态规划，考虑R[i]是由P[j]还是Q[k]转移过来的，因为P和Q都是排列，所以可以确定当前j和k的值。 #include<bits/stdc++.h> #define ll long long #define L(i,j,k) for(ll i=(j);i<=(k);i++) #define R(i,j,k) for...

HDU多校2 赛中五题，总结：签到、签到、枚举、枚举以及一道讨论到头大的线段树 1002 题意：去掉字符串中的“std::make_tuple”。 思路：遇到's'直接i+=14即可。遍历输出。 #include<bits/stdc++.h> #define ll long long #define L(i,j,k) for(ll i=(j);i<=(k);i++) #define R(i,j,k) for(ll i=(j);i>=(k);i--) #define inf 0x3f3f3f3f3f3f3f3f #define fi first #define se se...

HDU多校1 赛中过了四题，代码能力真的捞，都是一眼思路然后敲大半个小时…… 1011 题意：[0,1]随机生成n个数，然后m次操作，每次随机删除最小或最大的一个数，求最终剩下的数的和的期望。 思路：众所周知，期望这东西应用在随机数上，那就是他的平均值，即0.5。m次操作后剩下(n-m)个数，那么它的和的期望就是0.5*(n-m)，注意求下逆元即可。 #include<bits/stdc++.h> #define ll long long #define L(i,j,k) for(ll i=(j);i<=(k);i++) #define R(i,j,k) for(ll i=(...

北华大学计算机程序设计算法提高训练营个人赛 · 题解 前言：由于实力有限，在命题方面可能尚有不足，望各位海涵。 A-签到题 B-签到题 设二元一次方程组求解即可 C-签到题 化简式子 ∑i=1n−1(ai+1−ai)=an−a1\sum_{i=1}^{n-1}(a_{i+1}-a_i)=a_n-a_1∑i=1n−1​(ai+1​−ai​)=an​−a1​ 只需找出数组中的最大值和最小值，相减即可得到两个最值 D-贪心 考虑溢出最少，就先考虑先将其尽可能填满（无溢出） 之后优先考虑再加小书； 如果小书不够，考虑加中书，并在保证达到目标的前提下去掉几本小书； 如果中书不够，考虑加大书，并在保证达到...

题解链接：https://blog.nowcoder.net/n/47f1fcc5b340424db5fe4ab08ad83e5e

Subpermutation 题意： 将 n 的所有排列按字典序连接成一个新的序列，求在该序列中有多少连续子序列是 m 的排列。(1≤m≤n) (mod 1e9+7) 思路： 很明显，m的排列要么出现在一个n的排列中，要么出现在连续的两个n排列中。分类讨论。 1. m的排列在一个n的排列中 1 至 m 的排列有 m!m!m! 种； 将 1 至 m 视为一体，与剩余 n−mn-mn−m 个数排列有(n−m+1)!(n-m+1)!(n−m+1)!种。 共计为 m!(n−m+1)!m!(n-m+1)!m!(n−m+1)! 种 2. m的排列在连续的两个n排列中 假设一个排列为{p1,p2,...,p...

G-好心情没了 （愚人节快乐，很明显，这篇题解是在愚人节的背景下赶出来的 很明显，这题就是一个A题的hard版本，那么我们先回顾一下A题我们是怎么做的。 A题：愚人节是个令人开心的节日，所以小沙为了让大家开心，选择让大伙乐呵乐呵，如果你说的话让小沙开心了，小沙也会让你开心。 我们可以发现，A题的题目概括下来，就是我们要让小沙开心，才能让我们自己也开心。所以我们要怎么哄小沙开心呢？这是一个很哲学♂的问题。我们总结经验发现有这么几种方法。 先找出让他不开心的缘由，有误会就先进行解释；做错就要道歉，勇于承认错误，做一个知错就改的好孩子。 接着到商场去，给他买一份心仪的礼物。带着礼物到他家里做客。 ...

题7 - 树上行走 最近做到的牛客挑战赛57的C题，我拿来分析一下 题目要求两个操作： 给定 x,y，令 x→y 的最短路上的点构成的点序列为 p，对于所有 i>1，令 b[ p[i] ] 增加 a[ p[i-1] ] 给定 x，输出 b[x] 的值。 很明显的树链操作，对于 x 到 y 的最短路径上的点的计数器 b 依次加上前一个点的点权 a。 一样的先树链剖分，对于一个结点，我们可以发现只需统计三个值： 由父亲加过来的点权 由重儿子加过来的点权 由其他轻儿子加过来的点权 在操作1中，因为 x 到 y 的重链数量为logn量级，所以可以发现，第3个值的统计也为logn量...

题6 - 小沙的身法 寒假训练营2的一道题 给定一棵树的路径关系，每个结点有一个高度，从低到高需要花费它俩高度之差的体力。有m个询问，每次询问从 x 到 y 结点需要花费多少体力（刚开始在地面，需要从地面上到结点x）。 思路：因为没有修改操作，直接前缀和即可（ max(0,差值) 的前缀和）。做dfs序的前缀和与后缀和。由x到LCA(x,y)的过程中，是从dfn大的一端跑向小的一端，因此用后缀和；由y到LCA(x,y)的过程中，是从dfn小的一端跑向大的一端，因此用前缀和。 代码： #include<bits/stdc++.h> #define ll long long #defi...

题5 - [JLOI2014]松鼠的新家 给定一棵树的路径关系，给定一个访问结点的顺序序列a，先去a1，再去a2，……，最后到an。同时每经过一次结点，结点权值+1，对于最后一个访问的结点不用+1。最后询问每一个结点的权值。 思路：对于从x结点去y结点，只需将x到y的链上权值+1，同时对y结点权值-1即可，模板题。 代码： #include<bits/stdc++.h> #define ll long long #define L(i,j,k) for(ll i=(j);i<=(k);i++) #define R(i,j,k) for(ll i=(j);i>=(k);i...