CF1792 D. Fixed Prefix Permutations : Educational Codeforces Round 142 (Rated for Div. 2) D

给出n个长度为m的排列(a₁, a₂, a₃, ..., a_n)

定义一个操作 r=ai•aj : r[k]=a[j][a[i][k]]

定义一个排列(p1, p2, ..., pn)的beauty为最大的k，使得p[1]=1, p[2]=2, .., p[k]=k (p[1]!=1时, beauty=0)

分析：

　　暴力：从1~n枚举i，j，求出排列r=ai*aj，然后再去求beauty，这样做法时间复杂度为O(mn²)，肯定会超时

　　正确做法：

　　　　以aj序列3 1 2 4举例，这个序列对2 3 1 4（这几个数字分别为aj中 1 2 3 4的位置）这样的序列有贡献

　　　　所以可以枚举1~n的aj，预处理出一个n×m的表，然后枚举1~n的aj在表中查找与自身最接近的一行，然后算出beauty

具体做法：

　　vector< vector<int> > a(n, vector<int> m), b(a); //其中a存输入数据，b是生成的表，b[i][k]的值应为k在a[i]这个序列中的位置（注意：由于后面对b.begin(), b.end()排序，所以b[i]序列是以0起的，所以输入数据时，每个数据减1，使得长度为m的排列从1~m变成0~m-1）

　　然后对b.begin(), b.end()进行排序，之后用int loc=lower_bound(b.begin(), b.end(), a[i])-b.begin()来找出b这个表中与a[i]最接近的一行序列下标，b[loc]与b[loc-1]（如果两者都存在的话）时与a[i]最接近的两个，分别求出前多少个数是相同的，更新答案即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 void solve()
 4 {
 5     int n, m;
 6     scanf("%d%d", &n, &m);
 7     vector< vector<int> > a(n, vector<int>(m)), b(a);
 8     for(int i=0; i<n; i++){
 9         for(int j=0; j<m; j++){
10             scanf("%d", &a[i][j]);
11             a[i][j]--;
12             b[i][a[i][j]]=j;
13         }
14     }
15     sort(b.begin(), b.end());
16     for(int i=0; i<n; i++){
17         int ans=0;
18         int loc=lower_bound(b.begin(), b.end(), a[i])-b.begin(); //b[loc]与b[loc-1]是最接近a[i]的两个序列 
19         if(loc<n){
20             int cnt=0;
21             for(int k=0; k<m; k++){
22                 if(a[i][k]==b[loc][k]){
23                     cnt++;
24                 }else{
25                     break;
26                 }
27             }
28             ans=max(ans, cnt);
29         }
30         if(loc>0){
31             int cnt=0;
32             for(int k=0; k<m; k++){
33                 if(a[i][k]==b[loc-1][k]){
34                     cnt++;
35                 }else{
36                     break;
37                 }
38             }
39             ans=max(ans, cnt);
40         }
41         printf("%d ", ans);
42     }
43     printf("\n");
44 }
45 int main(void)
46 {
47     int T=1;
48     scanf("%d", &T);
49     while(T--)solve();
50     return 0;
51 }