526互联

AtCoder Grand Contest 036

发布时间 2023-09-27 19:00:14作者: Zhou_JK

A - Triangle

考虑 \(x_1,y_1\) 选原点，构造另外两个点。考虑叉积的形式，可以得出：

\[x_2y_3+x_3y_2=S \]

令 \(x_2=y_3=\lceil \sqrt S\rceil\)，令 \(t=S-x_2y_3\)，暴力枚举 \(t\) 的因数即可。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=200005;
long long s;
int main()
{
	scanf("%lld",&s);
	long long x1,y1,x2,y2,x3,y3;
	x1=0,y1=0;
	x2=y3=ceil(sqrt(s));
	long long t=x2*y3-s;
	if(t==0) y2=x3=0;
	for(long long i=1;i<=sqrt(t);i++)
		if(t%i==0)
		{
			if(i<=1e9&&t/i<=1e9) y2=i,x3=t/i;
		}
	printf("%lld %lld %lld %lld %lld %lld",x1,y1,x2,y2,x3,y3);
	return 0;
}

B - Do Not Duplicate

令 \(s_i\) 表示加入 \(a_i,a_{i+1},\cdots ,a_n\) 后的序列，\(f_0\) 表示空串。可以发现，最后的序列一定为 \(s_0,s_1,\cdots ,s_n\) 中的一个。因为如果 \(s_i[1]\) 的下一个位置为 \(j\)，则 \(1\to j\) 这段就变成了空串，串变成了 \(s_j\)。

令 \(f_{i,j}\) 表示 \(s_i\) 操作 \(j\) 次后为 \(s_{f_{i,j}}\)，倍增加速即可。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
const int N=400005;
int n;
long long k;
int a[N];
int pos[N],nxt[N];
int f[N][60];
int vis[N];
int main()
{
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),a[i+n]=a[i];
	for(int i=n*2;i>=1;i--)
		nxt[i]=pos[a[i]],pos[a[i]]=i;
	f[0][0]=1;
	for(int i=n;i>=1;i--)
		if(nxt[i]>n)
		{
			if(nxt[i]==n+n) f[i][0]=0;
			else f[i][0]=nxt[i]-n+1;
		}
		else
		{
			if(nxt[i]==n) f[i][0]=1;
			else f[i][0]=f[nxt[i]+1][0];
		}
	for(int i=1;i<=log2(k);i++)
		for(int u=0;u<=n;u++)
			f[u][i]=f[f[u][i-1]][i-1];
	int p=0;
	for(int i=0;i<=log2(k);i++)
		if(k&(1LL<<i)) p=f[p][i];
	if(p==0) return 0;
	stack<int>s;
	for(int i=p;i<=n;i++)
	{
		if(vis[a[i]])
		{
			while(!s.empty()&&s.top()!=a[i]) vis[s.top()]--,s.pop();
			if(!s.empty()) vis[s.top()]--,s.pop();
		}
		else s.push(a[i]),vis[a[i]]++;
	}
	vector<int>res;
	while(!s.empty()) res.push_back(s.top()),s.pop();
	reverse(res.begin(),res.end());
	for(int u:res)
		printf("%d ",u);
	return 0;
}

C - GP 2

可以发现，合法的局面需要满足：

  • 所有位置的 \(x_i\) 之和为 \(3M\)；
  • 最大的 \(x_i\) 需要满足 \(x_i\leq 2M\)；
  • 奇数的 \(x_i\) 个数不超过 \(M\)；
  • 奇数的 \(x_i\) 个数的奇偶性需要跟 \(M\) 相同。

