「bsoj5041」挑战nbc - 数论 发表于 2017-10-07 更新于 2019-06-10 分类于 OI Valine： 题目大意 Abwad现在拿到了难度为1,2,3,……,n的n道原题，每次操作他可以挑出任意两道题，并使用一种叫做“NOIP二合一”的方法合成一道难度为其平均值的题。Abwad希望在操作了n-1次之后，最后剩下的那道题难度最大。 题目分析显然我们从小到大合并可以做到最后的难度最大。我们可以得到以下式子： 阅读全文 »
「jzoj5173」B - 分数规划+最优比例环 发表于 2017-10-07 更新于 2019-06-10 分类于 OI Valine： 题目大意 求最小平均权值的环。 题目分析这道题是01分数规划中的一类—最优比例环。与此类似的一道题是【USACO 2007 December Gold】奶牛的旅行Sightseeing Cows 阅读全文 »
「CQOI2011」放棋子 - 动规Dp+组合数学 发表于 2017-10-06 更新于 2019-06-10 分类于 OI Valine： 题目大意 在一个n行m列的棋盘里放一些彩色的棋子，使得每个格子最多放一个棋子，且不同颜色的棋子不能在同一行或者同一列。有多少种方法？例如，n=m=3，有两个白棋子和一个灰棋子，下面左边两种方法都是合法的，但右边两种都是非法的。 阅读全文 »
「bsoj1159」背包 - 贪心 发表于 2017-10-06 更新于 2019-06-10 分类于 OI Valine： 题目大意 多组询问，有$n$个物品，每个物品有占用体积$a$，同时占用过后会归还一部分体积$b$，询问能否将所有物品选完。 对于1~4个测试点，T=10,1≤n≤9,1≤V≤100000,0≤a,b≤100000对于5~8个测试点，T=20,1≤n≤1000,1≤V≤100000,0≤a,b≤100000对于9~12个测试点，T=5,1≤n≤100000,1≤V≤1000,0≤a,b≤1000对于13~16个测试点，T=500,1≤n≤1000,1≤V≤100000,0≤a,b≤100000对于17~20个测试点，T=8,1≤n≤50000,1≤V≤100000,0≤a,b≤100000 阅读全文 »
「2015四校联考-一中」避难向导 - 树形动规+倍增 发表于 2017-10-03 更新于 2019-06-10 分类于 OI Valine： 题目大意 题目分析我们可以用两次树形动规预处理出安全系数Si方法就是先用一次Dp求出子树的最长距离以及子树的次长距离。再用一次Dp求出来自父亲的距离，要注意排开自身信息（不能把自己的信息再从父亲传下来），故要记录$From[i]$表示$i$的最长距离来自哪边。 阅读全文 »
「2015四校联考-一中」疫情延迟 - 二分+最短路径 发表于 2017-10-03 更新于 2019-06-10 分类于 OI Valine： 题目大意 题目分析好的这道题显然可以使用二分+Dijkstra，偷懒不讲了。 阅读全文 »
「2015四校联考-一中」病毒分裂 - 折半递归/矩阵快速幂 发表于 2017-10-03 更新于 2019-06-10 分类于 OI Valine： 题目大意 求 $(1+k+k^2+k^3+\cdots+k^{n-1})\bmod p$ 的值。 题目分析这道题可以使用折半递归的方法做，具体的就是每次分一半，右边的就是左边的乘上$k^x$，每次丢掉一半，时间是$O(\log^2n)$的。 我们还可以使用矩阵快速幂做这道题。（本人构造的矩阵很智障？） 阅读全文 »
「bsoj4496」关于女朋友 - 最短路径树+倍增 发表于 2017-10-03 更新于 2019-06-10 分类于 OI Valine： 题目大意 给出一个图，要求多次询问从1出发至少往$x[i]$沿最短路走$k[i]$条边或走$t[i]$分钟，然后走到$n$的最少时间。注：往$x[i]$走的不算做要求输出的时间。 题目分析从1开始建立最短路径树，并预处理出每个点到达$n$的最短路径长度。接着用Sparse_Table稀疏表预处理出树上的$k$倍祖先及到达$k$倍祖先路径上走到$n$的最短路径最小值。对于给定的询问，我们爬爬树即可。 阅读全文 »
