codeforces 1269D. Domino for Young （二分图证明/结论题）

链接：https://codeforces.com/contest/1269/problem/D

题意：给一个不规则的网格，在上面放置多米诺骨牌，多米诺骨牌长度要么是1x2，要么是2x1大小，问最多放置多米诺骨牌的数量。

思路：首先这是一个结论题，对每个方格进行染色，一个方格染黑色，周围邻近的就染白色，答案就是黑色方格数量和白色方格数量的最小值。这个结论可以用二分图进行证明：把问题抽象成最大二分图匹配，每两个点之间连一条边。一个格子和周围格子连一条边，如果一个格子周围的还没被匹配，那么匹配数+1。如果一个格子周围已经全部被匹配完，那么该格子可以增广到任意一个为匹配位置，匹配数+1。所以只要在另一种颜色格子数量充沛的情况下，每一次匹配都能对匹配数贡献1，所以答案就是两种颜色的最小值。

AC代码：

 #include<iostream>

 #include<string>

 #include<vector>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef long long ll;

 ll mod = 1e9+;

 const int maxn = 2e5+;

 struct node{

     int dif;

     int ti;

 }g[maxn];

 bool cmp(node a,node b){

     if(a.ti !=b.ti ) return a.ti<b.ti ;

     return a.dif <b.dif ;

 }

 bool check(ll x){

     for(int i = ;i<=sqrt(x);i++){

         if(x%i == ) return true;

     }

     return false;

 }

 int main(){

     ll black =  , white = ;

     int n;cin>>n;

     int cur = ;

     for(int i = ;i<n;i++){

         ll a ;cin>>a;

         if(cur == ){

             black +=(a/+a%);

             white +=a/;

             cur = ;

         }

         else{

             cur = ;

             black +=a/;

             white +=(a/+a%);

         }

     }

     ll ans = min(black,white);

     cout<<ans;

     return ;

 }

巴特西

codeforces 1269D. Domino for Young （二分图证明/结论题）

最新文章

热门文章