考虑枚举 \(x_i\) 为奇数的个数，可以将奇数位置 \(-1\) 变成偶数位置，然后将两个球一起考虑，问题变成了 \(\frac{3M-i}{2}\) 的情况。对第二个条件进行容斥，钦定某个位置的个数 \(> 2M\)，然后隔板法搞一搞。需要对这个位置的个数为奇数和偶数的情况分类讨论。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=4000005;
const int MOD=998244353;
int n,m;
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
long long fac[N],inv[N];
void init(int n=4000000)
{
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%MOD;
	inv[n]=ksm(fac[n],MOD-2);
	for(int i=n;i>=1;i--)
		inv[i-1]=inv[i]*i%MOD;
	return;
}
long long C(int n,int m)
{
	if(m>n) return 0;
	else return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main()
{
	init();
	scanf("%d%d",&n,&m);
	long long ans=0;
	int num=(m+1)%2==1?m+1:m+2;
	for(int i=0;i<=n&&i<=m;i++)
	{
		if(i%2!=m%2) continue;
		int t=(3*m-i)/2;
		if(t<0) continue; 
		long long res=0;
		res=(res+C(t+n-1,n-1)*C(n,i)%MOD)%MOD;
		if(t-m>=0) res=(res-C(t-m+n-1,n-1)*C(n-1,i-1)%MOD*n%MOD+MOD)%MOD;
		if(t-(m+1)>=0) res=(res-C(t-(m+1)+n-1,n-1)*C(n-1,i)%MOD*n%MOD+MOD)%MOD;
		ans=(ans+res)%MOD;
	}
	printf("%lld",ans);
	return 0;
}

D - Negative Cycle

因为不存在负环，则存在到每个点的最短路，不妨设为 \(d_i\)。

考虑 \(d\) 需要满足的条件，因为有 \(i\to i+1\) 的边，即 \(d_i\ge d_{i+1}\)。

令 \(p_i=d_i-d_{i+1}\)，则 \(p_i\ge 0\)，且 \(p_i\leq 1\)，否则一定会产生负环。

如果有一条边权为 \(-1\) 的边 \(i\to j\)，需要满足

\[x_i-1\ge x_j \Leftrightarrow \sum\limits_{k=i}^{j-1}p_i \ge 1 \]

即如果 \(\sum\limits_{k=i}^{j-1}p_i=0\) 必须删除 \(i\to j\)。

如果有一条边权为 \(1\) 的边 \(i\to j\)，即

\[x_i+1\ge x_j \Leftrightarrow \sum\limits_{k=j}^{i-1}p_i \le 1 \]

即如果 \(\sum\limits_{k=j}^{i-1}p_i\ge 2\) 必须删除 \(i\to j\)。

我们的目标要使被删除的边尽可能少。

考虑 DP，令 \(f_{i,j}\) 表示位置 \(i,j\) 为 \(1\)，\([i+1,j-1]\) 均为 \(0\)。转移考虑枚举下一个 \(1\) 的位置 \(k\)，需要删掉的边 \(l\to r\) 为满足 \(l> k,i< r\ge j\) 或 \(j< l< r\le k\)，这个可以用前缀和优化转移。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=505;
const long long INF=4557430888798830399;
int n;
int a[N][N];
long long s1[N][N],s2[N][N];
long long f[N][N];
long long calc1(int l1,int r1,int l2,int r2)
{
	if(l1>r1) return 0;
	if(l2>r2) return 0;
	return s1[r1][r2]-s1[l1-1][r2]-s1[r1][l2-1]+s1[l1-1][l2-1];
}
long long calc2(int l1,int r1,int l2,int r2)
{
	if(l1>r1) return 0;
	if(l2>r2) return 0;
	return s2[r1][r2]-s2[l1-1][r2]-s2[r1][l2-1]+s2[l1-1][l2-1];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i!=j) scanf("%d",&a[i][j]);
	for(int i=1;i<=n+1;i++)
		for(int j=1;j<=n+1;j++)
		{
			s1[i][j]=s1[i-1][j]+s1[i][j-1]-s1[i-1][j-1];
			if(i>j) s1[i][j]+=a[i][j];
			s2[i][j]=s2[i-1][j]+s2[i][j-1]-s2[i-1][j-1];
			if(i<j) s2[i][j]+=a[i][j];
		}
	memset(f,63,sizeof(f));
	f[0][0]=0;
	for(int i=0;i<=n;i++)
		for(int j=i;j<=n;j++)
			if(f[i][j]<INF)
				for(int k=j+1;k<=n+1;k++)
					f[j][k]=min(f[j][k],f[i][j]+calc1(k+1,n+1,i+1,j)+calc2(j+1,k,j+1,k));
	long long res=INF;
	for(int i=0;i<=n;i++)
		res=min(res,f[i][n+1]);
	printf("%lld",res);
	return 0;
}

