SkyWT

SkyWT

我们的征途是星辰大海

🚧 本站已迁移到 skywt.cn/blog。所有链接都已重定向。
✨ 如果想体验这个 Typecho 博客主题,可访问 beta.skywt.cn

坠痛苦的是,POJ 的辣鸡 G++ 编译器不支持 long long,害得我调试调了半天……

Description

For every pair of triplets, $T_a = (I_a, J_a, K_a)$ and $T_b = (I_b, J_b, K_b)$, we define the difference value between $T_a$ and $T_b$ as follows:

$$ D(T_a, T_b) = \max (I_a − I_b, J_a − J_b, K_a − K_b) − \min (I_a − I_b, J_a − J_b, K_a − K_b) $$

Now you are given $N$ triplets, could you write a program to calculate the sum of the difference values between every unordered pair of triplets?

More...


这题思路很简单,但是调试花了我一个下午……最后发现是一种情况没取 abs……(吐血)

题目链接:POJ 3977 Subset

More...


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)$.

More...



在一维线性动态规划里,我们经常见到形如 $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$ 有关。这时候就要用到另一种优化方式:斜率优化。

More...


Topcoder Single Round Match 634 Div 2 T3 SpecialStrings 题解

More...


Topcoder Single Round Match 635 Div2 T3 LonglongestPathTree 题解

More...


所谓二分图(Bipartite Graph)就是这样的一个图:

简单地说,就是一张图里的所有点可以分为两组(如上图),并且每条边都跨越两组。这样的图就是二分图。

More...


Topcoder Single Round Match 616 Div 2 T3 题解

More...


Topcoder Single Round Match 640 Div 1 T1 ChristmasTreeDecoration 题解
别看了,这篇博客很水……

More...