SkyWT

Fighting 2019!

简单来说,数位 DP 大概就是把一个数字拆开按位进行 DP 的一种思想。

HDU 3555 Bomb

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

Read more...

发布 0 条评论

Linux 下没有 Dev-cpp,每次遇到想要调试的代码就是坠痛苦的。所以我们还是得学点 gdb 调试的命令。

首先执行 g++ a.cpp -g,生成 a.out 或者 a.exe
执行 gdb a.out,出现一大段介绍,进入 gdb 调试。

Read more...

发布 0 条评论

主定理可以用来分析递归算法的时间复杂度(也叫渐进复杂度)。在以前,我们知道快速排序的时间复杂度是 \Theta (N \ast \log_2 N ) ,我们也知道它不稳定,但是我们仿佛不知道这个 \Theta (N \ast \log_2 N ) 是怎么来的……学习了主定理,我们就可以证明了~

这个“主定理”名字真的十分霸气:Master Theorem……

Read more...

发布 0 条评论

很多题目的贪心想法都是一个简单粗暴的贪心加上可“反悔”的操作。这样可以确保答案的正确性。

Description

You're Zhu Rengong, a formidable hero. After a number of challenging missions, you are finally facing the final Boss – a black dragon called Heilong. Due to his overwhelming power, you have to plan your actions carefully.

Read more...

发布 0 条评论

坠痛苦的是,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?

Read more...

发布 0 条评论

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 条评论