CmYkRgB123

这道题的解决方法隐藏得很深，不经过严密的数学推理分析是很难想到正确方法的。

注意到题上的一个看似无关紧要的条件，“不包括三角形”，这是一个突破口。由这个条件，我们可以证明，如果一个图不存在度数为1的顶点，B永远也追不上A。也就是B想追上A，必须让A“走投无路”。

于是我们首先把原图处理一下，求出对于A来说的安全区。对于A来说的安全区，也就是一个没有度为1的顶点的最大子图。我们把这个安全区求出，并标记上。

A要想不被B抓住，则一定要向安全区中逃跑。如果A能够在B追上A之前逃离到安全区，则B就永远也追不上A。否则，A无论如何也会被B追上。在A“必死无疑”的时候，A要想尽可能晚的被B追上，就必须想远离B的方向跑。

有了以上的分析，得出下列算法
1、求出安全区的顶点。
2、分别求出A，B初始位置开始，到每个顶点的距离，记作DA[i]和DB[i]。
3、若存在安全区中的顶点k，使得DA[k] 4、如果不存在上述顶点k，则找到满足DA[i]

时间复杂度：O(M+N)
Read the rest of this entry »

二维费用01背包问题，动态规划，但是要注意边界条件。

状态设定

F[i,j,k] 前i个瓶，氧为j，氮为k的最小重量

状态转移方程

F[i,j,k]=Min
{
F[i-1,j,k],
F[i-1,j-P_O[i],k-P_N[j]] + C[i] ( j-P_O[i]>=0 ,k-P_N[j]>=0 ),
C[i] ( j-P_O[i]<0 ,k-P_N[j]<0 )
}

边界条件

F[i,j,k]=无穷大
F[i,0,0]=0

目标结果

Min{F[N,i,j] | i>=T , j>=A}

上述动态规划可以用滚动数组优化，或者直接优化为二维。
Read the rest of this entry »

为了适应NOI比赛恶劣的操作环境，从上周起我就开始使用Ubuntu，编程用Vim，G++，DDD。不要向我推荐Emacs，我讨厌这东西。尽量减少调试，不要依赖于调试器，要靠自己认真细心，和静态查错。

毕竟Windows用惯了，使用Linux真的有许多不方便的地方，太多了。最显著的问题是输入法，Google拼音输入法为什么没有For Linux版？就连Chrome也没有Linux版，还好Firefox和Opera都是不错的。播放音频和视频支持的格式很少，Real player还不错。

没有批量更名的软件，对付大量的测试数据很麻烦。大小写区分，换行符不同，令人棘手。还好换行符的问题可以用dos2unix命令解决，批量更名就麻烦了，我承认我不会shell编程。

我用C++写了两个方便的工具，测试数据改名程序和测试数据答案文件生成程序。
测试数据改名程序用法 ./ren PROB#.IN prob#.in 1 10
把PROB1.IN … PROB10.IN 改成 prob1.in … prob10.in
代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <iostream>
#include <stdlib.h>
 
using namespace std;
 
int i,S,T;
char Ti[100],To[100];
char *Fi,*Fo;
 
void rm(char *t,char *p,int k)
{
	for (;*t;t++)
	{
		if (*t!='#')
		{
			*p=*t;
			p++;
		}
		else
		{
			sprintf(p,"%d",k);
			while (*p) p++;
		}
	}
	*p=0;
}
 
int main(int argc,char **argv)
{
	int suc;
	Fi=argv[1];
	Fo=argv[2];
	sscanf(argv[3],"%d",&S);
	sscanf(argv[4],"%d",&T);
	printf("\nData Renamer. Author: CmYkRgB123 \nFrom:%s\nTo:%s\nRange:[%d,%d] \n\n",Fi,Fo,S,T);
	for (i=S;i<=T;i++)
	{
		rm(Fi,Ti,i);
		rm(Fo,To,i);
		printf("Rename from %s to %s ...",Ti,To);
		suc=rename(Ti,To);
		if (suc==0)
			printf("Done.\n");
		else
			printf("Failed.\n");
	}
	printf("\n");
	return 0;
}

测试数据答案文件生成程序用法 ./datacreator prob 1 10
根据prob1.in … prob10.in，调用./prob，生成prob1.ans … prob10.ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <iostream>
#include <stdlib.h>
 
using namespace std;
 
int main(int argc,char **argv)
{
	int i,S,T;
	char FI[100],FO[100],ti[100],to[100],Run[100];
	char *name;
	name=argv[1];
	sprintf(Run,"./%s",name);
	sscanf(argv[2],"%d",&S);
	sscanf(argv[3],"%d",&T);
	printf("\nData Creator. Author: CmYkRgB123 \nProblem Name:%s\nRange:[%d,%d] \n\n",name,S,T);
	for (i=S;i<=T;i++)
	{
		printf("Creating %s #%d ...",name,i);
		sprintf(FI,"%s%d.in",name,i);
		sprintf(ti,"%s.in",name);
		sprintf(to,"%s.out",name);
		sprintf(FO,"%s%d.ans",name,i);
		rename(FI,ti);
		system(Run);
		rename(ti,FI);
		rename(to,FO);
		printf(" Done.\n");
	}
	printf("\n");
	return 0;
}

