博文
zoj 2301 Color the Ball(2007-03-13 15:34:00)
摘要：在线段染色之类的题目中，这是一种很常见的做法。这里还可以用到线段树，可惜我还不会：-（
事实上，这也算最简单的离散化题目了。关键在于判断何时两条线段可以合并，何时拆散，合并后对多于线段的处理也很重要。值得高兴的是我qsort可以写的很熟练......
#include <cstdio>
#include <cstring>
#include <cstdlib>
typedef struct
{
int b, e;
char c;
} sect;
sect s[2001], r[20001];
int N, r_size, mx, ans_b, ans_e;
int cmp ( const void *a, const void *b )
{
sect *A, *B;
A = ( sect * ) a, B = ( sect * ) b ;
return A->b > B->b ? 1 : -1;
}
int gt ( int a, int b )
{
return a > b ? a : b;
}
void init ()
{
int i;
r_size = 0, mx = 0;
for ( i = 0; i < N; i ++ )
{
scanf ( "%d %d %c ", &s[i].b, &s[i].e, &s[i].c );
//printf ( "%d %d %c\n", s[i].......
zoj 2002 Copying Books(2007-03-11 23:58:00)
摘要：经典的判定。对N个正整数的k-划分，要求的是划分中最大数的最小值。如有相同最小值，使前面的划分和最小。
这题的思路是穷举这个最小值，然后计算是否满足k划分。设当前的划分数为x，mx得到的是满足x<=k的最小值。穷举的过程可以用二分。
判定计算采用的是贪婪算法，从后向前，尽量使后面的划分之和在要求判定的值范围内最大。同时把划分处b[i]置1。
另外，有可能出现mx的划分数x<k，而mx-1的划分数x>k的情况。此时为了使前面的划分最小，只消将前面几个空闲的b[i]置1即可。
#include <cstdio>
#include <string>
int m, n, t, b[501]; //seperate
double a[501], sum, mx, mn; //book
int check ( double chk_n )
{
int i, total = 0;
double t_sum = 0;
memset ( b, 0, sizeof ( b ) );
for ( i = n - 1; i >= 0; i -- )
{
t_sum += a[i];
if ( t_sum > chk_n )
{
t_sum = a[i];
......
Zoj 1222 Just the Facts(2007-03-02 22:54:00)
摘要：这是标准的数学题。求N!的非零末位。
这也是标准的BT题，光是N就可以到100位。完全没有直接做的办法。还是看LeeMars的报告吧!
首先考虑某一个N!(N < 10)，我们先将所有5的倍数提出来，用1代替原来5的倍数的位置。由于5的倍数全被提走了，所以这样就不会出现尾数0了。我们先把0..9的阶乘的尾数列出来（注意，5的倍数的位置上是1），可以得到table[0..9] = (1, 1, 2, 6, 4, 4, 4, 8, 4, 6)。对于N < 5，直接输出table[N]即可；对于N > = 5，由于提出了一个5，因此需要一个2与之配成10，即将尾数除以2。注意到除了0 !和1!，阶乘的最后一个非零数字必为偶数（显然，因为在N!的质因数里2的个数要多），所以有一个很特别的除法规律：2 / 2 = 6，4 / 2 = 2，6 / 2 = 8，8 / 2 = 4。比较特殊的就是2 / 2 = 12 / 2 = 6， 6 / 2 = 16 / 2 = 8。这样我们就可以得到如下式子：
代码:
table[N]
F(N) = ------------ (0 <= N < 10)
2^([N/5])
再考虑复杂的。考虑某一个N!(N >= 10)，我们先将所有5的倍数提出来，用1代替原来5的倍数的位置。由于5的倍数全被提走了，所以这样就不会出现尾数0了。我们观察一下剩下的数的乘积的尾数，通过table表，我们发现这10个数的乘积的尾数是6，6 * 6的尾数还是6，因此我们将剩下的数每10个分成一组，则剩下的数的乘积的尾数只与最后一组的情况有关，即与N的最后一位数字有关。由于我们把5的倍数提出来了，N!中一次可以提出[N/5]个5的倍数，有多少个5，就需要有多少个2与之配成10，所以有多少个5，最后就要除以多少个2。注意到除2的结果变化是4个一循环，因此如果有A个5，只需要除(A MOD 4)次2就可以了。A MOD......
Zoj 2422 Terrible Sets(2007-03-02 15:31:00)
摘要：此题是zoj1985的变种。
1985的每个小矩形没有宽度w，只有高度h。故加入计算从第x1到第xn个矩形的w总和。对于每个小矩形i，求以其为最小基准左右能到达的位置，然后计算总面积。
其中cqf用迭代求左右两侧最多能到达矩形的方法尤为经典。
#include <cstdio>
#include <string>
typedef struct
{
int w, h;
} Rect;
Rect a[50001];
int n, l[50001], r[50001], s[50001];
void pt ( int i )
{
printf ( "l%d r%d s%d h%d\n", l[i], r[i], s[r[i] + 1] - s[l[i]] , a[i].h);
}
int main ()
{
//freopen ( "in.txt", "r", stdin );
while ( scanf ( "%d", &n ) && n != -1 )
{
int i, ii, sum = 0;
s[0] = 0;
for ( i = 0; i < n; i ++ )
{
scanf ( "%d %d", &a[i].w, &a[i].h );
sum += a[i].w;
s[i + 1] = sum;
}
for ( i = 0; i < n; i ++ )
{
ii = i;
while ( ii > 0 && a[i].h <= a[ii - 1].h)
&nbs......
Zju 2059 The Twin Towers(2007-02-18 16:35:00)
摘要：最近几天在研究usaco，那是一个很有趣的地方，做起题来像通关游戏，所以zoj倒做得少了。不有趣的地方是一旦一道题解不出，就像碰到一位大Boss，死打也不扣血，非得你跑到城外去拼命练级方可过关。于是回过头来写写以前没做出的几道简单dp题，这就是其一。
题目的大意如下：有一列N个水晶，把他们搭成双子塔，要求塔高一样，求塔的最大高度。当初做的时候不小心看错了条件，以为每块水晶最大高度是2000，接着开了个200000的数组，自己机子都过不了。今天看了busycai的程序，才明白搞错了。总高度是2000，所以O(n) = N×2000.时间还算不错。
起初想用b[i]来表示塔高为i的某种状态（塔高之差？或是别的什么），结果想了半天不得其解。其实把设定倒过来，当bi表示塔高之差为i的时候，对总高度dp，这样就简单了。
对0<= i <= 2000，当在左或右边放入a[k]之后，差有两种可能，i + a[k], i - a[k]。然后更新，即可。
#include <cstdio>
#include <string>
int abs ( int i )
{
return i > 0 ? i : -i ;
}
int N, a[101], b[2][2001], p;
int main ()
{
//freopen ( "in.txt", "r", stdin );
while ( scanf ( "%d", &N ) && N >= 0 )
{
int i, end, j, k;
for ( i = 0; i < N; i ++ )
{
&......
恋爱游戏猛于虎(2007-02-15 21:22:00)
摘要： 电驴真是个好东西。收集稀奇古怪、见所未闻的资料，打发几辈子的空闲时间，真是再好不过了。所以我以前把电驴的下载目录取名为D&D，Download and Delete，一个极具西方魔幻色彩的名字。
可古人也云，林益大而鸟欲来。东西下多了，Install多了，什么样的毛病都有。昨天在电驴上，看到一个叫做“魔兽学园”的后宫向老游戏，我很高兴。于是半个小时后，这个游戏的安装包顺理成章里落到了我的硬盘上。老实地说，我对“樱花大战”这样的恋爱养成+弱智战棋类AVG并不是很感冒；而且众所周知，ELF和EGO以做HGame闻名，我又是一位牢记八荣八耻的良好公民，“电车之狼通关图档”之类的文件夹是不会出现在我的U盘里的。但既来之，则安之，家里的电脑也只能玩玩这样的老游戏了。
那么玩之。具体的游戏不想描述，日式AVG都是一样，只需要点点鼠标，躺在椅子上就可以看剧情。唯一不一样的是它还有战斗，战斗居然还很复杂。
正在我悠闲地给自己倒上第三杯立顿奶茶的时候，突然从右下角弹出一个模糊的对话框，幽幽地发着绿光。俗话说，不做亏心事，不怕鬼上门。我从来不写恐怖小说，向来只和程序打交道，在我的世界里没有幽灵存在的位置。
因此我拈起手边的奥利奥，给自己占了一卦。饼干微微发黑，卦象大凶，于是我把它吃掉，又重新占了一卦。
不一会儿绿光和奥利奥都消失了，于是我心安理得地继续狂点鼠标。一夜无事。
今天中午，日照三竿。我揉揉眼，坐到电脑前，打开dfo，想看看昨天梅子灌了Ajax几个球。不料弹出来一行大字：该页无法显示。其他网站却一切照旧，该自杀的自杀，该炒作的炒作。
奇怪啊，难道是昨天看球前没有祭祀神灵？我可是很虔诚的啊。
然后msn在右......
Zju 1705 Exchange Rates(2007-02-14 20:30:00)
摘要：放到图论里面，是因为用到了近似Floyd的算法。这题的输入麻烦，到最后直接用C++搞定了。
题目给出一系列物品之间的交换关系（比如6个i交换15个k），要求递推计算出给出的物品之间交换关系。采用的方法是建立图。a[i][k]代表了i和k交换时需要i的个数，a[k][i]是需要k的个数。每次更新信息之后对图遍历，对于那些已知a[i][j]和a[j][k]的路径，求出a[i][k]，就如同Floyd求最短路径一样。
其实不用vector和string也可以解决，但是懒惰了 = = 。
PS:到了寒假，ZOJ似乎又复苏了，做题目的人好多。当初信心满满地想着要在3月份前做到400题，现在看起来像个笑话。好吧……随便做点，我最大的计划就是没有计划。
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
int a[60][60];
vector < string > sv;
void ps ()
{
int i, k;
for ( i = 0; i < sv.size (); i ++ )
{
for ( k = 0; k < sv.size (); k ++ )
{
printf ( "%d ", a[i][k] );
}
}
}
int gcd ( int x, int y )
{
int t;
if ( x > y )
{
t = x, x = y, y = t;
}
while ( x )
{
t = x;
x = y % x;
y = t;
}......
sort和qsort(2007-02-05 00:00:00)
摘要： 这是最好的时代，这是最坏的时代。
——狄更斯
当在pascal里埋头苦干的前辈们还在为快排和堆排哪个效率更高争吵不休时，我们拥有了qsort。
当我还在为qsort里最后一个参数愁眉苦脸时，STL的工程师们发明了sort。
——Crux.D
qsort(array,asize,sizeo......
Zju 1787 Tiling Up Blocks(2007-01-27 22:25:00)
摘要：这道题相当的经典，本身就有很多做法，而CQF大牛的做法尤为精妙。
给出一系列零件Si，零件有两个参数Ai Bi。现在将其排序，要求若i>j，则Ai>=Aj Bi>=Bj。也就是前面的两个参数要分别小于等于后面的两个参数。求此队列的最大长度。
那么如果将其投影到二维平面上，对每个零件Ai Bi点计数，那么问题就转换成为从最左下的1 1到左上的100 100，只能向右和向上运动，求运动过程中的访问总和最大值。
因此只要把每个点下面和左面的点比较，大者记入此点总和即可。
今天偶然看了一下排名，ZOJ果然有没落的倾向，而据说POJ越来越繁荣了。
#include <cstdio>
#include <string>
int n, a[101][101], b[101][101], nx, ny, mx, my;
int maxi ( int a, int b )
{
return a > b ? a : b;
}
void pb ()
{
//printf ( "%d %d %d %d\n", mx, my, nx, ny );
int i, k;
for ( i = nx; i <= mx; i ++ )
{
for ( k = ny; k <= my; k ++ )
{
printf ( "%d ", b[i][k] );
}
printf ( "\n" );
}
}
void init ()
{
memset ( a, 0, sizeof (a) );
memset ( b, 0, sizeof (b) );
mx = my = 0, nx = ny = 101;
}
int dp ()
{
int i, k;
for ( i = nx; i <= mx; i ++ )
&nb......
Zju 1731 Supermarket(2007-01-27 01:34:00)
摘要：
Supermarket
Time limit: 10 Seconds Memory limit: 32768K
Total Submit: 134 Accepted Submit: 70
A supermarket has a set Prod of products on sale. It earns a profit px for each product x in Prod sold by a deadline dx that is measured as an integral number of time units starting from the moment the sale begins. Each product takes precisely one unit of time for being sold. A selling schedule is an ordered subset of products Sell (subset of Prod) such that the selling of each product x in Sell, according to the ordering of Sell, completes before the deadline dx or just when dx expires. The profit of the selling schedule is Profit(Sell)=sum of px (x in Sell). An optimal selling schedule is a schedule with a maximum profit.
在一个超市里，有一系列商品出售。从开始出售到截止期dx前，它可以获得利润px。每件商品精确地花费一个单位时间。一张销售计划表是一个销售商品的顺序子集，它包括了每个商品的利润px，和它的销售时间（次序），这个时间必须小于等于dx。销售计划的总利润是每个px的总和。最优解是使总利润最大化的计划表。注意：每个商品只有一件。
For example, consider ......