Detect Shuing Method（ Andrew Stankevich Contest 44 ）

Detect Shuing Method（ Andrew Stankevich Contest 44, XIII Open Cup Onsite

Petrozavodsk Summer Training Camp, September 1, 2013 ）

题目描述：

在某个计算机系统中，存在一个潜在的网络安全问题：通过分析一些字符串，可以判断某些字符串是否是恶意的。我们的目标是根据字符串的特征将其分为两类：正常的（random）和恶意的（block）。 每个字符串由若干个四个字符组成的子串组成。你需要根据这些子串的出现频率来判断字符串的类型。 具体来说，给定一个字符串，其中每四个字符为一组，如果某组的字符在其他字符串中也频繁出现，那么该字符串很可能是恶意的。基于这一规律，我们的任务是判定每个字符串是正常的（random）还是恶意的（block）。

题解：

该题的关键在于对每个字符串的四字符子串的频率进行统计，并通过这些频率来判断每个字符串的类型。我们首先统计所有字符串中每个四字符子串的出现次数，然后根据这些统计信息判断每个字符串的恶意程度。

解题思路：

1. 四字符子串频率统计 ：

• 对每个字符串中的每一个四字符子串（由四个字符组成）进行排序，作为一个“标准化”的子串。对于每个字符串中的每个四字符子串，我们使用 map 来记录其出现的次数。

2. 计算每个字符串的恶意值 ：

• 对每个字符串，通过其包含的所有四字符子串来计算该字符串的恶意值。恶意值的计算方法是：每个四字符子串出现的次数的平方之和。

3. 排序和分类 ：

• 根据计算得到的恶意值排序，将恶意值较高的字符串判定为恶意（block），恶意值较低的字符串判定为正常（random）。
• 输出结果时，首先输出恶意的字符串，再输出正常的字符串。

具体步骤：

1. 初始化 ：

• 使用一个 map 来记录每个四字符子串的出现次数。

2. 统计频率 ：

• 遍历所有字符串，提取每个四字符子串并更新其频率。

3. 计算恶意值 ：

• 对于每个字符串，计算其恶意值。恶意值是由该字符串中的每个四字符子串的频率的平方之和决定的。

4. 排序并输出 ：

• 按照恶意值从小到大的顺序对字符串进行排序，并根据排序结果输出 block 或 random。

代码解析：

#include #define endl ‘\n’ #define int long long #define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; const int mod = 1e9 + 7; const int inf = 0x3f3f3f3f; const int N = 100 + 10; const int M = 3 * 1e5 + 10; char s[N][M], b[5]; map mp_string; // 用于存储四字符子串的频率 pair p[N]; // 存储字符串的恶意值和原始索引 int ans[N]; // 存储每个字符串的类型，0表示random，1表示block signed main() { freopen(“detect.in”, “r”, stdin); // 输入文件 freopen(“detect.out”, “w”, stdout); // 输出文件 int n; cin » n; // 读取字符串的个数 getchar(); // 读取字符串并统计每个四字符子串的频率 for (int k = 1; k <= n; k++) { gets(s[k]); // 读取第 k 个字符串 for (int i = 0; s[k][i]; i += 4) { for (int j = 0; j < 4; j++) // 处理每个四字符子串 { b[j] = s[k][i + j]; } sort(b, b + 4); // 对四字符子串排序，统一表示 ++mp_string[b]; // 更新该子串的频率 } } // 计算每个字符串的恶意值 for (int k = 1; k <= n; k++) { p[k].first = 0; p[k].second = k; for (int i = 0; s[k][i]; i += 4) { for (int j = 0; j < 4; j++) // 处理每个四字符子串 { b[j] = s[k][i + j]; } sort(b, b + 4); // 对四字符子串排序，统一表示 p[k].first += mp_string[b] * mp_string[b]; // 计算该字符串的恶意值 } } // 按恶意值排序 sort(p + 1, p + n + 1); // 根据排序结果将字符串分类 for (int i = 1; i <= n / 2; i++) { ans[p[i].second] = 0; // 前半部分为random } for (int i = n / 2 + 1; i <= n; i++) { ans[p[i].second] = 1; // 后半部分为block } // 输出每个字符串的分类结果 for (int i = 1; i <= n; i++) { if (ans[i]) // block { cout « “block” « endl; } else // random { cout « “random” « endl; } } return 0; }

时间复杂度分析：

1. 统计四字符子串频率 ：对于每个字符串，每个四字符子串需要排序，因此时间复杂度为 O(n * m / 4 * log 4)，其中 n 是字符串的数量，m 是每个字符串的长度。由于排序的常数项是固定的，所以可以简化为 O(n * m)。
2. 计算恶意值 ：对于每个字符串，需要遍历所有四字符子串，并计算恶意值，时间复杂度为 O(n * m / 4)，同样简化为 O(n * m)。
3. 排序 ：对 n 个字符串进行排序，时间复杂度为 O(n log n)。 因此，总时间复杂度为 O(n * m + n log n)，可以在较大的输入规模下有效执行。

总结：

这道题目通过对四字符子串频率的统计，结合字符串中四字符子串的频率计算恶意值，最终通过排序和分类来判定每个字符串的类型。