S001A. 壁垒

$\mathsf{\color{Plum}Statement}$

给定一个长度为 $n$ 的序列 $a$，是否存在一种重排方式使得每个长度为偶数的前缀，出现的数字种类数为偶数。若存在，输出方案；否则，输出 -1。

$\mathsf{\color{Plum}Solution}$

若整个序列的数字种类数为奇数，则不存在方案；否则，必定存在一种方案

• 如果整个序列的数字种类数是奇数，那么第 $n$ 位（题目中保证了 $n$ 为偶数）的数字种类数必定不是偶数
• 如果整个序列的数字种类数是偶数（令其为 $m$），那么只需将前 $m$ 个位置放置 每种数字，后面随便放置即可（这样，即可保证前 $m$ 个位置，相邻偶数位每次加 $2$，后面恒定不变）。

综上所述，即可在 $O(n)$ 的时间复杂度下 $\mathsf{\color{green} AC}$ 此题。

$\mathsf{\color{Plum}Code}$

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;
	unordered_map<int, int> cnt;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], cnt[a[i]] ++;

	if (cnt.size() & 1) cout << -1 << endl;
	else {
		for (auto v : cnt)
			cout << v.fi << " ";
		for (auto v : cnt) {
			int tot = v.se - 1;
			while (tot -- ) cout << v.fi << " ";
		}
		cout << endl;
	}

	return 0;
}

签到题。

设 $a$ 中不同元素的个数为 $s$，若 $s$ 为奇数，易知不存在解。

考虑 $s$ 为偶数，此时定存在一种顺序使 $a$ 的前 $s$ 个元素互不相同，此时第 $s$ 个元素之后的每一个元素都已出现过，不会对元素种类产生影响，符合题意。

AC 代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define len 214514
int n, a[214514], s;
map <int, bool> v;
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) { 
		cin >> a[i]; 
		if (!v[a[i]]) v[a[i]] = 1, s++;
	}
	if (s % 2) { cout << -1; return 0; }
	v.clear();
	for (int i = 1; i <= n; i++) if (!v[a[i]]) cout << a[i] << ' ', v[a[i]] = 1, a[i] = -1;
	for (int i = 1; i <= n; i++) if (a[i] != -1) cout << a[i] << ' ';
	return 0;
}

壁垒

思路

这是一道构造题。

首先，计算出数的种类数。如果种类数是奇数，就无法构造，反之可以。

证明：种类数是奇数时，前 𝑛 n 个数的种类数就一定是奇数。当种类数是偶数时，设数列中数的种类数为 𝑘 k，则构造数列，使得构造的数列前 𝑘 k 项均不相同，剩下的位置把剩余的数输出即可。

Code

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],sum,vis[100005];
int main(){
	cin>>n; for(int i=1;i<=n;i++) cin>>a[i],vis[a[i]]++;
	sort(a+1,a+n+1); sum=1;
	for(int i=2;i<=n;i++) if(a[i]!=a[i-1]) sum++;
	if(sum%2==1) {cout<<"-1"; return 0;}
	cout<<a[1]<<" ";
	for(int i=2;i<=n;i++) if(a[i]!=a[i-1]) cout<<a[i]<<" ";
	for(int i=1;i<=n;i++) while(vis[i]>1) vis[i]--,cout<<i<<" ";
	return 0;
}

考察知识点: 构造法

首先考虑无解的情况，因为 $n$ 是偶数，所以当数列中出现了 $x$ 种不同的数字，且 $x$ 为奇数时，无解，输出 $-1$。

接着就是有解的情况，把 $x$ 个数字全都输出，由于 $x$ 是偶数，且每个数字有且仅有出现了 $1$ 次，所以偶数个数字构成的序列中数字种类数必定为偶数。所有的都输出完毕了，后面只可能出现 $x$ 种数字，而 $x$ 又是偶数，所以可以直接按顺序直接输出。

Code:

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
    memset(a,0,sizeof a);
    int n,s = 0,ma = 0,x;
    cin >> n;
    for (int i = 1;i <= n;i++)
    {
        cin >> x;
        ma = max(ma,x);
        if (a[x] == 0) s++;
        a[x]++;
    }
    if (s % 2 == 1) 
    {
        cout << -1;
        return 0;
    }
    for (int i = 1;i <= ma;i++)
    {
        if (a[i] >= 1) 
        {
            cout << i << ' ';
            a[i]--;
        }
    }
    for (int i = 1;i <= ma;i++)
    {
        if (a[i] >= 1)
        {
            for (int j = 1;j <= a[i];j++)
            {
                cout << i << ' ';
            }
        }
    }
    return 0;
}

思路

设总共有 $kds$ 种。

