解题：CF1130E Wrong Answer

巧妙构造题

这种题一定要限制一个条件，使得在这个条件下能推出要叉的代码的式子

令序列$a$的第一个元素为负，其余元素为正，且保证序列中至少有两个元素，那么Alice的代码将会从第二个元素开始计算，得到$(n-1)*(sum-a[1])$的答案。而这里答案实际可能有两种，Alice那样的$(n-1)*(sum-a[1])$和全部选取的$n*sum$(因为后面全是正的所以其他方案一定劣于这两种)。我们后者-前者作个差得到$sum-n-a[1]$，不妨令$a[1]=-1$，那么只需要构造一个长度为$n$而总和为$k+n-1$的序列即可

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,Maxx=1e6;

 int k,s,p,a[N];

 int main()

 {

     scanf("%d",&k);

     a[p=]=-,s=-;

     while(p!=)

     {

         a[++p]=Maxx,s+=a[p];

         if(s-p+>k) {s-=a[p],a[p]-=s+a[p]-p+-k; break;}

     }

     s=;

     for(int i=;i<=p;i++) s+=a[i];

     if(s!=k+p-) printf("-1");

     else

     {

         printf("%d\n",p);

         for(int i=;i<=p;i++)

             printf("%d ",a[i]);

     }

     return ;

 }

巴特西

解题：CF1130E Wrong Answer

最新文章

热门文章