E - ABC String

可以发现，原串中相邻的字符只需要保留一个即可，剩下的都是不可能成为答案的。

令 \(c_{i}\) 表示 \(i\) 这个字符出现的次数，不妨令 \(c_A\leq c_B\leq c_C\)，其他情况同理。

可以发现答案的上界为 \(c_A\cdot 3\)，那么我们肯定尽可能删除 \(A\) 使得序列合法。

先让 \(c_B=c_C\)，我们需要删去某些 C。如果一个 C 的两边的字符是不相同的，那么删去这个字符对答案是没有影响的。删完这些 C 后如果还是不满足条件，我们可以将两个 ACA 中删去一个 AC，直到合法为止。

这时 \(c_A\leq c_B=c_C\)，我们每次删一个 BC 的字串，需要保证删去后不会产生相邻相同的情况。可以证明如果有解，那么肯定可以删到 \(c_A=c_B=c_C\) 的情况。

如果最终还是不相等就无解。

#include<iostream>
#include<cstdio>
#include<cassert>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000005;
int n;
char str[N],s[N];
int cnt[4];
int id[4];
int pre[N],nxt[N];
void del(int i)
{
	pre[nxt[i]]=pre[i];
	nxt[pre[i]]=nxt[i];
	return;
}
int main()
{
	scanf("%s",str+1);
	for(size_t i=1;i<=strlen(str+1);i++)
		if(str[i]!=str[i-1]) s[++n]=str[i];
	for(int i=1;i<=n;i++)
		cnt[s[i]-'A'+1]++;
	id[1]=1,id[2]=2,id[3]=3;
	sort(id+1,id+3+1,[=](const int &x,const int &y){return cnt[x]<cnt[y];});
	sort(cnt+1,cnt+3+1);
	for(int i=1;i<=n;i++)
		nxt[i]=i+1,pre[i]=i-1;
	nxt[0]=1,pre[n+1]=n;
	int head=0,tail=n+1;
	for(int i=head;i!=tail&&cnt[2]<cnt[3];i=nxt[i])
		if(i&&nxt[i]&&s[i]==id[3]+'A'-1&&s[pre[i]]!=s[nxt[i]]) cnt[3]--,del(i);
	if(cnt[2]<cnt[3])
	{
		for(int i=head;i!=tail&&cnt[2]<cnt[3];i=nxt[i])
			if(i&&pre[i]&&nxt[i]&&s[i]==id[3]+'A'-1&&s[pre[i]]==s[nxt[i]]&&s[pre[i]]==id[1]+'A'-1)
			{
				cnt[1]--,cnt[3]--;
				del(pre[i]),del(i);
			}
	}
	if(cnt[2]!=cnt[3]) return 0;
	if(cnt[1]<cnt[2])
	{
		for(int i=head;i!=tail&&cnt[1]<cnt[2];i=nxt[i])
		{
			if(i&&pre[i]&&s[pre[i]]!=id[1]+'A'-1&&s[i]!=id[1]+'A'-1)
			{
				if(s[pre[pre[i]]]==id[1]+'A'-1&&s[nxt[i]]==id[1]+'A'-1) continue;
				cnt[2]--,cnt[3]--;
				del(pre[i]),del(i);
			}
		}
	}
	if(cnt[1]!=cnt[2]||cnt[2]!=cnt[3]) return 0;
	for(int i=head;i!=tail;i=nxt[i])
		if(i) printf("%c",s[i]);
	return 0;
}

F - Square Constraints

因为 \(N^2 \leq i^2+P_i^2 \leq (2N)^2\)，我们可以求出 \(P_i\) 的上下界 \(l_i,r_i\)：

  • 当 \(0\leq i< N\) 时，$l_i = \lceil \sqrt{N^2 - i^2} \rceil, r_i = \lfloor \sqrt{(2N)^2 - i^2}\rfloor $。
  • 当 \(N\leq i< 2N\) 时，\(l_i=0,r_i=\lfloor \sqrt{(2N)^2−i^2}\rfloor\)。

