红包接龙

ll ans=-1e18,n,lst,a[(int)1e5+9];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    map<ll,ll> res;
    cin>>n;
    f(i,1,n)cin>>a[i];
    for(int i=1;i<n;++i){
    	res[a[i]]-=i,res[a[i+1]]+=i;
    }
    for(auto [aa,bb]:res)ans=max(ans,bb);
    cout<<ans;
    return 0;
}

最后一班

ll n;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    if(n==0){
    	cout<<"0\n";
    	return 0;
    }
    ll l=0,r=1e5;
    while(l<r){
    	ll mid=(l+r+1)>>1;
    	if(mid*(mid+1)/2<n)l=mid;
    	else r=mid-1;
    }
    cout<<l+1<<"\n";
    return 0;
}

勇者兔

ll ans,n,w;
pii a[(int)1e5+9]; 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>w;
    for(int i=1,x,y;i<=n;++i)cin>>x>>a[i].first>>y>>a[i].second;
    sort(a+1,a+1+n,[](pii aa,pii bb){return aa.first==bb.first?aa.second<bb.second:aa.first<bb.first;});
	//for(int i=1;i<=n;++i)cout<<a[i].first<<"::"<<a[i].second<<"\n";
	ll l=1,r=1,mx;
	while(r<=n){
		l=r,r=l+1,ans+=1,mx=a[l].second;
		//cerr<<l<<"::"<<r<<"\n";
		while(r<=n&&a[r].first-mx<w)mx=min(mx,a[r].second),r+=1;
		if(r>n)break;
		//cerr<<l<<"::"<<r<<"\n";
	}
	cout<<ans;
    return 0;
}

兔兔爱消除

ll n,ans;
map<int,vector<pii>> v; 

struct dsu{
	vi fa,sz;
	dsu(int n){
		fa.resize(n+1),sz.resize(n+1);
		for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;
	}
	int fnd(int x){
		return fa[x]==x?x:fa[x]=fnd(fa[x]);
	}
	bool merge(int x ,int y){
		int oa=fnd(x),ob=fnd(y);
		if(oa!=ob){
			fa[ob]=oa,sz[oa]+=sz[ob];
			return true;
		}
		return false;
	}
};

int id(int x,int y){
	return (x-1)*n+y;
}

ll solve(vector<pii> e){
	dsu d(60*60);
	ll sz=e.size(),res=0;
	vector<array<ll,3>> tmp;
	for(int i=0;i<sz;++i){
		for(int j=i+1;j<sz;++j){
			tmp.push_back({abs(e[i].first-e[j].first)+abs(e[i].second-e[j].second),id(e[i].first,e[i].second),id(e[j].first,e[j].second)});
		}
	}
	sort(all(tmp),[](array<ll,3> aa,array<ll,3> bb){return aa[0]>bb[0];});
	for(auto [aa,bb,cc]:tmp){
		if(d.merge(bb,cc))res+=aa;
	}
	return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1,x;i<=n;++i){
    	for(int j=1;j<=n;++j){
    		cin>>x;
    		v[x].push_back({i,j});
    	}
    }
    for(auto [_,aa]:v)ans+=solve(aa);
    cout<<ans;
    return 0;
}

吃席兔

ll cx[(int)1e5+9],n,cnt,tar;
vi g[(int)1e5+9]; 
bitset<(int)1e5+9> vis;

bool dfs(int u,int fa,int ok){
	//if(u==3){\
		cerr<<fa<<"--->"<<ok<<"\n";\
	}
	int rs=0,sons=0;
	if(cx[u]&&fa!=0)ok=1,rs=1;
	if(ok)vis[u]=1;
	for(auto it:g[u])sons+=cx[it]&&it!=fa;
	//if(sons)cerr<<u<<"::"<<sons<<"---\n";
	for(auto it:g[u]){
		if(it==fa)continue;
		if(sons>1)rs|=dfs(it,u,1);
		else if(sons==1&&cx[it]==0)rs|=dfs(it,u,1);
		else rs|=dfs(it,u,ok);
	}
	return rs;
}
vi qsb;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    f(i,1,n)cin>>cx[i],cnt+=cx[i];
    if(cnt==0){
    	for(int i=1;i<=n;++i)cout<<0<<" \n"[i==n];
    	return 0;
    }

    for(int i=1,x,y;i<n;++i){
    	cin>>x>>y;
    	g[x].push_back(y),g[y].push_back(x);
    }
    for(int i=1;i<=n;++i){
    	if(cx[i]==1){
    		qsb.push_back(i);
    		tar=i;
    		vis[i]=1;
    		for(auto it:g[i]){
    			vis[it]=1;
    		}
    	}
    }
    dfs(tar,0,0);
    dfs(qsb[0],0,0);
    dfs(qsb.back(),0,0);
    for(int i=1;i<=n;++i)cout<<vis[i]<<" \n"[i==n];
    	return 0;
    return 0;
}