Dwango Programming Contest V-JZTXT

A - Thumbnail

直接按照题意模拟。。。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=105;
int n;
int a[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int sum=0;
	for(int i=1;i<=n;i++)
		sum+=a[i];
	double avg=(double)sum/n;
	double Min=1e9;
	int t=0;
	for(int i=1;i<=n;i++)
		if(abs(a[i]-avg)<Min) Min=abs(a[i]-avg),t=i;
	printf("%d",t-1);
	return 0;
}

B - Sum AND Subarrays

把 \(\frac{n(n-1)}{2}\) 个区间和分别找出来，按位确定即可，如果当前位可以为 \(1\) 将所有的当前位为 \(0\) 删除。

#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
const int N=1005;
int n;
long long k;
int a[N];
long long sum[N];
long long v[N*N];
int tot;
bool check(long long x)
{
	int cnt=0;
	for(int i=1;i<=tot;i++)
		if((v[i]&x)==x) cnt++;
	return cnt>=k;
}
int main()
{
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+a[i];
	for(int l=1;l<=n;l++)
		for(int r=l;r<=n;r++)
			v[++tot]=sum[r]-sum[l-1];
	long long res=0;
	for(int i=60;i>=0;i--)
		if(check(res|(1LL<<i))) res|=1LL<<i;
	printf("%lld",res);
	return 0;
}

C - k-DMC

从前往后维护一个类似单调队列的东西，队列里维护合法的 D 的位置。

如果遇到一个 M，我们需要将当前队列里所有的 D 加上 \(1\)；遇到一个 D 我们将它加入队列；遇到一个 C 计算一次所有队列里合法的数贡献之和。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=1000005;
int n,Q;
char s[N];
void solve()
{
	int k;
	scanf("%d",&k);
	deque<pair<int,int>>q;
	int add=0;
	long long sum=0;
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		while(!q.empty()&&i-q.front().first>=k) sum-=q.front().second,q.pop_front();
		if(s[i]=='D')
		{
			q.emplace_back(i,-add);
			sum+=-add;
		}
		else if(s[i]=='M') add++;
		else if(s[i]=='C') ans+=1LL*add*q.size()+sum;
	}
	printf("%lld\n",ans);
	return;
}
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	scanf("%d",&Q);
	while(Q--)
		solve();
	return 0;
}

D - Square Rotation

对于 \((x,y)\)，它和 \((x\bmod D,y\bmod D)\) 是等价的，我们可以讨论对于模 \(D\) 剩余系的所有点的情况，下文的 \(A_{x,y}\) 表示模 \(D\) 剩余系下 \((x,y)\) 的点的个数。

最终答案可以表示成 \(aD+b\) 的形式，不妨令矩形左下角为 \((0,0)\)，\(cnt_{i,j}\) 表示模 \(D\) 剩余系下 \((i,j)\) 在矩形中有几个，则：

对于 \(0\leq i,j\leq b\) 的情况，\(cnt_{i,j}=(a+1)^2\)；
对于 \(b< i,j< D\) 的情况，\(cnt_{i,j}=a^2\)；
对于剩下的情况，\(cnt_{i,j}=a(a+1)\)。

需要满足的条件为 \(A_{i,j}\leq cnt_{i,j}\)，我们需要找到一个最小的 \(a\)，使得 \((a+1)^2\ge \max\{A_{i,j}\}\)，\(a\) 的最小值为 \(\sqrt{\max\{A_{i,j}\}}-1\)，考虑计算 \(b\)。

显然可以二分 \(b\)，可以枚举矩形的左下角，判断合法。

对于 \(a^2< A_{i,j}\leq a(a+1)\)，判断一下 \(A_{i,j}\) 有没有在 \(a^2\) 的地方出现。

