QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#325459#8225. 最小值之和flying#Compile Error//C++142.3kb2024-02-11 14:07:002024-07-04 03:23:32

Judging History

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

  • [2024-07-04 03:23:32]
  • 评测
  • [2024-02-11 14:07:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N=85;

int a[N],Min[N][N],dp[N][N][N],n;
bool vis[N][N];
array <int,3> pre[N][N][N];

void work(int i,int j,int w,int f,int f1,int f2)
{
    int m=j-i;
    if(w<0 || w>Min[i][j])
    	return;

    int k=w%m;
    if(w<=dp[i][j][k])
    	return;

    dp[i][j][k]=w;
    pre[i][j][k]={f,f1,f2};
}

set <int> st;

int fun(int w,int up,int m)
{
    if(w>up)
    	w-=(w-up+m-1)/m*m;
    return w;
}

int fun2(int w,int up,int m)
{
    if(w>up)
    	w-=(w-up+m-1)/m*m;
    else
    	w+=(up-w)/m*m;
    return w;
}

void solve(int l,int r)
{
    if(l>=r || vis[l][r])
    	return;

    vis[l][r]=true;
    int m=r-l,w=Min[l][r];
    if(m==1)
    {
        if(a[l]==a[r])
            dp[l][r][0]=a[l];
        return;
    }

    solve(l+1,r), solve(l,r-1);
    if(dp[l+1][r][a[l]%(m-1)]>=a[l])
        work(l,r,a[l],l,0,a[l]%(m-1));

    if(dp[l][r-1][a[r]%(m-1)]>=a[r])
        work(l,r,a[r],r-1,a[r]%(m-1),0);

    for(int i=l+1;i<r-1;i++)
    {
        solve(l,i), solve(i+1,r);
        int m1=i-l,m2=r-i-1;
        int g=lcm(m,lcm(m1,m2));
        for(int k=0;k<g;k++)
        {
            int j=k%m,j1=k%m1,j2=k%m2;
            int up=min({w,dp[l][i][j1],dp[i+1][r][j2]});
            if(up<0)
            	continue;
            work(l,r,fun2(k,up,g),i,j1,j2);
        }
    }
}

int c[N];

void print(int l,int r,int d,int w2=0)
{
    if(l>=r)
    	return;

    int i=pre[l][r][d][0],w=(dp[l][r][d]-w2)/(r-l);
    c[l]+=w,c[r]-=w;
    if(l+1>=r)
    	return;

    print(l,i,pre[l][r][d][1],dp[l][r][d]);
    print(i+1,r,pre[l][r][d][2],dp[l][r][d]);
}

int main()
{
    memset(dp,0xff,sizeof(dp));
    cin >> n;
    for(int i=1;i<=n;i++)
    	scanf("%d",&a[i]);

    if(n==1)
    {
        if(a[1])
        	printf("No\n");
        else
        	printf("Yes\n");
        return 0;
    }

    for(int i=1;i<=n;i++)
    {
        Min[i][i]=a[i];
        for(int j=i+1;j<=n;j++)
        	Min[i][j]=min(Min[i][j-1],a[j]);
    }

    solve(1,n);
    if(!~dp[1][n][0])
    {
    	printf("No\n");
    	return 0;
    }

    printf("Yes\n");
    print(1,n,0);
    for(int i=1;i<n;i++)
    {
    	c[i] += c[i-1];
    	printf("%d ",c[i]);
    }
    printf("\n");
    return 0;
}

Details

answer.code: In function ‘void solve(int, int)’:
answer.code:67:21: error: ‘lcm’ was not declared in this scope
   67 |         int g=lcm(m,lcm(m1,m2));
      |                     ^~~
answer.code:67:15: error: ‘lcm’ was not declared in this scope
   67 |         int g=lcm(m,lcm(m1,m2));
      |               ^~~
answer.code: In function ‘int main()’:
answer.code:100:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  100 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~