Codeforces Round #815 (Div.2)

By xiaruize

A. Burenka Plays with Fractions

分情况考虑

  • a=0a=0或b=0b=0时,一次
  • a×d=b×ca\times d=b\times c,两分数已经相等,答案为00
  • (a×d,b×c)(a\times d,b\times c)有非11倍的倍数关系时,答案为11
  • 其他情况,答案为22
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
// Problem: A. Burenka Plays with Fractions
// Contest: Codeforces Round #815 (Div. 2)
// URL: https://codeforces.com/contest/1720/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    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 t;
int a, b, c, d;
// 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 >> t;
    while (t--)
    {
        cin >> a >> b >> c >> d;
        if (a * d == c * b)
            cout << "0" << endl;
        else if (a == 0 || c == 0 || (a * d) % (b * c) == 0 || (b * c) % (a * d) == 0)
            cout << "1" << endl;
        else
            cout << "2" << 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;
}

B.Interesting Sum

求出序列最大值mxmx,次大值smxsmx,最小值mimi,次小值smismi

可以发现,一定存在一组[l,r][l,r]使得最大值和次大值在两个部分,最小值和次小值在两个部分

所以答案为mx+smx−mi−smimx+smx-mi-smi

可以O(n)O(n)求得

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
88
89
90
91
92
93
94
// Problem: B. Interesting Sum
// Contest: Codeforces Round #815 (Div. 2)
// URL: https://codeforces.com/contest/1720/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    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 = 1e5 + 10;

// bool st;
int t;
int n;
int a[N];
int mx, mp, mxx, mpp, mi, mip, mii, mipp;
// bool en;

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    mx = mp = mxx = mpp = mi = mip = mii = mipp = 0;
    mi = mii = INF;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] > mx)
        {
            mxx = mx;
            mpp = mp;
            mx = a[i];
            mpp = i;
        }
        else if (a[i] > mxx)
        {
            mxx = a[i];
            mpp = i;
        }
        if (a[i] < mi)
        {
            mii = mi;
            mipp = mip;
            mi = a[i];
            mip = i;
        }
        else if (a[i] < mii)
        {
            mii = a[i];
            mipp = i;
        }
    }
    cout << mx + mxx - mi - mii << endl;
}

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 >> t;
    while (t--)
        solve();
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}

C. Corners

首先,考虑如果有一个LL形的00在一开始就存在,那么一定可以每次只取一个11

所以要最小化第一个LL中11的个数,可以O(nm)O(nm)的扫一遍整个数组来达成

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
// Problem: C. Corners
// Contest: Codeforces Round #815 (Div. 2)
// URL: https://codeforces.com/contest/1720/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    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, m;
int t;
int a[505][505];
// bool en;

void solve()
{
    cin >> n >> m;
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++)
        {
            a[i][j] = s[j - 1] - '0';
            if (a[i][j])
                res++;
        }
    }
    int mi = INF;
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            mi =
                min(mi, min(min(a[i][j] + a[i + 1][j] + a[i][j + 1], a[i][j] + a[i + 1][j] + a[i + 1][j + 1]),
                            min(a[i + 1][j] + a[i + 1][j + 1] + a[i][j + 1], a[i][j] + a[i][j + 1] + a[i + 1][j + 1])));
        }
    }
    if (mi == 0)
        mi = 1;
    cout << res - mi + 1 << endl;
}

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 >> t;
    while (t--)
        solve();
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}

D1. Xor-Subsequence (easy version)

很容易想到一个 O(N2)O(N^2) 的 dpdp.

但是,可以发现转移并不需要从前面的nn个转移过来,而是只需要从前面的400400个转移到当前位即可

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
// Problem: D1. Xor-Subsequence (easy version)
// Contest: Codeforces Round #815 (Div. 2)
// URL: https://codeforces.com/contest/1720/problem/D1
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    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 = 3e5 + 10;

// bool st;
int t;
int n;
int a[N];
int dp[N];
// bool en;

void chkmax(int &x, int y)
{
    if (y > x)
        x = y;
}

void solve()
{
    memset(dp, 0, sizeof(dp));
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        dp[i] = 1;
    }
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i - 1; j >= max(0ll, i - 400); j--)
        {
            if ((a[j] ^ i) < (a[i] ^ j))
                chkmax(dp[i], dp[j] + 1);
        }
        chkmax(res, dp[i]);
    }
    cout << res << endl;
}

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 >> t;
    while (t--)
        solve();
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}