A. Social Experiment

题目链接

题意

有n个人分成若干组，每个组只能是2或3个人，每个组可以选择两个实验的其中一个，求两个实验的人数差最少是多少

分析

  • 当n<=3时，只能分成一组，所以人数差只能是n

  • 当n>3时，如果n为偶数，那么必定可以使人数相等，输出0即可；如果n为奇数时，先把n-1个人分成相等的两份，多出来的一个一定可以融入某一方(2+1=3,3+1=2+2)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve() {
    int n;
    cin>>n;
    if(n==2 || n==3){
        cout<<n<<endl;
        return;
    }
    if(n%2==0){
        cout<<0<<endl;
        return;
    }
    else{
        cout<<1<<endl;
        return;
    }
}

B. Hourglass

题目链接

题意

一个沙漏漏完需要s分钟，每隔k分钟就翻转一次，问m分钟之后还要过几分钟沙漏才能漏完。

分析

  • 如果s>k
    • 考虑第一次翻转，将要反转的时候，沙漏上面还剩s-k，下面有k，翻转之后k变成了上面,即接下来漏完的时间是k；
    • 考虑第二次翻转，将要反转的时候，沙漏上面剩了0，下面是s，翻转后又回到了初始阶段。
  • 如果k>=s
    • 考虑第一次翻转，将要翻转的时候，沙漏上面剩了0，下面是k，反转之后回到了初始值

综上，只要知道在m这段时间内翻转了几次和在最后一次翻转之后又经过了多少时间到m就可以算出来了
我们假设在最后一次翻转后又经过了res分钟到m
如果翻转次数是奇数次的话那么还要漏min(s,k)-res才能漏完，当然答案不能小于0
如果翻转次数是偶数次，也就是说最后一次翻转之后等同于初始情况下开始漏，所以只要s-res才能漏完，答案也不能小于零

代码

1
2
3
4
5
6
7
8
9
10
11
12
void solve() {
    int s,k,m;
    cin>>s>>k>>m;
    int cs=m/k;
    int res=m%k;
    if(cs%2==1){
        cout<<max(0,min(s,k)-res)<<endl;
    }
    else{
        cout<<max(0,s-res)<<endl;
    }
}

-

C. Huge Pile

题目链接

题意

有一堆数量为n的苹果，可以对一堆数量为x苹果对半分成两堆一堆为$ \lfloor \frac{x}{2} \rfloor $ ，另一堆为$ \lceil \frac{x}{2} \rceil $问最少要分几次才能出现一堆为k的苹果堆

分析

在二进制中，对半分意味着对这个数进行：

  • 向下取整：x=x>>1
  • 向上取整：x=(x>>1)+(x&1)
    设i为分的次数
  • 如果某个i正好使(n>>i)==k，则答案是i
  • 如果某个i正好使(n>>i)+1==k并且n%(1<<i)!=0(这句表示在这之前出现过1,如果没出现过1的话也就加不了1)

代码

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
void solve() {
    ll n, k;
    cin >> n >> k;
    if (k > n) {
        cout << -1 << endl;
        return;
    }
    for (int i = 0; i <= 31; i++) {
        ll p = 1ll << i; 
        ll q = n / p;
        ll rem = n % p;
        if (q + 1 == k) {
            if (rem > 0) {
                cout << i << endl;
                return;
            }
        }
        if (q == k) {
            if (p - rem > 0) {
                cout << i << endl;
                return;
            }
        }
        if (q + 1 < k) {
            break;
        }
    }
 
    cout << -1 << endl;
}

D. Unfair Game

题目链接

题意

鲍勃在1到n中想一个数x，爱丽丝需要对x进行如下操作知道x变为0

  • 如果x为奇数，爱丽丝只能使x=x-1
  • 如果x为偶数，爱丽丝可以使x=x-1 或 x=x/2
    设爱丽丝使x变为0的最少操作次数为c
    问1到n中有几个x的c能满足c>k
    输入的n一定是2的幂次

分析

考虑x的二进制数，举个简单的例子，比如10，其二进制数为1010
爱丽丝可以选择-1或/2发现/2相当于-5，明显比-1更优所以爱丽丝的最优解肯定是偶数/2 奇数-1
如果2进制的末尾为0，/2操作相当于消除末尾的0，即变成101
现在末尾为1，只能-1，二进制数变为100
再/2消除了1位,变成了10
可以发现，除了首位的1需要一次操作外，后面的0需要1次操作消除，1需要2次操作消除
因为最高位必定需要一次操作才能消除，所以我们可以先对k–
设i为二进制数除最高位外的位数数量，那消除这个数的基础次数就是i了，我们需要找次数大于k的数量，所以我们至少还需要（k-i+1）个1，当然k-i+1不能大于i也不能小于0，设p为至少还要1的个数，那么答案就是

$$ \sum_{i=1}^{len} \sum_{j=p}^{i} C_i^j $$

组合数的话，直接求会爆ll，可以先预处理一下，我赛时用的是杨辉三角的预处理

