文章目录

• A. Everything Everywhere All But One
• • 题目详情：
  • 题解：
• B. Odd Subarrays
• • 题目详情：
  • 题解：
• C. Circular Local MiniMax
• • 题目详情：
  • 题解：

A. Everything Everywhere All But One

题目详情：

给定一个包含 n 个整数 a1,a2,…,an 的数组。 用数组的 n-1 个元素，并用它们的算术平均值（不必是整数）替换它们中的每一个。 问：是否可以通过执行有限数量的此类操作来使数组的所有元素相等？

题解：

模拟题意即可。

#includeusing namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> pii;typedef vector<int> vi;typedef vector<pair<int,int>> vpii;#define all(a) a.begin(), a.end()#define nl '\n'const int inf=0x3f3f3f3f;const int maxn=1e6+5;void solve(){    int n;    cin >> n;    int sum = 0;    vi a(n);    for (int i = 0; i < n;i++){ cin >> a[i]; sum += a[i];    }    int flag = 0;    for (int i = 0; i < n;i++){ if(a[i]==floor(sum-a[i])/(n-1)){     flag = 1;     break; }    }    if (flag){ cout << "yes" << nl;    }    else{ cout << "no" << nl;    }}int main(){    ios::sync_with_stdio(0);    int t = 1;    cin>>t;    while(t--) solve();    return 0;}

B. Odd Subarrays

题目详情：

对于数组 [ b 1 , b 2 , … , b m ] [b_1,b_2,…,b_m] [b1​,b2​,…,bm​]，将其反转次数定义为整数对 $(i,j)$ 的数量，使得 $1\le i<j\le m$ 和 b i > b j b_i>b_j bi​>bj​。 如果数组 $b$ 的反转次数是奇数，我们就称它为奇数。

例如，数组 [4,2,7] 是奇数，因为它的反转次数是 1，而数组 [2,1,4,3] 不是，因为它的反转次数是 2。

给定一个从 1 到 n 的整数排列 [p1,p2,…,pn]（每个整数在排列中只出现一次）。 您想将其拆分为几个连续的子数组（可能只有一个），以便其中奇数子数组的数量尽可能大。

题解：

考虑相邻逆序数的对数。

#includeusing namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> pii;typedef vector<int> vi;typedef vector<pair<int,int>> vpii;#define all(a) a.begin(), a.end()#define nl '\n'#define debug() cout << "debug:"const int inf=0x3f3f3f3f;const int maxn=1e6+5;void solve(){    int n;    cin >> n;    int a[n];    for (int i = 0; i < n; i++) cin >> a[i];    int c = 0;    for (int i = 0; i < n - 1; i++){ if (a[i] > a[i + 1]){     //cout << a[i] << " " << a[i + 1];     c++;     i++; }    }    //debug();    cout << c << nl;}int main(){    ios::sync_with_stdio(0);    int t = 1;    cin>>t;    while(t--) solve();    return 0;}

C. Circular Local MiniMax

题目详情：

给你 n 个整数 a1,a2,…,an。是否可以将它们排列在一个圆圈上，以使每个数字都严格大于其邻居或严格小于其邻居？

换句话说，检查是否存在整数 a1,a2,…,an 的重排 b1,b2,…,bn 使得对于从 1 到 n 的每个 i，至少满足以下条件之一：

• bi−1 bi+1
• bi−1> bi < bi+1

为了理解前面关于 i=1 和 i=n 的公式，我们应该定义 b0=bn 和 bn+1=b1。

输入
输入的第一行包含一个整数 t (1≤t≤3⋅10^4) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 n (3≤n≤10^5) — 整数的个数。

每个测试用例的第二行包含 n 个整数 a1,a2,…,an (0≤ai≤10^9)。

所有测试用例的 n 总和不超过 2⋅10^5。

输出
对于每个测试用例，如果不能将满足语句条件的数字排列在圆圈上，则输出 NO。您可以在任何情况下输出每个字母。

否则，输出YES。在第二行中，输出 n 个整数 b1,b2,…,bn，它们是 a1,a2,…,an 的重新排列，并满足语句中的条件。如果有多种有效的排列数字的方法，您可以输出其中任何一种。

inputCopy431 1 241 9 8 442 0 2 261 1 1 11 111 1111outputCopyNOYES1 8 4 9 NOYES1 11 1 111 1 1111 

题解：

#include using namespace std;typedef long long ll;typedef long double ld;typedef pair<int, int> pii;typedef vector<int> vi;typedef vector<pair<int, int>> vpii;#define all(a) a.begin(), a.end()#define nl '\n'#define debug() cout << "debug:";const int inf = 0x3f3f3f3f;const int maxn = 1e6 + 5;int a[maxn], b[maxn];void solve(){    int n;    cin >> n;    for (int i = 0; i < n; ++i) cin >> a[i];    if (n & 1) return cout << "NO\n", void();    sort(a, a + n);    int m = n >> 1;    for (int i = 0; i < m; ++i) b[i * 2] = a[i], b[i * 2 + 1] = a[i + m];    for (int i = 1; i < n; ++i) if (b[i] == b[i - 1])     return cout << "NO\n", void();    cout << "YES\n";    for (int i = 0; i < n; ++i) cout << b[i] << ' ';    cout << '\n';}int main(){    ios::sync_with_stdio(0);    int t = 1;    cin >> t;    while (t--) solve();    return 0;}