首页 > 其他分享 >浅谈哈希及一类应用杂题

浅谈哈希及一类应用杂题

时间：2024-10-23 08:58:46浏览次数：7  
标签：return 浅谈 vv int 哈希 杂题 col size

浅谈哈希及一类应用杂题

关于哈希的一些另类想法

PS：与后文实际应用无关

哈希的目的本质就是比较两个无法直接比较是否相同的一些东西，通过赋值来使其获得比较大小的能力，然后就想能不能搞一个随手就能整出来还不容易被卡常数比如之前好多题卡 \(131\) 什么的。如果我的数是纯随机的即使不是质数也不一定会出问题，就写了个这么个玩意儿试了一下。

namespace Rand_hash
{
typedef unsigned int ull;
	int vv[20000007];
	ull get_hash(int col)
	{
		if (vv[col]) return vv[col];
		vv[col] = col * rand() * rand();
		return vv[col];
	}
}using namespace Rand_hash;

然后好像能用。。。。。。

这个坑先留着，以后有别的实验机会再说。

P7605 [THUPC2021] 小 E 爱消除

设 \(f(l,r)\) 为答案

转移 \(f(l,r)\) 考虑第一步选择了左边还是右边，不妨设左边。

如果最终都没消去，那么就是 \(f(l + 1,r) + (1, 1)\)

如果最终利用 \(c_k\) 消去了，考虑一下 \(c_k\) 是从左端取出的还是
从右端取出的。

不妨设是右端取出的，那么显然 \([k + 1,r]\) 要先被删除，考虑
枚举 \(j\) 表示 \([l + 1, j]\) 辅助了这一段的删除，那么转化后的子
区间就是 \([j + 1, k − 1]\)

用 \(\max\{f(j + 1, k − 1),2, 1 + g(l + 1, j, k + 1,r)\}\) 来表示这个转移

其中 \(g(l_1,r_1, l_2,r_2)\) 表示完全消除 \([l_1,r_1] ∪ [l_2,r_2]\) 所需要的栈的大小。当然也有可能为无穷，此时对应的状态不能用来转移
。

关于 \(g\) 的转移，考虑是先取出 \(l_1\) 还是 \(r_2\)。

比如是 \(l_1\)，考虑它和哪个位置配对，比如是和 \(c_i\)，其中 \(i ∈ [l_2,r_2]\)。再枚举左侧辅助消除 \([i + 1,r_2]\) 的区间是 \([l_1 + 1, j]\)，那么转移就可以表示为 \(\max\{g(l_1 + 1, j, i + 1, r_2) + 1, g(j + 1,r_1, l_2, i-1)\}\)

理论复杂度 \(O(n^6)\) ，实际上可以快速判断一些 \(g\) 的值为无穷，比如区间长度和是否为偶数，区间内的数是否两两配对，可以哈希然后异或和，但是如果使用前文瞎搞的那个随机化也可以并且不用脑子。可以用记忆化搜索实现中间的计算。

#include <bits/stdc++.h>

#define rint register int
#define int long long
#define endl '\n'

using namespace std;

//哈希 
namespace Rand_hash
{
typedef unsigned int ull;
#define inc(p) make_pair(p.first + 1, p.second + 1)
#define Max(l, r) make_pair(max(l.first, r.first), max(l.second, r.second))
	int vv[20000007];
	ull get_hash(int col)
	{
		if (vv[col]) return vv[col];
		vv[col] = col * rand() * rand();
		return vv[col];
	}
}using namespace Rand_hash;

const pair<int, int> inf = make_pair(0x3f3f3f3f, 0x3f3f3f3f);
const int N = 5e1 + 5;
const int Inf = 0x3f3f3f3f;
int n, w[N], s[N][N][N][N];
ull x[N];
pair<int, int> f[N][N];

