排列组合2

· · 个人记录

A - Parquet

题目链接

这跟组合数学有什么关系？

首先，我们发现，若 n 或 m 是奇数，就会多出来一列（行），而这一列（行）就需要用一块 2 \times 1（1\times 2）的砖去填充，这时，只需要填充中间的部分，而这部分一定用 2\times 2 的砖，当然也可以用剩下来的 1\times 2 的或 2\times 1 的来组成 2\times 2 的。

考虑无解的情况，即 n 和 m 都为奇数或 2\times 2 的砖不够。

代码：

#include<bits/stdc++.h>
using namespace std;
int n, m, a, b, b1, c, c1;
int sum, l, r;
char ans[105][105];
int main() {
//  freopen("Output.txt", "w", stdout);
    cin>>n>>m>>b>>c>>a;
    b1 = b, c1 = c;
    if(n & 1 && m & 1) {
        puts("IMPOSSIBLE");
        return 0;   
    }
    sum = (n / 2) * (m / 2);
    if(m & 1) l = n / 2;
    if(n & 1) r = m / 2;
    if(b < r) {
        puts("IMPOSSIBLE");
        return 0;
    }
    if(c < l) {
        puts("IMPOSSIBLE");
        return 0; 
    }
    if(sum > a + ((b - r) / 2) + ((c - l) / 2)) {
        puts("IMPOSSIBLE");
        return 0;
    }
    b1 -= r;
    c1 -= l;
    for(int i = 1; i <= n - (n & 1); i += 2) {
        for(int j = 1; j <= m - (m & 1); j += 2) {
//          cout<<i<<' '<<j<<' '<<a<<' '<<b1<<' '<<c1<<endl;
            if(a) {
                int p = 'a';
                while(p == ans[i - 1][j] || p == ans[i - 1][j + 1] || p == ans[i][j - 1] || p == ans[i + 1][j - 1]) p++;
                ans[i][j] = ans[i + 1][j] = ans[i][j + 1] = ans[i + 1][j + 1] = p;
                a--;    
            } else if(b1 > 1) {
                int p = 'a';
                while(p == ans[i - 1][j] || p == ans[i - 1][j + 1] || p == ans[i][j - 1] || p == ans[i + 1][j - 1]) p++;
                ans[i][j] = ans[i][j + 1] = p;
                p = 'a';
                i++;
                while(p == ans[i - 1][j] || p == ans[i - 1][j + 1] || p == ans[i][j - 1] || p == ans[i + 1][j - 1]) p++;
                i--;
                ans[i + 1][j] = ans[i + 1][j + 1] = p;
                b1 -= 2;
            } else if(c1 > 1) {
                int p = 'a';
                while(p == ans[i - 1][j] || p == ans[i - 1][j + 1] || p == ans[i][j - 1] || p == ans[i + 1][j - 1]) p++;
                ans[i][j] = ans[i + 1][j] = p;
                p = 'a';
                j++;
                while(p == ans[i - 1][j] || p == ans[i - 1][j + 1] || p == ans[i][j - 1] || p == ans[i + 1][j - 1]) p++;
                j--;
                ans[i][j + 1] = ans[i + 1][j + 1] = p;
                c1 -= 2;    
            }
        }
    }
    if(m & 1) {
        int j = m;
        for(int i = 1; i <= n; i += 2) {
            int p = 'a';
            while(p == ans[i - 1][j] || p == ans[i - 1][j + 1] || p == ans[i][j - 1] || p == ans[i + 1][j - 1]) p++;
            ans[i][j] = ans[i + 1][j] = p;
        }
    } else if(n & 1) {
        int i = n;
        for(int j = 1; j <= m; j += 2) {
            int p = 'a';
            while(p == ans[i - 1][j] || p == ans[i - 1][j + 1] || p == ans[i][j - 1] || p == ans[i + 1][j - 1]) p++;
            ans[i][j] = ans[i][j + 1] = p;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cout<<ans[i][j];
        }
        cout<<endl;
    }
    return 0;
}

F - Not Quite Lee

题目链接

考虑如何判断一个数列 b_1,b_2,\dots,b_n 是不是「好的序列」。

假设「好的序列」的第 i 项的开头是 p_i，那么其后面的整数的值就是 p_i+1,p_i+2,\dots, p_i+b_i-1。那么第 i 项的和就是：

s_i=\frac{b_i\times(2\times p_i+b_i-1)}{2}

整个「好的序列」的和就是：

\sum^{n}_{i=1}s_i=\frac{\sum^{n}_{i=1}b_i\times (2\times p_i+b_i-1)}{2}

让整个式子为 0，也就是：

\sum^{n}_{i=1}b_i\times (2\times p_i+b_i-1)=0

即

\sum^{n}_{i=1}\left(2\times b_i\times p_i+{b_i}^2-b_i\right)=0 \sum^{n}_{i=1}b_i\times p_i=-\frac{\sum^{n}_{i=1}b_i\times \left(b_i-1\right)}{2}

等式右边为常数，根据翡翠定理可得，若这个多元一次不定方程有解当且仅当：

\gcd\{b_1,b_2,\dots,b_n\}|\sum^{n}_{i=1}\frac{b_i\times (b_i-1)}{2}

即

2|\sum^{n}_{i=1}\frac{b_i\times (b_i-1)}{\gcd\{b_1,b_2,\dots,b_n\}}

不妨设 \gcd\{b_1,b_2,\dots,b_n\}=2^t\times(2\times k - 1)，b_i=2^t\times c_i。

那么原式可以写成：

2|\sum^{n}_{i=1}\frac{2^tc_i\times(2^tc_i-1)}{2^t\times(2\times k - 1)} 2|\sum^{n}_{i=1}\frac{c_i\times(2^tc_i-1)}{2\times k - 1}

我们只需要讨论右边一坨的奇偶性，由于 2\times k-1 是一个奇数，所以可以直接去掉，变成：

\sum^{n}_{i=1}c_i\times(2^tc_i-1)

可以对这其中唯一的变量 t 经行讨论。

  1. 若 t=0，原式必然成立。而且只有当有 b_i 为奇数时，才会有 t=0。所以我们可以把奇数和偶数单独讨论。

  2. 若 t>0，无论如何 (2^tc_i-1) 是一个奇数，不做出贡献。只需要讨论 \sum^{n}_{i=1}c_i 的奇偶性。

对于第 2 种情况，我们只需要枚举 t 算出答案。