CF 1381B Unmerge（思維 + 01背包確定可行解）

題目：

Let a and b be two arrays of lengths n and m, respectively, with no elements in common. We can define a new array merge(a,b) of length n+m recursively as follows:

• If one of the arrays is empty, the result is the other array. That is, merge(?,b)=b and merge(a,?)=a. In particular, merge(?,?)=?.
• If both arrays are non-empty, and a1<b1, then merge(a,b)=[a1]+merge([a2,…,an],b). That is, we delete the first element a1 of a, merge the remaining arrays, then add a1 to the beginning of the result.
• If both arrays are non-empty, and a1>b1, then merge(a,b)=[b1]+merge(a,[b2,…,bm]) That is, we delete the first element b1 of b, merge the remaining arrays, then add b1 to the beginning of the result.

This algorithm has the nice property that if a and b are sorted, then merge(a,b) will also be sorted. For example, it is used as a subroutine in merge-sort. For this problem, however, we will consider the same procedure acting on non-sorted arrays as well. For example, if a=[3,1] and b=[2,4]，then merge(a,b)=[2,3,1,4].

A permutation is an array consisting of nn distinct integers from 11 to nn in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

There is a permutation p of length 2n. Determine if there exist two arrays a and b, each of length n and with no elements in common, so that p=merge(a,b).

思路：我們容易想到“3 2”，“7 1”這些情況，這兩個數一定屬于同一個集合且是連續的，根據這個規律看“7 1 6”，我們發現如果6和 7 1不屬于同一個集合的話，那么6一定時另一個集合的頭元素，那么6一定不可能出現在7的后面，可以推出“7 1 6”屬于同一個集合，這樣我們可以找到一個規律，例如：

6 1 3 7 4 5 8 2，我們可以分成[6 1 3] [7 4 5] [8 2]；3 2 6 1 5 7 8 4,我們可以分成[3 2] [6 1 5] [7] [8 4].這樣我們可以把每個塊的個數統計，然后我們只需要確定這些數字是不是可以組成n即可，

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <string>
 6 #include <vector>
 7 #include <cmath>
 8  
 9 using namespace std;
10  
11 #define ll long long
12 #define pb push_back
13 #define fi first
14 #define se second
15  
16 const int N = 2e5 + 10;
17 bool f[N];
18 int a[N];
19  
20 void solve()
21 {      
22     int T;
23     cin >> T;
24     while(T--){
25         int n;
26         cin >> n;
27         n <<= 1;
28         for(int i = 1; i <= n; ++i) cin >> a[i];
29         // for(int i = 1; i <= n; ++i) cout << a[i] << " ";
30         // cout << endl;
31         vector<int > v;
32         int x = a[1];
33         int cnt = 0, inx = 1;
34         while(1){
35             if(a[inx] <= x) cnt++, inx++;
36             else{
37                 v.pb(cnt);
38                 cnt = 0;
39                 x = a[inx];
40             }
41             if(inx > n) break;
42         }
43         if(cnt > 0) v.pb(cnt);
44        // cout << "n = " << n << endl;
45         n >>= 1;
46         for(int i = 0; i <= n; ++i) f[i] = false;
47         f[0] = true;
48         //cout << " f[n] = " << f[n] << endl;
49         for(auto vv : v){
50             for(int i = n; i >= 0; --i){
51                 if(i - vv < 0) break;
52                 if(f[i - vv] == true) f[i] = true;
53             }
54         }
55         //cout << "n = " << n << endl;
56         if(f[n] == true) cout << "YES" << endl;
57         else cout << "NO" << endl;
58     }
59 }
60  
61 int main()
62 {
63     ios::sync_with_stdio(false);
64     cin.tie(0);
65     cout.tie(0); 
66     solve();
67  
68     return 0;
69 }

標籤：其他

上一篇：0260. Single Number III (M)

下一篇：CF 1372C Omkar and Baseball