P13440 题解

ikunTLE · 2025-07-25 09:23:11 · 题解

题目传送门

思路

根据题目要求，不难想到一条性质：一行中起到决定性因素的是该行的最后一个 1。

对此，可以进行贪心操作：

• 另 L_i 表示第 i 行最后一个 1 的下标。
• 如果该行需要移动，则计算所需移动次数 L_i-i。
• 该行移动后，更新所有的该行移动时所经过的行。

时间复杂度 \mathcal{O}(N^2)，而 N\le40，可以通过此题。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=50;
char s[N][N];
int last[N];
bool flag[N];
int main(){
    int T=read();
    for(int t=1;t<=T;++t){
        memset(last,0,sizeof(last));
        memset(flag,0,sizeof(flag));
        int n=read();
        for(int i=1;i<=n;++i){
            scanf("%s",s[i]+1);
            for(int j=n;j>=1;--j)
                if(s[i][j]=='1'){
                    last[i]=j;
                    break;
                }
        }
        int ans=0;
        for(int i=1;i<=n;++i){
            int j=i;
            while(j<=n&&last[j]>i)
                ++j;
            if(j>n)
                continue;
            ans+=j-i;
            int temp=last[j];
            for(int k=j;k>i;--k)
                last[k]=last[k-1];
            last[i]=temp;
        }
        printf("Case #%d: %d\n",t,ans);
    }
    return 0;
}