ZROI - 2023csp七连测附加赛day1

掉大分。

A. 急急急

题目简介

给定一个长度为 的序列 ，每次操作你可以选择一个位置 ，将 折叠到 ，即：

$$\begin{align} a_{l+1}&\leftarrow\nonumber a_l+a_{l+1}\\ a_{l+2}&\leftarrow\nonumber a_{l-1}+a_{l+2}\\ &\cdots\nonumber\\ a_{2l}&\leftarrow\nonumber a_{1}+a_{2l} \end{align}$$

然后删除 。需要注意的是，你选择的 必须有 。

问是否能够将整个序列删除到只剩下一个数时，这个数是非负整数。多测。

数据范围：

仔细发现不管怎么叠 不变，所以当 时绝无可能。然后观察样例和限制发现 时也绝无可能。

所以我们考虑无解情况只有一种，就是当某一个数 足够小（为负数）且无法被之前的所有数消掉。

对比 和 ，对于第二种情况，我们前面就算一个一个叠叠成一个正数也无法抵消 ，所以无解。

所以无解情况为存在一个 使得 。

---

B. 绷绷绷

题目简介

给定 个弹簧，第 个长度为 ，满足 。一共 次询问，每次询问区间 。

在第 时刻时，所有弹簧被松弛，会逐渐伸长。在第 时刻时，第 个弹簧在 时刻满足 时则会长度 。每次询问的 不会有任何变化。

每次询问独立，求 在第几个时刻伸长到 。

数据范围：

首先考虑单询问，我们记录 表示第 个位置伸长到 的时间，有递推式：

$$f_i=\max\{a_r-a_i,f_{i+1}+1\}$$

但如果存在右端点为 的相等连续段时，我们需要将其全部舍弃只保留最小，设为 。

然后我们拆贡献，得到：

$$\begin{align} f_i&=\nonumber\max\{a_r-a_i,\max\{a_r-a_{i-1},f_{i+2}+1\}+1\}\\ &=\nonumber \max\{a_r-a_i,a_r-(a_{i+1}-1),\max\{a_r-a_{i+2},f_{i+3}+1\}+2\}\\ &=\nonumber\cdots\\ &=\nonumber \max_{j=i}^{r'}\{ a_r-a_j+(j-i) \}\\ &=\nonumber b_r-i+\max_{j=i}^{r'}\{j-b_j\} \end{align}$$

后面这个部分显然可以用线段树维护区间最大值，然后就结束了。

时间复杂度 。

AC Code

// ----- Eternally question-----
// Problem: B. [2023CSP七连 附加赛1] 绷绷绷
// Contest: ZROI - 23csp7连测附加赛1
// URL: http://zhengruioi.com/contest/1457/problem/2693
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-04 08:23:05
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10;
const int Inf=0x3f3f3f3f;
int N,Q,val[MAXN];
#define ls (p<<1)
#define rs (p<<1|1)
struct Segment
{ int l,r,val; }Tr[MAXN<<2];
inline void pushUp(int p)
{ Tr[p].val=std::max(Tr[ls].val,Tr[rs].val); }
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r;
	if(l==r) return Tr[p].val=l-val[l],void();
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
int queryMax(int p,int l,int r)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
	int mid=(Tr[p].l+Tr[p].r)>>1,res=-Inf;
	if(l<=mid) checkMax(res,queryMax(ls,l,r));
	if(mid<r) checkMax(res,queryMax(rs,l,r));
	return res;
}
inline int get(int sl,int sr)
{
	int l=sl,r=sr,res=r;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(val[mid]==val[sr]) res=mid,r=mid-1;
		else l=mid+1;
	}
	return res;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(val[i]);
	build(1,1,N);
	read(Q);
	for(int ql,qr;Q--;)
	{
		read(ql,qr);qr=get(ql,qr);
		if(ql==qr) puts("0");
		else write(val[qr]-ql+queryMax(1,ql,qr),'\n');
	}
	return 0;
}
/*

*/

---

C. 乐乐乐

题目简介

