acwing148周赛
title: acwing148周赛
categories:
- ICPC
tags:
- null
abbrlink: 47a0ff1d
date: 2023-05-19 00:00:00
赛时困得睡着了
B题 https://www.acwing.com/problem/content/5562/
第二题赛事一直在想模拟加贪心,却发现非常难实现,我们需要转变思维,这时候一般有3种可能
双指针?二分?dp?
后来清醒了一点我们判断一个答案是不是合法很容易,我们再考虑答案求最大值,显然具有单调性,所以我们考虑二分答案,前缀和u优化判断
// Problem: 摆放棋子
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/5562/
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl "\n"
#define debug1(x) cerr<<x<<" "
#define debug2(x) cerr<<x<<endl
const int N = 3e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];
int s[N];
int k;
bool check(int mid){
for(int i=1;i+mid-1<=n;i++){
int r=i+mid-1;
//if(mid==4) cerr<<i<<" "<<r<<" "<<s[r]-s[i-1]<<endl;
if(mid-s[r]+s[i-1]<=k)return true;
}
return false;
}
void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
int l=0,r=n;
while(l<r){
//cerr<<l<<" "<<r<<endl;
int mid=(l+r+1)>>1;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<l<<endl;
for(int i=1;i+l-1<=n;i++){
int r=i+l-1;
if(l-s[r]+s[i-1]<=k){
for(int o=i;o<=r;o++)a[o]=1;
for(int j=1;j<=n;j++)cout<<a[j]<<" ";
return ;
}
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int t;
//cin>>t;
t=1;
while (t--) {
solve();
}
return 0;
}
C题是个不错的题,本题需要动态建树在线回答直径,似乎只能用倍增,不能其他方法,所以还是要全能。
考察直径的性质,从一次改变入手
前置
思路
定理:
- 边权非负时,树的直径求法:任选一个点 $a$,找到离它最远的点 $b$,再找到离 $b$ 最远的点 $c$,则 $b \sim c$ 是一条直径。
- 树上任意两点 $a, b$ 间距离 $dist(a, b) = depth(a) + depth(b) - 2 \times depth(lca(a, b))$,其中 $depth(x)$ 是 $x$ 到根的距离,$lca(a, b)$ 是 $a, b$ 两点的最近公共祖先。
性质:
若上一次树的直径是 $A \sim B$,现在要在 $u$ 下增加两个子节点 $x, y$,若直径变大,则新直径的一个端点必然是 $x$ 或 $y$。$x, y$ 等价,下面仅考虑 $x$。
- 若 $dist(A, B) < max(dist(A, x), dist(B, x))$,由于未添加节点前 $u$ 到任何节点的距离小于等于 $dist(A, B)$,因此 $x$ 到任何节点的距离最多比 $u$ 到任何节点的距离多 $1$,因此 $dist(A, x) \le dist(A, B) + 1$。不妨设此时 $dist(A, x) > dist(A, B)$,则 $dist(A, x) = dist(A, B) + 1$。由于 $x$ 到任何节点的距离不可能超过 $dist(A, B) + 1$,所以此刻 $A \sim x$ 是一条新直径。同理,若 $dist(B, x) > dist(A, B)$,$B \sim x$ 是一条新直径。
- 若 $dist(A, B) \ge max(dist(A, x), dist(B, x))$,则距离 $A$ 最远的点是 $B$,且距离 $B$ 最远的点是 $A$,因此 $A \sim B$ 仍是直径。
时间复杂度:$mlog(n)$,其中 $m$ 为询问次数,$n$ 为最大节点数。
debug:嵌套数组下标的中括号混乱,表示不仔细看根本看不出来
debug:数组开的大小应该是len+1,数组开小了,越界出发未定义行为
https://www.acwing.com/solution/content/236111/
参考题解
// Problem: 树的直径
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/5563/
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl "\n"
#define debug1(x) cerr<<x<<" "
#define debug2(x) cerr<<x<<endl
const int N = 1e6 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];
int len=__lg(N);
int fa[N][20];//绷数组越界出发ub
int dep[N];
//掌握直径的性质:两次dfs在正权树上求直径
//这道题对于每次新加进来的点都需要重新维护倍增信息,
// 首先是在线的,无法使用targan
// 树跑需要提前预处理dfs序,而动态建树会改变重儿子,所以无法预处理两次dfs
int lca(int x,int y){
//cerr<<"start"<<endl;
//cerr<<x<<" "<<y<<endl;
if(dep[x]<dep[y])swap(x,y);
for(int i=len;i>=0;i--){
//不要嵌套数组写,还是多创建变量
if(dep[fa[x][i]]>=dep[y]){
x=fa[x][i];
//cerr<<"y "<<y<<" "<<dep[y]<<endl;
//cerr<<"iter"<<" "<<i<<" "<<x<<" "<<dep[x]<<endl;
}
}
//cerr<<"samehigh"<<" "<<x<<" "<<y<<endl;
if(x==y)return x;
for(int i=len;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
//cerr<<x<<" "<<y<<endl;
x=fa[x][i];y=fa[y][i];
}
}
// cerr<<x<<" "<<y<<endl;
// cerr<<fa[x][0]<<endl;
// cerr<<"end"<<endl;
return fa[x][0];
}
int dis(int x,int y){
int mid=lca(x,y);
//cerr<<x<<" "<<y<<" "<<mid<<endl;
return dep[x]+dep[y]-2*dep[mid];
//cerr<<x<<" "<<y<<" <<mid<<endl;
}
void solve(){
//cout<<"len"<<" "<<len<<endl;
cin>>m;
n=4;
dep[1]=1;
for(int i=2;i<=4;i++){
fa[i][0]=1;
dep[i]=2;
}
int res1=2;int res2=3;
//动态维护树的直径两个端点
int ans=2;
while(m--){
int u;cin>>u;
int v1=++n;
int v2=++n;
//动态维护新加的点的求lca所需信息
dep[v1]=dep[u]+1;
dep[v2]=dep[u]+1;
fa[v1][0]=fa[v2][0]=u;
for(int i=1;i<=len;i++){
fa[v1][i]=fa[fa[v1][i-1]][i-1];
fa[v2][i]=fa[fa[v2][i-1]][i-1];
}
//cerr<<"fa[5][1]"<<" "<<fa[5][1]<<endl;
//cerr<<"fa[7][1]"<<" "<<fa[7][1]<<endl;
int dis1=dis(v1,res1);
int dis2=dis(v1,res2);
if(dis1>=dis2&&dis1>=ans){
ans=dis1;
res2=v1;
}
else if(dis2>=dis1&&dis2>=ans)
{ans=dis2;
res1=v1;
}
cout<<ans<<endl;
}
//for(int i=1;i<=n;i++)cerr<<i<<" "<<dep[i]<<" "<<endl;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int t;
//cin>>t;
t=1;
while (t--) {
solve();
}
return 0;
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!