NOIP2023前 随机题选做

……叫醒我吧。

---

因为考前大部分是集训，一直在考试，所以做题不会很多，能更多少更多少。

---

P9607 [CERC2019] Be Geeks!

题目简介

题目名称：

题目来源：

评测链接：https://www.luogu.com.cn/problem/P9607

形式化题意：定义 表示区间内所有数的 ， 表示区间最大值，求：

$$\sum_{l=1}^{n}\sum_{r=l}^{n}g(l,r)\cdot m(l,r)\bmod 10^9+7$$

数据范围：

不考虑 ，发现是一个特别经典的问题，对所有的 维护出其作为最大值的区间 ，那么 产生贡献的次数就是 ，而这个 可以通过单调栈来回一次解决。时间复杂度 。

那我们沿袭这个思路，对所有 求出：

$$\sum_{i\in[l_i,i]}\sum_{j\in[i,r_i]}g(i,j)$$

即是 作为最大值的贡献。

然后考虑上面这个形式非常复杂，也不是很好求，暴力 。

但是，考虑到 的性质，如果存在 个数，那么其任意组合 种方案的 中，至多存在 个值，这个结论与数的质因子个数为 相关。

那么我们将 中所有的 找出来，两两合并独立求解，这个过程是 的。

这个过程可以首先预处理出 的 表，然后通过倍增跳找到所有区间，这个过程也是 的。

至于从始至终都有一个 ，因为所有区间至少有一个端点是 ，这意味着这些 呈倍数关系，所以事实上很少触碰上界，数之间是递减的。

所以最后时间复杂度 。

事实上对于刚开始那个式子可以扫描线做，差分为 ，但是复杂度过高过不了。

AC Code

// ----- Eternally question-----
// Problem: P9607 [CERC2019] Be Geeks!
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9607
// Memory Limit: 128 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-10-31 19:42:10
// ----- 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){ std::cout<<x; }
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,MAXS=20;
const int Mod=1e9+7;
template<class T1,class T2>
inline void add(T1 &x,T2 y){ x=x+y>=Mod?x+y-Mod:x+y; }
const int Inf=0x3f3f3f3f;
int N,val[MAXN];
int Lst[MAXN],Rst[MAXN];
int Stk[MAXN],Top;
int Gc[MAXN][MAXS],Lg[MAXN];
inline int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }
inline void build()
{
	for(int i=2;i<=N;++i) Lg[i]=Lg[i>>1]+1;
	for(int i=1;i<=N;++i) Gc[i][0]=val[i];
	for(int s=1;(1<<s)<=N;++s)
		for(int i=1;i+(1<<s)-1<=N;++i)
			Gc[i][s]=gcd(Gc[i][s-1],Gc[i+(1<<(s-1))][s-1]);	
}
inline int getGcd(int l,int r)
{
	if(l>r) return 0;
	int lg=Lg[r-l+1];
	return gcd(Gc[l][lg],Gc[r-(1<<lg)+1][lg]);
}
struct Node
{
	int l,r,v;
	Node(int _l=0,int _r=0,int _v=0):l(_l),r(_r),v(_v){}
}Li[MAXN],Ri[MAXN];
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N);val[0]=val[N+1]=Inf;
	for(int i=1;i<=N;++i) read(val[i]);
	Stk[Top=1]=0;
	for(int i=1;i<=N;++i)
	{
		while(Top&&val[Stk[Top]]<val[i]) --Top;
		Lst[i]=Stk[Top]+1;
		Stk[++Top]=i;
	}
	Stk[Top=1]=N+1;
	for(int i=N;i>=1;--i)
	{
		while(Top&&val[Stk[Top]]<=val[i]) --Top;
		Rst[i]=Stk[Top]-1;
		Stk[++Top]=i;
	}
	// for(int i=1;i<=N;++i) write(Lst[i],' ',Rst[i],'\n');
	build();
	ll ans=0;
	for(int i=1;i<=N;++i)
	{
		int cntl=0,cntr=0;
		int pos=i,tar=val[i];
		// for(pos=i;pos>=Lst[i];--pos) Li[++cntl]=Node(pos,pos,getGcd(pos,i));
		while(pos>=Lst[i])
		{
			int nxt=pos;
			for(int s=19;~s;--s) if(pos-(1<<s)>=Lst[i]&&Gc[pos-(1<<s)][s]%tar==0) pos-=(1<<s);
			Li[++cntl]=Node(pos,nxt,tar);
			tar=gcd(tar,val[--pos]);
		}
		pos=i,tar=val[i];
		// for(pos=i;pos<=Rst[i];++pos) Ri[++cntr]=Node(pos,pos,getGcd(i,pos));
		while(pos<=Rst[i])
		{
			int nxt=pos;
			for(int s=19;~s;--s) if(pos+(1<<s)<=Rst[i]&&Gc[pos+1][s]%tar==0) pos+=(1<<s);
			Ri[++cntr]=Node(nxt,pos,tar);
			tar=gcd(tar,val[++pos]);
		}
		ll sum=0;
		for(int j=1;j<=cntl;++j)
			for(int k=1;k<=cntr;++k)
			{
				// printf("[%d,%d]-[%d,%d]-%d\n",Li[j].l,Li[j].r,Ri[k].l,Ri[k].r,gcd(Li[j].v,Ri[k].v));
				int lenl=Li[j].r-Li[j].l+1,lenr=Ri[k].r-Ri[k].l+1;
				add(sum,(ll)lenl*lenr%Mod*gcd(Li[j].v,Ri[k].v)%Mod);
			}
		add(ans,sum*val[i]%Mod);
	}
	write(ans);
	return 0;
}
/*

*/

