Atcoder Grand Contest 058

By xiaruize

A - Make it Zigzag

对于每一个PiP_i

  • i为偶数 如果Pi+1>PiP_{i+1}>P_i，则有两种选择
    • Pi+2<PiP_{i+2}<P_i 交换(Pi+1,Pi+2)(P_{i+1},P_{i+2})
    • 否则交换(Pi,Pi+1)(P_{i},P_{i+1})
  • i为奇数 如果Pi+1<PiP_{i+1}<P_i，则有两种选择
    • Pi+2>PiP_{i+2}>P_i 交换(Pi+1,Pi+2)(P_{i+1},P_{i+2})
    • 否则交换(Pi,Pi+1)(P_{i},P_{i+1})

一定是步数最少的可行方案

感性理解：

因为如果相邻两数不满足要求，那么一定需要交换来解决

如果满足条件11，那么一次交换可以解决两个不满足要求的排序

否则则只解决一个

Code
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
87
/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int n;
int p[N];
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    // auto t_1=chrono::high_resolution_clock::now();
    cin >> n;
    for (int i = 1; i <= 2 * n; i++)
        cin >> p[i];
    int res = 0;
    vector<int> v;
    for (int i = 1; i < 2 * n; i++)
    {
        if (i % 2 == 1)
        {
            if (p[i] > p[i + 1])
            {
                if (i + 2 <= n + n && p[i + 2] > p[i])
                {
                    swap(p[i + 1], p[i + 2]);
                    v.pb(i + 1);
                    res++;
                    continue;
                }
                swap(p[i], p[i + 1]);
                v.pb(i);
                res++;
            }
        }
        else
        {
            if (p[i] < p[i + 1])
            {
                if (i + 2 <= n + n && p[i + 2] < p[i])
                {
                    swap(p[i + 1], p[i + 2]);
                    v.pb(i + 1);
                    res++;
                    continue;
                }
                swap(p[i], p[i + 1]);
                v.pb(i);
                res++;
            }
        }
    }
    cout << res << endl;
    for (auto x : v)
        cout << x << ' ';
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}

B - Adjacent Chmax

首先，可以将比max看作是大的数向比它小的数拓展的过程

明显的dpdp题，我们考虑 dpi,jdp_{i,j} 表示只考虑前面的 ii 个数进行拓展，到第 jj 位且前面都有覆盖的情况数

设每个数左侧第一个大于它的是LiL_i，右侧是RiR_i

dpi,j(j在i可以拓展到的范围内)=∑x=L[i]jdpi−1,xdp_{i,j}(j在i可以拓展到的范围内)=\sum_{x=L[i]}^{j} dp_{i-1,x}

似乎就结束了。

ii 这一维可以去掉，每次在原来的数组上进行转移就行

1
2
3
4
5
for i: 1->n
    sum=0;
    for j: (L[i])->(R[i]-1)
        sum=sum+dp[j]
        dp[j]=sum
Code
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
/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 2e5 + 10;

// bool st;
int n;
int a[5005];
int dp[5005];
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    // auto t_1=chrono::high_resolution_clock::now();
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        dp[i] = 0;
    }
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        int l = 0, r = n;
        for (int j = i - 1; j >= 1; j--)
        {
            if (a[j] > a[i])
            {
                l = j;
                break;
            }
        }
        for (int j = i + 1; j <= n; j++)
        {
            if (a[j] > a[i])
            {
                r = j - 1;
                break;
            }
        }
        int sum = 0;
        for (int j = l; j <= r; j++)
        {
            sum += dp[j];
           sum%=MOD;
          dp[j]=sum;
        }
    }
    cout << dp[n] << endl;
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}