动态规划+字符串哈希判断有无冲突

小鱼儿 2022-09-12 03:56 37阅读 0赞

[https://codeforces.com/group/vFwRVj9WjO/contest/345181/problem/H][https_codeforces.com_group_vFwRVj9WjO_contest_345181_problem_H]

第一次交的时候p用的是1e7，有冲突，用13331可以。

题解：判断前1-5个是否出现过，如果出现了，计算它的贡献值。

#include <iostream>
    #include <cstring>
    using namespace std;
    #include <map>
    
    const int N = 1e5 + 10;
    const int mod = 128;
    const int P = 13331;
    map<string, int> mp;
    
    string str;
    int dp[N], Hash[N];
    
    int main()
    { 
    	int T;
    	cin >> T;
    	while(T--)
    	{ 
    		mp.clear();
    		memset(dp, 0, sizeof dp);
    		memset(Hash, 0, sizeof Hash);
    		int n , m;
    		cin >> n >> m;
    		char ch; string x;
    		for(int i = 1; i <= m; i++)
    		{ 
    			cin >> ch >> x;
    			mp[x] ++;
    		}
    		cin >> str;
    		str = " " + str;
    		dp[0] = Hash[0] = 1;
    		for(int i = 1; i <= n; i++)
    		{ 
    			for(int j = 1; j <= 5 and j <= i; j++)
    			{ 
    				string t = str.substr(i-j+1, j);
    				if(mp[t])
    				{ 
    					dp[i] = (dp[i] + dp[i-j] * mp[t] % mod) % mod;
    					Hash[i] = (Hash[i] + Hash[i-j * mp[t] % P) % P;
    				}
    			}
    		}
    		if(dp[n] == 0 and Hash[n] == 0) cout << "nonono\n";
    		else if(dp[n]==1 and Hash[n]==1) cout << "happymorsecode\n";
    		else cout << "puppymousecat " << dp[n] << endl;  
    	}
    	
    	return 0;
    }

[https_codeforces.com_group_vFwRVj9WjO_contest_345181_problem_H]: https://codeforces.com/group/vFwRVj9WjO/contest/345181/problem/H

发表评论取消回复

表情：

评论列表（有 0 条评论，37人围观）

还没有评论，来说两句吧...

相关阅读

相关哈希表与哈希冲突（手动实现哈希桶）

一直在说哈希，你还记得哈希冲突吗？尝试过自己手动实现哈希桶来解决哈希冲突吗？挑战一下，你会发现源码也没那么难，嘻嘻?

谁借莪１个温暖的怀抱￠/ 2024年04月23日 15:35/ 0 赞/ 158 阅读

相关字符串哈希

[原题链接841. 字符串哈希 - AcWing题库][841. _ - AcWing] [视频讲解AcWing 841. 字符串哈希 - AcWing][AcWing 84

谁借莪１个温暖的怀抱￠/ 2023年09月23日 23:08/ 0 赞/ 88 阅读

相关哈希冲突解决方法

1. 开放地址方法（1）线性探测：按顺序决定哈希值时，如果某数据的哈希值已经存在，则在原来哈希值的基础上往后加一个单位，直至不发生哈希冲突。（2）再平方探测：按顺序决

妖狐艹你老母/ 2023年03月06日 08:14/ 0 赞/ 60 阅读

相关哈希表（哈希函数的设计与哈希冲突的解决）

文章目录一、什么是哈希表二、哈希函数三、哈希冲突的原因与解决方法 1、数组扩容 2

电玩女神/ 2022年10月29日 07:47/ 0 赞/ 393 阅读

相关 [HashCollision][哈希冲突][HashValue]:最佳哈希质数

个人使用: 解决哈希冲突的方法有很多,所以,希望大家可以根据自己心中所想来解决,此方法非唯一标准. 规则: > 1. 列表中的每个数字都是质数 > 2. 每个数字都

小灰灰/ 2022年10月15日 00:38/ 0 赞/ 257 阅读

相关动态规划+字符串哈希判断有无冲突

[https://codeforces.com/group/vFwRVj9WjO/contest/345181/problem/H][https_codeforces.com_

小鱼儿/ 2022年09月12日 03:56/ 0 赞/ 38 阅读

相关哈希冲突

解决哈希冲突的三种方法（拉链法、开放地址法、再散列法）拉链法的优点与开放定址法相比，拉链法有如下几个优点： ①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生

左手的ㄟ右手/ 2022年04月24日 10:02/ 0 赞/ 292 阅读

相关字符串哈希

下面介绍的字符串Hash函数把一个任意长度的字符串映射成一个非负整数，并且其冲突概率几乎为零。取一固定值P，把字符串看作P进制数，并分配一个大于0的数值，代表每种字符。一

一时失言乱红尘/ 2022年04月22日 14:02/ 0 赞/ 330 阅读

相关哈希冲突知识点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

妖狐艹你老母/ 2022年03月12日 13:56/ 0 赞/ 265 阅读

相关哈希表及哈希冲突解决办法

哈希表及哈希冲突解决办法 -------------------- 目录 1. 什么是哈希表？ 2. 哈希表的数据结构 3. 哈希冲突 4. 哈希冲突解决

旧城等待，/ 2021年12月05日 05:15/ 0 赞/ 444 阅读