//记忆化搜索计算 g 数组 
int g(int a, int b, int c, int d) 
{
	if (a > b && c > d) return 0;
	if (x[b] ^ x[a - 1] ^ x[d] ^ x[c - 1] || ((b - a + d - c) & 1)) return Inf;
	if (~s[a][b][c][d]) return s[a][b][c][d];
	int &res = s[a][b][c][d];
	res = 0x3f3f3f3f;
	if (a <= b) 
	{
		for (rint i = a + 1; i <= b; i++) if (w[a] == w[i]) 
			for (rint j = c; j <= d + 1; j++) 
				res = min(res, max(g(a + 1, i - 1, j, d) + 1, g(i + 1, b, c, j - 1)));
		for (rint i = c; i <= d; i++) if (w[a] == w[i]) 
			for (rint j = a; j <= b; j++) 
				res = min(res, max(g(a + 1, j, i + 1, d) + 1, g(j + 1, b, c, i - 1)));
	}
	if (c <= d) 
	{
		for (rint i = a; i <= b; i++) if (w[d] == w[i]) 
			for (rint j = c - 1; j <= d - 1; j++) 
				res = min(res, max(g(a, i - 1, j + 1, d - 1) + 1, g(i + 1, b, c, j)));
		for (rint i = c; i < d; i++) if (w[d] == w[i]) 
			for (rint j = a - 1; j <= b; j++) 
				res = min(res, max(g(a, j, i + 1, d - 1) + 1, g(j + 1, b, c, i - 1)));
	}
	res = max(2ll, res);
	return res;
}

pair<int, int> sol(int a, int b, int c, int d)
{
	int res = g(a, b, c, d);
	if (res > n) return inf;
	return make_pair(0ll, max(2ll, res + 1ll));
}

signed main() 
{
	cin >> n;
	for (rint i = 1; i <= n; i++) cin >> w[i], x[i] = x[i - 1] ^ get_hash(w[i]);
	for (rint i = 1; i <= n; i++) 
		for (rint j = i; j <= n; j++)
			f[i][j] = inf;
	memset(s, -1, sizeof s);
	for (rint r = 1; r <= n; r++) 
	{
		for (rint l = r; l != 0; l--) 
		{
			f[l][r] = inc(min(f[l + 1][r], f[l][r - 1]));
			for (rint k = l + 1; k <= r; k++) 
			{
			    if (w[l] == w[k]) 
			    {
					for (rint j = k + 1; j <= r + 1; j++) 
						f[l][r] = min(f[l][r], Max(f[k + 1][j - 1], sol(l + 1, k - 1, j, r)));
					for (rint j = l; j < k; j++) 
						f[l][r] = min(f[l][r], Max(f[j + 1][k - 1], sol(l + 1, j, k + 1, r)));
				}				
			}
			for (rint k = l; k < r; k++) 
			{
			    if (w[r] == w[k]) 
				{
					for (rint j = k + 1; j <= r; j++) 
						f[l][r] = min(f[l][r], Max(f[k + 1][j - 1], sol(l, k - 1, j, r - 1)));
					for (rint j = l - 1; j < k; j++) 
						f[l][r] = min(f[l][r], Max(f[j + 1][k - 1], sol(l, j, k + 1, r - 1)));
				}				
			}
		}
	}
	cout << f[1][n].first << " " << f[1][n].second << endl;
	return 0;
}

[NOI2024 D1T1] 集合

NOI 的出题方向果然和 APIO WC 对应，提高思维量但是算法本身的难度在逐渐下降。比较两个集合序列之间是否等价，很自然的想到哈希，但是直接哈希的复杂度是不能接受的，把哈希值扔进 set 里再去维护显然扯淡，但是可以拿到相当客观的暴力分数，如果选择使用线段树维护哈希值应该是可以做的，用 zkw 线段数然后快读应该能卡进去，但是双指针更优，对于任意左右边界 \(l\) 和 \(r\)，如果该边界合法并且存在 \(l + 1\) 即 \(l + 1\) 也合法。对于 \(∀i\)，找对应最右位置 \(j\) 最后复杂度应该是线性的。

UVA1502

引入 2025 HE 队爷 ReTF 的题解。

设 \(f_i\) 表示以 \(i\) 开头的最长子序列

\[f_i=\max\limits_{j\in(i,n]\land \,s_i\text{ ∈}s_j} f_j+w_i \]

令 \(w=\sum |s_i|\)，则不同的串的长度不会超过 \(\sqrt{w}\) 种。

用哈希表存每个串 \(s_i\) 及其 \(dp\) 值 \(f_i\)，对于每一个串枚举在他之前所有出现过的串的长度 \(l\)，对于每一个 \(l\) 找出该串所有长度为 \(l\) 的子串，在哈希表里查询即可实现转移。复杂度只有一个根号。

