前言
听说多写构造题可以提升思维能力...
C. Turtle and an Incomplete Sequence
题目大意
给定一个数组a,只有正整数和-1，-1可以改为正整数，问数组能否满足$\lfloor a[i]/2 \rfloor = a[i+1] 或 \lfloor a[i+1]/2 \rfloor = a[i] $，能则输出方案
解题思路
可以发现，相邻2个数在完全二叉树上一定是相邻的，其实这个数列就是一个在完全二叉树上游走的过程，我们只要看相邻的2个数能否在树上以特定的步数达到即可
构造要找到相关的因素，然后大胆猜测与探索
神奇的代码
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
using namespace std;
#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int N=2e5+10;
int a[N];
int n;
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
if(count(a+1,a+1+n,-1)==n){
for(int i=1;i<=n;i++)cout<<(i%2==1?1:2)<<' ';
cout<<endl;
return;
}
for(int i=1,j=1;i<=n;i++){
if(a[i]==-1)continue;
j=max(i+1,j);
while(j<=n and a[j]==-1)j++;
if(j<=n){
int v1=a[i],v2=a[j];
int c1=31,c2=31;
while((v1>>c1&1)==0)c1--;
while((v2>>c2&1)==0)c2--;
while(c1>=0 and c2>=0){
if((v1>>c1&1) != (v2>>c2&1))break;
c1--,c2--;
}
c1++,c2++;
for(int k=i+1;k<=i+c1 and k<=j-1;k++)a[k]=a[k-1]/2;
for(int k=j-1;k>=j-c2 and k>=i+1;k--)a[k]=a[k+1]/2;
for(int k=i+c1+1,t=0;k<=j-c2-1;k++,t^=1)a[k]=(t==0?a[k-1]*2:a[k-1]/2);
}
}
int p=1;
while(a[p]==-1)p++;
for(int i=p-1;i>=1;i--){
if(a[i+1]*2>1e9)a[i]=a[i+1]/2;
else a[i]=a[i+1]*2;
}
p=n;
while(a[p]==-1)p--;
for(int i=p+1;i<=n;i++){
if(a[i-1]*2>1e9)a[i]=a[i-1]/2;
else a[i]=a[i-1]*2;
}
for(int i=2;i<=n;i++){
if(a[i-1]/2==a[i] or a[i]/2==a[i-1])continue;
cout<<-1<<endl;
return;
}
for(int i=1;i<=n;i++)cout<<a[i]<<' ';
cout<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin>>T;
while(T--){
solve();
}
return 0;
}
E. Permutation of Rows and Columns
题目大意
给2个n * m的矩阵，里面的数是1~n * m的排列，能够任意交换行和列，问是否能够使得2个矩阵一致
解题思路
发现操作后，原来在同一列的仍然会在同一列，在同一行的仍然会在同一行，只是顺序变了，于是我们验证第二个矩阵中的每一行每一列，看其在第一个矩阵中行列是否相同
写构造题要对特性敏感，同时要敢于猜测，大胆猜测
神奇的代码
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
using namespace std;
#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
void solve(){
int n,m;
cin>>n>>m;
vector<vector<int>>a(n,vector<int>(m)),b(n,vector<int>(m));
vector<PII>at(n*m+5);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
at[a[i][j]]={i,j};
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>b[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(at[b[i][j]].first!=at[b[i][0]].first){
cout<<"NO"<<endl;
return;
}
}
}
for(int j=0;j<m;j++){
for(int i=0;i<n;i++){
if(at[b[i][j]].second!=at[b[0][j]].second){
cout<<"NO"<<endl;
return;
}
}
}
cout<<"YES"<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin>>T;
while(T--){
solve();
}
return 0;
}
C. Nene's Magical Matrix
题目大意
对于一个n * n的矩阵，我们每次可以选择1行(或1列)，给该行(该列)赋值一个1~n的排列，要在2 * n步内实现矩阵所有数的和最大，输出方案
解题思路
构造题也要多利用样例，看了样例，再加上自己尝试，可以大概清楚最大的情况就是第二个点那样，向外一层层增大的
那么如何操作呢？往简单方面想就是先做完行的操作，然后再做列的操作，发现这样做没法在2 * n内完成，然后另一种可能就是交叉着做，确实可行
构造题排除法来做也是不错的
神奇的代码
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
using namespace std;
#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
void solve(){
int n;cin>>n;
LL s=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int v=max(i,j)+1;
s+=v;
}
}
cout<<s<<' '<<2*n<<endl;
for(int j=n;j>=1;j--){
cout<<1<<' '<<j<<' ';
for(int k=1;k<=n;k++)cout<<k<<' ';
cout<<endl;
cout<<2<<' '<<j<<' ';
for(int k=1;k<=n;k++)cout<<k<<' ';
cout<<endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin>>T;
while(T--){
solve();
}
return 0;
}