---

P9836 种树

题目简介

题目名称： 种树

题目来源：

评测链接：https://www.luogu.com.cn/problem/P9836

题目简介：给定 个数 ，你可以对 乘上 ，要求 ，要求最大化：

$$\prod_{i=1}^{n}f\Big(a_i\times b_i\Big)$$

其中 表示 的正因子个数。

数据范围：

首先明确，设 ，那么有 。

我们考虑将 拆分成质因子来做，假设当前考虑 ，那么考虑 和 的关系。

设 包含了 个 。

那么乘上 后产生的贡献是 。所以我们考虑 的所有质因子，然后维护关于 的大根堆即可。

时间复杂度 。

---

另外一种思路是，质因子贡献独立，所以我们考虑直接枚举质因子计算，然后每次对 的质因子 ，这也可以通过大根堆维护，最后把没有统计的计算进去即可。

时间复杂度 。

AC Code

// ----- Eternally question-----
// Problem: P9836 种树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9836
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-11-12 18:15:57
// ----- 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=1e4+10,MAXV=1e2+10;
const int Mod=998244353;
int N;
ll W,P[MAXN],ans=1;
inline ll getSqrt(ll x)
{
	ll cnt=1;
	for(int i=2;i*i<=x;++i)
		if(x%i==0)
		{
			int cm=0;
			while(x%i==0) ++cm,x/=i;
			cnt=cnt*(cm+1)%Mod;
		}
	if(x>1) cnt=cnt*2%Mod;
	return cnt;
}
inline void solve(int x,int ct)
{
	std::priority_queue<int,std::vector<int>,std::greater<int>>Pq;
	for(int i=1;i<=N;++i)
	{
		int cnt=0;auto &tmp=P[i];
		while(tmp%x==0) ++cnt,tmp/=x;
		Pq.push(cnt+1);
	}
	while(ct--)
	{
		auto tmp=Pq.top();Pq.pop();
		Pq.push(tmp+1);
	}
	for(int i=1;i<=N;++i) ans=ans*Pq.top()%Mod,Pq.pop();
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,W);
	for(int i=1;i<=N;++i) read(P[i]);
	for(int i=2;i*i<=W;++i)
		if(W%i==0)
		{
			int cnt=0;
			while(W%i==0) ++cnt,W/=i;
			solve(i,cnt);
		}
	if(W>1) solve(W,1);
	for(int i=1;i<=N;++i) ans=ans*getSqrt(P[i])%Mod;
	write(ans);
	return 0;
}
/*

*/

---

P9837 汪了个汪

题目简介

题目名称： 汪了个汪

题目来源：

评测链接：https://www.luogu.com.cn/problem/P9837

形式化题意：给定一个 阶数字金字塔（第 行只有 个数的网格），要求构造出一组解满足：

• ；
• 两两不同；
• 任意 行不能出现相同的数；
• 对于任何横向相邻的无序数对（ 和 算一种，），只能出现至多一次。

保证有解。

