• A Two Permutations
• B Elimination of a Ring
• C Set Construction
• D Carry Bit
• E Make It Connected
• F1 ~ G 不会

A - Two Permutations

题意

是否存在两个长度为 $n$ 的排列, 是的其最长公共前缀和最长公共后缀长度分别为为给定的 $a$, $b$

题解

若 $a+b+2\le n$, 则可以构造

$$\begin{array}{rl}A& =\{1,2,\cdots ,a,n-b,a+1,a+2,\cdots ,n-b-1,n-b+1,n-b+2,\cdots ,n\}\\ B& =\{1,2,\cdots ,a,a+1,a+2,\cdots ,n-b-1,n-b,n-b+1,n-b+2,\cdots ,n\}\end{array}$$

否则当且仅当 $a=b=n$ 是存在满足条件的排列(两排列相等)

代码

signed main(){
    fastio();
    int T;
    cin>>T;
    while(T--){
        int n, a, b;
        cin>>n>>a>>b;
        if(n-a-b>1||(a==n&&b==n)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

B - Elimination of a Ring

题意

环上消消乐, 每次操作在环上删去一个数, 然后自动消消乐, 求删去全部元素的最大操作次数.

题解

显然, 当环上元素种类等于 $2$ 时, 答案为 $\frac{n}{2}+1$, 否则就是 $n$.

代码

constexpr int N = 1005;
int a[N];

signed main()
{
    fastio();
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        Fe(i, 1, n) cin >> a[i];
        if (n == 1)
            cout << 1 << endl;
        else if (n == 2)
            cout << 2 << endl;
        else
        {
            bool flag = 0;
            for (int i = 3; i <= n; i++)
            {
                if (a[i - 2] != a[i])
                {
                    flag = 1;
                    cout << n << endl;
                    break;
                }
            }
            if (!flag)
                cout << n / 2 + 1 << endl;
        }
    }
    return 0;
}

C - Set Construction

题意

构造一些集合, 使得它们满足给定的每两个集合间是否真包含的要求.

题解

诈骗题, 可以直接图论跑, 也可以特殊构造.

考虑矩阵 $b$ 全为 $0$ 作为初始状态, 可以发现, $A_i=\{i\}$ 可以满足这个矩阵的要求.

然后逐个向 $b$ 中加入 $1$, 当 $b_{i,j}=1$ 时, 可以把 $A_i$ 的全部元素加入 $A_j$, 即可满足条件.

最终就可以得到答案, 可以证明这样的构造一定合法.

可以使用 set 直接模拟上述做法.

代码

constexpr int N = 105;
int a[N][N];
set<int> s[N];
inline void solve()
{
    int n;
    cin >> n;
    Fe(i, 1, n) s[i].clear();
    Fe(i, 1, n)
    {
        char c;
        Fe(j, 1, n)
        {
            cin >> c;
            a[i][j] = c - '0';
        }
    }
    Fe(i, 1, n) s[i].insert(i);
    Fe(i, 1, n)
        Fe(j, 1, n)
            if (a[i][j] == 1)
                for (auto k : s[i])
                    s[j].insert(k);
    Fe(i, 1, n)
    {
        cout << s[i].size() << ' ';
        for (auto k : s[i]) cout << k << ' ';
        cout << endl;
    }
}

---

D - Carry Bit

题意

求 $a$, $b$ 两二进制数加法进位的值等于 $k$ 的数对个数.

题解

枚举段数

有两种可能

第一种是 $00$ 开头, 将 $k$ 个$11$分成 $x$ 段, 除了每段首尾固定的 $00$ 和 $11$ 外, 其他位置有三种可能( 在段中间有$01$, $11$, $10$ 不在段中有 $00$, $01$, $10$ )因此有 $3^{n-2x}$. 接下来, 选择$11$的位置, 已知有 $x$ 段, 我们只要在其他 $n-k$ 个不进位的位置进行插入, 由于 $00$ 左侧不能插入, 故选择可能性有 $\mathrm{C}(k-x,x)$. 再将这 $k$ 个 $11$ 分成 $x$ 段, 利用组合数有 $\mathrm{C}(k-1,x-1)$可能. 所以当 $n$ 大于等于 $2x$ 的时候 有 $3^{n-2x}\times \mathrm{C}(k-x,x)\times \mathrm{C}(k-1,x-1)$ 种可能.

第二种是 ($10$, $11$, $01$) 开头, 由于($10$, $11$, $01$) 开头, 第一段不用固定 $00$, 所以除了固定$11$和$00$外, 有可能性 $3^{n-2x+1}$. 选择插入位置, 由于第一段位置固定, 选择$n-k$个位置由于第一段在第一个不进位位置左侧故只需要在$n-k$个位置选择$x-1$个位置进行插入, 有 $\mathrm{C}(n-k,x-1)$ . 再将这 $k$ 个进位分成 $x$ 段有 $\mathrm{C}(k-1,x-1)$ . 所以当 $n$ 大于等于 $2x-1$ 的时候, 有可能性 $3^{n-2x+1}\times \mathrm{C}(n-k,x-1)\times \mathrm{C}(k-1,x-1)$

Attention: 快速幂实现时不要溢出

代码

constexpr int N = 1000005, mod = 1000000007;
int n,k,pw[N],prd[N],inv[N];

int pow(int x) {
    if (x < 0)
        return 0;
    return pw[x];
}

int C(int n, int m) {
    if (n < m)
        return 0;
    return (ll)prd[n] * inv[m] % mod * inv[n - m] % mod;
}

int qpow(ll b, ll p) {
    ll res = 1;
    while (p) {
        if (p & 1)
            res = res * b % mod;
        b = b * b % mod;
        p >>= 1;
    }
    return res % mod;
}

signed main() {
    fastio();
    cin >> n >> k;
    pw[0] = prd[0] = 1;
    Fe(i, 1, n) pw[i] = 3ll * pw[i - 1] % mod;
    if (!k) {
        cout<<pw[n]<<endl;
        return 0;
    }
    Fe(i, 1, n) prd[i] = (ll)prd[i - 1] * i % mod;
    inv[n] = qpow(prd[n], mod - 2);
    for (int i = n - 1; ~i; --i)
        inv[i] = (ll)inv[i + 1] * (i + 1) % mod;
    ll ans = 0;
    Fe(i, 1, k) {
        ans += (ll)C(k - 1, i - 1) * C(n + 1 - k - 1, i) % mod *
               pow(n - 2 * i) % mod;
        ans += (ll)C(k - 1, i - 1) * C(n + 1 - k - 1, i - 1) % mod *
               pow(n - 2 * i + 1) % mod;
    }
    cout << ans % mod << endl;
    return 0;
}

E - Make It Connected

题意

有一张无向图, 你可以操作任意次, 每次选定一个点 $u$, 将连接 $u$ 的变为不连接, 不连接的变为连接, 问最少操作次数.

官方题解

First of all, we need to check if the graph is already connected at the beginning. If so, the answer would be 0.

Otherwise, there will be more than $1$ connected component. If there exists a vertex that is the only vertex required to be operated to make the graph connected, we call such a vertex "feasible vertex". We may find out that a feasible vertex can only appear in a connected component that is not a clique.

But actually, there will always be such a vertex in a non-clique component. To prove this, we may figure out the sufficient condition for being a feasible vertex first.

The sufficient condition is that, if a vertex is not a cut vertex, and it is not adjacent to all other vertices in the connected component, then it must be a feasible vertex. We can prove that such a vertex always exists in a non-clique component. Here is the proof:

• Firstly, if there exist vertices that are adjacent to all other vertices in the component, we erase all of them.

Apparently, the remaining component would still be a non-clique component. Otherwise, the component could only be a clique from the beginning, which contradicts the premise.

• Then, we will find a non-cut vertex in the remaining component, since that vertices in a graph couldn't be all cut vertices. The non-cut vertex we found is the vertex we are searching for.

But implementing it directly (meaning using Tarjan's algorithm to find a non-cut vertex) might not be the easiest way to solve the problem. Actually, there are two other ways we have found so far to solve the problem alternatively. The first one is that we can simply output the vertex with the least degree in a connected component; the other one is that we can do DFS in a connected component and output the last visited vertex (as long as the connected component is not a clique). We would like to leave the proof work of these two alternative ways to you.

Now we have proven that, if there exists a connected component that is not a clique, then the answer would be at most $1$ . What if all connected components are cliques?

If there are exactly $2$ connected components, then apparently we will have to operate on all vertices in a connected component. So we'll choose the smaller connected component to operate, and the answer is exactly the size of it.

Otherwise, we can arbitrarily choose two vertices from two different connected components and operate on them. The answer is $2$ .

Note that we also need to deal with isolated vertices (meaning vertices that are not adjacent to any other vertices) separately.

可以通过找到所有点中度数最小的点找到一个非完全图连通块中的合法操作点.

代码

constexpr int N = 4005;
int n;
int deg[N];
int fa[N];
int c[N];
vector<int> v[N];
vector<int> cv;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void solve()
{
    cin >> n;
    Fe(i, 1, n) fa[i] = i, c[i] = 0, deg[i] = 0;
    Fe(i, 1, n) Fe(j, 1, n)
    {
        char o;
        cin >> o;
        if (o == '1')
        {
            int x = find(i), y = find(j);
            if (x != y)
                c[y] += c[x], fa[x] = y;
            c[find(j)]++;
            deg[i]++;
        }
    }
    cv.clear();
    Fe(i, 1, n) v[i].clear();
    Fe(i, 1, n) v[find(i)].pb(i);
    Fe(i, 1, n) if (fa[i] == i) cv.pb(i);
    if (cv.size() == 1)
    {
        cout << 0 << endl;
        return;
    }
    Fe(i, 1, n) if (fa[i] == i)
    {
        if (deg[i] == 0 || c[i] != v[i].size() * (v[i].size() - 1))
        {
            int p = 0;
            for (int u : v[i])
                if (!p || deg[u] < deg[p])
                    p = u;
            cout << "1\n"
                 << p << endl;
            return;
        }
    }
    if (cv.size() > 2)
    {
        cout << "2\n"
             << v[cv[0]].back() << ' ' << v[cv[1]].back() << endl;
        return;
    }

    if (v[cv[0]].size() > v[cv[1]].size())
        swap(cv[0], cv[1]);
    cout << (int)v[cv[0]].size() << endl;
    for (int u : v[cv[0]])
        cout << u << ' ';
    cout << "\n";
}