首页 > 代码库 > [3555] [Ctsc2014]企鹅QQ（Hash）

[3555] [Ctsc2014]企鹅QQ（Hash）

2024-09-22 04:48:29   327人阅读

传送门

 

可以枚举被删除的位置，然后用hash表判重，然而网上好多题解都是用 sort 判重的。

不知道为什么，int 总是过不了，换成 long long 或者是 unsigned long long 就过了 QAQ

 

——代码

技术分享
 1 #include <cstdio> 2 #include <cstring> 3 #define ULL unsigned long long 4 #define M(a, x) memset(a, x, sizeof(a)) 5  6 const int p = 30011, MAXN = 40001; 7 int n, m, k, cnt, ans; 8 int head[MAXN], num[MAXN], next[MAXN]; 9 ULL bit[201], sum[MAXN][201], val[MAXN];10 char s[MAXN][201];11 12 inline int insert(ULL x)13 {14     int i, a = x % p;15     for(i = head[a]; i != -1; i = next[i])16         if(val[i] == x)17         {18             num[i]++;19             return num[i] - 1;20         }21     num[cnt]++;22     val[cnt] = x;23     next[cnt] = head[a];24     head[a] = cnt++;25     return 0;26 }27 28 int main()29 {30     int i, j;31     scanf("%d %d %d", &n, &m, &k);32     bit[0] = 1;33     for(i = 1; i <= m; i++) bit[i] = bit[i - 1] * 107;34     for(i = 1; i <= n; i++) scanf("%s", s[i] + 1);35     for(i = 1; i <= n; i++)36         for(j = 1; j <= m; j++)37             sum[i][j] = sum[i][j - 1] * 107 + s[i][j];38     for(i = 1; i <= m; i++)39     {40         cnt = 0;41         M(head, -1);42         M(next, 0);43         M(val, 0);44         M(num, 0);45         for(j = 1; j <= n; j++)46             ans += insert(sum[j][m] - sum[j][i] * bit[m - i] + sum[j][i - 1] * bit[m - i + 1]);47     }48     printf("%d\n", ans);49     return 0;50 }
View Code

 

[3555] [Ctsc2014]企鹅QQ（Hash）


联系
我们