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; }
- Regionals Contest Online 2022 ICPCregionals contest online 2022 regionals contest online 2023 regionals contest online mdielk regionals contest online string regionals游记contest online regionals contest online abefj regional contest 2022 icpc periodicity regionals contest problem regionals multiply contest problem 2022 icpc