acwing148周赛

赛时困得睡着了

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题是个不错的题，本题需要动态建树在线回答直径，似乎只能用倍增，不能其他方法，所以还是要全能。

考察直径的性质，从一次改变入手

前置

• 1072. 树的最长路径
• 1171. 距离

思路

定理：

1. 边权非负时，树的直径求法：任选一个点 $a$，找到离它最远的点 $b$，再找到离 $b$ 最远的点 $c$，则 $b \sim c$ 是一条直径。
2. 树上任意两点 $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$。

1. 若 $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$ 是一条新直径。
2. 若 $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;
}