bnu-faraway/2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018)

Info

Date:2018.10.23

Link

Solutions

A Altruistic Amphibians

unsolved

B Baby Bites

solved by


’s solution

C Code Cleanups

solved by


’s solution

D Delivery Delays

upsolved by ghc


ghc’s solution

二分套dp。\(dp[i]\)表示从店里出发,送完前\(i\)份外卖且回到店里的最早时间,有

\(dp[i]=min_{k<i} \{ max(dp[k],t[i])+f(k+1,i) \}\)

其中\(f(x,y)\)表示从店里出发,按顺序送完第\(x\)至第\(y\)份外卖后回到店里的最短时间,

\(f(x,y)=dis[1][x]+dis[x][x+1]+dis[x+1][x+2]+...+dis[y-1][y]+dis[y][1]\)

二分答案后,认为每份外卖订单的等待时间不能超过\(mid\)。dp转移时会对k产生限制,即\(max(dp[k],t[i])+dis[1][k+1]+dis[k+1][k+2]+...+dis[j-1][j] < s[j]+mid , k+1 \leq j \leq i\)

从后往前枚举k,即可实现对上述限制的\(O(1)\)更新,dp复杂度\(O(n^2)\)

E Explosion Exploit

solved by gjy


gjy’s solution

F Firing the Phaser

unsolved

G Game Scheduling

unsolved

H House Lawn

solved by gjy


gjy’s solution

I Intergalactic Bidding

solved by


’s solution

J Jumbled String

solved by


’s solution

K King’s Colors

solved by

’s solution

Replay

ghc

gjy

sk