D. Fixed Prefix Permutations
题目大意
给定两个排列\(p,q\)，\(r=p\cdot q\)表示\(r_j=q_{p_j}\)。
一个排列\(p\)的美丽值为满足\(p_1=1,\ p_2=2,\ p_3=3,\ \cdots,\ p_k=k\)最大的\(k\)，若\(p_1\neq 1\)，则\(k=0\)。
现给定\(n\)个长度一样的排列\(a[n]\)，输出\(n\)个答案，第\(i\)个答案表示\(a_i\cdot a_j\ (1\le j \le n)\)的最大美丽值。
解题思路
在\(k \neq 0\)的情况下我们有\(p\cdot q=(1,\ 2,\ \cdots,\ k,\ r_{k+1},\ \cdots,\ ,r_m)\)，两边同时乘以\(q^{-1}（p^{-1}满足p\cdot q^{-1}=(1,\ 2,\ \cdots,\ n)）\)得到\(p=(1,\ 2,\ \cdots,\ k,\ r_{k+1},\ \cdots,\ ,r_m)\cdot q^{-1}\)，我们会发现\(p\)的前\(k\)个数与\(q^{-1}\)前\(k\)个数相同。那么要找大最大的\(k\)，就是对\(p\)而言找到具有最长相同前缀的\(q^{-1}\)。
参考代码
#include <bits/stdc++.h>
using namespace std;
int get(vector<int> &a, vector<int> &b)
{
int ans = 0;
while (ans < a.size() && a[ans] == b[ans])
{
++ans;
}
return ans;
}
void work()
{
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
cin >> a[i][j];
--a[i][j];
}
}
vector<vector<int>> b(n, vector<int>(m));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
b[i][a[i][j]] = j;
}
}
sort(b.begin(), b.end());
for (int i = 0; i < n; ++i)
{
int ans = 0;
int t = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
if (t > 0)
ans = max(ans, get(b[t - 1], a[i]));
if (t < n)
ans = max(ans, get(b[t], a[i]));
cout << ans << " ";
}
cout << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin >> T;
while (T--)
{
work();
}
return 0;
}