情况

时间：2024年7月16日22:35
image.png
复健场，被A题当头棒喝···吐了。

题解

A

题意

对一个多重集合（可以有重复数字的集合）。刚开始只有一个数n，之后可以去掉任意一个数，增加不超过k个数，使得这些数和为n。求让这个多重集合都为1的最小操作数。

思路

一次最多可以拆下来k-1个1，然后总值为n,拆到最后一个1就少一次操作。因此是(n-1)/(k-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
31
32
33
void solve()
{
    int n, k;
    cin >> n >> k;
    if (n == 1)
    {
        cout << 0 << endl;
        return;
    }
    if (n <= k)
    {
        cout << 1 << endl;
        return;
    }

    int arr[N];
    arr[0] = n;
    int ans = 0;
    int pnt = 0;
    while (pnt < n-1)
    {
        int temp = arr[pnt];
        int i = 0;
        for (; i < temp-1 && i < k-1; i++, pnt++)
        {
            arr[pnt] = 1;
        }
        arr[pnt] = temp - k+1;
        ans++;
    }
cout<<ans<<endl;
return;
}

数学

用ceil上取整

1
2
3
4
5
6
7
8
9
void solve()
{
    int n, k;
    cin >> n >> k;
    int ans = ceil((double)(n-1)/(k-1));

    cout << ans << endl;
    return;
}

用分式上取整

1
2
3
4
5
6
7
8
9
void solve()
{
    int n, k;
    cin >> n >> k;
    int ans = (n - 1 + k - 2) / (k - 1);

    cout << ans << endl;
    return;
}

问题

刚开始非得去想如何拆成平均一点的数，数学想不出来。然后只能模拟。还有，上取整!不是在后面加1。可以写a/b + (b-1)/b，也就是 (a+b-1)/b

B

题意

01序列，你可以对一个区间的数进行替换：
如果这个区间0的个数大于等于1的个数，换成0；否则换成1
能否得到[1]？

思路

先把0全部缩成一个0，再看1多还是0多。

代码

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
void solve()
{
    int t;
    cin >> t;
    char temp;
    int cnt1 = 0, cnt0 = 0;
    char last = 1;
    for(int i = 0;i < t;++i)
    {
        cin >> temp;
        if(temp == '1')
           {
               cnt1++;
               if(last == '0'){
                   cnt0++;
               }
               last = '1';
           }else {
               last = '0';
               continue;
           }
        
    }
    if(last == '0')
        cnt0++;
        if(cnt0 >= cnt1)
            cout << "No" << endl;
            else cout << "Yes" << endl;
}

C

题意

一个正整数n。找到一个最长正整数序列，满足
1.都小于等于n
2.严格递增
3.相邻两数按位或=n

思路

观察发现答案位数只与二进值有多少个1，也就是popcount有关。遍历输出去掉每一位1的情况。

代码

jiangly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve()
{
    LL n;
    cin >> n;

    int c = __builtin_popcountll(n);
    if (c == 1)
    {
        std::cout << 1 << "\n";
        std::cout << n << "\n";
    }
    else
    {
        std::cout << c + 1 << "\n";
        for (int i = 59; i >= 0; i--)
        {
            if (n >> i & 1)
            {
                std::cout << (n ^ (1LL << i)) << " ";
            }
        }
        std::cout << n << "\n";
    }
}

zcf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve()
{
    int n;
    cin >> n;
    vector<int> ans;
    ans.push_back(n);
    for (int i = 0; (1ll << i) <= n; i++)
    {
        if (n >> i & 1)
        {
            if (n - (1ll << i) != 0)
                ans.push_back(n - (1ll << i));
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << "\n";
    for (auto it : ans)
        cout << it << " ";
    cout << "\n";
}

杂交版

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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

void solve()
{
    LL n;
    cin >> n;
    int lengthx = __builtin_popcountll(n);
    if (lengthx == 1)
    {
        cout << 1 << "\n";
        cout << n << "\n";
        return;
    }
    cout << lengthx + 1 << endl;
    for (int i = 60; i >= 0; i--)
    {
        LL temp;
        if (n >> i & 1)
        {
            temp = n - (1ll << i);

            cout << temp << " ";
        }
    }
    cout << n << endl;

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

问题

首先for循环开头是遍历最高位到最低位。不要瞎搞，刚开始补错还一直是=lengthx
然后，关于i从哪个数开始，为什么是60、59？题目范围是10的18次方，即二进制的18/3*10
最后： 为什么减号和按位异或^都可以？

1
2
temp = n - (1ll << i);
temp = n ^ (1ll << i);

减号就是去掉一个2的i次方，
按位异或，因为前面已经限制这个位上必须是1才if，因此也只有两种结果：1^1 = 0（相当于减去了),其他位都是1不动。

D

图没学，看jiangly代码学一些语法细节：

jiangly

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
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 inf = 1E18;

void solve()
{
    int n;
    std::cin >> n;

    std::vector<i64> a(n);
    for (int i = 0; i < n; i++)
    {
        std::cin >> a[i];
    }

    std::vector<std::vector<int>> adj(n);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    std::vector<i64> f(n, inf), g(n, inf);
    std::vector<int> r(n);
    auto dfs = [&](auto self, int x, int p) -> void
    {
        int d = 0;
        for (auto y : adj[x])
        {
            if (y == p)
            {
                continue;
            }
            d++;
            self(self, y, x);
        }

        std::vector<i64> val(d + 2);
        i64 sum = 0;
        for (auto y : adj[x])
        {
            if (y == p)
            {
                continue;
            }
            sum += f[y];
            if (r[y] < d + 2)
            {
                val[r[y]] += g[y] - f[y];
            }
        }
        for (int i = 0; i < d + 2; i++)
        {
            i64 res = sum + val[i] + (i + 1) * a[x];
            if (res < f[x])
            {
                g[x] = f[x];
                f[x] = res;
                r[x] = i;
            }
            else if (res < g[x])
            {
                g[x] = res;
            }
        }
    };
    dfs(dfs, 0, -1);

    std::cout << f[0] << "\n";
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--)
    {
        solve();
    }

    return 0;
}

邻接表写法：

1
2
3
4
5
6
7
8
9
10
std::vector<std::vector<int>> adj(n);
  for (int i = 1; i < n; i++)
  {
      int u, v;
      std::cin >> u >> v;
      u--;
      v--;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }

注意是二维数组

dfs lambda写法来遍历树，x是当前，p是父节点
用y==p防止死循环。

val存的某个子节点隔一个后的和。
d是子节点数量。
f[x]最小值。
g[x]次优解
res=:

  • sum 表示如果不击杀当前节点 x，其所有子树的最小健康值减少量。
  • val[i] 表示如果我们选择击杀 i + 1 个子节点（包括当前节点），那么这些子节点的额外贡献。
  • (i + 1) * a[x] 表示在这一轮选择击杀 i + 1 个子节点时，这些节点对健康值减少的贡献。

将这三部分加在一起，我们得到了在当前轮次选择击杀 i + 1 个子节点时的总健康值减少量。这个总减少量是我们需要最小化的目标，因此我们通过遍历所有可能的 i 值来找到最小的 res。

zcf

用了很多函数来简化操作，应该是模板一类的。

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pll pair<int, int>

const int N = 3e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;

struct edges
{
    int to;
    int before;
} e[N * 2];

int cnt, last[N];
int p[N];

void add(int u, int v)
{
    e[++cnt].to = v;
    e[cnt].before = last[u];
    last[u] = cnt;
}
const int K = 25;
int f[N][K + 1];

void dfs_f(int u, int fa)
{
    for (int i = 1; i <= K; i++)
        f[u][i] = p[u] * i;
    for (int i = last[u]; i; i = e[i].before)
    {
        int v = e[i].to;
        if (v == fa)
            continue;
        dfs_f(v, u);
        for (int j = 1; j <= K; j++)
        {
            int res = INF;
            for (int k = 1; k <= K; k++)
                if (k != j)
                    res = min(res, f[v][k]);
            f[u][j] += res;
        }
    }
}

void init(int n)
{
    cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= K; j++)
            f[i][j] = 0;
        last[i] = 0;
    }
}

void solve()
{
    int n;
    cin >> n;
    init(n);
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
        sum += p[i];
    }
    int de[n + 1] = {};
    for (int i = 1, u, v; i <= n - 1; i++)
    {
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs_f(1, 0);
    int ans = INF;
    for (int i = 1; i <= K; i++)
        ans = min(ans, f[1][i]);
    cout << ans << "\n";
}

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