专栏文章

SP7555题解

NNahia
SP7555题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip476a9
此快照首次捕获于
2025/12/03 05:53
3 个月前
此快照最后确认于
2025/12/03 05:53
3 个月前
查看原文

思路

N≤8N \le 8？
那直接 bfs 1^\texttt{1} 吧。
1\texttt{1}：在此指 "baoli first suanfa"，即“暴力优先算法”。
但是还要加点贪心的思路，遍历所有行，如果这一行不合法，就和下面第一个合法的行交换，如果这一行合法就直接跳过。

solution

CPP
#include<bits/stdc++.h>
#define For(i,a,b) for(int i = a;i<=b;i++)
using namespace std;
inline __int128 read(){__int128 x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){f=-1;}c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
inline void write(__int128 x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');}
int n,a[1005],t,sum;
char b;
int main(){
	t = read();
	For(l,1,t){
		n = read();
		memset(a,0,sizeof(a));//多测清空好习惯 
		sum = 0;
		For(i,1,n){
			For(j,1,n){
				cin>>b;
				if(b=='1') a[i] = j;
			}
		}
		For(i,1,n){
			if(a[i]<=i) continue;
			For(j,i+1,n){
				if(a[j]<=i){
					sum+= j-i;
					for(j = j;j>i;j--) a[j]=a[j-1];
					break;
				}
			}
		}
		printf("Case #%d: %d\n",l,sum);
	}
}

注意

看到是 SPOJ 的题目，意识到注意输出格式。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...