对于 \(a(a+1)< A_{i,j} \leq (a+1)^2\) 的数，判断一下 \(A_{i,j}\) 是否都在 \((a+1)^2\) 的地方。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=100005,M=2005;
int n,D;
int x[N],y[N];
int cnt[M][M];
int s2[M][M],s3[M][M];
int getsum2(int x1,int y1,int x2,int y2)
{
	if(x1>x2) return 0;
	if(y1>y2) return 0;
	int res=s2[x2][y2];
	if(x1-1>=0) res-=s2[x1-1][y2];
	if(y1-1>=0) res-=s2[x2][y1-1];
	if(x1-1>=0&&y1-1>=0) res+=s2[x1-1][y1-1];
	return res;
}
int getsum3(int x1,int y1,int x2,int y2)
{
	if(x1>x2) return 0;
	if(y1>y2) return 0;
	int res=s3[x2][y2];
	if(x1-1>=0) res-=s3[x1-1][y2];
	if(y1-1>=0) res-=s3[x2][y1-1];
	if(x1-1>=0&&y1-1>=0) res+=s3[x1-1][y1-1];
	return res;
}
bool check2(int x,int y,int b)
{
	return getsum2(x+b+1,y+b+1,x+D-1,y+D-1)==0;
}
bool check3(int x,int y,int b)
{
	return getsum3(x,y,x+b,y+b)==getsum3(0,0,D-1,D-1);
}
int main()
{
	scanf("%d%d",&n,&D);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	for(int i=1;i<=n;i++)
		cnt[x[i]%D][y[i]%D]++;
	int a=0;
	for(int i=0;i<D;i++)
		for(int j=0;j<D;j++)
			a=max(a,(int)ceil(sqrt(cnt[i][j])));
	a--;
	for(int i=0;i<D;i++)
		for(int j=0;j<D;j++)
		{
			if(cnt[i][j]>a*a&&cnt[i][j]<=a*(a+1)) s2[i][j]++;
			else if(cnt[i][j]>a*(a+1)) s3[i][j]++;
		}
	for(int i=0;i<D;i++)
		for(int j=0;j<D;j++)
			s2[i+D][j]=s2[i][j+D]=s2[i+D][j+D]=s2[i][j],s3[i+D][j]=s3[i][j+D]=s3[i+D][j+D]=s3[i][j];
	for(int i=0;i<D+D;i++)
		for(int j=0;j<D+D;j++)
		{
			if(i-1>=0) s2[i][j]+=s2[i-1][j];
			if(j-1>=0) s2[i][j]+=s2[i][j-1];
			if(i-1>=0&&j-1>=0) s2[i][j]-=s2[i-1][j-1];
			if(i-1>=0) s3[i][j]+=s3[i-1][j];
			if(j-1>=0) s3[i][j]+=s3[i][j-1];
			if(i-1>=0&&j-1>=0) s3[i][j]-=s3[i-1][j-1];
		}
	int res=D-1;
	for(int i=0;i<D;i++)
		for(int j=0;j<D;j++)
		{
			int l=0,r=D-1,ans=-1;
			while(l<=r)
			{
				int mid=(l+r)/2;
				if(check2(i,j,mid)&&check3(i,j,mid)) ans=mid,r=mid-1;
				else l=mid+1;
			}
			if(ans!=-1) res=min(res,ans);
		}
	printf("%d",a*D+res);
	return 0;
}

E - Cyclic GCDs

首先有一个 DP，令 \(f_{i,j}\) 表示前 \(i\) 个数组成了 \(j\) 个环的总和。转移为：

\[f_{i,j}=a_if_{i-1,j-1}+(i-1)f_{i-1,j} \]

答案为 \(\gcd(f_{n,i})\)。

考虑 \(f_i\) 的生成函数 \(P(n)\)，则 \(P(n)=P(n-1)(a_ix+(i-1))\)，其中 \(P(0)=1\)。可以推出：

\[P(n)=\prod\limits_{i=1}^n (a_ix+(i-1)) \]

然后就有一个结论：

令 \(w(P)\) 表示 \(P\) 的各项系数的 \(\gcd\)，则 \(w(PQ)=w(P)\cdot w(Q)\)。

首先 \(w(P)\cdot w(Q)|w(PQ)\)，我们需要证明的即为当 \(w(P)=w(Q)=1\) 时，\(w(PQ)=1\)。

考虑反证，设 \(P,Q\) 分别有 \(n,m\) 项。如果 \(w(PQ)\) 有一个质因子 \(p\)，则 \(PQ\) 的最高次项为 \(P_nQ_mx^{n+m}\)，则 \(P_n,Q_m\) 必然有一个是 \(p\) 的倍数，我们可以将这个位置的数删去，然后继续考虑剩下的位置。这样做下去，必然有一个多项式 \(P\) 或 \(Q\) 被删到了空，则这个多项式系数会有一个公因数 \(p\)，矛盾，故假设不成立。

所以答案即为 \(\prod\limits_{i=1}^n\gcd(a_i,i-1)\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
const int MOD=998244353;
int n;
int a[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	long long ans=1;
	for(int i=1;i<=n;i++)
		ans=ans*__gcd(a[i],i-1)%MOD;
	printf("%lld",ans);
	return 0;
}

Programming

Contest

Dwango

programming contest dwango 6th

programming contest dwango

contest programming beginner atcoder

programming collegiate provincial contest

subregional programming acm-icpc contest

programming collegiate jiangsu contest

programming collegiate contest guilin

contest programming beginner registry

programming collegiate mianyang contest

contest programming securities beginner