2024.11.27 周三
-
Q1. 1000
给定x,y，设ai=i^x，bi=i^y，问两个无穷序列a和b的最长公共子序列的长度。 -
Q2. 1400
给定一条链，所有点未激活，在开始点放一棋子并激活，2人轮流操作：将棋子移动到相邻的未激活的点并激活。不能操作者输。问均最优策略的赢家。 -
Q3. 1600
给你两个大小为n×m的矩阵a,b，其中元素的是n×m的排列，你可以任意进行行变换/列变换，问是否通过操作使得矩阵a变成矩阵b。 -
A1. 补：怎么感觉今天的题1000分的最难 >_<
神秘位运算题 "看到本题的数据范围，可以猜想这是一道结论题，结合样例就出了。"
[l,r]⊕x=[l′,r′]⊕y => [l,r]=[l′,r′]⊕(x⊕y)。令v=(x⊕y)，即求最长的 [l,r]使得异或上v后依然连续。
如果 v=abc100000，任意 l=cde100000,r=cde111111一定是最长的，答案为lowbit(v)。 -
A2. 补：我就说对不上样例得"仔细"重读题吧，读漏了。
显然只有第一步操作有2种选择，其余操作没有选择，且奇数为必胜态。直接搜索两侧链的点数，若有奇数便可胜。 -
A3. 13mins-33mins 假思路：最初的想法是判断每一行的和和每一列的和，但是不严谨。行和只是必要条件，非充分。后又想到用行首元素vector存其余元素，然后发现判断困难。
发现无论怎么交换同一行和同一列中的元素种类是不会改变的，只会改变相对位置。 因此答案就是判断a中每一行和每一列在b中是否有无序版。
判断方式多样如哈希，我这里直接使用并查集把a每一行看成一个集合，在b中判断是否冲突，列同理。
A1.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' //
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
const int mod = 998244353;
const int N = 10 + 5e5;
void _();
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
_();
return 0;
}
// 给定x,y，设ai=i^x，bi=i^y，问两个无穷序列a和b的最长公共子序列的长度。
// 神秘位运算题 "看到本题的数据范围，可以猜想这是一道结论题，结合样例就出了。"
// [l,r]⊕x=[l′,r′]⊕y => [l,r]=[l′,r′]⊕(x⊕y)。令v=(x⊕y)，即求最长的 [l,r]使得异或上v后依然连续。
// 如果 v=abc100000，任意 l=cde100000,r=cde111111一定是最长的，答案为lowbit(v)。
void _()
{
int x, y;
cin >> x >> y;
auto lowbit = [](int x)
{
return x & -x;
};
cout << lowbit(x ^ y) << endl;
}
A2.
#include <bits/stdc++.h>
// #define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
_();
return 0;
}
// 给定一条链，所有点未激活，在开始点放一棋子并激活，2人轮流操作：将棋子移动到相邻的未激活的点并激活。不能操作者输。问均最优策略的赢家。
// 我就说对不上样例得"仔细"重读题吧，读漏了。
// 显然只有第一步操作有2种选择，其余操作没有选择，且奇数为必胜态。直接搜索两侧链的点数，若有奇数便可胜。
void _()
{
int n, t;
cin >> n >> t;
vector<vector<int>> e(n + 1);
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
int st = 0;
cin >> st;
vector<int> vis(n + 1);
function<int(int)> dfs = [&](int u)
{
if (vis[u])
return 0;
vis[u] = 1;
int cnt = 1;
for (auto v : e[u])
cnt += dfs(v);
return cnt;
};
vis[st] = 1;
bool f = 0;
for (auto u : e[st])
if (dfs(u) & 1)
f = 1;
cout << (f ? "Ron" : "Hermione") << endl;
}
A3.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
// 给你两个大小为n×m的矩阵a,b，其中元素的是n×m的排列，你可以任意进行行变换/列变换，问是否通过操作使得矩阵a变成矩阵b。
// 假思路：最初的想法是判断每一行的和和每一列的和，但是不严谨。行和只是必要条件，非充分。后又想到用行首元素vector存其余元素，然后发现判断困难。
// 发现无论怎么交换同一行和同一列中的元素种类是不会改变的，只会改变相对位置。 因此答案就是判断a中每一行和每一列在b中是否有无序版。
// 判断方式多样如哈希，我这里直接使用并查集把a每一行看成一个集合，在b中判断是否冲突，列同理。
// 13mins-33mins
// 带权并查集
vector<int> p, vs, es; // 集合数 点数 边数 (对一个连通块而言)
void init(int n1) // p[x]不一定为根节点 find(x)一定是根节点
{
int n = n1 + 2;
p.assign(n, 0);
vs.assign(n, 0);
es.assign(n, 0);
for (int i = 1; i <= n1; i++)
p[i] = i, vs[i] = 1, es[i] = 0;
}
int find(int x) // 找到根节点
{
if (p[x] == x)
return x;
int px = find(p[x]);
return p[x] = px;
}
bool same(int a, int b)
{
return find(a) == find(b);
}
void merge(int a, int b) // 合并集合
{
int pa = find(a);
int pb = find(b);
if (pa == pb) // pa pb 均为根节点 p[pa]==pa
{
es[pa]++; // 1个集合 边+1
return;
}
p[pb] = p[pa]; // 改变b的根节点
vs[pa] += vs[pb]; // 将b合并进a
es[pa] += es[pb] + 1; // 2个集合
}
int size(int a) // 集合内的元素的个数
{
return vs[find(a)];
}
// init(n);
void _()
{
int n, m;
cin >> n >> m;
init(n * m);
vector<vector<int>> a(n + 1, vector<int>(m + 1)), b(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
if (j - 1)
merge(a[i][j], a[i][1]);
}
bool f = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> b[i][j];
if (j - 1 && !same(b[i][j], b[i][1]))
f = 0;
}
}
init(n * m);
for (int j = 1; j <= m; j++)
for (int i = 1; i <= n; i++)
if (i - 1)
merge(a[i][j], a[1][j]);
for (int j = 1; j <= m; j++)
for (int i = 1; i <= n; i++)
if (i - 1 && !same(b[i][j], b[1][j]))
f = 0;
cout << (f ? "YES" : "NO") << endl;
}
// void _()
// {
// int n, m;
// cin >> n >> m;
// vector<vector<int>> a(n + 1, vector<int>(m + 1)), b(n + 1, vector<int>(m + 1));
// map<int, vector<int>> a_row, b_row;
// for (int i = 1; i <= n; i++)
// {
// int x;
// for (int j = 1; j <= m; j++)
// {
// cin >> a[i][j];
// if (j == 1)
// x = a[i][j];
// a_row[x].push_back(a[i][j]);
// }
// }
// for (int i = 1; i <= n; i++)
// {
// int x;
// for (int j = 1; j <= m; j++)
// {
// cin >> b[i][j];
// if (j == 1)
// x = b[i][j];
// b_row[x].push_back(b[i][j]);
// }
// }
// bool f = 1;
// for (auto &[x, a] : a_row)
// {
// auto &b = b_row[x];
// sort(a.begin(), a.end());
// sort(b.begin(), b.end());
// if (a != b)
// f = 0;
// }
// cout << (f ? "YES" : "NO") << endl;
// }
// void _()
// {
// int n, m;
// cin >> n >> m;
// vector<vector<int>> a(n + 1, vector<int>(m + 1)), b(n + 1, vector<int>(m + 1));
// map<int, int> a_row, b_row, a_col, b_col;
// for (int i = 1; i <= n; i++)
// {
// int s = 0;
// for (int j = 1; j <= m; j++)
// {
// cin >> a[i][j];
// s += a[i][j];
// }
// a_row[s]++;
// }
// for (int i = 1; i <= n; i++)
// {
// int s = 0;
// for (int j = 1; j <= m; j++)
// {
// cin >> b[i][j];
// s += b[i][j];
// }
// b_row[s]++;
// }
// for (int j = 1; j <= m; j++)
// {
// int s = 0;
// for (int i = 1; i <= n; i++)
// s += a[i][j];
// a_col[s]++;
// }
// for (int j = 1; j <= m; j++)
// {
// int s = 0;
// for (int i = 1; i <= n; i++)
// s += b[i][j];
// b_col[s]++;
// }
// int f = 1;
// for (auto [s, cnt] : a_row)
// if (cnt - b_row[s])
// f = 0;
// for (auto [s, cnt] : a_col)
// if (cnt - b_col[s])
// f = 0;
// cout << (f ? "YES" : "NO") << endl;
// }