D题不太会！

目录

A. Fedya and Array - 1100 - spj构造+思维

B. Dora and Search - 1200 - 双指针

C. Matching Numbers - 数学 + 构造 + 找规律

D. Sum on Subarrays - 1500 - spj构造 + 思维

A. Fedya and Array - 1100 - spj构造+思维

Problem - 1793B - Codeforces

题目：

• maxx是严格大于两边的点，minx是严格小于两边的点，数组两端相连构成环形
• 需要构造一个长度最短的数组，要求数组之间两个相邻元素的差的绝对值为1且满足maxx和minx的权值总和分别为a，b

思路：

题目给出峰值总和a以及谷值总和b

因为题目是spj，所以往最简单的想

即构造一个峰值和一个谷值，两者权值分别为a和b

则构造出的最短序列长度为（a-b）*2

具体实现：

先从从峰值a开始往谷值b构造出序列【a，a-1，……，b】

再从谷值b向a-1构造  【b+1，b+2，……，a-1】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <deque>
#define pb push_back
//#define int long long
#define INF 0x3f3f3f3f
#define x first
#define y second
#define all(v) (v).begin(),(v).end()
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;void solve()
{int maxx,minx;cin>>maxx>>minx;vector<int> v;//既然环内总峰值是maxx，总谷值是minx，则只构造一个峰值和谷值int t=maxx;while(t>minx) v.pb(t--);while(minx<maxx) v.pb(minx++);cout<<v.size()<<endl;for(int x:v) cout<<x<<" ";cout<<endl;
} signed main()
{io;int t;cin>>t;while(t--)solve();return 0;
}

B. Dora and Search - 1200 - 双指针

Problem - 1793C - Codeforces

题目：

定义数组a为含有n个元素序列，元素值由1~n组成，任意找到一个区间 [l,r]

max 为区间内的最大值，min 为区间内的最小值

要求 al 与 ar ≠ 任意一个区间极值，请任意输出一个答案

思路：

• 从数组两端向内遍历，最初max值为n，min值为1
• 如果双指针指到的端点为该区间的极值，则向内移动指针，并更新极值
• 若遍历完后l==r，说明无满足条件的序列存在
• 主要是因为序列由1~n组成，则若某端点=极值，当前区间的极值更新只需++或--

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <deque>
#define pb push_back
//#define int long long
#define INF 0x3f3f3f3f
#define x first
#define y second
#define all(v) (v).begin(),(v).end()
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;const int N=2*1e5+10;
int a[N];void solve()
{int n;cin>>n;int maxx=0,minx=n+1;for(int i=1;i<=n;i++) cin>>a[i];int curmin=1,curmax=n; //因为序列元素为 1~n int l=1,r=n;//从数组两端开始向内遍历，如果某端不满足条件则删去 while(l<r){if(a[l]==curmin) l++,curmin++;else if(a[l]==curmax) l++,curmax--;else if(a[r]==curmin) r--,curmin++;else if(a[r]==curmax) r--,curmax--;else break;}if(l==r) cout<<-1<<endl;else cout<<l<<" "<<r<<endl; 
} signed main()
{io;int t;cin>>t;while(t--)solve();return 0;
}

C. Matching Numbers - 数学 + 构造 + 找规律

Problem - 1788C - Codeforces

题目：

• 给你一个整数n，则数列为1~2n
• 现在需要构造n个数对，使其满足数对（a，b）中a和b在数列中
• 且a1+b1，a2+b2……组成的s1，s2……满足si为公差为1的等差数列
• 数列中1~2n所有数均要使用完

• 如果可以构造出满足条件的数列，输出yes，并将数对输出
• 否则输出no

思路：

由等差数列公式得

        

则化简得

        

则构造出的数列，最小值和最大值为：

                    

易得n为偶数时无解

关于构造，举两个栗子：

n=3时，1   2   3   ||   4   5   6

1+6=7

2+4=6

3+5=8

n=7时，1   2   3   4   5   6   7   ||  8   9   10   11   12   13   14

2+10=12

4+9=13

6+8=14

1+14=15

3+13=16

5+12=17

7+11=18

综合上述两个栗子，我们可以发现规律——

先让奇数位与末尾进行匹配，再让偶数位接着匹配

设t=n

对【1~n】的奇数位，t-- 依次匹配

对【1~n】的偶数位，t-- 依次匹配

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <deque>
#define pb push_back
//#define int long long
#define INF 0x3f3f3f3f
#define x first
#define y second
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;const int N=2*1e5+10;
int a[N];void solve()
{int n;cin>>n;if(n%2==0) {cout<<"No"<<endl;return;}int t=2*n;vector<PII> v;for(int i=1;i<=n;i+=2) v.pb({i,t--});for(int i=2;i<=n;i+=2) v.pb({i,t--});cout<<"Yes"<<endl;for(auto p:v) cout<<p.x<<" "<<p.y<<endl;
} signed main()
{io;int t;cin>>t;while(t--)solve();return 0;
}

D. Sum on Subarrays - 1500 - spj构造 + 思维

Problem - 1809C - Codeforces

题目：

用-1000~1000的数，构造一个长度为n，有k个子序列的元素和为正数，其余（n*(n+1)/2-k）个子序列元素之和为负数的整数序列

思路：

k个正数，我们已知长度为n的序列有n*(n+1)/2个子序列

对于k个整数，我们可以通过构造全正数序列来满足正数子序列需求

构造形如：2，2，2……2，x，-1000，-1000

例如：

n=4，k=5时

2  2  -1  -1000

设k为当前状态仍需要的正数个数

前两个2可提供3（i=1 + i=2 = 3）个正数，还差2个整数，则该x需要保证自身是负数的情况下，与前面的数组合提供2个正数，x=（-1）*2*（i-k）+1

n=7，k=4时

2  2  -3  -1000  -1000  -1000

前两个2可以提供3个正数，还差1个正数，要保证自己是负数的情况下，与前面的数组合只提供1个正数，则为x=（-1）*2*（i-k）+1

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <deque>
#define pb push_back
//#define int long long
#define INF 0x3f3f3f3f
#define x first
#define y second
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;const int N=2*1e5+10;
int a[N];void solve()
{int n,k;cin>>n>>k;for(int i=1;i<=n;i++){if(k>=i){cout<<2<<" ";k-=i;continue;}if(k==0){cout<<-1000<<" ";continue;}cout<<-2*(i-k)+1<<" ";k=0;}cout<<endl;
} signed main()
{io;int t;cin>>t;while(t--)solve();return 0;
}