[NOI2022] 挑战 NPC Ⅱ

判断是否同构，显然考虑哈希。如果两棵树对应儿子子树同构，根节点儿子数量相等且存在两棵树的根儿子的唯一相互对应关系，那么通过这个性质可以把数据规模从一棵树缩小到子树规模，考虑 dp。对于哈希函数 \(f[i]\)，其值只与子节点的个数和大小有关系。所以计算树哈希函数时随便加点乘一乘就行。判同构子树匹配时直接暴力可以二分图，但是复杂度会很高，观察注意到若 \(a∈son_x\) 同构于 \(b∈son_y\) 的子树直接匹配掉就行。所以不用二分图。至于剩下的也好处理，由于 \(k\) 很小记搜就好，中间减点枝就好。复杂度大概是 \(O(nK)\) 的，\(K\) 的大小不太清楚是指数级还是阶乘级，但是一定不会 T，因为远远跑不到这个上界，而且这个 \(K\) 是关于 \(k\) 的，不会很大。

int c, t, k;
int pw[N];
unordered_map<int, int> f[N];

namespace Rand_hash
{
const int Typ = 11451419;
typedef unsigned int ull;
	int vv[20000007];
	ull get_hash(int col)
	{
		if (vv[col]) return vv[col];
		vv[col] = (col * rand() % Typ * rand()) % Typ;
		return vv[col];
	}
}using namespace Rand_hash;

struct node 
{
	vector<int> e[N];
	int n, r, f[N], sz[N];
	void dfs(int x) 
	{
		f[x] = get_hash((int)e[x].size());
		sz[x] = 1;
		for (rint y : e[x]) 
		{
			dfs(y);
			f[x] = f[x] * f[y] % mod;
			sz[x] += sz[y];
		}
		f[x] = (f[x] + Typ) % mod;
		sort(e[x].begin(), e[x].end(), [&](int x, int y) {return f[x] < f[y];});
	}
	void _clear() 
	{
		cin >> n;
		for (rint i = 1; i <= n; i++) e[i].clear();
		for (rint i = 1; i <= n; i++) 
		{
			int x;
			cin >> x;
			if (x != -1) e[x].push_back(i);
			else r = i;
		}
		dfs(r);
	}
} g, h;

bool dfs(int x, int y) 
{
	if (g.e[x].size() < h.e[y].size()) 
	    return 0;
	if (g.sz[x] == h.sz[y]) 
	    return g.f[x] == h.f[y];
	if (f[x].find(y) != f[x].end()) 
	    return f[x][y];
	vector<int> s1, s2;
	int idx1 = 0, idx2 = 0;
	while (idx1 < g.e[x].size() && idx2 < h.e[y].size()) 
	{
		if (g.f[g.e[x][idx1]] == h.f[h.e[y][idx2]]) 
		{
			idx1++;
			idx2++;
		}
		else if (g.f[g.e[x][idx1]] < h.f[h.e[y][idx2]]) 
		    s1.push_back(g.e[x][idx1++]);
		else  
		    s2.push_back(h.e[y][idx2++]);
	}
	
	while (idx1 < g.e[x].size()) s1.push_back(g.e[x][idx1++]);
	while (idx2 < h.e[y].size()) s2.push_back(h.e[y][idx2++]);

	if (s1.size() > g.sz[x] - h.sz[y]) 
	    return 0;
	vector<int> d(s1.size());
	
	for (rint i = 0; i < s1.size(); i++) d[i] = i;
	do 
	{
		bool flag = 1;
		for (rint i = 0; i < s2.size(); i++) 
		{
			flag &= g.sz[s1[d[i]]] > h.sz[s2[i]];
		}
		if (!flag) continue;
		for (rint i = 0; i < s2.size(); i++) 
		{
			flag &= dfs(s1[d[i]], s2[i]);
		}
		if (flag) 
		{
			f[x][y] = 1;
			return f[x][y];
		}
	} while (next_permutation(d.begin(), d.end()));
	f[x][y] = 0;
	return f[x][y];
}
signed main() 
{
	cin >> c >> t >> k;
	while (t--) 
	{
		g._clear(), h._clear();
		for (rint i = 1; i <= g.n; i++) f[i].clear();
		puts(dfs(g.r, h.r) ? "Yes" : "No");	
	}
	return 0;
}