代码

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
#include"bits/stdc++.h"
#define ll long long
#define maxn 200005
#define endl '\n'
using namespace std;
const int mod=1e9+7;
ll c[40][40];

void solve() {
    int n,k;
    cin>>n>>k;
    int len=0;
    ll ans=0;
    while(n){
        len++;
        n=n/2;
    }
    if(len>k){
        ans++;
    }
    k--;
    len-=2;
    
    for(int i=1;i<=len;i++){
        int p=max(-1,k-i);
        for(int j=p+1;j<=i;j++){
            ans+=c[i][j];
        }
    }

    cout<<ans<<endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    for (int i = 0; i <= 32; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
    }
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E. Exquisite Array

题目链接

题意

给你一个排序，问你对于1到n-1的每个k，求有多少个子数组的任意相邻两个数的差值大于等于k

分析

因为只要考虑相邻的差值，所以我们可以单独把差值拿出来加入数组中，然后只要找数组元素大于k的值
可以发现如果一个连续的区间都满足条件，设这个区间的长度为len，那么它对答案的贡献是（len+1）*len/2
我们的目的就是找满足条件的连续区间的贡献的和
我们把k从大到小考虑，因为k越来越小，数组就越“连通”，我们可以先把每个元素出现的位置记录下来，遍历到k时就开始遍历元素大小是k的位置，判断前后是否需要连通，如果要连通的话，先减去左右两边的贡献再加上连通后的新贡献。要连通上去自然而然就想到了并查集。

代码

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include"bits/stdc++.h"
#define ll long long
#define maxn 200005
#define endl '\n'
using namespace std;

int n, p[maxn];
int f[maxn], sz[maxn];
bool vis[maxn];
vector<int> pos[maxn];
ll res[maxn];

int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}

ll cal(int x) {
    return 1ll * x * (x + 1) / 2;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        pos[i].clear();
        vis[i] = 0;
        f[i] = i;
        sz[i] = 1;
    }
    
    for (int i = 1; i < n; i++) {
        int diff = abs(p[i] - p[i + 1]);
        pos[diff].push_back(i);
    }

    ll cur = 0;
    for (int k = n - 1; k >= 1; k--) {
        for (auto x : pos[k]) {
            vis[x] = 1;
            cur += 1;
            
            if (x > 1 && vis[x - 1]) {
                int u = find(x - 1);
                int v = find(x);
                if (u != v) {
                    cur -= cal(sz[u]);
                    cur -= cal(sz[v]);
                    f[u] = v;
                    sz[v] += sz[u];
                    cur += cal(sz[v]);
                }
            }
            if (x < n - 1 && vis[x + 1]) {
                int u = find(x);
                int v = find(x + 1);
                if (u != v) {
                    cur -= cal(sz[u]);
                    cur -= cal(sz[v]);
                    f[v] = u;
                    sz[u] += sz[v];
                    cur += cal(sz[u]);
                }
            }
        }
        res[k] = cur;
    }

    for (int i = 1; i < n; i++){
        cout << res[i] << " \n"[i == n - 1];
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F. Cherry Tree

题意

给你一棵根为1的树，能否找到x个子树满足以下条件：

  • 这x个子树要包含所有叶子节点
  • x是3的倍数
  • 子树之间不能有重叠
    如果能找到则输出yes，否则输出no

分析

考虑dp，$ dp[v][k] (k=0,1,2) $表示以v为根的子树在模3的意义下能否用k个子树覆盖所有以v为根的子树的叶子

  • 初始状态：$dp[v][1]=true$因为可以直接选择v
  • 转移：看自己的儿子节点的各种可能加起来能否等于k

最后判断$ dp[1][0] $是否是true，如果是则输出yes，否则输出no

代码

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
65
66
67
#include"bits/stdc++.h"
#define ll long long
#define maxn 200005
#define endl '\n'
using namespace std;
vector<int>vt[maxn];
int dp[maxn][3];
int n;
void dfs(int v,int fa){
    dp[v][1]=1;
    vector<int>flag={1,0,0};
    for(auto it:vt[v]){
        if(it==fa){
            continue;
        }
        dfs(it,v);
        vector<int>p={0,0,0};
        for(int i=0;i<3;i++){
            if(flag[i]==1){
                for(int j=0;j<3;j++){
                    if(dp[it][j]==1){
                        p[(i+j)%3]=1;
                    }
                }
            }
        }
        for(int i=0;i<3;i++){
            flag[i]=p[i];
        }
    }
    if(vt[v].size()!=1 || v==1){
        for(int i=0;i<3;i++){
            dp[v][i]=flag[i];
        }
        dp[v][1]=1;
    }
}
void solve() {
    
    cin>>n;
    for(int i=1;i<=n;i++){
        vt[i].clear();
        dp[i][0]=dp[i][1]=dp[i][2]=0;
    }
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        vt[u].push_back(v);
        vt[v].push_back(u);
    }
    dfs(1,0);
    if(dp[1][0]==1){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}