SkyWT

Fighting 2019!

Problem Description

YJJ is a salesman who has traveled through western country. YJJ is always on journey. Either is he at the destination, or on the way to destination.
One day, he is going to travel from city A to southeastern city B. Let us assume that A is (0,0) on the rectangle map and B (10^9,10^9). YJJ is so busy so he never turn back or go twice the same way, he will only move to east, south or southeast, which means, if YJJ is at (x,y) now (0\leqslant x\leqslant 10^9,0\leqslant y\leqslant 10^9), he will only forward to (x+1,y), (x,y+1) or (x+1,y+1).

Read more...

发布 0 条评论

在一维线性动态规划里,我们经常见到形如 f(i)=min/max(f(j)+c_i)(其实可以看成 f(i)=min/max(a_i+b_j) )这样形式的转移方程。朴素做法是 \Theta (N^2)。显然这样的形式可以用单调队列维护,优化到 \Theta (N)。但是如果遇到 f(i)=min/max(a_i\ast b_j+c_i+d_j) 这样的,似乎用单调队列就难以维护了……因为 a_i\ast b_j 既与 i 有关,又与 j 有关。这时候就要用到另一种优化方式:斜率优化。

Read more...

发布 0 条评论

今天考试的时候遇到一题背包题目,我直接打了暴力的 0/1 背包,理论复杂度是 \Theta (N^3\ast W),大概是 10^9 这个级别……时限 1s,交上去就全部 TLE 了……然后我就想起了这个终极优化模板,加上以后居然全 A 了!时间居然只有 200ms 左右……

10^9 级别居然都可以压过去!!!

Read more...

发布 0 条评论

这年头,离开了 Google 已经不能活了。Chrome 标签页同步用 Google,搜索用 Google,云盘用 Google……然而在学校机房 Ubuntu 16.04 上安装小飞机就不如 Windows 上方便(不过其实也挺方便的)。

Read more...

发布 0 条评论