标签：return,浅谈,vv,int,哈希,杂题,col,size
From： https://www.cnblogs.com/spaceswalker/p/18494375

相关文章

  • 精神股东浅谈博客园盈利的问题
    历史上从来没有憋大招实现成功改革的前例，更何况赚钱 1方面憋大招需要漫长的时间，另一方面漫长的时间后市场环境已经发生变化2博客园已经有了一批终生会员，为啥没有终生会员参与原子未来发展的讨论会呢作为博客园的精神股东，这次从小处入手，谈谈园子的建设问题1捐助功能http......
  • 哈希碰撞
    问：两个字符串hashcode相同equals一定相同吗？equals相同hashcode一定相同吗？答：equals相同hashcode一定相同，hashcode因为哈希碰撞所以equals不一定相同。Hash如何存数据hash表的本质其实就是数组，hash表中通常存放的是键值对Entry。如下图:  这里的学号是个key，哈希表就是根据k......
  • 浅谈混合云的特点及管理
    本文分享自天翼云开发者社区《浅谈混合云的特点及管理》，作者：罗****义近年来云计算技术的已被广泛的应用于各大行业，同时使用者也高度重视云计算技术的发展和管理，混合云就是基于云计算技术融合了公有云和私有云，为使用者提供更多的服务发展机遇，同时混合云应用也成为当前的选择主流。......
  • NOIP2024集训Day57 哈希
    NOIP2024集训Day57哈希A.[CF213E]TwoPermutations考虑到都是排列，值域连续，于是\(a\)都加\(x\)之后相当于在值域上平移了一段，也是连续的。由于要进行比较，个很容易想到哈希。\(a\)的哈希值很好维护，每次平移一位加上\(\sumbase^i\)即可。考虑如何快速取出\(b\)中在......
  • 2024.10.21 杂题
    2024.10.21杂题P11217【MX-S4-T1】「yyOIR2」youyou的垃圾桶\(O(n\logn)\)线段树二分不会，想写\(O(q\log^2n)\)的二分，但是htdlz说常数大可能过不去。所以我选择写树状数组实现的\(O(q\log^2n)\)做法然后跑的飞快比线段树二分还快直接过了（doge）记录前缀和\(s[i......
  • 在 Git 中，获取提交的哈希值（commit hash）
    在Git中，获取提交的哈希值（commithash）的方法有多种。以下是一些常用的方法：1.使用gitlog命令你可以使用gitlog命令查看提交历史，其中包括每个提交的哈希值。gitlog这将输出类似以下的内容：commit8927698069e9c719f452d7a71faac23ef25d27ab(HEAD->main)Auth......
  • 浅谈 Manacher
    从某种方面来说，Manacher算法是朴素\(O(n^2)\)暴力算法的优化。。。那就得先了解一下Manacher的朴素算法------朴素算法枚举中心点并不断向外展开（例如：\([i,i]\rightarrow[i+1,i+1]\rightarrow[i+2,i+2]\rightarrow\dots\)）缺点：时间复杂度：\(O(n^2)\)，慢不能处理长度为......
  • 算法专题九: 哈希表与字符串
    目录哈希表1.两数之和2.判断是否为字符重拍排3.是否存在重复元素4.存在重复元素Ⅱ5.字母异位词分组字符串1.最长公共前缀2.最长回文子串3.二进制求和4.字符串相乘哈希表1.两数之和固定一个数,找前面有没有target-x这个数,使用哈希表,每次查找之后......
  • 2024.10.20 杂题
    P11208『STA-R8』轮回疯狂只执行操作一就是逆序对的个数，统计对于每一个\(a_i\)的逆序对个数为\(b_i\)，然后模拟执行删除操作，如果删除操作比换位操作更优就更新答案。复杂度\(O(n\logn)\)record将最小的删除可以等价成往里加最大的数，倒着模拟即可。至于操作一，每次往数......
  • 浅谈红队攻防之道-Cobalt Strike实战
    我不想一辈子被人踩在脚下，你以为我是臭要饭的，我努力了三年，就是要等一个机会，我要争一口气，不是想证明我了不起；我是要告诉人家，我失去的东西一定要拿回来！成果cs获取shellmsf已经拿到了meterpreter现在把这个meterpreter的shell派生到CS上面，也就是让CS也也拿到一个shellms......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99