Codeforces Round Intel Code Challenge Final Round B.Batch Sort

news/2024/5/18 21:51:45 标签: codeforces, 枚举

题目大意:给你一个矩阵,每行可以选择两个数交换一次,还可以交换一次两列,问你可否操作后使得每行都是1到m的排列


考虑暴力枚举交换的列,然后看每行是否可以再交换一次使得合法

有小于等于两个数不在对应的位置即为合法


#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[31][31],b[31][31];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	int i,j,ii,jj;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	for(i=1;i<=m;i++)
	{
		for(j=i;j<=m;j++)
		{
			for(ii=1;ii<=n;ii++)
				for(jj=1;jj<=m;jj++)
					b[ii][jj]=a[ii][jj];
			for(ii=1;ii<=n;ii++)
			{
				int t=b[ii][i];
				b[ii][i]=b[ii][j];
				b[ii][j]=t;
			}
			bool flag=true;
			for(ii=1;ii<=n;ii++)
			{
				int ss=0;
				for(jj=1;jj<=m;jj++)
				{
					if(b[ii][jj]!=jj)
						ss++;
				}
				if(ss>2)
				{
					flag=false;
					break;
				}
			}
			if(flag)
			{
				printf("YES\n");
				return 0;
			}
		}
	}
	printf("NO\n");
	return 0;
}



http://www.niftyadmin.cn/n/942604.html

相关文章

GDOI 2016 Day2 T3 机密网络

Description 给出一个n个点n条边的无向连通图&#xff0c;每个点有点权Ai&#xff0c;每条边的边权都为1&#xff0c;求所有距离<k的点对个数以及它们的权值乘积和。 n<10^5, Solution 很明显&#xff0c;原图是一个环套外向树。&#xff08;就是一个环&#xff0c;外…

……

God Keeps that……

Codeforces Round Intel Code Challenge Final Round C. Ray Tracing

题目大意&#xff1a;光线从(0,0)点出发斜向上45角&#xff0c;速度为√2。平面上有若干个点&#xff0c;问每个点第一次被光线穿过的时间&#xff0c;未被穿过输出-1 似乎可以用CRT做&#xff0c;但是我写的是大模拟。 因为碰撞点只有4(nm)个&#xff0c;而且每条对角线只可能…

bzoj4569[Scoi2016]萌萌哒

Description 给出一个有n位的无前导0正整数&#xff0c;再给出m个限制&#xff0c;每个限制形如l1…r1,l2..r2表示这个数的l1~r1位和第l2~r2位是相等的。求这样的数的个数。 n,m<10^5 Solution 我们可以先来考虑一下暴力。 对于这一个区间&#xff0c;我们暴力把它们用…

BZOJ 1030 [JSOI2007]文本生成器 DP+AC自动机

Description JSOI交给队员ZYX一个任务&#xff0c;编制一个称之为“文本生成器”的电脑软件&#xff1a;该软件的使用者是一些低幼人群&#xff0c; 他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文 章—— 也就是说&a…

Codeforces Round Intel Code Challenge Final Round D. Dense Subsequence

题目大意&#xff1a;给你一个字符串&#xff0c;要求你选择若干个位置&#xff0c;使得任意相邻m个字符都至少有一个被选中&#xff0c;并且要求选中字符排序后的字典序列最小 一开始写了个单调队列DP&#xff0c;然后WA5发现并不具有局部最优推到全局最优的性质 洗澡的时候发…

关于一只神奇的Howar Li

开♂车开太快超速了&#xff0c;翻了。。。 嘿嘿&#xff0c;那么我只能说 雾

既然过去了&#xff0c; 就放了把……