A tb 的区间问题


预估通过率：0.9

条件限制只能删除头尾，最后留下的是原数组中任意一段下标连续的长度为 n-k 的子区间，前缀和后做差，枚举一遍取最大值即可。

复杂度 O(n)。

题目中给的数据范围暴力枚举 O(n^2) 也是能过的。 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1000005;
int k[M];
ll sumt=0;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,lent,w;
	cin>>n>>lent>>w;
	for(int i=1;i<=n;i++)
	{
		cin>>k[i];
	}
	if(n<lent)
	{
		for(int i=1;i<=n;i++)
		{
			sumt+=k[i];
		}
	}
	else
	{
		for(int i=1;i<w;i++)
		{
			sumt+=k[i];
		}
		lent-=w;
		while(lent)
		{
			sumt+=k[n];
			lent--;
			n--;
		}
	}
	cout<<sumt<<"\n";
	return 0;
}

B tb 的字符串问题

预估通过率：0.75

方便大家理解，我们可以将 `t' 看成 `('， b 看成 `)' ，`f' 看成 `[' ，`c' 看成 `]'，其它字符看成 `@'，原问题就等价于将相邻的括号对尽可能消除，消除到不能消除为止。

用一个栈存此时此刻等待匹配的左括号序列，如果栈非空且遇到与栈顶匹配的右括号，则弹栈并将可消除的括号对数加一，否则将栈清空。

最后字符串总长度减去可消除括号对乘二即可，复杂度 O(n) 。

#include<bits/stdc++.h>
using namespace std;
string s,st;
const int M=1000005;
int tp[M],tot=0,ans=0;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	cin>>st;
	s=" "+st;
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='f') tp[++tot]=1;
		else if(s[i]=='t') tp[++tot]=2;
		else if(s[i]=='c')
		{
			if(tot&&tp[tot]==1) ans++,tot--;
			else tot=0;
		}
		else if(s[i]=='b')
		{
			if(tot&&tp[tot]==2) ans++,tot--;
			else tot=0;
		}
		else tot=0;
	}
	cout<<n-ans*2<<"\n";
	return 0;
}

C tb 的路径问题

预估通过率：0.6

手模几组样例，不难发现，
当 n < 4 时，直接不使用传送阵更优。

当 n \ge 4 时:

若使用传送阵：

当 n 为偶数时，gcd(n,n-2) = 2 ，则可以走 2 步到达 (2,2) 并使用传送阵到 (n,n-2) ，再走 2 步到 (n,n) ，总消耗为 4 。

由于 gcd(n,n-1) = 1 ，则其移动到不为 1 的位置至少需要 2 步，且从 (1,1) 移动到不为 1 的位置也至少需要 2 步，则答案至少为 4 步。

故此时的答案为 4。

当 n 为奇数时，gcd(n-1,n-3) = 2 ，则可以走 2 步到达 (2,2) 并使用传送阵到 (n-1,n-3) ，再走 4 步到 (n,n) ，总消耗为 6。

由于 gcd(n,n-1) = 1,gcd(n,n-2) = 1 ，则其移动到不为 1,2,n-1 的位置至少需要 3 步，且从 (1,1) 移动到不为 1,2 的位置也至少需要 3 步，则答案至少为 6 步。

而仅有 (n-1,n-1) 一个格子数字为 n-1 ，无法使用传送阵。

故此时答案为 6 。

若不使用传送阵：

答案为 2(n-1)，劣于之前讨论的使用传送阵情况。

综上所述， n < 4 时，答案为 2(n-1)，n \ge 4 时，若 n 为偶数，答案为 4 ，若 n 为奇数，答案为 6 。

时间复杂度 O(1)。 

#include<iostream>
using namespace std;
int main()
{
	int x;
	cin>>x;
	if(x==1) cout<<0;
	else if(x==2) cout<<2;
	else if(x==3) cout<<4;
	else if(x&1) cout<<6;
	else cout<<4;
	return 0;
}

D tb 的平方问题

预估通过率：0.3

考虑一个和为平方数的区间，假设其下标为 l - r ，则其可以对 \forall\ x \in [l,r] 提供 1 的贡献。

于是我们可以先求前缀和，再枚举 l 和 r，判断其是否符合条件，如果符合条件，就对表示答案的差分数组下标为 r+1 的位置减一，对下标为 l 的位置加一，然后对其求前缀和，就是覆盖某个位置符合条件的区间数。

