【TYVJ】P1001-1099题解(44/99)by hzwer

2016年8月25日14,1766

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

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

【tyvj1001】第K极值

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

只需要循环到√m即可

【tyvj1002】NOIP2005谁拿了最多奖学金

模拟

【tyvj1003】越野跑

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

【tyvj1004】滑雪

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

【tyvj1005】NOIP2005采药

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

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

【tyvj1006】NOIP2008ISBN号码

模拟

【tyvj1007】NOIP2008排座椅

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

贪心取最大的若干行/列

【tyvj1008】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\]

【tyvj1009】NOIP2008立体图(略)

【tyvj1010】NOIP2008笨小猴

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

【tyvj1011】NOIP2008传纸条

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

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

【tyvj1012】NOIP2008火柴棒等式

枚举A,B验证

【tyvj1013】找啊找啊找GF

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

做一个01背包

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

【tyvj1014】乘法游戏

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

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

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

记忆化搜索

【tyvj1015】公路乘车

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

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

【tyvj1016】NOIP2001装箱问题

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

推荐阅读《背包九讲》

【tyvj1017】冗余关系

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

【tyvj1018】阶乘统计

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

【tyvj1019】配对

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

【tyvj1020】寻找质因数

对每个数字分解质因数

【tyvj1021】线段长度

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

【tyvj1022】进制转换

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

【tyvj1023】奶牛的锻炼

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

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

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

【tyvj1024】外星人的密码数字

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

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

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

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

【tyvj1025】单数?双数?

不明觉厉

【tyvj1026】犁田机器人

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

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

复杂度\(O(XYL)\)

【tyvj1027】木瓜地

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

【tyvj1028】Bessie的体重

同1016

【tyvj1029】牛棚回声

枚举答案,正反模拟判断

【tyvj1030】乳草的入侵

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

【tyvj1031】热浪

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

这里给出的是堆优化的dijkstra

【tyvj1032】零花钱

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

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

【tyvj1033】悠闲的漫步

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

搜索或者dp皆可

【tyvj1034】尼克的任务

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

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

否则要做一个工作

当然最短路也可以

【tyvj1035】棋盘覆盖

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

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

当然网络流也可以

【tyvj1036】统计数字

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

【tyvj1037】阶乘统计2

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

【tyvj1038】忠诚

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

【tyvj1039】忠诚2

又一道线段树入门题

【tyvj1040】表达式计算

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

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

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

【tyvj1041】表达式计算2

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

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

然后倒过来高精度计算

【tyvj1042】表达式计算3

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

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

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

否则用tmp进行运算

【tyvj1043】表达式计算4

正经的表达式计算

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

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

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

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

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

【tyvj1044】数字三角形

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

 

  • […] 前100题代码见 【TYVJ】P1001-1099题解(6/99)by hzwer […]

    #1  
  • NewLinZiyu2016年7月27日 上午9:47 回复

    Tyvj似乎挂了

    #2  
    • 高璨2016年7月31日 下午9:09 回复

      现在可以了

      #21
  • zy2016年8月12日 下午11:18 回复

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

    #3  
    • J2016年8月19日 下午7:36 回复

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

      #31
      • will71012016年8月19日 下午10:31 回复

        Orz黄老师

        #32