这次开VP做的..
C:
知识点get:
对于同一副对角线的矩阵元素ai,j和bi,j,满足:i+j相等
题意:给两个矩阵A,B;对A的每次变换可以选择A的任意一个正方形子矩阵T使其行列互换(Ti,j =>Tj,i)问A是否可以经过若凡此变换成为矩阵B
比赛的时候这题不会(当时只想着如何对主对角线操作了,还异或了一下看哪些是变化的...),赛后看题解发现,因为每次变换都是以主对角线为对称轴,那么无论怎么变换,同一条副对角线上的数只会改变顺序,不会改变数,所以对每条副对角线排序看一下变换前后是不是全等就OK,(牛批网友真是牛批orz....)
代码如下:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m; 4 const int maxn=5e2+5; 5 int a[maxn][maxn],b[maxn][maxn]; 6 int vis[maxn][maxn]; 7 vector<int>v1[maxn*2],v2[maxn*2]; 8 int main() 9 { 10 ios::sync_with_stdio(0); 11 cin>>n>>m; 12 for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>a[i][j]; 13 for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>b[i][j]; 14 for(int i=1;i<=n;++i) 15 { 16 for(int j=1;j<=m;++j) 17 { 18 v1[i+j].push_back(a[i][j]); 19 v2[i+j].push_back(b[i][j]); 20 } 21 } 22 for(int i=2;i<=n+m;++i) 23 { 24 sort(v1[i].begin(),v1[i].end()); 25 sort(v2[i].begin(),v2[i].end()); 26 for(int j=0;j<v1[i].size();++j) 27 { 28 if(v1[i][j]!=v2[i][j]) 29 { 30 cout<<"NO"; 31 return 0; 32 } 33 } 34 } 35 cout<<"YES"; 36 }
D:疯狂xjb理解错题意的一道题emmmm
正确题意:对于序列n给定1~n的一个全排列代表位置i有编号为ai的一个同学,已知小明在队伍的最后一个. 给你m个数对(u,v),表示编号为u和v的两个同学可以交换(只有两人相邻的时候才可以交换),
求:小明最多可以前进多少步
一开始写了个dij最长路...然后发现有环最长路会无限循环?(这东西都忘了,我真是个弟弟...)
牛批网友做法：
代码如下:
1 #include<bits/stdc++.h> 2 #define pii pair<int,int> 3 using namespace std; 4 const int maxn=3e5+5; 5 int n,m; 6 map<pii,int>ma; 7 int pul[maxn]; 8 int main() 9 { 10 ios::sync_with_stdio(0); 11 cin>>n>>m; 12 for(int i=1;i<=n;++i) cin>>pul[i]; 13 for(int i=1;i<=m;++i) 14 { 15 int a,b;cin>>a>>b; 16 ma[make_pair(a,b)]=1; 17 } 18 vector<int>v; 19 v.push_back(pul[n]); 20 int ans=0; 21 for(int i=n-1;i>=1;--i) 22 { 23 int flag=0; 24 for(auto t:v) 25 { 26 if(ma[make_pair(pul[i],t)]==0) 27 { 28 flag=1; 29 break; 30 } 31 } 32 if(flag) v.push_back(pul[i]); 33 else 34 { 35 ++ans; 36 } 37 38 } 39 cout<<ans<<endl; 40 }