liaoxuewu 2020-01-04
链接: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+7; const int maxn = 2e5+10; 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 = 2;i<=sqrt(x);i++){ if(x%i == 0) return true; } return false; } int main(){ ll black = 0 , white = 0; int n;cin>>n; int cur = 0; for(int i = 0;i<n;i++){ ll a ;cin>>a; if(cur == 0){ black +=(a/2+a%2); white +=a/2; cur = 1; } else{ cur = 0; black +=a/2; white +=(a/2+a%2); } } ll ans = min(black,white); cout<<ans; return 0; }