2022杭电多校（九）

2022杭电多校（九）

一、比赛小结

比赛链接：

二、题目分析及解法（基础题） 1001、Arithmetic Subsequence

题目链接：Problem - 7233 (hdu.edu.cn)

题意：

题目描述. 给一个长度为𝑁的整数序列𝐴 = (𝐴𝑖)，问能否将该序列重排得到序列𝐵 = (𝐵𝑖)，满足

• 1 ≤ 𝑖 < 𝑗 < 𝑘 ≤ 𝑁;

• (𝐵𝑖 , 𝐵𝑗 , 𝐵𝑘 )不构成等差序列。

题解：

首先如果某个数出现次数大于等于3则不存在解。然后如果所有数字均为偶数，我们可将所有数除以二;如果所有数字均为奇数，我们可将所有数减去一;否则,我们将所有奇数放在左边，所有偶数放在右边，对奇数/偶数分治解决。单组数据时间复杂度𝑂(𝑛 log max𝐴𝑖)。

代码：

// #pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
// #pragma GCC optimize("trapv")
#include 
// #include 
#define int long long
#define double long double
// #define i128 long long
// #define double long double
using namespace std;

#define rep(i, n) for (int i = 0; i > a[i];
    map cnt;
    ans.clear();
    rep(i, n) {
      cnt[a[i]]++;
      if (cnt[a[i]] > 2) {
        cout