迟到30min没打，不过好像问题不是特别大

1348A Phoenix and Balance

二进制下非常明显

a.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        cout << (1 << n / 2 + 1) - 2 << endl;
    }
    return 0;
}

1348B Phoenix and Beauty

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

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int &i : a) cin >> i;
        sort(a.begin(), a.end());
        a.resize(unique(a.begin(), a.end()) - a.begin());
        if (a.size() > k) {
            cout << -1 << endl;
            continue;
        }
        while (a.size() < k)
            a.emplace_back(1);
        cout << k * n << endl;
        for (int i = 0; i < n; ++i) {
            for (int &j : a)
                cout << j << ' ';
        }
        cout << endl;
    }
    return 0;
}

1348C Phoenix and Distribution

就是个分类讨论，先排序，然后

  • 对于前$k$个字符，如果$s_k != s_0$，那么答案就是$s_k$；
  • 如果$s_k==s_0$
    • 对于后$n-k$个字符，如果$s_{k+1}==s_n$，也就是全部相同，均分是最优的；
    • 如果不全相同，那么应该全分给$a_k$，即$a_k=s_{k+1:n}$。
c.cpp
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
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        string s;
        int n, k;
        cin >> n >> k >> s;
        sort(s.begin(), s.end());
        string ans;
        if (s[k - 1] != s[0]) {
            ans = s[k - 1];
        } else {
            if (s[k] == s[n - 1]) {
                n = ceil(double(n) / k);
                cout << s[0];
                while (--n) ans.push_back(s[k]);
            } else {
                ans = s.substr(k - 1);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

1348D Phoenix and Science

题意转化一下，就是找到一个最短非递减序列，其中$a_{i+1}<=2a_i$，使$\sum a=k$。
转化好了就随便做了，我这里代码可能和上面说的实现的有点不一样，不过关键是这个思路吧。

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

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        int aans = 31 - __builtin_clz(n);
        vector<int> ans;
        --n;
        for (int i = 0, la = 1; i < aans; ++i) {
            int tp = min(1 << (i + 1), n / (aans - i));
            ans.emplace_back(tp - la);
            n -= tp;
            la = tp;
        }
        cout << aans << endl;
        for (int &i : ans)
            cout << i << ' ';
        cout << endl;
    }
    return 0;
}

1348E Phoenix and Berries

首先如果只能放同色的话，答案是$\frac {\sum a}k + \frac {\sum b}k$，剩下的数目一定在 $[0,2k-2]$ 内，那么如果答案再增加，一定是凑出某个树内的一个装两色的框。
现在设$dp[i][j]$表示前$i$个树，剩余$j$个红色没用，其他的全部用了的状态。如果 $j \ge k$ 的话，那么可以多加一个只装红色的筐，因此只考虑模$k$内的状态。
那么对于一棵树来说，他能剩的红色数量必定在 $min(k-1,a_i)$ 内，不过由于我们需要把其余红色全用掉，因此必须满足 $(a_i-l)\mod k+b_i \ge k$，$l$表示剩下没用红色的数量，然后就是像背包的$dp$，最终的答案由于剩余的红色全入框，等同蓝色，答案即。
这里由于状态直邮可不可行，可以用$bitset$让复杂度$/32$，$cf$上直接从$O(nk^2)$降到$O(nk)$了？？然后由于每次只从上一棵树的状态转移，还可以使用滚动数组优化空间。

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

int main() {
    int n, k;
    cin >> n >> k;
    ll suma = 0, sumb = 0;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        suma += a[i];
        sumb += b[i];
    }
    ll sum = suma + sumb;

    bitset<1024> dp(1), dp2;
    for (int i = 0; i < n; ++i) {
        dp2 = (dp << a[i] % k) | (dp >> (k - a[i] % k));
        for (int j = 0, ed = min(k - 1, a[i]); j <= ed; ++j)
            if ((a[i] - j) % k + b[i] >= k)
                dp2 |= (dp << j) | (dp >> (k - j));
        dp = dp2;
        dp2.reset();
    }
    ll ans = 0;
    for (int i = 0; i < k; ++i) {
        if (dp[i]) {
            ans = (sum - i) / k;
            break;
        }
    }
    cout << ans << endl;
}

1348F Phoenix and Memory

1