11.24 周日

codeforces
Q1. 1100 给定01字符串a,b,长度n,n-1，遍历b每次任意选择a中a[i]!=a[i+1],将a[i]a[i+1]替换为b[i],长度减一，问是否能完成n-1次操作。
Q2. 1300 给定n，是否能构造出长度为n的序列，其中每个元素出现>1次且任意相同元素的距离为平方数。
Q3. 1500 给定一棵以1为根的树，可进行任意次操作：选择有子节点的节点p,w[p]++,子树的每个元素w--。问根节点的最大值。

A1. 17min A2. 10min-24min A3. 30min-38min
A1. 结论：发现b[i]每次操作会减少a中(b[i]-'0')^1的数量，故操作时只需要判断是否为0即可。
A2. 构造：n为偶数一定可以：11223344...，n为奇数时需要一个数出现3次即可，即需要满足：d1,d2,d1+d2均为平方数。
               观察平方数发现：1 4 9 16 25 (9+16=25) 故构造前缀：1, 2, 2, 3, 3, 4, 4, 5, 5, 1, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 13, 12, 12, 1, 13。
A3. 树形dp：设min为子树的最小值，如果min>w[u],dp[u]=w[u]+min>>1，否则dp[u]=w[u]; 除此之外如果u==1，dp[1]=w[1]+min;

牛客周赛 Round 69
B. long long格式化输入%d wa一发
C. 空间反射
D. 爆搜 读错题意调一个小时 dfs/数位状压 爆搜每个子方案选不选，判断是否冲突，记录最优方案。
QE. 给定一数组，将其分为3个连续子数组，每个子数组和相等并至少有一个正数，求方案数。
AE. ...

A1.

#include <bits/stdc++.h>
// #define int long long //
#define endl '\n' //
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
const int mod = 998244353;
const int N = 10 + 5e5;
void _();
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        _();
    return 0;
}

//  17min
void _()
{
    int n;
    cin >> n;
    string a;
    string b;
    cin >> a >> b;
    int cnt_a[2] = {};
    for (auto v : a)
        cnt_a[v - '0']++;
    int f = 1;
    if (!cnt_a[0] || !cnt_a[1])
        f = 0;
    else
    {
        for (int i = 0; i < b.size() - 1; i++)
        {
            auto v = b[i];
            int t = (v - '0') ^ 1;
            cnt_a[t]--;
            if (!cnt_a[t])
                f = 0;
        }
    }
    cout << (f ? "YES" : "NO") << endl;
}

A2.

#include <bits/stdc++.h>
// #define int long long //
#define endl '\n' //
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
const int mod = 998244353;
const int N = 10 + 5e5;
void _();
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        _();
    return 0;
}

//  10min 24min
void _()
{
    int n;
    cin >> n;
    if (n & 1 && n < 27)
    {
        cout << -1 << endl;
        return;
    }

    if (n & 1)
    {
        vector<int> res{0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 1, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 13, 12, 12, 1, 13};
        for (int i = 28; i <= n; i++)
            res.push_back(i >> 1);
        for (int i = 1; i <= n; i++)
            cout << res[i] << ' ';
    }
    else
        for (int i = 1; i <= n >> 1; i++)
            cout << i << ' ' << i << ' ';
    cout << endl;
}

A3.

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

//  30min  38min
void _()
{
    int n;
    cin >> n;
    vector<int> w(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    vector<vector<int>> e(n + 1);
    for (int i = 2; i <= n; i++)
    {
        int p;
        cin >> p;
        e[p].push_back(i);
    }
    function<int(int)> dp = [&](int u)
    {
        int min_w = 1e18;
        int res = w[u];
        for (auto v : e[u])
            min_w = min(min_w, dp(v));
        if (min_w == (int)1e18)
            return res; // leaf
        if (u == 1)
            return res + min_w;
        if (res < min_w)
            res = res + min_w >> 1;
        else
            res = min_w;
        return res;
    };
    cout << dp(1) << endl;
}