17南宁区域赛 J - Rearrangement 【规律】

115 阅读 0 评论 76 点赞

我是靠谱客的博主殷勤缘分，这篇文章主要介绍17南宁区域赛 J - Rearrangement 【规律】，现在分享给大家，希望可以做个参考。

题目链接

https://nanti.jisuanke.com/t/19976

题意

给出一个n 然后给出 2*n 个数

可以重新排列成两行然后相邻的两个数加起来不能被三整除

可以上下相邻也可以左右相邻

思路
因为相加根据同余定理我们可以先把每个数模3

因为可以重新排列那么我们不妨以最优的方式去排看能不能得到 YES

很显然， 0 和 0 1 和 2 不能放在一起

也就是说

0 要摆放的话肯定是错位摆放的比如这样

这里写图片描述

星号表示空位 那么很显然 0 的个数不能超过 n

那么我们可以知道因为 1 和 2 不能在一起

那么可以是这样

用两个 0 形成一条分界线上面放1 下面放2

这里写图片描述

然后可以知道如果 只有两个 0 的话那么很显然只有当 1的个数是奇数并且 2 的个数是偶数才是成立的

还有一个比较显然的是
假如只有1 或者只有2 的话那么在满足 0的个数 < n的情况下是恒成立的

那么很显然如果0 的个数 <= 1 并且同时存在 1 和 2 的话那么肯定存在至少一对(1, 2) 相邻

那只需要讨论 0 的个数 > 3 的情况了
先讨论 0 的个数 == 3 的情况如果 0 的个数 == 3 那么就可以多出一个0 去弥补空位

也就是说可以存在奇数1 偶数2 或者奇数2 偶数1 的情况
那么也就是说偶数1 偶数2 是不可行的

但实际上不会存在这种情况因为这种情况是一奇两偶相加是奇数易知数字总个数是2*n 必然为偶数

所以这种情况不用考虑 也就是说 0的个数 == 3 并且 < n 的时候是恒成立的

很显然当0的个数 >= 4的时候也满足

AC代码

复制代码

#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <stack>
#include <set>
#include <list>
#include <numeric>
#include <sstream>
#include <iomanip>
#include <limits>
#define pb push_back
#define fi first
#define se second
#define L(on) ((on)<<1)
#define R(on) (L(on) | 1)
#define mkp(a, b) make_pair(a, b)
#define bug puts("***bug***");
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define CLR(a, b) memset(a, (b), sizeof(a));
#define syn_close ios::sync_with_stdio(false); cin.tie(0);
#define sp system("pause");
//#define gets gets_s 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector < vi > vvi;
const double PI = acos(-1.0);
const double EI = exp(1.0);
const double eps = 1e-8;
inline int read()
{
char c = getchar(); int ans = 0, vis = 1;
while (c < '0' || c > '9') { if (c == '-') vis = -vis;
c = getchar(); }
while (c >= '0' && c <= '9') { ans = ans * 10 + c - '0'; c = getchar(); }
return ans * vis;
}
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fll;
const int maxn = (int)1e2 + 10;
const int MAXN = (int)1e4 + 10;
const ll MOD = (ll)1e9 + 7;
int n;
int arr[3];
void input()
{
n = read();
CLR(arr, 0);
for (int i = 0; i < 2 * n; i++)
arr[read() % 3]++;
}
bool solve()
{
if (arr[0] > n) return false;
if (arr[0] <= 1 && arr[1] && arr[2]) return false;
if (arr[0] == 2 && (arr[1] % 2 == 0) && (arr[2] % 2 == 0)) return false;
return true;
}
int main()
{
int t = read();
while (t--)
{
input();
puts(solve() ? "YES" : "NO");
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <stack>
#include <set>
#include <list>
#include <numeric>
#include <sstream>
#include <iomanip>
#include <limits>
#define pb push_back
#define fi first
#define se second
#define L(on) ((on)<<1)
#define R(on) (L(on) | 1)
#define mkp(a, b) make_pair(a, b)
#define bug puts("***bug***");
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define CLR(a, b) memset(a, (b), sizeof(a));
#define syn_close ios::sync_with_stdio(false); cin.tie(0);
#define sp system("pause");
//#define gets gets_s 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector < vi > vvi;
const double PI = acos(-1.0);
const double EI = exp(1.0);
const double eps = 1e-8;
inline int read()
{
char c = getchar(); int ans = 0, vis = 1;
while (c < '0' || c > '9') { if (c == '-') vis = -vis;
c = getchar(); }
while (c >= '0' && c <= '9') { ans = ans * 10 + c - '0'; c = getchar(); }
return ans * vis;
}
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fll;
const int maxn = (int)1e2 + 10;
const int MAXN = (int)1e4 + 10;
const ll MOD = (ll)1e9 + 7;
int n;
int arr[3];
void input()
{
n = read();
CLR(arr, 0);
for (int i = 0; i < 2 * n; i++)
arr[read() % 3]++;
}
bool solve()
{
if (arr[0] > n) return false;
if (arr[0] <= 1 && arr[1] && arr[2]) return false;
if (arr[0] == 2 && (arr[1] % 2 == 0) && (arr[2] % 2 == 0)) return false;
return true;
}
int main()
{
int t = read();
while (t--)
{
input();
puts(solve() ? "YES" : "NO");
}
}