给定一个包含了 所有整数的集合 ，然后指定 个数 ，将 从 中删去。

然后执行若干次操作，每次取出 中的两个元素，满足 ，其中 为任意非负整数，并将 删去。

求最多能执行多少次操作。

数据范围：

首先考虑最简单的形式，即 ，那么所有数都能够形成一棵满二叉树。而我们发现可以配对 ，最后只会剩下 一个数，最多能匹配 次。

然后扩展到 为任意数。这道题里我们当然没有办法将完全二叉树拆分成 棵满二叉树，因为子树并不合法。

这里我们设 ，那么这棵树少了 的结点，那么 就无法被配对。然后你发现这就是个 的子问题，所以我们直接递归处理。

时间复杂度 。

---

然后考虑 的限制。但我们依然考虑优先匹配叶结点，然后将 归于子问题，进行递归，所以我们只需要处理 被删除的结点的贡献。

如果这个点不是叶结点，那其匹配的叶结点就无法匹配，所以答案 ；但如果这个点是叶结点，那么与之匹配的父亲就会空出来，我们设空出的结点的集合为 。

对于 ，首先考虑其是否能够自匹配，也就是匹配到 中去，那么连边后会形成森林结构，贪心是正确的。否则，我们将其与其在 中的父亲匹配，并将这些父亲视作被删除的结点。

然后搞个哈希之类的维护一下，滚动一下数组，时间复杂度 或 。

AC Code

// ----- Eternally question-----
// Problem: #2694. [2023CSP七连 附加赛1] 乐乐乐
// Contest: 
// URL: http://zhengruioi.com/problem/2694
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-04 16:37:03
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define clz(x) __builtin_clzll(x)
const int MAXM=1e5+10;
int M,Id;
ull N,Pos[2][MAXM],Rt[MAXM],tmp[MAXM],ans;
bool Vis[MAXM];
std::unordered_map<ull,int>Hash,Bck;
std::vector<int>Edges[MAXM];
inline ull get(ull x){ return 1ull<<(64-clz(x)); }
void dfsTr(int x)
{
	bool ok=0;Vis[x]=0;
	for(int v:Edges[x]) dfsTr(v),ok|=(!Vis[v]);
	if(ok) Vis[x]=1,++ans;
}
void solve(ull x,int op,int len)
{
	if(x<=2) return ;
	if(x<=5000){ int ccc=x;while(ccc--); }
	int cnt=0,lcnt=0,rcnt=0;
	Bck.clear();
	ull bt=get(x),nx=bt-(x+1);
	ans+=x-(bt>>1);
	for(int i=1;i<=len;++i)
	{
		if(Pos[op][i]>=bt-Pos[op][i])
		{
			if(Hash.find(bt-Pos[op][i])==Hash.end())
				tmp[++cnt]=bt-Pos[op][i],Bck[bt-Pos[op][i]]=cnt,--ans;
		}
		else if(Pos[op][i]>nx) --ans;
		else Pos[op^1][++lcnt]=Pos[op][i];
	}
	for(int i=1;i<=cnt;++i) std::vector<int>().swap(Edges[i]);
	for(int i=1;i<=cnt;++i)
	{
		ull val=get(tmp[i])-tmp[i];
		if(val==tmp[i]||val<=nx){ Rt[++rcnt]=i;continue; }
		if((Id=Bck[val])) Edges[Id].push_back(i);
		else Rt[++rcnt]=i;
	}
	for(int i=1;i<=rcnt;++i)
		if(dfsTr(Rt[i]),!Vis[Rt[i]])
		{
			ull val=get(tmp[Rt[i]])-tmp[Rt[i]];
			if(val<=nx&&Hash.find(val)==Hash.end())
				Pos[op^1][++lcnt]=val,Hash[val]=1,++ans;
		}
	solve(nx,op^1,lcnt);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M);
	for(int i=1;i<=M;++i) read(Pos[0][i]),Hash[Pos[0][i]]=1;
	solve(N,0,M);
	write(ans);
	return 0;
}
/*

*/

---