A

題意

構造兩個長為 \(n\) 排列，使得兩排列有長為 \(a\) 公共字首和長為 \(b\) 的公共字尾。

題解

知識點：構造。

注意到，當 \(a+b\leq n-2\) 時，中間段至少有兩個位置可以操作使其不同，於是公共前字尾可以分別滿足互不影響；否則，公共前字尾必然交叉，此時只有 \(a = n,b = n\) 的情況。

時間複雜度 \(O(1)\)

空間複雜度 \(O(1)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    int n, a, b;
    cin >> n >> a >> b;
    if (n - a - b >= 2 || a == n && b == n) cout << "Yes" << '\n';
    else cout << "No" << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

B

題意

給定一個環，初始時每個元素一定不同於它的相鄰元素。

每次操作可以刪除一個元素，刪除後環合併，相同的相鄰元素會立刻消失。

問最多能操作幾次。

題解

知識點：構造。

當環中只含有兩種不同的元素，那麼每次刪除（除了最後兩次）都會再額外消失一個，那麼最終答案是 \(\frac{n}{2} + 1\) 。
當環中至少含有三種不同的元素，我們發現這類環一定存在三個連續的不同元素。

我們可以找到兩個元素 \(a_i,a_j(i \neq j)\) ，滿足 \(a_i = a_j\) 且 \(a_i\) 有兩個不同的相鄰元素，然後刪除 \(a_i\)，直到不存在這樣兩個元素。

最後，至少有一種元素只剩下一個。如果所有種類的元素都至少有兩個，因為一定存在三個連續的不同元素，那麼這三個元素中間的那個元素滿足有相同元素，且這個元素的相鄰元素不同，所以我們可以按上述操作繼續刪。

我們可以以這個元素作為中心，持續刪它的相鄰元素。因為這個元素只有這一個，就不存在環合併後相鄰元素相同的情況，所以最後沒有元素是操作後額外消失的，答案是 \(n\) 。

時間複雜度 \(O(n \log n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    int n;
    cin >> n;
    set<int> st;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        st.insert(x);
    }
    if (st.size() >= 3) cout << n << '\n';
    else cout << n / 2 + 1 << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

C

題意

給出一個 \(n \times n\) 的關係矩陣 \(b\) ，根據 \(b\) 構造 \(n\) 個非空集合 \(A_i\) 。

\(b_{i,j} = 1\) 時表示 \(A_i \subset A_j\) ，其他情況 \(b_{i,j} = 0\) 。

\(A_i\) 中的元素只能是 \([1,n]\) 中的整數。

題解

知識點：構造，STL。

為了使得每個集合與其它沒有關係的集合之間始終是獨立的，我們先給每個集合加入一個唯一的元素，為了方便可以一開始 \(A_i = \{i\}\) 。

這樣以後，我們對 \(b\) 遍歷，對於 \(A_i \subset A_j\) 可以讓 \(A_j = A_i \cup A_j\) 。

最後，兩個互不相干的集合 \(A_i,A_j\) 在合法的關係 \(b\) 之下一定不會有關，因為 \(A_i\) 不會有 \(A_j\) 的獨立元素 \(j\) ，反之亦然。

用 bitset 實現會很舒服qwq。

時間複雜度 \(O(n^3)\)

空間複雜度 \(O(n^2)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool b[107][107];
bitset<107> bs[107];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            char ch;
            cin >> ch;
            b[i][j] = ch == '1';
        }
    }
    for (int i = 1;i <= n;i++) {
        bs[i].reset();
        bs[i][i] = 1;
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (b[i][j]) bs[j] |= bs[i];
        }
    }
    for (int i = 1;i <= n;i++) {
        cout << bs[i].count() << ' ';
        for (int j = 1;j <= n;j++)if (bs[i][j]) cout << j << ' ';
        cout << '\n';
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

D

題意

\(f(a,b)\) 為 \(a+b\) 時發生進位的二進位制位的數量。

求有序對 \((a,b)\) 滿足 \(a,b \in [0,2^n)\) 時， \(f(a,b) = k\) 的數量。

題解

方法一

知識點：排列組合，數學。

我們考慮發生進位位置對答案的影響。

設 \(a_i,b_i\) 分別為 \(a,b\) 的二進位制第 \(i\) 位（從 \(1\) 開始），\(c_i\) 表示 \(a+b\) 在第 \(i\) 位（從 \(1\) 開始）是否進位。另外，\(c_0 = 0\) 方便之後計數。

顯然只有以下四種情況：

如果 \(c_i = 0,c_{i-1} = 1\) ，那麼可以推斷 \((a_{i},b_{i}) = (0,0)\) 。
如果 \(c_i = 1,c_{i-1} = 0\) ，那麼可以推斷 \((a_{i},b_{i}) = (1,1)\) 。
如果 \(c_i = c_{i-1} = 1\) ，那麼可以推斷 \((a_{i},b_{i})\) 有三種組合：\((0,1),(1,0),(1,1)\) 。
如果 \(c_i = c_{i-1} = 0\) ，那麼可以推斷 \((a_{i},b_{i})\) 有三種組合：\((0,1),(1,0),(0,0)\) 。

進一步考慮 \(c\) ，其一定形如 101000....110011100|0 （從右往左）。假設有 \(m\) 個位置 \(c_i \neq c_{i-1},i\in [1,n]\) ，那麼可以歸納得出，有 \(m+1\) 個交替的連續 01 段。

其中，進位元欄（連續 1 段）有 \(\lfloor \frac{m+1}{2} \rfloor\) 個，不進位元欄（連續 0 段）有 \(\lceil \frac{m+1}{2} \rceil\) 個，有三種組合的自由位有 \(n-m\) 個。因此，我們隔板法求出 \(k\) 個進位分成 \(\lfloor \frac{m+1}{2} \rfloor\) 個連續段的方案數 \(C_{k-1}^{\lfloor \frac{m+1}{2} \rfloor - 1}\) 和剩下 \(n+1-k\) 個不進位分成 \(\lceil \frac{m+1}{2} \rceil\) 個連續段的方案數 \(C_{n+1-k-1}^{\lceil \frac{m+1}{2} \rceil - 1}\) ，以及求出自由位貢獻 \(3^{n-m}\) ，將三種方案乘法原理組合在一起就是有 \(m\) 個位置 \(c_i \neq c_{i-1},i\in [1,n]\) 的答案。

最後 \(m \in [0,n]\) 列舉一下求和即可。其中兩個隔板法的組合數要特判 \(C_{0-1}^{0-1}\) 的情況，這種情況設為 \(1\) ，其他不合法情況設為 \(0\) 。

時間複雜度 \(O(n \log n)\)

空間複雜度 \(O(n)\)

方法二

知識點：排列組合，數學。

方法二思維量更少一點。

我們直接討論 \(k\) 個進位連續段分成 \(i\) 個連續段的情況，以及顯然進位元欄和不進位元欄是交替的。

首先，會有 \(i\) 個位置必須設為 \((1,1)\) ，因為有 \(i\) 個進位元欄。其次，如果不進位元欄右側有進位元欄，則不進位元欄因為需要阻止進位元欄繼續進位，右端必須設為 \(0\) 。

我們需要分別考慮前導和後導是否是進位元欄的自由位情況。因為前導不進位時，\(i\) 個進位元欄左側都有不進位元欄，自由位有 \(n - 2i\) 個；前導進位時，只有 \(i-1\) 個進位元欄左側有不進位元欄，前導進位元欄左側天然是 \(0\) ，自由位有 \(n - 2i+1\) 個。

進一步，考慮四類段分配情況。以前導後導都不進位為例，則有 \(i\) 段進位元欄和 \(i+1\) 段不進位元欄，組合數求一下就行，其他以此類推。

時間複雜度 \(O(n \log n)\)

空間複雜度 \(O(n)\)

程式碼

方法一

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mod = 1e9 + 7;

int qpow(int a, int k) {
    int ans = 1;
    while (k) {
        if (k & 1) ans = 1LL * ans * a % mod;
        k >>= 1;
        a = 1LL * a * a % mod;
    }
    return ans;
}

int fact[1000007], factinv[1000007];
void init(int n) {
    fact[0] = 1;
    for (int i = 1;i <= n;i++) fact[i] = 1LL * i * fact[i - 1] % mod;
    factinv[n] = qpow(fact[n], mod - 2);
    for (int i = n;i >= 1;i--) factinv[i - 1] = 1LL * factinv[i] * i % mod;
}

int C(int n, int m) {
    if (n == m && m == -1) return 1;
    if (n < m || m < 0) return 0;
    return 1LL * fact[n] * factinv[n - m] % mod * factinv[m] % mod;
}

bool solve() {
    int n, k;
    cin >> n >> k;
    init(n);
    int ans = 0;
    for (int i = 0;i <= n;i++) {
        ans = (ans + 1LL * C(k - 1, (i + 1) / 2 - 1) * C(n + 1 - k - 1, (i + 2) / 2 - 1) % mod * qpow(3, n - i) % mod) % mod;
    }
    cout << ans << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

方法二

#include <bits/stdc++.h>
#define ll long long
 
using namespace std;
 
const int mod = 1e9 + 7;
 
int qpow(int a, int k) {
    int ans = 1;
    while (k) {
        if (k & 1) ans = 1LL * ans * a % mod;
        k >>= 1;
        a = 1LL * a * a % mod;
    }
    return ans;
}
 
int fact[1000007], factinv[1000007];
void init(int n) {
    fact[0] = 1;
    for (int i = 1;i <= n;i++) fact[i] = 1LL * i * fact[i - 1] % mod;
    factinv[n] = qpow(fact[n], mod - 2);
    for (int i = n;i >= 1;i--) factinv[i - 1] = 1LL * factinv[i] * i % mod;
}
 
int C(int n, int m) {
    if (n < m || m < 0) return 0;
    return 1LL * fact[n] * factinv[n - m] % mod * factinv[m] % mod;
}
 
bool solve() {
    int n, k;
    cin >> n >> k;
    if (k == 0) {
        cout << qpow(3, n) << '\n';
        return true;
    }
    init(n);
    int ans = 0;
    for (int i = 1;i <= k;i++) {
        if (n - 2 * i >= 0) {
            //前導不進位，後導不進位
            ans = (ans + 1LL * C(n - k - 1, i) * C(k - 1, i - 1) % mod * qpow(3, n - 2 * i) % mod) % mod;
            //前導不進位，後導進位
            ans = (ans + 1LL * C(n - k - 1, i - 1) * C(k - 1, i - 1) % mod * qpow(3, n - 2 * i) % mod) % mod;
        }
        if (n - 2 * i + 1 >= 0) {
            //前導進位，後導不進位
            ans = (ans + 1LL * C(n - k - 1, i - 1) * C(k - 1, i - 1) % mod * qpow(3, n - 2 * i + 1) % mod) % mod;
            //前導進位，後導進位
            ans = (ans + 1LL * C(n - k - 1, i - 2) * C(k - 1, i - 1) % mod * qpow(3, n - 2 * i + 1) % mod) % mod;
        }
    }
    cout << ans << '\n';
    return true;
}
 
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

Pinely Round 1 (Div. 1 + Div. 2)

A

題意

題解

程式碼

B

題意

題解

程式碼

C

題意

題解

程式碼

D

題意

題解

方法一

方法二

程式碼

方法一

方法二