The 2022 ICPC Asia Regionals Online Contest (I)
C
统计度的大小,算贡献,特判 \(n = 1\)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
int n, d[N];
vector<int> e[N];
ll res = 0;
void dfs(int u, int from)
{
int cnt = 0;
for(auto v : e[u])
{
if(v == from) continue;
cnt++;
dfs(v, u);
}
if(u != 1)
res = res + max(cnt - 1, 0);
}
void solve()
{
res = 0;
cin>>n;
if(n == 1)
{
cout<<1<<'\n';
return;
}
for(int i = 1; i <= n; i++)
{
d[i] = 0;
e[i].clear();
}
for(int i = 1; i <= n - 1; i++)
{
int u, v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
d[u]++, d[v]++;
}
dfs(1, 0);
res += 2;
if(d[1] >= 2)
res += (d[1] - 2);
cout<<res<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tc; cin>>tc;
while(tc--)
solve();
}
L
动态规划
预处理所有不合法情况
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
typedef long long ll;
int n, m, res;
int a[N], b[N], f[N][27], g[N][27];
string s, t;
bool st[N][27], vis[27];
void solve()
{
cin>>s>>t;
n = s.size(), m = t.size();
s = "?" + s, t = "?" + t;
for(int i = 1; i <= n; i++)
a[i] = s[i] - 'a' + 1;
for(int i = m; i >= 1; i--)
{
b[i] = t[i] - 'a' + 1;
for(int j = 1; j <= 26; j++)
if(vis[j]) st[b[i]][j] = true;
vis[b[i]] = true;
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= 26; j++)
f[i][j] = f[i - 1][j] + (vis[a[i]] == false), res = max(f[i][j], res);
if(vis[a[i]] == false) continue;
f[i][a[i]] = max(1, f[i][a[i]]);
res = max(f[i][a[i]], res);
for(int j = 1; j <= 26; j++)
if(st[j][a[i]] == false)
f[i][a[i]] = max(f[i - 1][j] + 1, f[i][a[i]]),
res = max(f[i][a[i]], res);
}
cout<<res<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
}
A
观察得:
-
一团大小为\(k\) 的 \(1\) 可以删掉 \(\dfrac{k}{2} + k \% 2\)
-
对于 \(1,1,0,\dots,0,1,1\), 首尾的 \(1\) 会相互影响,但对于记录一下其前后缀就可以得出首尾的 一团 \(1\) 的大小
-
那么预处理出删的次数即可
const int N = 1e6 + 10; int n, q, pre[N], suf[N], f[N], cnt; string s; void solve() { cin>>n>>q; cin>>s; s = "?" + s; for(int i = 1; i <= n; i++) { if(s[i] == '1') cnt++; else cnt = 0; pre[i] = cnt; f[i] = f[i - cnt - 1] + (cnt / 2 + cnt % 2); } cnt = 0; for(int i = n; i >= 1; i--) { if(s[i] == '1') cnt++; else cnt = 0; suf[i] = cnt; } for(int i = 1; i <= q; i++) { int l, r; cin>>l>>r; int tl = l + suf[l], tr = r - pre[r]; if(suf[l] == 0 && pre[r] != 0) tl++; if(pre[r] == 0 && suf[l] != 0) tr--; int t = suf[l] + pre[r]; t = t / 2 + t % 2; int add = 0; if(tl <= tr) add = f[tr] - f[tl - 1]; int res = (r - l + 1) / 3 - t - add; res = max(0, res); cout<<res<<'\n'; } return; }