然后对于每个询问输出其对应的答案即可，判断的时候有开根号的操作，这个操作经过编译器优化后是常数级别的，复杂度为 O(n^2+q) 。 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1005;
ll sumt[M];
int ans[M],a[M],f[M];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,q,x;
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sumt[i]=sumt[i-1]+a[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			int bs=sqrt(sumt[j]-sumt[i-1]);
			if((sumt[j]-sumt[i-1])==1ll*bs*bs)
			{
				f[j+1]--;
				f[i]++;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		ans[i]=ans[i-1]+f[i];
	}
	for(int i=1;i<=q;i++)
	{
		cin>>x;
		cout<<ans[x]<<"\n";
	}
	return 0;
}

E tb 的数数问题

预估通过率：0.2

先对集合去重。

解一：

考虑如果 x 是符合条件的数，则集合内其约数的个数应该等于它约数的总个数。

于是外层枚约数，内层枚举其倍数，每个约数如果在集合中出现，则对其倍数有 1 的贡献，再用线性筛求一下每个数的约数个数，比较一下二者即可。

复杂度均为 O(alna) 。

解二：

考虑如果 x 符合条件二，设 P 为质数集，其充要条件为 \forall\ p \in P ，若有 p | x ，有x/p 也符合条件二。

于是考虑线性筛维护 x 的质因数集，再从小到大枚举 x 以及 x 的质因数求解。

复杂度均为 O(alog_2a) 。

解三：

考虑 1-10^6 内哪些数不符合条件，如果 x 没有出现，那么 x 的倍数都是不符合条件的数，直接枚举其倍数标记即可，然后输出没被标记的值。

复杂度 O(alog_2a) 。 

#include<bits/stdc++.h>
using namespace std;
const int M=1000005;
int p[M],d[M],ts[M],zs[M],f[M],upt[M];
bool vis[M];
void xxs(int n){
	d[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!p[i])
		{
			p[i]=i;
			zs[++zs[0]]=i;
			d[i]=2;
			f[i]=1;
		}
		for(int j=1;j<=zs[0]&&i*zs[j]<=n&&p[i]>=zs[j];j++)
		{
			if(p[i]!=zs[j]) d[i*zs[j]]=d[i]*d[zs[j]],f[i*zs[j]]=1;
			else d[i*zs[j]]=d[i]/(f[i]+1)*(f[i]+2),f[i*zs[j]]=f[i]+1;
			p[i*zs[j]]=zs[j];
		}
	}
	return ;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,ans=0,mx=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>ts[i];
		mx=max(ts[i],mx);
		vis[ts[i]]=true;
	}
	for(int i=1;i<=mx;i++)
	{
		if(!vis[i]) continue;
		for(int j=i;j<=mx;j+=i)
		{
			upt[j]++;
		}
	}
	xxs(mx);
	for(int i=1;i<=mx;i++)
	{
		if(vis[i]&&upt[i]==d[i]) ans++;
	}
	cout<<ans<<"\n";
	return 0;
}

F tb 的排列问题

预估通过率：0.1

设 A 中未出现的数的集合为 P 。

枚举第 i 次操作，此时，对于 B 排列，我们有两种情况：

  1.  若 b_i 不属于 P : 此时 b_i 所对应的数如果在 A 中的初始位置就大于了 i+s ，则一定不存在操作使之复位，否则，其初始位置如果在 1 到 i-1，则一定通过置换操作移动到了 i 到 i+s，则此次置换操作一定可以将其复位，能复位贡献为1，否则贡献为0。
  2.  若 b_i 属于 P : 此时 b_i 可以填入 1 到 i+s 中所有为 -1 的位置，因为通过之前的操作，1 到 i-1 的位置均已复位，则之前未填的为 -1 的位置通过置换操作至多移到了 i-1+s 的位置，于是一定可以填充，此时贡献为 sum(i+s)-cnts，cnts 为已经填充的 -1 个数，sum(i+s) 为 A 数组中下标为 1 到 i+s 中 -1 的个数；
最终答案为 1 ，2 情况的所有贡献求积即可。

复杂度为 O(n) 。 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=500005,mod=998244353;
int sumt[M],a[M],b[M],id[M],mp[M];
void solve(){
	int n,s;
	ll ans=1;
	cin>>n>>s;
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];
	}
	for(int i=1;i<=n;i++)
	{
		id[i]=0;
		cin>>a[i];
		mp[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		if(b[i]==-1) continue;
		b[i]=mp[b[i]];
		id[b[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		sumt[i]=sumt[i-1];
		if(b[i]==-1) sumt[i]++;
	}
	for(int i=1,cnts=0;i<=n;i++)
	{
		if(!id[i]) ans=(ans*(sumt[min(i+s,n)]-cnts))%mod,cnts++;
		else if(id[i]>i+s) ans=0;
	}
	cout<<ans<<"\n";
	return ;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}