首先考虑无解

因为 $n$ 一定是偶数，所以如果 $kds$ 是个奇数，不管你怎么排，有 $n$ 个数的数列一定是奇数种。

综上，当 $kds$ 为奇数时，直接 $-1$。

有解的情况

思路也很简单。因为我们判断了 $kds$ 为偶数，所以只需要第一次把每种都打出来一个，前面偶数个必定没问题。后面你随意，因为所有种类都输出了，你怎么搞都行。

Code

#include<bits/stdc++.h>
using namespace std;
int n,a,b[100005],kds,mx=-1;
int main()
{
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>a;
        mx=max(mx,a);
        if(b[a]==0)
        {
            kds++;
        }
        ++b[a];
    }
    if(kds%2==1)
    {
        cout<<-1;
        return 0;
    }
    kds=0;
    int i=1,nn=n;
    while(n>0)
    {
        if(b[i]!=0)
        {
            cout<<i<<" ";
            b[i]--;
            n--;
        }
        ++i;
        if(i>mx)
        {
            i=1;
        }
    }
    return 0;
}

S1A 题解

第四篇题解。

此题是构造题。因为序列的单调递增序列一定包含了这个序列的所有元素，所以我们这个序列剩下的一定是重复的元素，又因为重复的元素不影响数字的种类，所以我们把它们放在后面输出。首先判断无解的情况，然后构造序列的单调递增序列并输出，接着将剩下的元素输出即可。

代码：

#include<iostream>
using namespace std;
int a[100001];
int main()
{
    int n,t=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int b;
        cin>>b;
        a[b]++;
        if(a[b]==1)t++;
    }
    if(t%2)cout<<-1;
    else
    {
        for(int i=1;i<=n;i++)if(a[i])a[i]--,cout<<i<<' ';
        for(int i=1;i<=n;i++)while(a[i]--)cout<<i<<' ';
    }
    return 0;
}

我在洛谷的题解没通过，就搬到 MXOJ 上来吧。

转化一下题意：无法找到一个偶数 $i$ 使得构造出来的序列的第 $1\sim i$ 项所有元素的出现次数为奇数。

结论：若 $1\sim n$ 的种类数为奇数，那么一定无法构造出来。

证明：很显然，我们取 $i$ 为 $n$ 即可。

那么我们可以把 $a$ 中所有出现过的数都只输出一遍，然后接下来去掉刚刚出现过的数，然后随便输出即可。

证明一下这个构造。

我们设 $a$ 中有 $x$ 个不同的数，那么因为 $x$ 不为奇数，按这样构造前 $x$ 个一定满足要求。

而后 $n-x$ 个的每个数因为都在前 $x$ 个出现过了，那么后 $n-x$ 个也满足要求。

那么我们就直接模拟即可：

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n;
int a[N];
vector<int> v;
map<int,int> mp;

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mp[a[i]]++;
	}
	if(mp.size()%2){
		cout<<-1;
		return 0;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		if(mp[i]){
			cout<<i<<' ';
			for(int j=1;j<mp[i];j++) v.push_back(i);
		}
	}
	for(int i:v) cout<<i<<' ';
	return 0;
}

题解: S001A 壁垒

传送门

思路&解题方法

首先发现如果种类数本身为奇数，则一定无解（整个数列也算一个前缀）

发现可以对构造出来的数列进行分析。前缀两个两个地增加，不难发现，每次要么增加 $0$ 种数字，要么增加 $2$ 种数字。

构造时，可以先将偶数种数字依次用一遍（每次增加 $2$ 种），然后就随便放了，因为剩下的数字前面都出现过，每次只有可能增加 $0$ 种数字。

所以，在种类数为偶数时，肯定有解。

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(n)$

Code

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int times[N];
vector<int>ans;

int main() {
    int n, m=0;
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        int x;
        scanf("%d", &x);
        ++times[x];
        if(times[x]==1)
            ++m; // 用m记录种类数
    }
    if(m%2)
        return printf("-1\n")&0; // 无解的情况
    for(int i=1; i<=n; i++) {
        if(times[i]==0)
            continue;
        printf("%d ", i);
        --times[i];
    } // 第一遍，每个种类都消耗一遍，增加2种数字
    for(int i=1; i<=n; i++) {
        while(times[i]) {
            --times[i];
            printf("%d ", i);
        }
    } // 第二遍，每次总是增加0种数字
    puts("");
    return 0;
}

标题

思路

容易证明只需要去重并构造单调递增序列即可。

解题方法

同上。

复杂度

时空复杂度：$O(n)$

标题

思路

容易证明只需要去重并构造单调递增序列即可。

解题方法

同上。

复杂度

时空复杂度：$O(n)$

Code