个人题解：A~E

（尝试了一下ai解释自己的代码，发现比自己解释的都好）

A题：

按题意直接输出即可

void solved()
{
	int n;cin>>n;
	cout<<n-max(n-114514-19260817,1)+1;
}

B题：

简单博弈：因为双方都要最优，所以都只选最大的一个即可（选多了可能会使平均数或中位数变小）（k1,k2无用）

先预处理出前缀最值和后缀最值，再枚举分割点进行前缀最值与后缀最值比较即可，存在前缀最值>相应后缀最值即输出“Yes”，不存在则输出“No”

void solved()
{
	int n,k1,k2;cin>>n>>k1>>k2;
	vector<int> a(n+2),ma1(n+2),ma2(n+2);
	for(int i=1;i<=n;i++)cin>>a[i];
	
	//预处理前缀最大值 
	for(int i=1;i<=n;i++)ma1[i]=max(ma1[i-1],a[i]);
	
	//预处理后缀最大值
	for(int i=n;i>=1;i--)ma2[i]=max(ma2[i+1],a[i]);
	
	int ok=0;
	for(int i=1;i<=n-1;i++)//枚举分割点
		if(ma1[i]>ma2[i+1])ok=1;
		
	cout<<(ok?"Yes":"No")<<'\n';
}

C题：并查集

并查集的作用

区间合并：
- 使用并查集维护未玩过的猪猪区间。
- 每次操作 1 遍历 [l, r] 时，跳过已经玩过的猪猪（通过并查集快速找到下一个未玩过的猪猪）。
- 玩过的猪猪会与右边的区间合并，表示它们已经被跳过。
路径压缩：
- 通过路径压缩优化并查集的查找效率，确保每次查找的时间复杂度接近 O(1)。
记录顺序：
- 使用数组 vis 记录每只猪猪被玩的顺序。

代码核心逻辑

初始化：
- 并查集 p 初始化为每个猪猪独自为一个集合。
- vis 数组记录每只猪猪被玩的顺序，初始为 0。
操作 1：
- 遍历 [l, r]，跳过已玩过的猪猪（通过 find(i) 找到下一个未玩过的猪猪）。
- 标记当前猪猪为已玩过，并记录顺序 cnt。
- 合并当前猪猪与右边相邻的区间，表示它们已经被跳过。
操作 2：
- 直接输出 vis[x]，表示猪猪 x 被玩的顺序。

时间复杂度

操作 1：均摊复杂度接近 O(1)（路径压缩优化）。
操作 2：直接查询 vis[x]，复杂度 O(1)。
总复杂度：O(n + q)，适合 n, q ≤ 1e5 的规模。

void solved()
{
    int n,q;cin>>n>>q;
    vector<int> p(n+2),vis(n+2);
    for(int i=1;i<=n+1;i++)p[i]=i;//并查集初始化
    
    function<int(int)> find=[&](int x)//路径压缩 
    {
        if(p[x]!=x)p[x]=find(p[x]);
        return p[x];
    };
    
    function<void(int,int)> merge=[&](int x,int y)
    {
        int fx=find(x),fy=find(y);
        if(fx>fy)swap(fx,fy);
        if(fx!=fy)p[fx]=fy;
    };
    
    int cnt=0;
    while(q--)
    {
    	int op;cin>>op;
    	if(op==1)
    	{
    		int l,r;cin>>l>>r;
    		for(int i=l;i<=r;i=find(i))
    		{
    			if(!vis[i])vis[i]=++cnt;
    			if(p[i]!=p[i+1])merge(i,i+1);
			}
		}
		else
		{
			int x;cin>>x;
			cout<<vis[x]<<'\n';
		}
    }
}

D题：线性Dp

因为猪猪之间可能存在相互限制关系，故不能用局部贪心，考虑dp。

1. 输入部分

int n, m; cin >> n >> m;
vector<int> p(n + 1);
for (int i = 1; i <= n; i++) cin >> p[i];

读取猪猪数量 n 和陪伴天数 m。
读取每只猪猪要求陪伴的起始天数 p[i]，存储在数组 p 中。

2. 预处理部分

