Preface

补题ing

上周由于疫情鸽了好多场，趁现在空下来尽量多写点吧

A. Hossam and Combinatorics

SB题，直接统计下最大的数和最小的数的个数即可

注意所有数相同的情况要特判下

#include<cstdio>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)	scanf("%d",&a[i]);
		for (sort(a+1,a+n+1),i=2;i<=n&&a[i]==a[1];++i);
		if (i>n) { printf("%lld\n",1LL*n*(n-1)); continue; }
		for (j=n-1;j>=1&&a[j]==a[n];--j);
		printf("%lld\n",2LL*(i-1)*(n-j));
	}
	return 0;
}

B. Hossam and Friends

考虑每一个隔断区间\([l,r]\)，若右端点\(R\ge r\)，则合法的左端点\(L\)不能\(\le l\)

那么我们可以开一个vector，记录下每个隔断区间的右端点对应的左端点

然后依次枚举右端点的位置，左端点的最小取值就是经过的所有vector里元素的最大值再加一

总复杂度\(O(n)\)

#include<cstdio>
#include<vector>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,m,l,r; vector <int> pos[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) pos[i].clear();
		for (i=1;i<=m;++i) scanf("%d%d",&l,&r),pos[max(l,r)].push_back(min(l,r));
		long long ans=0; int lst=0; for (i=1;i<=n;++i)
		{
			for (int x:pos[i]) lst=max(lst,x); ans+=i-lst;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

C. Hossam and Trainees

SB题，直接分解质因数判断即可

但是要注意\(O(n\sqrt {a_i})\)是会TLE的，因此我们可以先预处理筛出\(\sqrt {a_i}\)范围内的质数，这样复杂度降到\(O(n\times \pi(\sqrt{a_i}))\)即可通过

#include<cstdio>
#include<set>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[N],prm[N],cnt; bool vis[N]; set <int> s;
inline void init(CI n)
{
	for (RI i=2,j;i<=n;++i)
	{
		if (!vis[i]) prm[++cnt]=i;
		for (j=1;j<=cnt&&i*prm[j]<=n;++j)
		if (vis[i*prm[j]]=1,i%prm[j]==0) break;
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (init(100000),scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		bool flag=0; for (s.clear(),i=1;i<=n&&!flag;++i)
		{
			for (j=1;j<=cnt&&1LL*prm[j]*prm[j]<=a[i];++j)
			if (a[i]%prm[j]==0)
			{
				if (s.count(prm[j])) flag=1; s.insert(prm[j]);
				while (a[i]%prm[j]==0) a[i]/=prm[j];
			}
			if (a[i]>1)
			{
				if (s.count(a[i])) flag=1; s.insert(a[i]);
			}
		}
		puts(flag?"YES":"NO");
	}
	return 0;
}

D. Hossam and (sub-)palindromic tree

之前好像写过类似的思路的题（还是OI时期了），但是时间太长忘记了

思想就是序列上的区间DP上树的常见套路，最长回文子序列的序列版本很好处理，我们设\(f_{l,r}\)表示区间\([l,r]\)的答案，则：

• 先考虑两个端点跳过的情况，\(f_{l,r}=\max(f_{l+1,r},f_{l,r-1})\)

• 若\(s_l=s_r\)，有转移\(f_{l,r}=\max(f_{l,r},f_{l+1,r-1}+2)\)

然后我们发现这个东西拿到树上依然是可以转移的，我们设\(f_{x,y}\)表示树上两点\(x,y\)之间的答案

不难发现如果\(x,y\)没有祖先关系，上面的\(l+1,r-1\)对应的就是\(x,y\)的父节点

如果有祖先关系（设\(x\)是\(y\)的祖先），那么区别就是我们此时要找到\(x\)在\(y\)方向的儿子来转移

这部分可以在树上倍增结合LCA实现，由于这种区间DP在序列上的复杂度是\(O(n^2)\)的

我们把它搬到树上也就多了每次转移一个\(\log\)的复杂度，因此总复杂度\(O(n^2\log n )\)

#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=2005,P=12;
int t,n,x,y,ans,dep[N],anc[N][P],f[N][N]; char s[N]; vector <int> v[N];
inline void DFS(CI now=1,CI fa=0)
{
	dep[now]=dep[fa]+1; anc[now][0]=fa;
	for (RI i=0;i<P-1;++i) anc[now][i+1]=anc[anc[now][i]][i];
	for (int to:v[now]) if (to!=fa) DFS(to,now);
}
inline int getLCA(int x,int y)
{
	if (dep[x]<dep[y]) swap(x,y);
	for (RI i=P-1;~i;--i) if (dep[anc[x][i]]>=dep[y]) x=anc[x][i];
	if (x==y) return x;
	for (RI i=P-1;~i;--i) if (anc[x][i]!=anc[y][i])
	x=anc[x][i],y=anc[y][i]; return anc[x][0];
}
inline int jump(int x,CI y)
{
	for (RI i=0;i<P;++i) if ((y>>i)&1) x=anc[x][i]; return x;
}
inline int DP(CI x,CI y)
{
	if (!x||!y) return 0;
	if (~f[x][y]) return f[x][y]; if (x==y) return f[x][y]=1;
	int fa=getLCA(x,y),fx=anc[x][0],fy=anc[y][0];
	if (fa==x) fx=jump(y,dep[y]-dep[x]-1);
	else if (fa==y) fy=jump(x,dep[x]-dep[y]-1);
	f[x][y]=max(DP(fx,y),DP(fy,x));
	if (s[x]!=s[y]) return f[x][y];
	if (fx==y&&fy==x) f[x][y]=max(f[x][y],2);
	else f[x][y]=max(f[x][y],DP(fx,fy)+2); return f[x][y];
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i)
		for (v[i].clear(),j=1;j<=n;++j) f[i][j]=-1;
		for (i=1;i<n;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
		for (i=1;i<=n;++i) for (j=0;j<P;++j) anc[i][j]=0;
		for (ans=0,DFS(),i=1;i<=n;++i) for (j=1;j<=n;++j)
		ans=max(ans,DP(i,j)); printf("%d\n",ans);
	}
	return 0;
}