QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#323420#8225. 最小值之和LarunatrecyCompile Error//C++142.4kb2024-02-09 18:46:332024-02-09 18:46:33

Judging History

你现在查看的是最新测评结果

  • [2024-02-09 18:46:33]
  • 评测
  • [2024-02-09 18:46:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	LL d=exgcd(b,a%b,x,y);
	LL z=x;
	x=y;y=z-1ll*(a/b)*y;
	return d;
}
LL gcd(LL a,LL b)
{
	if(!b)return a;
	return gcd(b,a%b);
}
const int N = 82;
typedef long long LL;
LL dp[N][N][N];
struct info
{
	int k,p,q;
	LL w;
}tr[N][N][N];
mt19937 rnd(time(0));
LL Make(int l,int r)
{
	return rnd()%(r-l+1)+l;
}
LL a[N],f[N],ans[N];
void print(int l,int r,int v,LL w,LL D)//v 是dp 值,w 是实际值,D 是累加 
{
	if(l==r)return;
	if(r==l+1)
	{
		ans[l]=f[l]-w+D;
		return;
	}
	int C=r-l;
	if(f[l]%C==v&&f[l]<=dp[l+1][r][f[l]%(C-1)]&&f[l]==dp[l][r][v])
	{
		ans[l]=D+(f[l]-w)/C;
		print(l+1,r,f[l]%(C-1),f[l],ans[l]);
		return;
	}
	if(f[r]%C==v&&f[r]<=dp[l][r-1][f[r]%(C-1)]&&f[r]==dp[l][r][v])
	{
		ans[r-1]=D+(f[r]-w)/C;
		print(l,r-1,f[r]%(C-1),f[r],ans[r-1]);
		return;
	}
	auto u=tr[l][r][v];
	int k=u.k;
	ans[k]=D+(u.w-w)/C;
	print(l,k,u.p,u.w,ans[k]);
	print(k+1,r,u.q,u.w,ans[k]);
	return;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%lld",&f[i]);
	if(n==1)
	{
		if(f[1]===0)cout<<"Yes";
		else cout<<"No";
		return 0;
	}
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<n;i++)
	{
		dp[i][i+1][0]=-1;
		if(f[i]!=f[i+1])continue;
		dp[i][i+1][0]=f[i];
	}
	for(int len=3;len<=n;len++)
	for(int i=1;i+len-1<=n;i++)
	{
		int j=i+len-1;
		int C=len-1;
		for(int k=i;k<=j-1;k++)
		{
			int A=k-i,B=j-k-1;
			if(!A)
			{
				LL x=f[i];
				if(x<=dp[k+1][j][x%B])dp[i][j][x%C]=max(dp[i][j][x%C],x);
			}
			else if(!B)
			{
				LL x=f[j];
				if(x<=dp[i][k][x%A])dp[i][j][x%C]=max(dp[i][j][x%C],x);
			}
			else 
			{
				for(int p=0;p<A;p++)
				for(int q=0;q<B;q++)
				if(min(dp[i][k][p],dp[k+1][j][q])>=0)
				{
					LL k1=0,k2=0;
					LL d=exgcd(A,B,k1,k2);
					if((q-p)%d!=0)continue;
					k1=(q-p)/d*k1;
					LL x=p+k1*A,P=(A*B/d);
					x=(x%P+P)%P;
					LL v=min(dp[i][k][p],dp[k+1][j][q]);
					if(v>=x)
					{
						v=((v-x)/P)*P+x;
						for(int d=0;d<C&&v>=0;d++,v-=P)
						if(v>=dp[i][j][v%C])
						{
							dp[i][j][v%C]=v;
							tr[i][j][v%C]=(info){k,p,q,v};
						}
					}
				}
			}
		}
	}
	if(dp[1][n][0]<0)printf("No\n");
	else 
	{
		printf("Yes\n");
		print(1,n,0,0ll,0ll);
		for(int i=1;i<n;i++)printf("%lld ",ans[i]);printf("\n");
		return 0;
	}
	return 0;
} 

Details

answer.code: In function ‘int main()’:
answer.code:71:26: error: expected primary-expression before ‘=’ token
   71 |                 if(f[1]===0)cout<<"Yes";
      |                          ^
answer.code:68:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   68 |         for(int i=1;i<=n;i++)scanf("%lld",&f[i]);
      |                              ~~~~~^~~~~~~~~~~~~~