T1 number
计算字符的数量就好了。。。。
T2 transfer
模拟,如果是地铁的话,就把它的时间和票价记下来,用数组记下。。。
如果是公交,那就把记下的时间和票价从数组的标记处循环,和公交比,用过了的票标记-1。。。。
如果地铁的票超时了就把标记往前挪。。。当时没有这一步的三行,然后时间超限40。。。
t3 souvenir
当时看到这个就????于是就刷了特例1和2。。。
正在推背包。。。
t4 work
想到是最短路径,但是只打出了30。。。。
T1 number
计算字符的数量就好了。。。。
T2 transfer
模拟,如果是地铁的话,就把它的时间和票价记下来,用数组记下。。。
如果是公交,那就把记下的时间和票价从数组的标记处循环,和公交比,用过了的票标记-1。。。。
如果地铁的票超时了就把标记往前挪。。。当时没有这一步的三行,然后时间超限40。。。
t3 souvenir
当时看到这个就????于是就刷了特例1和2。。。
正在推背包。。。
t4 work
想到是最短路径,但是只打出了30。。。。
NO.1
hh
NO.2
我我我我我一不小心把一些符合条件的票踢出队列了。
zz
蒟蒻数据毁我青春
这题单纯模拟就好了
没啥好说
NO.3
想不出=骗分=10分
背包是个什么玩意儿
NO.4
大意就是一个人要生产一个型号不为1的零件n,然后叫上传送带上的小伙伴一起生产零件n-1,然后传送带上的小伙伴叫上传送带上的小伙伴一起生产零件n-2......直到生产到原材料为止,然后问轩轩能不能抽空去抠jio蹦迪什么的
我大概是打了个找儿子函数?
挺短但超时了
听Father.汤 说要打堆还是什么鬼玩意儿
反正不会。。。
考前跟hjj去买了好多吃的 准备在考场里"野餐"
到了考场 发现右边没人 很宽敞很幸运!!
T1是字符串 草草打完的同时检查了好几遍。
T3不会做 用得分点t=1骗了10分
T4直接模拟 抱着0分的希望打 因为知道输送带是个环的情况不成立
最后还有25就很幸运
一看到T2就感jio是队列!!
两分钟后
内心OS:woc这不对啊
于是 队列 模拟√
好的 俺和省一 只差俩分钟
立个flag:明年没省一 名字倒着念!!
最后成绩100+35+10+25=170
在香港澳门云南贵州河北新疆等等好多好多好多(*N)省是省一
o俺想改户口!!
t1
没啥好说的就计算字符的数量就好了
t2
模拟,如果是地铁的话,就把它的时间和票价记下来,用队列记下。
如果是公交,那就把记下的时间和票价公交做比较,用过了的票标记一下。
可以用一个队列,然后如果做地铁的票超时了可以出队。
当时只顾着比时间,忘记了时间没超过还可以再用,直接把票价比公交小的优惠卷给出队了
t3
当时看到这个就想到了背包,但不知道怎么推,于是就刷了样例。
t4
当时打了个宽搜,想到是最短路径,但想着打宽搜会保险一点。
110分
卑微
水题AC
爆零
主要是标记用过的优惠票出了问题,
我把用过票的钱调到了INF,结果出现了《无限优惠(白嫖记)》,优惠票直到时间过了都可以无限用,然而只要把钱调到-1就好了
卑微的10分
踩分失误
爆零
踩分失败
省一210
《假如给我题二AC》
T1
简单的判断,八个字符,错了真的也是没有办法了
T2
一道可以暴力的模拟题,我也不知道为什么比赛的时候我会少打队列的一个判断,可能太紧张了。基于此应该想到可以利用优先队列(或类似)的数据结构来维护,每次坐公交,在所有价值大于本次票价的优惠券中优先使用过期时间最早的(不用就过期了!),价值最低的优惠券。一旦票过期了,就删掉,但是如果票只是价值不够,那可能后面还会有用,所以还要压回去。
T3
本题思路可以根据数据范围来想。这是一道动态规划题。
刚开始想到的是建立一张全图,但是后来发现节点数量不是N 而是N*T ,并且总价值也不一定只能走一条路。后来发现可以用动态规划解决,首先设f[x]是第x天能够赚到最多多少钱。那么f[1] = m。重点在于状态转移,f[ i ] 肯定是由f[1]到f[i-1]中推出来的,而且单独一个f[i-1]无法表示所有状态。所以假设当前处于状态j ,将第j 天物品的价格可以看作花费,第i天的物品价格看作价值,就做出了一个完全背包问题,背包容量是当天的金币数f[j] 。
if(f[k]<=f[ k-a[i-1][j] ] - a[i-1][j] + a[i][j])
f[k]=f[k-a[i-1][j]]-a[i-1][j]+a[i][j];
跟完全背包基本一样,就是将其改成了数组。考试的时候想不出来,根据那个数据范围,也可以扣个十分甚至更多。
T4
最短路径把。再判断一个有环无环,有环就跳出来,然后一直往前搜。
那曾经美好的时光,
是我永远沉醉的梦想。
那奔腾燃烧的岁月
——永生难忘。
有时候我想,生命是一条奔腾不息的大河,你永远无法赶上。
有些遗憾,有些不甘,但从来都无可奈何。
这次比赛,我唯一的成就就是,每道题都有分。