CF Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)

时间:2021-08-21 06:40:54

1、 Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)

B. Batch Sort    暴力枚举,水

1、题意:n*m的数组,每行最多可交换1次,列最多可交换两列,问最终是否可以变换到每行都是1~m。

2、总结:暴力即可。

#include<bits/stdc++.h>
#define F(i,a,b) for (int i=a;i<b;i++)
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define mes(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=,MAX=;
int n,m,flag;
int a[][],vis[]; void exchange(int i,int j)
{
int t;
FF(l,,n){
t=a[l][i],a[l][i]=a[l][j],a[l][j]=t;
}
} int is()
{
int num=;
FF(l,,n){
num=;
FF(i,,m){
if(a[l][i]!=i){
num++;
if(num>){return ;}
}
}
}
return ;
} void solve()
{
if(is()){flag=;return ;}
FF(i,,m-)FF(j,i+,m)
{
exchange(i,j);
if(is()){flag=;return ;}
exchange(i,j);
}
} int main()
{
while(~scanf("%d%d",&n,&m))
{
FF(i,,n)FF(j,,m)cin>>a[i][j];
flag=;
solve();
if(flag)puts("YES");
else puts("NO");
} return ;
}

D. Dense Subsequence   暴力枚举

1、题意:小写字母组成的字符串中选出一些位置,使得任意的间距为m的区间至少要有一个字符被选出。字典序最小输出。

2、总结:看了题解,原来还是暴力枚举

2、思路:在26个小写字母中,如果选出了ch,那么比ch小的字母都要选才可保证字典序最小。所以,假设选出的字母中最大的是ch,只要搜出ch最少需要多少个即可。也就是对26个字母逐一搜一遍。

#include<bits/stdc++.h>
#define F(i,a,b) for (int i=a;i<b;i++)
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define mes(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=,MAX=; int m,len;
char str[N]; int solve(int ans)
{
int pre=-,now=-,num=;
F(i,,len){
if(str[i]-'a'<=ans){
now=i;
if(str[i]-'a'<ans)pre=i;
}
if(i-pre==m) {
if(now>pre) num++,pre=now;
else return -;
}
}
return num;
} int main()
{
scanf("%d%s",&m,str);
len=strlen(str);
int vis[]; mes(vis,);
F(i,,len) vis[str[i]-'a']++;
F(i,,){
int flag=solve(i);
if(flag!=-){
F(j,,i)F(l,,vis[j]){
printf("%c",'a'+j);
}
F(j,,flag) printf("%c",'a'+i);
puts("");
break;
} } return ;
}