cf:
1.https://codeforces.com/problemset/problem/1739/B
题目大意：
给定一个数组B，令数组B[i]=abs(a[i]-a[i-1))，你的任务是尽可能的还原A数组，输出任意满足条件的构造数组
做法：
利用题目给出的条件构造数组即可，首先肯定是a[1]=b[1]并且在此之后，根据差分公式可得，a[i]是大于s[i-1]的，并且a[i]还必须是非负数
参考代码
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define int long long
4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
5 const int N=110;
6 int t;
7 int n;
8 int a[N];
9 int s[N];
10 void solved()
11 {
12 /*c.clear();
13 cin>>n;
14 int cnt=0;
15 for(int i=0;i<n;i++)
16 {
17 cin>>a[i];
18 if(a[i]!=0)
19 {
20 c.push_back(a[i]);
21 }
22 }
23 b[0]=a[0];
24 if(!is_sorted(c.begin(),c.end()))
25 {
26 cout<<-1<<endl;
27 return ;
28 }
29 for(int i=1;i<n;i++)
30 {
31 b[i]=b[i-1]+a[i];
32 }
33 for(int i=0;i<n;i++)
34 {
35 cout<<b[i]<<" ";
36 }
37 cout<<endl;*/
38
39 cin >> n;
40 for(int i=1;i<=n;i++)
41 {
42 cin>>a[i];
43 }
44 s[1]=a[1];
45
46 for(int i=2;i<=n;i++)
47 {
48 if((a[i]<=s[i-1])&&a[i])
49 {
50 cout<<-1<<endl;
51 return ;
52 }
53 s[i]=s[i-1]+a[i];
54 }
55 for(int i = 1; i <= n ; i ++ )
56 cout << s[i] << " ";
57 cout << endl;
58
59 }
60 signed main()
61 {
62 IOS;
63 cin>>t;
64 while(t--)
65 {
66 solved();
67 }
68 return 0;
69 }
2.https://codeforces.com/problemset/problem/1741/B
大体题意：
要求构造这样的一个数组，满足a[i]!=i的前提下并且与前一位相差1
做法：
现特判，对于n=3肯定是不行的，因为对于1~3肯定有一个数不满足上面的条件，其余的只要是错位输出就满足条件了
可以先输出从3往后的，最后在输出2，1
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N=2e5+10;
int a[N];
int t;
void solved()
{
int n;
cin>>n;
if(n==3)
{
cout<<-1<<endl;
return ;
}
else
{
for(int i=3;i<=n;i++)
{
cout<<i<<" ";
}
cout<<2<<" "<<1<<endl;
}
}
signed main()
{
IOS;
cin>>t;
while(t--)
{
solved();
}
return 0;
}
3.https://codeforces.com/problemset/problem/1738/B
大意：
给定一个前缀和数组s，表示的是从s[n-k+1]~s[n]的前缀和数组
前缀和数组定义：
要求判断这个前缀和数组是不是可以被构造的（即满足上面的前缀和定义），并且构成这个前缀和数组的原来a数组还必须是非递减序
做法：
首先k==1，即前n个a[i]的和
另外在根据差分公式还原后k-1个a数组，
并且判断原来的a数组是否是递减的；
假设前n-k+1个a数组的和是b[n-k+2]，那就设前n-k+1个a[i]都等于a[n-k+1]实现最大化
那对于b[n-k+2]来说，肯定是要满足小于等于(n-k+1)*a[n-k+1]的
然后判断是或不是的情况就可以了
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define int long long
4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
5 const int N=1e5+10;
6 int a[N];
7 int n;
8 int t;
9 int s[N];
10 int k;
11 void solved()
12 {
13 /*bool flag=false;
14 cnt=0;
15 ans.clear();
16 cin>>n>>k;
17 if(n-k+1<=0)
18 {
19 cout<<"No"<<endl;
20 return ;
21 }
22 for(int i=1;i<=n;i++)
23 {
24 cin>>a[i];
25 ++cnt;
26 }
27 int sum=0;
28 for(int i=n-k+1;i<=n;i++)
29 {
30 sum=0;
31 for(int j=1;j<=i;j++)
32 {
33 sum+=a[j];
34 }
35 ans+=sum;
36 }
37 if(is_sorted(a+1,a+1+n)&&ans==k)
38 {
39 cout<<"Yes"<<endl;
40 }
41 else
42 {
43 cout<<"No"<<endl;
44 }*/
45 cin>>n>>k;
46 for(int i=n-k+1;i<=n;i++)
47 {
48 cin>>s[i];
49 }
50 for(int i=n;i>=n-k+2;i--)
51 {
52 a[i]=s[i]-s[i-1];
53 }
54 if(k==1)
55 {
56 cout<<"Yes"<<endl;
57 return ;
58 }
59 for(int i=n-1;i>=n-k+2;i--)
60 {
61 if(a[i]>a[i+1])
62 {
63 cout<<"No"<<endl;
64 return ;
65 }
66 }
67 int tmp=s[n-k+1];
68 if(tmp<=(n-k+1)*a[n-k+2])
69 {
70 cout<<"Yes"<<endl;
71 }
72 else
73 {
74 cout<<"No"<<endl;
75 }
76 }
77 signed main()
78 {
79 // IOS;
80 cin>>t;
81 while(t--)
82 {
83 solved();
84 }
85 return 0;
86 }
AT回宿舍再写
标签：cout,int,cf,long,solved,数组,小题,专练,define From： https://www.cnblogs.com/LQS-blog/p/16834109.html