牛客国庆集训派对Day6 B-Board

题解

①

假设n=5，有三列被加过，有一行被加过，

那么我们依次遍历每一行的最小值，

把行最小值减去，就能恢复行操作。

再依次遍历每一列的最小值，

把列最小值减去，就能恢复列操作。

 

考虑，有五列被加过且一行被加过的情形。

那么，行最小值，就不完全是行操作所导致了。

但是，我们这么操作，可以使每行减去（行操作+每列均操作过的最小值）。

而这对行最小行元素而言，已经恢复了，其他元素也并没有多减。

后续，我们再每一列找，已经有0元素的列就会被跳过。

而那些少减的列，就会因此被减去。

前提：把-1那个点改成0，多减的值，就是原本应该被减成0的值。

②

思路来源 

https://blog.****.net/m0_37444209/article/details/81454110

考虑以下这种染色方案，将(i行+j列)%n染成同种颜色。

这样我们每次操作的时候，每种颜色的权当且仅当被加一次。

如果n=1，特判为0。

如果n不等于1，

找到与标记点颜色不同的任一颜色，

使之与标记点颜色作差即可。

前提：标记点也需改为权值0。

代码①

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const double INF=0x3f3f3f3f;
const int maxn=1e5+10;
const int mod=1e9+7;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int>
#define si set<int>
#define pii pair<double,int>
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int a[1005][1005],ex,ey;
int main()
{
    int n;
    sci(n);
    rep(i,0,n-1)
    {
        rep(j,0,n-1)
        {
            sci(a[i][j]);
            if(a[i][j]==-1)
            {
                ex=i,ey=j;
                a[i][j]=0;
            }
        }
    }
    rep(i,0,n-1)
    {
        int v=10001;
        rep(j,0,n-1)
        {
            if(ex==i&&ey==j)continue;
            v=min(v,a[i][j]);
        }
        rep(j,0,n-1)a[i][j]-=v;
    }
    rep(j,0,n-1)
    {
        int v=10001;
        rep(i,0,n-1)
        {
            if(ex==i&&ey==j)continue;
            v=min(v,a[i][j]);
        }
        rep(i,0,n-1)a[i][j]-=v;
    }
    printf("%d\n",-a[ex][ey]);
    return 0;
}

代码②

#include <iostream>
#include <algorithm> 
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const double INF=0x3f3f3f3f;
const int maxn=1e5+10; 
const int mod=1e9+7;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<double,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std;
int a[1005][1005],ex,ey,ans[1005];
int main()
{
    bool flag=1;
	int n;
	sci(n);
	rep(i,0,n-1)
	{
		rep(j,0,n-1)
		{
			sci(a[i][j]);
			if(a[i][j]==-1)
			{
				ex=i,ey=j;
				a[i][j]=0;
			}
			ans[(i+j)%n]+=a[i][j];
		} 
	}
    if(n==1)puts("0");
    else
    {
    	rep(i,0,n-1)
    	{
    		if(i!=(ex+ey)%n)
    		{
    			printf("%d\n",ans[i]-ans[(ex+ey)%n]);
    			break;
    		}
    	}
    }
	return 0;
}