不过也是有不少好处的，起码我不能玩游戏了，减少时间的浪费。

这是合并等价类问题，由于每个未知量有多位，每位对应0或1，我们先把字母串按照展开拆开。例如样例可以展开成

1,b1,b2,a1,a2,a3,a4,d1,d2,d3,d4, 1
a1,a2,a3,a4,c1,c2,c3,c4,b1,b2,e1,e2

对于上述对应关系，进一步抽象成5个集合，每个元素属于唯一的一个集合，每个集合对应0或1。

{1,a1,a4,c3,e2}
{b1,a2,c1,d2}
{b2,a3,c2,d3}
{d1,c4}
{d4,e1}

除了第一个集合一定为1以外，其余四个集合都有两种可能的解，根据乘法原理，解的总数为2^4=16。

对于这道题而言，可能会无解。无解的情况之一是两个串展开后长度不相等，这样就会有一些没有对应关系，所以无解。另一种情况就是两个已知量1和0属于同一个集合，这显然是有悖于事实的，也是无解。

求等价类集合的方法可以用并查集，也可以按照关系构图，求无向图连通分量的个数。两种方法的时间复杂度都可以近似认为是O(N)的。

下面是我的代码，用了并查集。

Read the rest of this entry »

非常简单的枚举，三重循环。对于每一个城市对，枚举中间城市，如果中间有城市，则不是“相邻城市”，否则就是，输出即可。

Read the rest of this entry »

习惯于阅读RSS已经有半年了，一直在用Google阅读器，现在订阅了许多文章。阅读RSS真的会上瘾的，有时候不看它就感觉不舒服，感觉落后于世界的更新。

Solidot是一个不错的资讯网站，我很喜欢上面的新闻。河蟹上岸，匪话连篇也是我喜欢的。许多的牛博上的博客都是不错的。牛博，真牛！

刚刚给自己弄上了feedsky，以前一直没有注意过。其实也无所谓，我的博客反正也没几个人看。

动态规划，设F[i,j]为范围1..i的集合元素之和大于等于j，不含连续自然数的集合个数

由于可能存在空集的情况，即计算过程中出现了k=-1，这是很不方便的，所以我修改了定义，把大于k方便的改成了大于等于k＋1。N=100，K=400时，结果是很大的，要使用高精度。

状态转移方程

F[i,j]= Sum
{
F[i-1,j], (包含第i个元素)
F[i-2,j-i] (不包含第i个元素，j-i若小于0则为F[i-2,0])
}

边界条件

F[1,0]=2 //Ø,{1}
F[1,1]=1 //{1}
F[2,0]=3 //Ø,{1},{2}
F[2,1]=2 //{1},{2}
F[2,2]=1 //{2}

目标结果

F[N,K+1]

Read the rest of this entry »

标准的广度优先搜索，哈希判重。由于无法估计状态数，需要用链队列存储搜索状态。把初始状态加入队列，然后取出队列中的首元素，对其状态进行扩展。判断不能有重复，否则是多余的。如果当前扩展到的状态三种钱币的数目都大于等于目标状态，则找到了解，输出交易的次数。另外，为防止重复按照某些规则交易使钱币数目无意义地增长，人为规定每种钱币的数目不能超过目标状态的若干倍（比如10倍即可）。
Read the rest of this entry »

O(N^3)的枚举是无法忍受的，这道题可以从反面考虑。单色三角形的个数就是全部的三角形的个数减去不同色三角形的个数。

在一个不同色的三角形中，显然有两个顶点，每个顶点连着这个三角形内的不同颜色的两条边。反过来，如果顶点i连接着D[i]条红边，那么它一定连接着(N-1-D[i])条红边，这个顶点在D[i]*(N-1-D[i])个不同色三角形内。而一个顶点在一个三角形内被计算了两次，所以整个图中一共有
Sum{ D[i]*(N-1-D[i])/2 | i=1..N }个不同色三角形。

由于一共有C(N,3)个三角形，所以结果就是

C(N,3) - Sum{ D[i]*(N-1-D[i])/2 | i=1..N }
Read the rest of this entry »

提供一个没有优化的O(N^2)的动态规划解法。首先对所有的演讲时间区间按结束时间从小到大排序，然后设定状态。

S[i].l和S[i].r分别表示第i个演讲的开始和结束时间。
F[i]为进行第i个演讲时已经使用了的最大的时间

状态转移方程
F[i] = Max{ F[j] | S[j].r <=S[i].l } + S[i].r - S[i].l

结果
Max { F[i] }

Read the rest of this entry »