自动搬运

查看原文

来自洛谷，原作者为

	acat 我也想当人 win，可以让我 win 一次吗。/kel

搬运于2025-08-24 22:38:48，当前版本为作者最后更新于2022-07-04 15:14:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

首先要注意的是，利用行、列旋转可以放置任意元素。

对于给定的行或列。例如，让序列 $s= \{p_1,p_2,\dots,p_r\}$ 的 $r$ 个元素，我们想放在第一列。对于第 $i$ 个元素，我们可以：

• 如果 $p_i$ 已经在第一列，我们把它放出来，将行旋转 $1$。

• 旋转包含 $p_i$ 的列，使其在第 $i$ 行。

• 旋转包含 $p_i$ 的行，使其位于第 $1$ 列。

使用这个算法，我们可以将任意选择的 $r$ 元素放在第一列，任意选择的 $s$ 元素放在第一行。现在可以对第一行、列中的所有元素求反。如果我们重复这个过程，我们可以选择矩阵中任意的 $a \times r+b \times s \le r \times s$ 个元素并对它们求反。

因为这不总是可能的，我们需要选择这样的 $a$ 和 $b$，从而找到最小的可能的解决方案。对数组中的元素进行排序并使用动态规划可以很容易地得到最佳的 $a$ 和 $b$。

注意，对于每个元素，我们最多使用 $3$ 次旋转和 $2$ 次否定，这确保操作的次数小于 $5 \times r \times s$。

时间复杂度 $O((\max \{r,s\})^4)$。

AC Code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>

#define Row first
#define Col second

using namespace std;
vector< string > rez;
vector< pair< int, int > > koord;

int R, S, mat[ 105 ][ 105 ], niz[ 10005 ];
int recon[ 20005 ], moguce[ 20005 ] = { 1 };
int sumuk[ 20005 ] = { 0 }, negativnih = 0;
int por[ 10005 ], tmp[ 105 ], cnt = 0;
char tmpbuff[ 105 ], ozn[ 105 ][ 105 ];


void rotaterow( int row, int K ) {
	for( int i = 0; i < S; ++i )
		tmp[ ( i + K ) % S ] = mat[ row ][ i ];
	for( int i = 0; i < S; ++i )
		mat[ row ][ i ] = tmp[ i ];
	for( int i = 0; i < ( int )koord.size(); ++i )
		if( koord[ i ].Row == row )
			koord[ i ].Col = ( koord[ i ].Col + K ) % S;
	
	sprintf( tmpbuff, "rotR %d %d", row + 1, K );
	rez.push_back( string( tmpbuff ) );
}

void rotatecol( int col, int K ) {
	for( int i = 0; i < R; ++i )
		tmp[ ( i + K ) % R ] = mat[ i ][ col ];
	for( int i = 0; i < R; ++i )
		mat[ i ][ col ] = tmp[ i ];
	for( int i = 0; i < ( int )koord.size(); ++i )
		if( koord[ i ].Col == col )
			koord[ i ].Row = ( koord[ i ].Row + K ) % R;
	
	sprintf( tmpbuff, "rotS %d %d", col + 1, K );
	rez.push_back( string( tmpbuff ) );
}

void changerow( int row ) {
	for( int i = 0; i < S; ++i )
		mat[ row ][ i ] = -mat[ row ][ i ];
	
	sprintf( tmpbuff, "negR %d", row + 1 );
	rez.push_back( string( tmpbuff ) );
}

void changecol( int col ) {
	for( int i = 0; i < R; ++i )
		mat[ i ][ col ] = -mat[ i ][ col ];
	
	sprintf( tmpbuff, "negS %d", col + 1 );
	rez.push_back( string( tmpbuff ) );
}

int suma( int a, int b ) {
	if( a > b ) return( 0 );
	return( sumuk[ b ] - ( a == 0 ? 0 : sumuk[ a-1 ] ) );
}

int evalpod( int X ) {
	return( suma( X, R * S - 1 ) - suma( 0, X - 1 ) );
}

pair< int, int > pronadji( int X ) {
	for( int i = 0; i < R; ++i )
		for( int j = 0; j < S; ++j )
			if( !ozn[ i ][ j ]  &&  mat[ i ][ j ] == X ) {
				ozn[ i ][ j ] = 1;
				return make_pair( i, j );
			}
	
	return make_pair( -1, -1 );
}

void sredi_stupac( void ) {
	int len = ( int )koord.size();
	for( int i = 0; i < len; ++i ) {
		int razl = i - koord[ i ].Row;
		if( razl < 0 ) razl += R;
		
		if( koord[ i ].Col == 0 ) rotaterow( koord[ i ].Row, 1 );
		if( koord[ i ].Row != i ) rotatecol( koord[ i ].Col, razl );
		rotaterow( koord[ i ].Row, S - koord[ i ].Col );
	}
}

void sredi_redak( void ) {
	int len = ( int )koord.size();
	for( int i = 0; i < len; ++i ) {
		int razl = i - koord[ i ].Col;
		if( razl < 0 ) razl += S;
		
		if( koord[ i ].Row == 0 ) rotatecol( koord[ i ].Col, 1 );
		if( koord[ i ].Col != i ) rotaterow( koord[ i ].Row, razl );
		rotatecol( koord[ i ].Col, R - koord[ i ].Row );
	}
}

int main( void ) {
	scanf( "%d %d", &R, &S );
	for( int i = 0; i < R; ++i )
		for( int j = 0; j < S; ++j ) {
			scanf( "%d", &mat[ i ][ j ] );
			niz[ S * i + j ] = mat[ i ][ j ];
		}
	
	sort( niz, niz + R * S );
	for( int i = 0; i < R * S; ++i ) {
		negativnih += ( niz[ i ] < 0 );
		sumuk[ i ] = ( i > 0 ? sumuk[ i-1 ] : 0 ) + niz[ i ];
		
		if( !moguce[ i ] ) continue;
		moguce[ i + R ] = 1;
		moguce[ i + S ] = 1;
		recon[ i + R ] = i;
		recon[ i + S ] = i;
	}
	
	int X, A = -1, B = -1;
	for( int i = 0; i <= R * S; ++i ) {
		if( !moguce[ i ] ) continue;
		if( i <= negativnih ) A = i;
		if( i >= negativnih && B == -1 )
			B = i;
	}
	
	if( A == -1 ) X = B; else if( B == -1 ) X = A;
	else X = ( evalpod( A ) > evalpod( B ) ? A : B );
	
	int prez = evalpod( X );
	while( X != 0 ) {
		por[ cnt++ ] = X;
		X = recon[ X ];
	}
	
	por[ cnt++ ] = 0;
	reverse( por, por + cnt );
	
	for( int i = 0; i < cnt-1; ++i ) {
		memset( ozn, 0, sizeof( ozn ) );
		koord.clear();
		
		for( int j = por[ i ]; j < por[ i + 1 ]; ++j )
			koord.push_back( pronadji( niz[ j ] ) );
		
		if( por[ i + 1 ] - por[ i ] == R ) {
			sredi_stupac();
			changecol( 0 );
		} else {
			sredi_redak();
			changerow( 0 );
		}
	}
	
	printf( "%d %d\n", prez, ( int )rez.size() );
	for( int i = 0; i < ( int )rez.size(); ++i )
		printf( "%s\n", rez[ i ].c_str() );
	
	return( 0 );
}