「JoyOI」P1001 – 1099题解(44 / 99)by hzwer

2016年8月25日66,8856

只写简要题解,详见JoyOI官方题解

我会尽量给出简单直白的代码

「JoyOI1001」第K极值

排序,计算出m并判断其是不是质数

只需要循环到√m即可

「JoyOI1002」NOIP2005谁拿了最多奖学金

模拟

「JoyOI1003」越野跑

如果是平地,来回要花2F时间,否则花U+D的时间

「JoyOI1004」滑雪

记忆化搜索,从每个点向更低点记忆化深搜

「JoyOI1005」NOIP2005采药

01背包,f(i)表示花费i的时间能获得的最大价值

第二重时间倒序循环,保证一种草药只选一次

「JoyOI1006」NOIP2008ISBN号码

模拟

「JoyOI1007」NOIP2008排座椅

先统计划分某一行/列能减少多少说话的对数

贪心取最大的若干行/列

「JoyOI1008」NOIP2008传球游戏

用f(i,j)表示前i次传球,传给j的方案数

\[则f(i,j) => f(i+1,j+1)\]

\[f(i,j) => f(i+1,j-1)\]

\[边界f(0,1) =1\]

「JoyOI1009」NOIP2008立体图(略)

「JoyOI1010」NOIP2008笨小猴

统计一下字母的出现次数,然后同1001

「JoyOI1011」NOIP2008传纸条

可以看成从(1,1)到(m,n)找两条不相交的路径

f(i,j,k)表示传到第i个人,第一条路径在第j行,第二条路径在第k行的最大价值

「JoyOI1012」NOIP2008火柴棒等式

枚举A,B验证

「JoyOI1013」找啊找啊找GF

用\(F(i,j)\)表示消费 i 金钱 j 点 rp 能泡到的最多妹子

做一个01背包

用\(G(i,j)\)表示最小的代价

「JoyOI1014」乘法游戏

用dp(l,r)表示将 l 到 r 移动到只剩两张卡片的最小分数

枚举区间内最后一张取出来的牌,则

\[dp(l,r) = min\{dp(l,k)+dp(k,r)+a_l*a_k*a_r\}\]

记忆化搜索

「JoyOI1015」公路乘车

\[F_i表示移动i公里的最小代价\]

\[则F_i=min\{f_{i-j}+m_j\}\]

「JoyOI1016」NOIP2001装箱问题

最简单的01背包问题,f(i)表示能否得到 i 的体积

推荐阅读《背包九讲》

「JoyOI1017」冗余关系

并查集,依次合并集合,输出有多少次合并是无效的

「JoyOI1018」阶乘统计

答案可以直接用long long存下来,去掉0之后输出它的最后几位

「JoyOI1019」配对

将A数列从小到大排序,B数列从大到小排序,依次配对

「JoyOI1020」寻找质因数

对每个数字分解质因数

「JoyOI1021」线段长度

将坐标排序后,计算每一条小线段对答案的贡献

「JoyOI1022」进制转换

从低位开始,用n除以该位的进制数,看结果是否为奇数,注意要开longlong

「JoyOI1023」奶牛的锻炼

用f(i,j)表示第i天结束,疲劳值为j的最远跑步距离

则\(f(i,j)=f(i-1,j-1)+D_i\)

\(f(i,0)=max\{f(i-j,j)\}\)

「JoyOI1024」外星人的密码数字

根据第一行的字母表得到每个字母的权值

然后用\(O(n^2)\)的dp来求最长不降子序列

\(f_i\)表示以第i个字母结尾的最长不降子序列

\(f_i=max\{f_j\}+1\)(第j个字母权值不大于第i个字母)

「JoyOI1025」单数?双数?

不明觉厉

「JoyOI1026」犁田机器人

由于地图小指令少,所以模拟即可

每次把要犁的地for一遍,打上标记,最后统计标记数量

复杂度\(O(XYL)\)

「JoyOI1027」木瓜地

从(1,1)开始搜索,每次走相邻的最大值,走过的格子赋值为-1

「JoyOI1028」Bessie的体重

同1016

「JoyOI1029」牛棚回声

枚举答案,正反模拟判断

「JoyOI1030」乳草的入侵

从起点开始bfs,注意坐标的方向

「JoyOI1031」热浪

求Ts到Te的最短路,随便选种算法写都可以

这里给出的是堆优化的dijkstra

「JoyOI1032」零花钱

小的面值能整除大面值,因此可以想到一个贪心的做法

先用尽量大的面值凑,最后选一个面值最小的,这样可以使浪费尽可能少

「JoyOI1033」悠闲的漫步

给出一棵树,求出1号点出发的最远距离

搜索或者dp皆可

「JoyOI1034」尼克的任务

用f(i)表示到第i分钟,最大的休息时间

若i分钟没有工作开始,则更新f(i+1)

否则要做一个工作

当然最短路也可以

「JoyOI1035」棋盘覆盖

二分图匹配经典问题,先把棋盘黑白染色

一色分为X部,另一色分为Y部,每个黑色点向周围连边,匈牙利算法求最大匹配数量

当然网络流也可以

「JoyOI1036」统计数字

把所有数字排序,就能很方便地得出每个数字出现次数了

「JoyOI1037」阶乘统计2

高精度乘法,维护非0的最后20位

「JoyOI1038」忠诚

线段树入门题,线段树的学习材料应该比较多,这里提供一个模板供参考

「JoyOI1039」忠诚2

又一道线段树入门题

「JoyOI1040」表达式计算

要求实现高精度加法的表达式计算

倒着扫一遍字符串,遇到数字就把它加到当前数字的最高位

遇到加号就把当前数字加入答案后清空

「JoyOI1041」表达式计算2

要求从左往右计算才不会出现复数

用两个栈从右往左把操作和数字都记下来

然后倒过来高精度计算

「JoyOI1042」表达式计算3

先预处理把乘方变成乘法,然后从左到右计算

用一个临时的变量tmp来处理运算的优先级,即把一连串的乘除一起算完,再考虑加入答案

遇到一个加减符号就把tmp记入答案,tmp重新赋值

否则用tmp进行运算

「JoyOI1043」表达式计算4

正经的表达式计算

用一个数字栈+操作栈来实现

从左往右,将扫到的数字入数字栈,将扫到的操作与操作栈的栈顶对比优先级

如果当前操作优先级高,将其入栈

否则从数字栈中取出两个数字,用栈顶的操作进行运算

优先级次序是右括号和栈内左括号,加减,乘除,乘方,未入栈的左括号

「JoyOI1044」数字三角形

ans(i,j)表示走到(i,j)的最大路径和,从上往下一层一层递推

 

avatar
2 Comment threads
3 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
4 Comment authors
will7101JzyNewLinZiyu Recent comment authors
  Subscribe  
提醒
zy
zy

黄学长为什么在做TYVJ傻逼题啊

J
J

黄学长恐怕是要带新人了,从此化身黄老师

will7101
will7101

Orz黄老师

NewLinZiyu
NewLinZiyu

Tyvj似乎挂了

高璨

现在可以了