int sum = 0;
vector<int> day(n + 1, 1e18);
for (int i = 1; i <= n; i++) {
    int x, y; cin >> x >> y;
    sum += y;
    day[p[i] + m - 1] = min(day[p[i] + m - 1], x - y);
}

sum 记录所有猪猪不陪伴的总花费（即所有 y 的总和）。
day 数组用于记录每个时间点的最小花费调整值（x - y）。
- p[i] + m - 1 是第 i 只猪猪陪伴的结束时间。
- x - y 表示如果选择陪伴这只猪猪，可以减少的总花费（因为原本需要花费 y，现在花费 x）。
- 使用 min 确保 day 中存储的是最小的调整值。

3. 动态规划部分

vector<int> f(n + 1);
for (int i = 1; i <= n; i++) {
    if (i >= m) f[i] = min(f[i - 1], f[i - m] + day[i]);
}

f[i] 表示前 i 天的最小花费。
状态转移方程：
- 如果第 i 天不选择陪伴任何猪猪，则花费为 f[i - 1]。
- 如果第 i 天选择陪伴某只猪猪，则花费为 f[i - m] + day[i]（因为陪伴会覆盖 m 天）。
- 取两者的最小值作为 f[i]。

void solved()
{
	int n,m;cin>>n>>m;
	vector<int> p(n+1);
	for(int i=1;i<=n;i++)cin>>p[i];
	
	int sum=0;
	vector<int> day(n+1,1e9);
	for(int i=1;i<=n;i++)
	{
		int x,y;cin>>x>>y;
		sum+=y;
		day[p[i]+m-1]=min(day[p[i]+m-1],x-y);
	}
	
	vector<int> f(n+1);//f[i]:前i天的猪猪全部都安排好的最小花费
	for(int i=1;i<=n;i++)
		if(i>=m)f[i]=min(f[i-1],f[i-m]+day[i]);
	cout<<sum+f[n];
}

E题：

可以先想一下不用除25的版本怎么在O(n)复杂度下解决：利用前缀积和前缀和即可

再想一下对于一个数不断除25的情况：25=5*5，5是质数，不断除25表示数中5这个质因子只能有0个或者1个，可以想到分为两类分别处理即可

void solved()
{
	int n;cin>>n;
	vector<int> a(n+1);
	for(int i=1;i<=n;i++)cin>>a[i];
	
	vector<int> cnt(n+1);
	for(int i=1;i<=n;i++)
		while(a[i]%5==0)a[i]/=5,cnt[i]++;//cnt[i]：5质因子的个数
		
	for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];//cnt数组求前缀和 
	
	vector<int> s(n+1);
	s[0]=1;
	for(int i=1;i<=n;i++)s[i]=s[i-1]*a[i]%mod;//a数组求前缀积 
	
	vector<int> ss1(n+1),ss2(n+1);
	for(int i=1;i<=n;i++)//前缀和 
	{
		if(cnt[i]&1)ss1[i]=ss1[i-1]+s[i],ss2[i]=ss2[i-1];//为奇数时
		else ss1[i]=ss1[i-1],ss2[i]=ss2[i-1]+s[i];//为偶数时
	}
	
	function<int(int,int)> qpow=[&](int a,int b)//快速幂求逆元
	{
		int res=1;
		while(b)
		{
			if(b&1)res=res*a%mod;
			a=a*a%mod;
			b>>=1;
		}
		return res;
	};
	
	int ans=0;
	for(int i=1;i<=n;i++)//区间枚举左端点
	{
		if(cnt[i-1]&1)
		{
			ans=(ans+((ss1[n]-ss1[i-1])%mod+mod)%mod*qpow(s[i-1],mod-2)%mod)%mod;
			ans=(ans+((ss2[n]-ss2[i-1])%mod+mod)%mod*qpow(s[i-1],mod-2)%mod*5)%mod;
		}
		else
		{
			ans=(ans+((ss1[n]-ss1[i-1])%mod+mod)%mod*qpow(s[i-1],mod-2)%mod*5)%mod;
			ans=(ans+((ss2[n]-ss2[i-1])%mod+mod)%mod*qpow(s[i-1],mod-2)%mod)%mod;
		}
	}
	cout<<ans;
}

题解 | #小红的正整数构造#