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

ddddddf

　　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=400100,MAX=1000100;
int n,m,flag;
int a[30][30],vis[30];
void exchange(int i,int j)
{
int t;
FF(l,1,n){
t=a[l],a[l]=a[l][j],a[l][j]=t;
}
}
int is()
{
int num=0;
FF(l,1,n){
num=0;
FF(i,1,m){
if(a[l]!=i){
num++;
if(num>2){return 0;}
}
}
}
return 1;
}
void solve()
{
if(is()){flag=1;return ;}
FF(i,1,m-1)FF(j,i+1,m)
{
exchange(i,j);
if(is()){flag=1;return ;}
exchange(i,j);
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
FF(i,1,n)FF(j,1,m)cin>>a[j];
flag=0;
solve();
if(flag)puts("YES");
else puts("NO");
}
return 0;
}
View Code　　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=100100,MAX=1000100;
int m,len;
char str[N];
int solve(int ans)
{
int pre=-1,now=-1,num=0;
F(i,0,len){
if(str-'a'<=ans){
now=i;
if(str-'a'<ans)pre=i;
}
if(i-pre==m) {
if(now>pre) num++,pre=now;
else return -1;
}
}
return num;
}
int main()
{
scanf("%d%s",&m,str);
len=strlen(str);
int vis[26]; mes(vis,0);
F(i,0,len) vis[str-'a']++;
F(i,0,26){
int flag=solve(i);
if(flag!=-1){
F(j,0,i)F(l,0,vis[j]){
printf("%c",'a'+j);
}
F(j,0,flag) printf("%c",'a'+i);
puts("");
break;
}
}
return 0;
}
View Code