一段被瑞星判为病毒的代码

2008年5月31日琐事杂谈
0

Comments

这段代码其实是昨晚的测试中一道题的代码。这段代码虽不能AC，但是我贴出来，是因为用它编译得东西瑞星会报病毒……

附带一些信息：

  • 编译器：g++ 3.4.2
  • 瑞星版本：20.46.42
  • “病毒”名称：Trojan.PSW.Win32.GameOnline.cn

我现在越来越在想换卡巴斯基了……一年也不要多少钱……

下面是那段代码：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

#include <stdio.h>
#include <memory.h>
 
const bool IS_PRIMES[] = {
	/*      0  1  2  3  4  5  6  7  8  9*/
	/* 0 */ 0, 0, 1, 1, 0, 1, 0, 1, 0, 0,
	/* 1 */ 0, 1, 0, 1, 0, 0, 0, 1, 0, 1,
};
 
const int FAC[] = {	0, 1, 2, 6, 24, 120, 720, 5040, 40320 };
const int POW[] = {	0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000 };
 
bool s[10];
bool f[42000 /*370000*/ /*16100000*/];
int q[42000][10], qd[42000];
int l, r;
int ans;
 
int ktcv(int *x)
{
	int u = 11111111;
	int o = 0;
	for (int i = 0; i < 7; i++)
	{
		int p = POW[x[i]];
		u -= p;
		int k = u % p % 9;
		o += k * FAC[7 - i];
	}
	return o;
}
 
bool check(int *x)
{
	if (x[0] != 1)
		return false;
	for (int i = 1; i < 8; i++)
		if (x[i - 1] + 1 != x[i])
			return false;
	return true;
}
 
void push(int *x, int d)
{
	int h = ktcv(x);
	if (f[h])
		return ;
	f[h] = true;
	memcpy(q[r], x, sizeof(q[0]));
	qd[r] = d;
	r++;
}
 
inline int abs(int n) { return (n > 0) ? n : -n; }
 
int main()
{
	freopen("digits.in", "r", stdin);
	freopen("digits.out", "w", stdout);
 
	int number = 0;
 
	do
	{
		int tn[10];
		l = r = 0;
		memset(f, false, sizeof(f));
 
		for (int i = 0; i < 8; i++)
		{
			scanf("%d", &tn[i]);
			if (tn[i] == 0)
				return 0;
			s[abs(tn[i])] = (tn[i] > 0);
			tn[i] = abs(tn[i]);
		}
		ans = -1;
		number++;
		push(tn, 0);
 
		do
		{
			int d = qd[l];
			memcpy(tn, q[l], sizeof(tn));
 
			if (check(tn))
			{
				ans = d;
				break;
			}
			d++;
 
			for (int i = 0; i < 8; i++)
			{
				int ti = tn[i];
				if (s[ti])
					continue;
				for (int j = 0; j < 8; j++)
				{
					int tj = tn[j];
					if (s[tj] && IS_PRIMES[ti + tj])
					{
						int sn[10];
						int bi = i, bj = j, tij;
						if (i > j)
							tij = i, i = j, j = tij,
							tij = ti, ti = tj, tj = tij;
 
						// i -> ij
						memcpy(sn, tn, sizeof(sn));
						for (int k = i; k < j; k++)
							sn[k] = sn[k + 1];
						sn[j - 1] = ti;
						push(sn, d);
						// i -> ji
						sn[j - 1] = tj;
						sn[j] = ti;
						push(sn, d);
						// ji <- j
						memcpy(sn, tn, sizeof(sn));
						for (int k = j; k > i; k--)
							sn[k] = sn[k - 1];
						sn[i] = tj;
						push(sn, d);
						// ij <- j
						sn[i] = ti;
						sn[i + 1] = tj;
						push(sn, d);
 
						i = bi, j = bj;
						ti = tn[i], tj = tn[j];
					}
				}
			}
			l++;
		}
		while (l < r);
 
		printf("Case %d: %d\n", number, ans);
	}
	while (true);
}

这个程序是比较不严重地TLE，最慢的一个点为1.80s。我可以证明茅山的Hash是错的，不过我找不到一个足够快的Hash。如果谁有办法告诉我啊……

附这道题目：

跳舞的数字(digits)

问题描述

数字喜欢跳舞。一天，1, 2, 3, 4, 5, 6, 7 和 8 站在一行开始一个舞会。每个时刻，一个男性数字可邀请一个女性数字和他跳舞，或一个女性数字可邀请一个男性数字和她跳舞，只要他们的和是素数。

在每次跳舞前，只有一个数字走到他想一起跳舞的人旁边，紧邻他的左边或右边。简单的，我们表示一个男性数字x为x，表示一个女性数字x为-x。假设数字一开始有以下顺序{1, 2, 4, 5, 6, -7, -3, 8}。

如果-3想和4跳舞，她必须走到4的左边，顺序变成{1, 2, -3, 4, 5, 6, -7, 8}；或他的右边，顺序变成{1, 2, 4, -3, 5, 6, -7, 8}。注意到-3不能和5跳舞，因为他们的和3+5=8 不是素数；2不能和5跳舞因为他们都是男性。

给出数字的起始顺序，找到最少的跳舞次数，使他们成为升序（绝对值）。

输入文件

输入最多20组数据。每组数据包含8个数字在一行。他们的绝对值组成1到8的排列。最后一组数据后接着一个数字0，它不需要被处理。

输出文件

对于每组数据，输出组数和最少的跳舞次数。如果无法排成升序输出-1。

样例输入

1
2
3
4
5
6

1 2 4 5 6 -7 -3 8
1 2 3 4 5 6 7 8
1 2 3 5 -4 6 7 8
1 2 3 5 4 6 7 8
2 -8 -4 5 6 7 3 -1
0

样例输出

1
2
3
4
5

Case 1: 1
Case 2: 0
Case 3: 1
Case 4: -1
Case 5: 3

You can follow any responses to this entry through the RSS 2.0 | You can leave a response or trackback from your own site.

Related Posts Random Posts

Leave a Reply