数据范围：

非常好构造，爱来自欧埃。不会做，很巧妙。

你发现由 构成的无序二元组一共就 个，而这个 阶金字塔一共也会出现 个二元组，所以保证所有二元组一定会出现一次，也只会出现一次。

然后你发现 的二元组有 个，刚好可以填满第 层。

但是显然 不可能出现在同一层。

那我们是否可以将它们放置在同一列，甚至可以刚好满足 的限制。

所以，我们要求对于第 列，有 ，于是，以 为例，我们有：

$$\begin{align} \nonumber& 1\\ \nonumber& 2,1\\ \nonumber& 3,2,4\\ \nonumber& 4,3,5,2\\ \nonumber& 5,4,6,3,7\\ \nonumber& 6,5,7,4,8,3,9\\ \nonumber& 7,6,8,5,9,4,10 \end{align}$$

然后你发现超范围了，所以我们将 交换一下顺序：

$$\begin{align} \nonumber& 7\\ \nonumber& 1,2\\ \nonumber& 6,7,5\\ \nonumber& 2,3,1,4\\ \nonumber& 5,6,4,7,3\\ \nonumber& 3,4,2,5,1,6\\ \nonumber& 4,5,3,6,2,7,1\\ \end{align}$$

然后就完美了。时间复杂度 。

AC Code

// ----- Eternally question-----
// Problem: P9837 汪了个汪
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9837
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-11-12 19:30:52
// ----- 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=4e3+10;
int N,T;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,T);
	for(int i=1;i<=N;++i)
	{
		int x=i&1?N-(i>>1):i>>1;
		for(int j=1;j<=i;++j)
		{
			int len=(j>>1)*(j&1?-1:1);
			write(x+len,' ');
		}
		puts("");
	}
	return 0;
}
/*

*/

---

F. Hossam and Range Minimum Query

题目简介

给定一个长度为 的序列 ，一共 次询问，每次询问区间 中出现了奇数次的最小的数，无解为 。强制在线。

数据范围：

很经典的 ，异或随机值。

我们将 视作线段树结点，其权值随机，然后主席树二分即可，

时间复杂度 。

AC Code

// ----- Eternally question-----
// Problem: F. Hossam and Range Minimum Query
// Contest: Codeforces - Codeforces Round 837 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1771/F
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// Written by: Eternity
// Time: 2023-11-12 20:53:32
// ----- 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,S=1e9,a[MAXN];
std::map<int,ll>Hash;
std::mt19937 rnd((ll)new char);
struct PSegment_tree
{
	#define ls(p) Tr[p].lc
	#define rs(p) Tr[p].rc
	int Rt[MAXN],Idx;
	struct Segment
	{
		int lc,rc;
		ll val;
	}Tr[MAXN<<5];
	void modifyX(int &p,int l,int r,int x,ll v)
	{
		Tr[++Idx]=Tr[p];p=Idx;
		Tr[p].val^=v;
		if(l==r) return ;
		int mid=(l+r)>>1;
		x<=mid?modifyX(ls(p),l,mid,x,v):modifyX(rs(p),mid+1,r,x,v);
	}
	inline void insert(int id,int x,ll v)
	{
		Rt[id]=Rt[id-1];
		modifyX(Rt[id],1,S,x,v);
	}
	inline ll querySum(int pl,int pr,int l,int r)
	{
		if((Tr[pl].val^Tr[pr].val)==0) return Inf;
		if(l==r) return l;
		int mid=(l+r)>>1;
		if(Tr[ls(pl)].val^Tr[ls(pr)].val) return querySum(ls(pl),ls(pr),l,mid);
		return querySum(rs(pl),rs(pr),mid+1,r);
	}
	inline ll query(int l,int r){ return l>r?Inf:querySum(Rt[l-1],Rt[r],1,S); }
}Tr;
int lastans;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i)
	{
		read(a[i]);
		if(Hash.find(a[i])==Hash.end()) Hash[a[i]]=rnd();
		Tr.insert(i,a[i],Hash[a[i]]);
	}
	read(Q);
	for(int ql,qr;Q--;)
	{
		read(ql,qr);
		ql^=lastans,qr^=lastans;
		lastans=Tr.query(ql,qr);
		if(lastans==Inf) lastans=0;
		write(lastans,'\n');
	}
	return 0;
}
/*

*/

---