比赛链接：Dashboard - Codeforces Round 936 (Div. 2) - Codeforces

C

题意：给一棵有 $n$ 个节点的树，找到最大的 $x$ ，使得这棵树删去 $k$ 条边后剩下的每个联通块的大小至少为 $x$ 。

可以二分答案。

在每次check时，dfs统计以每个节点为根的子树大小，当以某个节点为根的子树大小大于等于 $x$ 时就删去这条边，同时将size清零，不影响父节点的儿子统计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> adj[100001]; 
int n, k;
int res;

int dfs(int x,int u,int fa)
{
    int sz=1;
    for(auto v:adj[u])
    {
        if(v==fa)continue;
        sz+=dfs(x,v,u);
    }
    if(sz>=x)
    {
        res++;
        sz=0;
    }
    return sz;
}

bool check(int x)
{
    res=0;
    dfs(x,1,0);
    if(res>k)return 1;
    else return 0;
}

int main() {
    int t;
    cin>>t;
    while(t--)
    {
        cin >> n >> k;
        for(int i=1;i<=n;i++)adj[i].clear();
        for (int i = 1; i < n; ++i) {
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        
        int l=1,r=n/(k+1)+1;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(check(mid))l=mid;
            else r=mid-1;
        }
        cout<<l<<endl;
    }
    
    return 0;
}

二分，bfs/dfs

D

题意：给出长度为 $n$ 的数组 $a$ ，求最大的 $k$ ，将数组分成 $k$ 个相连的区间，且满足：
$$
(a_{l_1}⊕a_{l_1+1}⊕…⊕a_{r_1})|(a_{l_2}⊕a_{l_2+1}⊕…⊕a_{r_2})|…|(a_{l_k}⊕a_{l_k+1}⊕…⊕a_{r_k})≤x
$$

将 $x$ 加1，现在使得这个值小于 $x$ 。按照每一位从高位到低位考虑：

  1. 先考虑数组中所有元素的这一位：
    • 若为0，则单独成为一个区间，不影响。
    • 若为1，则将其作为区间的开始，以下一个最近的1作为区间的结尾。
  2. 在考虑 $x $ 对应的这一位：
    • 若为1，若数组中出现的1为偶数，那么更新目前的ans。这一位的数组处理可以不做要求。
    • 若为0，若数组中出现的1为偶数，那么目前这是唯一的区间分法，更新数组；若出现的1为奇数，那么停止，输出ans（只有当 $x$ 为1且数组有偶数个1时才更新ans，这样保证后续的操作永远满足）。

有点头大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
   
#define int long long
    
void solve() 
{
    int n, x;
    cin >> n >> x;
    ++x;
    vector<int> a;
    for(int i=0;i<n;i++)
    {
        int tmp;
        cin>>tmp;
        a.push_back(tmp);
    }

    int res=-1;
    for(int i=30;i>=0;i--)
    {
        bool flag=0;
        vector<int>b;
        for(auto k:a)
        {
            if(flag==0)b.push_back(k);
            else b.back()^=k;

            if(k&(1<<i))
            {
                flag=!flag;
            }
        }

        if(!(x&(1<<i)))
        {
            if(flag)
            {
                cout<<res<<endl;
                return ;
            }
            a=b;
        }
        else
        {
            if(flag==0)
            {
                res=max(res,(int)b.size());
            }
        }

    }
    cout<<res<<endl;
}
    
signed main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)solve();
    return 0;
}

位运算

E

题意：给出一个 $k$ 排列的 $m_1$ 个前缀最大数的位置 $p_i$ 和 $m_2$ 个后缀最大数的位置 $s_i$ ，求排列 $k $ 的可能方案。

前缀最大数：$a_i$ 满足 $a_1<a_i,a_2<a_i,…,a_{i-1}<a_i$ 。

后缀最大数同理。

注意到前缀最大数和后缀最大数重合的位置就是最大的数的位置，么可以以此为中心把整个数组分成左右两部分分别讨论。

对于左部分，最后一个最大数的位置就是左边的所有数中最大的，又以此为中心分成两部分……

依次类推。

需要计算的就是：

  1. 第一次分成两类的方案数：$C^{s[1]-1}_{n-1}$
  2. 左边找出第一个中心后，中心到最大数之间的数的排列方案：$(p[m_2]-p[m_2-1]-1)!$
  3. ……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll mod = 1e9+7 ;

const int N = 2e5+23;

ll power(ll a, ll b)
{
    ll ans=1;
    a%=mod;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}

ll fact[N], inv[N];
int suff[N], pref[N], n, m1, m2;

ll C(ll r, ll n)
{
    if(r<0 || r>n) return 0;
    return fact[n]*inv[r]%mod*inv[n-r]%mod;
}

int main()
{
    fact[0]=1;
    for (int i=1; i<N; i++) fact[i]=fact[i-1]*i%mod;

    inv[N-1]=power(fact[N-1], mod-2);
    for (int i=N-2; i>=0; i--) inv[i]=inv[i+1]*(i+1)%mod;

    int T; cin>>T;
    while(T--)
    {
        cin>>n>>m1>>m2;
        for (int i=1; i<=m1; i++) cin>>pref[i];
        for (int i=1; i<=m2; i++) cin>>suff[i];
        if(pref[1]!=1 || suff[m2]!=n || pref[m1]!=suff[1])
        {
            cout<<0<<endl;
            continue;
        }
        ll ans=C(suff[1]-1, n-1);
        for (int i=1; i<m1; i++) ans=ans*C(pref[i]-1, pref[i+1]-2)%mod*fact[pref[i+1]-pref[i]-1]%mod;
        for (int i=2; i<=m2; i++) ans=ans*C(n-suff[i], n-suff[i-1]-1)%mod*fact[suff[i]-suff[i-1]-1]%mod;
        cout<<ans<<endl;
    }
    return 0;
}

分治