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 )\) 的数量，我们只要倒着算答案就行
\[f_{i,j} = f_{i - 1, j - 1} + f_{i - 1, j + 1} \]\[res = f_{len, i} \times f_{n - m - len, i + \texttt{S 中 '('数量 - ')' 的数量}} \]其中满足 \(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;
}