2023/8/9~2023/8/11 做题

Codeforces Round 121 (Div. 1) C. Fools and Roads

树形dp + LCA

先预处理LCA，将边下放到点处理， 对于每个路径在其 \(u\) ， \(v\)， \(lca\) 处分别打个标记，树形dp合并即可

const int N = 2e5 + 10;
const int LOGN = 20;

int n;
vector<int> e[N];
int id[N], cnt, dep[N], fa[N][LOGN + 2], val[N];
int res[N];
map<pair<int, int>, int> mp;

void lca_init()
{
    for(int j = 1; j <= LOGN; j++)
        for(int i = 1; i <= n; i++)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int lca_query(int u, int v)
{
    if(dep[u] < dep[v])   swap(u, v);
    int d = dep[u] - dep[v];
    for(int j = LOGN; j >= 0; j--)
        if(d & (1 << j))
            u = fa[u][j];
    if(u == v)    return u;
    for(int j = LOGN; j >= 0; j--)
        if(fa[u][j] != fa[v][j])
            u = fa[u][j],v = fa[v][j];
    return fa[u][0];
}

void dfs(int u, int from)
{
    dep[u] += dep[from] + 1;
    for(auto v : e[u])
    {
        if(v == from)   continue;
        id[v] = mp[{u, v}];
        fa[v][0] = u;
        dfs(v, u);
    }
}

void dfs2(int u, int from)
{
    for(auto v : e[u])
    {
        if(v == from)   continue;
        dfs2(v, u);
        val[u] = val[u] + val[v];
    }
    res[id[u]] = val[u];
}

void solve()
{       
    cin>>n;
    for(int i = 1; i < n; i++)
    {
        int u, v;   cin>>u>>v;
        mp[{u, v}] = ++cnt;
        mp[{v, u}] = cnt;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    lca_init();
    int q;  cin>>q;
    while(q--)
    {
        int u, v;   cin>>u>>v;
        int lca = lca_query(u, v);
        val[u]++, val[v]++, val[lca] -= 2;
    }

    // for(int i = 1; i <= n; i++) 
    //     cout<<id[i]<<"  ";
    // cout<<'\n';
    // for(int i = 1; i <= n; i++) 
    //     cout<<val[i]<<"  ";
    // cout<<'\n';

    dfs2(1, 0);
    for(int i = 1; i < n; i++)
        cout<<res[i]<<" ";
    cout<<'\n';
    return;
}

Codeforces Round 343 (Div. 2) C. Famil Door and Brackets

dp

定义状态 \(f_{i,j}\) ，为有 \(i\) 长度的字符串，其 \(j\) 为 \((\) 的数量 - \()\) 的数量，其中找出 \(S\) 串中 \((\) 的数量 - \()\) 的最小值 \(miv\)， 其 \(P\) 的\((\) 的数量 - \()\) 的数量 \(\geq miv\)，其 \(Q\) 中受到 \(P\) 和 \(S\) 的限制，\((\) 的数量 \(\geq )\) 的数量，我们只要倒着算答案就行

其中满足 \(i + \texttt{S 中 前缀'('数量 - 前缀')' 的最小值} \geq 0 \&\& i + \texttt{S 中 '('数量 - ')' 的数量} \leq n - m - len\) 的条件

int n, m;
int f[N][N], g[N][N];
string s;
void solve()
{       
    cin>>n>>m>>s;
    int cnt = 0, miv = 1e9;
    for(auto it : s)
    {
        if(it == '(')   cnt++;
        else cnt--;
        miv = min(cnt, miv);
    }
    f[0][0] = 1;
    for(int i = 1; i <= N - 10; i++)
    {
        f[i][0] = f[i - 1][1];
        for(int j = 1; j <= i; j++)
            f[i][j] = (f[i - 1][j - 1] + f[i - 1][j + 1]) % mod;
    }
    ll res = 0;
    for(int len = 0; len <= n - m; len++)
    {
        for(int i = 0; i <= len; i++)
        {
            if(i + miv >= 0 && i + cnt <= n - m - len)
            {
                //cout<<len<<"    "<<i<<"    "<<f[len][i]<<"   "<<f[n - m - len][i + cnt]<<'\n';
                res = (res + 1ll * f[len][i] * f[n - m - len][i + cnt]) % mod;
            }
        }
    }
    cout<<res<<'\n';
    return;
}

Codeforces Round 880 (Div. 1) A. k-th equality

在数位要求下，找到等式的第 \(k\) 小字典序

直接跑暴力

注意到题面 Each input file has at most $ 5 $ test cases which do not satisfy $ A, B, C \leq 3 $ .就是我们可以跑暴力的依据

穷举数字 \(a\) ，根据 \(c\) 的上下界确定 \(b\) 的上下界即可

ll qpow(ll base, ll r)
{
    int res = 1;
    while(r--)
        res = res * base;
    return res;
}

void solve()
{       
    ll a, b, c, k; cin>>a>>b>>c>>k;
    ll down1 = qpow(10, a - 1), up1 = qpow(10, a) - 1;
    ll down2 = qpow(10, b - 1), up2 = qpow(10, b) - 1;
    ll down3 = qpow(10, c - 1), up3 = qpow(10, c) - 1;
    ll d = 0;
    for(ll i = down1; i <= up1; i++)
    {
        ll miv = down3 - i;
        ll mav = up3 - i;
        ll l1 = max(miv, down2);
        ll r1 = min(mav, up2);
        d += max(0ll, (r1 - l1 + 1));
        if(d >= k)
        {
            d -= (r1 - l1 + 1);
            d = k - d;
            cout<<i<<" + "<<l1 + d - 1<<" = "<<i + l1 + d - 1<<'\n';
            return;
        }
    }   
    cout<<-1<<'\n';
    return;
}