南京Day1

赛中有点困睡着了

T1：

水

T2：

4自己独立，2和自己拼，1和3拼，还有剩的1和2拼

T3：

左端点排序O(n)扫一遍即可。

T4：

dp，当然有贪心做法不过没看懂。

转移部分：

 dp[i][0] = min(dp[i - 1][0] + (s[i] == 'B'), dp[i - 1][1] + 1);
 dp[i][1] = min(dp[i - 1][1] + (s[i] == 'A'), dp[i - 1][0] + 1);

T5：

分别将这些点分别按x，y，z排序，然后两两相邻的连边，最后最小生成树。虽然我无法证明，但是靠直觉感受是没问题的。

T6：

数组b为a的倒序，求b和a的最长公共上升子序列。

T7：

费用流

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
int n,m,s,t;
int idx,head[510],nex[510],edge[510];
int lv[510],cur[510];
ll mx,wt[510],_202[50][50];
void add_edge(int u,int v,ll w)
{
    nex[++idx]=head[u];
    edge[idx]=v;
    wt[idx]=w;
    head[u]=idx;
    nex[++idx]=head[v];
    edge[idx]=u;
    wt[idx]=0;
    head[u]=idx;
}
int tag(int x,int y)
{
    return n*(x-1)+y;
}
bool bfs()
{
    memcpy(cur,head,sizeof head);
    queue<int>q;
    lv[s]=1;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        if(now==t) return true;
        for(int i=head[now];i;i=nex[i])
        {
            if(wt[i]&&!lv[edge[i]])
            {
                lv[edge[i]]=lv[now]+1;
                q.push(edge[i]);
            }
        }
    }
    return false;
}

ll dfs(int now,ll flow)
{
    if(now==t) return flow;
    ll rest=flow;
    for(int i=cur[now];i;i=nex[i])
    {
        cur[now]=i;
        if(wt[i]&&lv[edge[i]]==lv[now]+1)
        {
            ll num=dfs(edge[i],min(rest,wt[i]));
            if(num)
            {
                wt[i]-=num;
                wt[i^1]+=num;
                rest-=num;
                if(!rest) break;    
            }
            else lv[edge[i]]=0;
        }
    }
    return flow-rest;
}
ll dinic()
{ 
    ll res=0;
    while(bfs()) res+=dfs(s,inf);
    return res;
}
bool build_and_check(int gl)
{
    if(gl<mx) return false;
    memset(head,0,sizeof head);
    idx=1,s=0,t=n*m+1;
    ll cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if((i+j)%2==1)
            {
                cnt+=gl-_202[i][j]; 
                int now=tag(i,j);
                add_edge(s,now,gl-_202[i][j]);
                if(i>1) add_edge(now,tag(i-1,j),inf);
                if(j>1) add_edge(now,tag(i,j-1),inf);
                if(i<n) add_edge(now,tag(i+1,j),inf);
                if(j<m) add_edge(now,tag(i,j+1),inf);
            }
        }
    }
    return dinic()==cnt;
}
void aha()
{
    int white=0,black=0;
    ll sw=0,sb=0;
    mx=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>_202[i][j];
            mx=max(mx,_202[i][j]);
            if((i+j)%2==1)
            {
                white++;
                sw+=_202[i][j];
            }
            else 
            {
                black++;
                sb+=_202[i][j];
            }
        }
    }
    if(white-black!=0)
    {
        if((sw-sb)%(white-black)!=0)
        {
            cout<<"-1"<<endl;
            return;
        }
        ll gl=(sw-sb)%(white-black);
        if(!build_and_check(gl))
        {
            cout<<"-1"<<endl;
            return;
        }
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                ans+=gl-_202[i][j];
            }
        }
        cout<<ans/2<<endl;  
    }
    else
    {
        ll l=mx,r=10000000000,res=-1;
        while(l<=r)
        {
            ll mid=(l+r)/2;
            if(build_and_check(mid))
            {
                r=mid-1;
                res=mid;
            }
            else
            {
                l=mid+1;
            }
        }
        if(res==-1)
        {
            cout<<"-1"<<endl;
            return;
        }
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                ans+=res-_202[i][j];
            }
        }
        cout<<ans/2<<endl;
    }
    return;
}
int main()
{
    int T;
    cin>>T;
    while(T--) aha();
    return 0;
}