第一次进前50，上分最爽的一次
D. Speedbreaker
对\(a\)按照时间升序排序，不难发现，对于升序排序后的数组，当我们搜到时间\(t\)时，记录已经搜过的时间对应原城市编号最小值为\(l\)，最大值为\(r\)，则我们一定要在\(a_t\)时间之前走过所有\([l,r]\)之间的城市。
则若\(r-l+1 > a_t\)则无解，因为不能在\(t\)内走过\([l,r]\)之间的所有城市
否则，可能的合法城市只会出现在\([r-t+1,l+t-1]\)之间
总的合法城市为所有合法城市的并集，此处可以用前缀和处理
时间复杂度\(O(nlogn)\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+50;
const int M = 2e5+50;
const ll mod = 1e9+7;
#define pll pair<ll,ll>
#define pii pair<int,int>
#define eps 1e-8
const ll inf = 1e18;
#define ls (p<<1)
#define rs ((p<<1)+1)
#define mi (l+r)/2
const double DINF = 12345678910 , PI = acos(-1);
int mx[] = {0,0,1,-1} , my[] = {1,-1,0,0};
void YES(){
cout << "YES\n";
return;
}
void NO(){
cout << "NO\n";
return;
}
int n;
pii a[N];
int pre[N];
void solve(){
cin >> n;
for (int i = 1 ; i <= n ; ++i){
pre[i] = 0;
cin >> a[i].first;
a[i].second = i;
}
sort(a+1,a+1+n);
int l = n+1 , r = 0;
for (int i = 1 ; i <= n ; ++i){
l = min(a[i].second,l);
r = max(a[i].second , r);
if (r-l+1 > a[i].first){
cout << "0\n";
return;
}
int left = r-a[i].first+1 , right = l+a[i].first-1;
left = max(left , 1);
right = min(right , n);
pre[left]++;
pre[right+1]--;
}
int tmp = 0 , ans = 0;
for (int i = 1 ; i <= n ; ++i){
// cout << pre[i] << " ";
tmp += pre[i];
ans += (tmp == n);
}
cout << ans << "\n";
}
int main(){
ios::sync_with_stdio(0) , cin.tie(0);
// init();
int t;
cin >> t;
for (int i = 1 ; i <= t ; ++i){
solve();
}
// solve();
}
E. Tree Pruning
一个结论：若答案为\(d\)，则我们要将深度大于 \(d\) 的所有节点砍掉，对于最深深度小于 \(d\) 的子树砍掉
记答案为\(d\)时，需要砍掉 \(a_d\) 个节点，子树\(v\)的大小为 \(sz_v\)
考虑在树上，当我们搜索到节点 \(u\) ，若 \(u\) 目前搜索过的子树最深深度为\(d_u\)，则当搜索完其一棵新的子树，并对当前节点进行更新，
若子树最深深度 \(d_v \leq d_u\)，则对于答案在区间 \([d_v+1,d_u]\) 之间时，需要砍掉这整棵子树，即 $a_{d_v+1},a_{d_v+2}...,a_{d_u} $需要加上 \(sz_v\)
若 \(d_v > d_u\) ，则对于答案在区间 \([d_u+1,d_v]\) 之间时，需要砍掉之前搜索过的子树，即加上已搜索的子树大小 \(sz_u\)
当一个节点\(u\)搜索结束后，得到对于\(a_d\)的贡献为其所有子树大小之和
容易发现，所有修改都是连续区间，可以使用前缀和维护
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5+50;
const int M = 2e5+50;
const ll mod = 1e9+7;
#define pll pair<ll,ll>
#define pii pair<int,int>
#define eps 1e-8
const ll inf = 1e18;
#define ls (p<<1)
#define rs ((p<<1)+1)
#define mi (l+r)/2
const double DINF = 12345678910 , PI = acos(-1);
int mx[] = {0,0,1,-1} , my[] = {1,-1,0,0};
void YES(){
cout << "YES\n";
return;
}
void NO(){
cout << "NO\n";
return;
}
int head[N];
int tot;
bool vi[N];
struct edge
{
int to , nxt , w;
}e[N*2];
void add(int u , int v , ll w = 0){
e[++tot] = (edge){v , head[u] , w};
head[u] = tot;
}
int n;
int pre[N];
int dep[N];
int sz[N];
int depest[N];
int maxn = 0;
void dfs(int u , int fa){
bool fg = 0;
sz[u] = 0;
dep[u] = dep[fa]+1;
maxn = max(maxn , dep[u]);
depest[u] = dep[u];
for (int i = head[u] ; i ; i = e[i].nxt){
int v = e[i].to;
if (v == fa) continue;
fg = 1;
dfs(v,u);
if (depest[u] != dep[u]){
if (depest[u] < depest[v]){
pre[depest[u]+1] += sz[u];
pre[depest[v]+1] -= sz[u];
depest[u] = depest[v];
}
else{
pre[depest[v]+1] += sz[v];
pre[depest[u]+1] -= sz[v];
}
}
else{
depest[u] = depest[v];
}
sz[u] += sz[v];
}
pre[dep[u]] += sz[u];
pre[dep[u]+1] -= sz[u];
sz[u]++;
}
void solve(){
cin >> n;
tot = 0;
maxn = 0;
for (int i = 1 ; i <= n ; ++i){
head[i] = 0;
pre[i] = 0;
}
for (int i = 1 ; i < n ; ++i){
int u , v;
cin >> u >> v;
add(u,v) , add(v,u);
}
dfs(1,0);
int minn = n*10 , tmp = 0;
for (int i = 1 ; i <= maxn ; ++i){
tmp += pre[i];
// cout << i << "*" << tmp << "\n";
minn = min(minn,tmp);
}
cout << minn << "\n";
}
int main(){
ios::sync_with_stdio(0) , cin.tie(0);
// init();
int t;
cin >> t;
for (int i = 1 ; i <= t ; ++i){
solve();
}
// solve();
}