每日一题~abc 367 F+luogu p10102(随机算法）

本文主要是介绍每日一题~abc 367 F+luogu p10102(随机算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

随机化的思想：
充分条件的计算代价比较大，想找个计算代价小的必要条件，但必要条件可能会出错，然后通过一些手段（比如随机映射）把这个出错的概率降低。(参考园子)

添加链接描述
题意：
两个数组，元素均为 1~N.
q 次查询，判断 a b 数组，这一区间内的元素是否相同。（排列的顺序不重要，主要是元素的种类个数相同）
n,q 均在2e5 内。
如果暴力，对每次查询，我们只能将这个区间内的所有数扫一遍。显然的复杂度不对。
考虑一个必要的条件。如果这个区间合法，那么这两个区间的和是相等的。但是和相等并不一定是合法的区间。（也就是不是充分条件）。所以我们对每一个数进行随机的映射。减少这种矛盾的情况。
关于冲突的计算，不是很明白。插个眼。以后再来看看。
这里使用的是 32 位的随机数进行映射。

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{mt19937 mt(time(0));int n, q;cin >> n >> q;vector<int> a(n + 1);vector<int> b(n + 1);vector<int> t(n + 1);for (int i = 1; i <= n; i++)t[i] = mt();for (int i = 1; i <= n; i++){cin >> a[i];a[i] = (t[a[i]] + a[i - 1]);}for (int i = 1; i <= n; i++){cin >> b[i];b[i] = (t[b[i]] + b[i - 1]);}int l1,r1,l2,r2;while(q--){cin>>l1>>r1>>l2>>r2;if (a[r1]-a[l1-1]==b[r2]-b[l2-1])cout<<"Yes\n";else cout<<"No\n";}
}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t;t = 1;// cin>>t;while (t--){solve();}return 0;
}

题意：
给你三个矩阵判断 A*B==C 是否成立。（这里的 * 代表了矩阵的乘法）
计算矩阵相乘的复杂度是 n^3 n<=3000，
判断俩矩阵乘是否等于第三个矩阵。充分条件就是直接相乘n^3
的矩阵相乘，但这显然时间复杂度过不去。找个必要条件，如果AB=C，那么XAB=XC，即左乘一个矩阵，左右两边仍相等，而如果
X是1×n的矩阵，那么左边两个矩阵乘法的复杂度就降为O(n^2)
，时间复杂度可以，但由于是必要条件，原本左右两边不相等的，左乘后可能会相等，所以这个X最好随机生成出来，这个误判的概率就会比较低，

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int mod=998244353;
mt19937 myrand(time(0));
int read()
{int x = 0, f = 1;char ch = getchar();while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}return x * f;
}
void solve()
{int n;cin >> n;vector<vector<int>> a(n, vector<int>(n));vector<vector<int>> b(n, vector<int>(n));vector<vector<int>> c(n, vector<int>(n));for (int i = 0; i < n; i++)for (int j = 0; j < n; j++){a[i][j]=read();}for (int i = 0; i < n; i++)for (int j = 0; j < n; j++){b[i][j]=read();}for (int i = 0; i < n; i++)for (int j = 0; j < n; j++){c[i][j]=read();}vector<int> d(n);for (int i = 0; i < n; i++){d[i] = myrand() % mod + 1;}vector<int> t(n);// 遍历 列 行 for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){t[i]=(t[i]+d[j]*a[j][i])%mod;}}vector<int>tt(n);for (int i=0;i<n;i++){for (int j=0;j<n;j++){tt[i]=(tt[i]+t[j]*b[j][i])%mod;}}vector<int>ttt(n);for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){ttt[i]=(ttt[i]+d[j]*c[j][i])%mod;}}if (tt==ttt){cout<<"Yes\n";}else cout<<"No\n";}
signed main()
{//std::cin.tie(nullptr)->sync_with_stdio(false);int t;cin >> t;while (t--){solve();}return 0;
}