|
|
A. Greatest Convex
思路：输出k-1即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) (x)&(-x)
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int maxn=200100;
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T--){
int n;cin>>n;
cout<<n-1<<&#39;\n&#39;;
}
return 0;
}
B. Quick Sort
思路：先思考怎么把一个排列变有序，因为每次操作都是把排列好的放到最后面，所以固定的做法是先选择1~k,把1~k放到最后面，然后是k+1~2k.....那么最优的操作就很明显了，如果前面1~x是有序的，我们只需要对后面n-x个元素进行操作，故答案是(n-x)(向上取整)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) (x)&(-x)
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int maxn=200100;
int a[maxn];
int hs[maxn];
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T--){
int n,k;cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>a;
hs[a]=i;
}
int cur=0;
int i=1;
for(;i<=n;++i){
if(hs>cur){
cur=hs;
}
else break;
}
if(i<=n)
cout<< (n-i)/k+1 <<&#39;\n&#39;;
else
cout<<0<<&#39;\n&#39;;
}
return 0;
}
C. Elemental Decompress
思路：这是由两个排列的每个位置的最大值构成的，故每个元素出现的次数只有0,1,2三种可能。对于出现2次的元素一定是抢占了出现0次的元素的出现机会，所以我们分别储存出现0次和2次的元素，进行排序。每个出现2次的元素一定对应了一个比它小的且出现0次的元素。对于出现1次的元素，我们可以直接令p=q即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) (x)&(-x)
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int maxn=200100;
int a[maxn];
int num[maxn];
int tmp[maxn];
int ansa[maxn],ansb[maxn];
int hs[maxn];
void solve(){
int n;cin>>n;
for(int i=0;i<=n;++i){
num=tmp=ansa=ansb=hs=0;
}
for(int i=1;i<=n;++i){
cin>>a;
num[a]++;
}
for(int i=1;i<=n;++i){
if(num>2){
cout<<&#34;NO\n&#34;;
return ;
}
}
vector<int> two,zero;
for(int i=1;i<=n;++i){
if(num==2)two.push_back(i);
if(num==0)zero.push_back(i);
}
sort(two.begin(),two.end());
sort(zero.begin(),zero.end());
if(two.size()!=zero.size()){
cout<<&#34;NO\n&#34;;
return ;
}
for(int i=0;i<two.size();++i){
if(two>zero)hs[two]=zero;
else{
cout<<&#34;NO\n&#34;;
return ;
}
}
for(int i=1;i<=n;++i){
if(num[a]==1)ansa=ansb=a;
}
for(int i=1;i<=n;++i){
tmp[a]++;
if(tmp[a]==1&&num[a]==2)ansa=a,ansb=hs[a];
if(tmp[a]==2&&num[a]==2)ansa=hs[a],ansb=a;
}
cout<<&#34;YES\n&#34;;
for(int i=1;i<=n;++i)cout<<ansa<<&#39; &#39;;
cout<<&#39;\n&#39;;
for(int i=1;i<=n;++i)cout<<ansb<<&#39; &#39;;
cout<<&#39;\n&#39;;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T--){
solve();
}
return 0;
}
D. Lucky Permutation
思路：显然只有一个逆序对的排列，肯定是形如 2 1 3 4、1 3 2 4、1 2 4 3，这种由一个顺序排列交换两个相邻元素得来的。于是我们可以通过枚举交换哪个位置的元素来看到底变成怎么样最优。那么把一个排列变成另一个排列需要多少次操作呢，一个经典的想法是：我们可以把a与i连边，需要交换的次数就是n-cnt，cnt是联通块的个数，用并查集维护即可。那么对于交换两个相邻元素，手摸一下发现如果这两个是在一个联通块的，那么一但交换就会分成两个联通块，如果是在两个联通块的，一但交换就会变成一个联通块。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) (x)&(-x)
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int maxn=200100;
int a[maxn];
int par[maxn];
int vis[maxn];
void init(int n){
for(int i=0;i<n+10;++i){
par=i;
vis=0;
}
}
int find(int x){
if(par[x]==x)return x;
else return par[x]=find(par[x]);
}
void solve(){
int n;cin>>n;
init(n);
for(int i=1;i<=n;++i)cin>>a;
for(int i=1;i<=n;++i){
int x=find(i),y=find(a);
if(x!=y)par[x]=y;
}
int cnt=0;
for(int i=1;i<=n;++i){
int x=find(i);
if(!vis[x]){
cnt++;
vis[x]=1;
}
}
int ans=inf;
for(int i=1;i<n;++i){
int x=find(a),y=find(a[i+1]);
if(x!=y){
ans=min(ans,n-cnt+1);
}
else{
ans=min(ans,n-cnt-1);
}
}
cout<<ans<<&#39;\n&#39;;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T--){
solve();
}
return 0;
} |
|
发表于 2023-1-8 14:56:32