当前位置: 代码迷 >> 综合 >> Codeforces Round #542 (Div. 2) E Wrong Answer (构造思维)
  详细解决方案

Codeforces Round #542 (Div. 2) E Wrong Answer (构造思维)

热度:29   发布时间:2023-11-15 12:17:27.0

题目链接:http://codeforces.com/contest/1130

题目大意

给定一个算法,
让你构造出一个序列,其真正的答案和
这个算法得到的答案之差为k。
k给定,关键是n序列长度和序列中的值的数据范围,
n最大为2000,值的绝对值不超过1e6.

 题目分析

构造思维。我刚开始想的是0,-1,0,-1...
这样,然后最后加上一个X,那么差就是
(X-N)*(N*2+1)-X=k,N为-1的个数,
我刚开始想求解这个方程,发现情况比较多,
主要就是数据范围的缘故,想不清楚一种构造
使得其数据范围能控制成那样。
看了题解真正怀疑自己的智商。。。
第一个数设为-1,然后后面的为a1,a2,...
让程序算法答案为S*N,让真正答案为(S-1)*(N+1),
-1+S-N=k,我们不妨N取1999,这样不管k多大,
我们可以把S搞出来,到这里这题就清楚了。
这个构造有点。。。。花俏吧T_T。

#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
int mod=20100501;
const int maxn=5e3+10;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意:
给定一个算法,
让你构造出一个序列,其真正的答案和
这个算法得到的答案之差为k。
k给定,关键是n序列长度和序列中的值的数据范围,
n最大为2000,值的绝对值不超过1e6.题目分析:
构造思维。我刚开始想的是0,-1,0,-1...
这样,然后最后加上一个X,那么差就是
(X-N)*(N*2+1)-X=k,N为-1的个数,
我刚开始想求解这个方程,发现情况比较多,
主要就是数据范围的缘故,想不清楚一种构造
使得其数据范围能控制成那样。
看了题解真正怀疑自己的智商。。。
第一个数设为-1,然后后面的为a1,a2,...
让程序算法答案为S*N,让真正答案为(S-1)*(N+1),
-1+S-N=k,我们不妨N取1999,这样不管k多大,
我们可以把S搞出来,到这里这题就清楚了。
这个构造有点。。。。花俏吧T_T。
*/
int k,tk;
int n,x;
int ans[maxn];
int main(){ans[0]=-1;cin>>k;k++;k+=1999;int tmp=1e6;rep(i,1,k/tmp+1) ans[i]=tmp;ans[k/tmp+1]=k%tmp;rep(i,k/tmp+2,2000) ans[i]=0;puts("2000");rep(i,0,2000) cout<<ans[i]<<" ";puts("");return 0;
}

 

 

 

  相关解决方案