CF1268B Domino for Young

· · 题解

一个思维喵喵题，出的很好，很喜欢

肯定是奇偶分析的，对于每一列讨论，如果当前这一列为偶数，那么一定是可以塞满的，无论旁边是奇数个，还是偶数个，都可以横着或者竖着的拼。其实本题的难点就是讨论奇数个的列，因为如果只考虑单列，会空出来一个，那么就要将这个空和其他空结合。
看了一眼其他的题解，写的都很好，很严谨。但是我做这题的时候没想这么多，感性的证明了一下。

结论：对于所有奇数个数的列，一个奇数位和一个偶数位相对应可以多拼一个出来。
先感性的理解一下，如果两个位置之间隔着奇数列（即两个奇数个数的列，位置奇偶性也相同），那么中间的那几列只能独立完成拼接，而不能传递旁边两列的空。如果两个位置之间隔着偶数列（即两个奇数个数的列，位置奇偶性不同），那么中间是可以完成传递的，只用考虑最后两列，全部横着交错拼就行。

具体证明如下： 旁边两列奇数列减去 1 就变成偶数列，显然可以独立拼满，对于偶数列，每列减去 2 显然也可以度列拼满。所以只需要考虑最后两列能不能横着传递拼完即可。
如果两个奇数列中间隔着奇数列是无解的，如图

那么其实横着根据奇偶传递是不能满足最后一列最后一个，和前一列下面最后一个同时空着。
如果两个奇数列中间隔着偶数列是有解的，如图

是可以通过技偶传递，满足最后一列最后一个，和前一列下面最后一个同时空着。
那么答案就可以算了，对于每个数上面可以完全拼完，所以每一列的初始贡献就是 \lfloor \frac{a_i}{2} \rfloor ,然后如果 x 记为 a_i \equiv 1\pmod 2 的数量，y 记为 a_i \equiv 0\pmod 2 的数量。因为一个奇数位置的列可以和一个偶数位置的列匹配，那么这个额外的贡献就是 min(x,y)。
那么综上所述，答案就是 \sum\limits_{i=1}^n \lfloor \frac{a_i}{2} \rfloor + min(x,y)。
代码如下： 

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<functional>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;

inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0',c=getchar();}
    return x*f;
}
const int N=3e5+10;
int a[N];
int main()
{
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    ll x=0,y=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=a[i]/2;
        if(a[i]&1)
        {
            if(i&1)x++;
            else y++;
        }
    }
    cout<<ans+min(x,y)<<endl;
    return 0;
}