碎碎念
我输麻了QAQ
Day8
中午瞄了一眼，昨天打的div2，+251分
然后这是我打的第三把比赛，初始分是250分，呜呜呜呜呜
我的水平大概就1500了，寄
--------碎碎念到此结束，下面是正文（手动分割线）--------
别问，问就是没写，开摆
A - Wonderful Permutation
给你一个排列，每次可以任意交换两个数
询问多少次交换可以使sum[1..k]最小
solution
就是问你多少次交换能把数1-k挪到位置1-k上
#include<bits/stdc++.h>
using namespace std;
int T,n,k,ans,a[110];
int main()
{
scanf("%d",&T);
for(int i=1;i<=T;i++)
{
scanf("%d%d",&n,&k),ans=0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=k+1;i<=n;i++)
if(a[i]<=k)ans++;
printf("%d\n",ans);
}
return 0;
}B - Woeful Permutation
构造一个排列，使sum{lcm(i,ai)}最大
solution
每个数最优肯定是与它相差1的数
判断奇数和偶数的情况即可
#include<bits/stdc++.h>
using namespace std;
int T,n;
int main()
{
scanf("%d",&T);
for(int i=1;i<=T;i++)
{
scanf("%d",&n);
if(n%2)
{
printf("1");
for(int i=2;i<=n;i+=2)
printf(" %d %d",i+1,i);
printf("\n");
}
else
{
printf("2 1");
for(int i=3;i<=n;i+=2)
printf(" %d %d",i+1,i);
printf("\n");
}
}
return 0;
}C - Sort Zero
给你一个数组，每次操作可以将所有等于x的元素设置成0
询问多少次操作可以让这个数组严格不降
solution
显然找末尾有多少不需要操作的元素即可
#include<bits/stdc++.h>
using namespace std;
int T,n,ans,nw,a[100010],s[100010];
int main()
{
scanf("%d",&T);
for(int _i=1;_i<=T;_i++)
{
scanf("%d",&n),ans=0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),s[i]=0;
for(int i=1;i<=n;i++)
{
if(!s[a[i]])ans++;
s[a[i]]++;
}
nw=a[n];
for(int i=n;i>=1;i--)
{
if(a[i]==nw)
{
s[nw]--;
if(!s[nw])ans--;
}
else
{
if(s[nw]||a[i]>nw)break;
nw=a[i],s[nw]--;
if(!s[nw])ans--;
}
}
printf("%d\n",ans);
}
return 0;
}D - Empty Graph
给定一个数组，设置一个无限图，i->j的边权为min{a[i]...a[j]}
你可以进行k次操作，每次操作可以将一个数改为[1...10^9]的任意数
要求输出最大化的直径
solution
有两个（显然的？）性质：
- 两点间的最短路要么为 两点间直连的边长，要么为 两倍全局最小 a 的值；
- 图的直径必然可在相邻两点的最短路处取得；
然后可以用二分来检验每一次的答案
首先将所有能作为全局最小a的不合法的数修改，然后找一个最优的相邻两点修改
比较修改次数与k即可，好像还有贪心的做法，但是我赛时搞了两个小时没搞出来呜呜呜
#include<bits/stdc++.h>
#define MAXX 1000000000
using namespace std;
int T,n,k,a[100010];
int check(int p)
{
int cnt=0,tag=2;
for(int i=1;i<=n;i++)
{
if(a[i]*2<p)cnt++,tag=min(tag,1);
if(a[i]>=p)tag=min(tag,1);
if(i!=1&&(a[i-1]>=p||a[i-1]*2<p)&&(a[i]>=p||a[i]*2<p))tag=min(tag,0);
}
return cnt+tag<=k;
}
int main()
{
scanf("%d",&T);
for(int _i=1;_i<=T;_i++)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int l=1,r=MAXX,ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))
ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d\n",ans);
}
return 0;
}
Comments NOTHING