考虑满足 \(i^2+P_i^2 \leq (2N)^2\)，容斥掉 \(N^2 \leq i^2+P_i^2\) 的条件，钦定 \(0\sim N-1\) 中的某些位置需要 \(\leq l_i-1\)。

考虑如果知道了每个位置的上界 \(a_i\)，从小到大排序后每个位置能选的数即为 \(a_i+1-i\)，答案即为 \(\prod\limits_{i=1}^n (a_i+1-i)\)。

现在的问题主要是没法快速求出 \(k\) 个位置 \(\leq l_i-1\) 的方案数。

对于一个数，我们需要知道出它的上界的排名后才能算出方案数。可以发现，\(l_i,r_i\) 都是单调递减的，且对于每个 \((i,j)\)（\(0\leq i,j\leq N-1\)），\(l_i-1\leq r_j\)。

对于 \(N \sim 2N-1\) 的数 \(i\)。排完序后比它们上界小的为 \(N \sim 2N-1\) 中的 \(j\) 满足 \(r_j\leq r_i\) 的数和 \(0 \sim N-1\) 中取 \(l_j-1\) 为上界且满足 \(l_j-1\leq r_i\) 的数。

对于 \(0 \sim N-1\) 的数 \(i\)，取 \(l_i-1\) 为上界。排完序后比它们上界小的为 \(N \sim 2N-1\) 中的 \(j\) 满足 \(r_j\leq l_i-1\) 的数和 \(0 \sim N-1\) 中取 \(l_j-1\) 为上界且满足 \(l_j-1\leq l_i-1\) 的数。

对于 \(0 \sim N-1\) 的数 \(i\)，取 \(r_i\) 为上界。排完序后比它们上界小的为 \(N \sim 2N-1\) 中的数和 \(0 \sim N-1\) 中取 \(l_j-1\) 为上界的数还有 \(0 \sim N-1\) 中取 \(r_j\) 为上界的数且满足 \(r_j\leq r_i\) 的数。

那么就可以对于 \(0\sim N-1\) 的数，将 \(l_i-1\) 作为第一关键字，\(r_i\) 作为第二关键字。对于 \(N\sim 2N-1\) 的数，将 \(r_i\) 作为关键字排序。

令 \(f_{i,j}\) 表示前 \(i\) 个数中选了 \(j\) 个上界为 \(l_i-1\) 的数的方案数。转移时分成三种情况讨论一下即可，可以记录一下当前 \(0\sim N-1\) 的数的个数 \(c_1\) 和 \(N\sim 2N-1\) 的数的个数 \(c_2\) 方便转移。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=505;
int n,P;
int l[N],r[N];
pair<int,int>a[N];
long long dp[N][N];
long long calc(int k)
{
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	int c1=0,c2=0;
	for(int i=0;i<n+n;i++)
		if(a[i].second==0)
		{
			for(int j=0;j<=c2;j++)
				dp[i+1][j]=(dp[i+1][j]+dp[i][j]*(a[i].first+1-(c1+j))%P)%P;
			c1++;
		}
		else
		{
			for(int j=0;j<=c2;j++)
				dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j]*(a[i].first+1-(c1+j))%P)%P;
			for(int j=0;j<=c2;j++)
				dp[i+1][j]=(dp[i+1][j]+dp[i][j]*(a[i].second+1-(n+k+(c2-j)))%P)%P;
			c2++;
		}
	return dp[n+n][k];
}
int main()
{
	scanf("%d%d",&n,&P);
	for(int i=0;i<n;i++)
		l[i]=max((int)ceil(sqrt(n*n-i*i)),0),r[i]=min((int)floor(sqrt(4*n*n-i*i)),n+n-1),a[i]=make_pair(l[i]-1,r[i]);
	for(int i=n;i<n+n;i++)
		l[i]=0,r[i]=sqrt(4*n*n-i*i),a[i]=make_pair(r[i],0);
	sort(a,a+n+n);
	long long ans=0;
	for(int i=n;i>=0;i--)
		if(i&1) ans=(ans-calc(i)+P)%P;
		else ans=(ans+calc(i))%P;
	printf("%lld",ans);
	return 0;
}