情况

时间：2024年8月4日22:35

题解

A

题意

4n个问题，每个答案正确选项abcd个数都是n。给出答案，有？则无。问你最多对几题。

思路

简单统计。不超过n的都加进去，超过n按n来算。

代码

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
void solve()
{
    int ans[4]={0,0,0,0};
    int n;
    cin >> n;
    string s;
    cin >> s;
    int len = 4 * n;
    int wen = 0;
    for (int i = 0; i < len; i++)
    {
        if (s[i] == '?')
            wen++;
        else
            ans[s[i] - 'A']++;
    }
    sort(ans, ans + 4);
    int f = 0;
    for (int i = 0; i < 4; i++)
    {
        if (ans[i] <= n)
            f += ans[i];
        else
            f += n;
    }

    cout << f << endl;
}

B

题意

操作：数组中选两个数，奇偶得不同。让两者相加，小的那个换成和。最少几次操作让数组奇偶性一样？

思路

奇数+偶数=奇数。
全是偶数不行，必须得至少一个奇数。
比最大奇数小的偶数一次操作。比最大奇数大的偶数，最多要两次。每次与偶数相加能更新更大的奇数。

代码

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
void solve()
{

    int n;
    cin >> n;
    vector<int> a(n);
    int ji = 0;
    vector<int> b(n, 0);
    bool flag = false;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        if (a[i] & 1)
        {
            b[i] = 1;
            flag = true;
            ji++;
        }
        // cout << "test" << b[i] << "\n";
    }

    if (!flag)
    {
        cout << 0 << "\n";
        return;
    }
    else
    {
        int maxji = 0;
        int maxou = 0;
        bool flag1 = true;
        bool flag2 = true;
        sort(a.begin(), a.end());
        for (int i = n - 1; i >= 0; --i)
        {
            if (a[i] % 2 == 1)
            {
                maxji = a[i];
                flag1 = false;
                break;
            }
            else
            {
                continue;
            }
        }
        // cout << "test" << maxji << "\n";
        for (int i = 0; i < n; ++i)
        {
            // cout << "test" << maxji << "\n";

            if (a[i] % 2 == 0)
            {
                // cout << "cc";
                if (maxji > a[i])
                {
                    maxji += a[i];
                }
                else
                {
                    flag2 = false;
                    // cout << "cao";

                    break;
                }
            }
        }

        if (!flag2)
            cout << n - ji + 1 << "\n";
        else
            cout << n - ji << "\n";
    }
    // 奇数+偶数=奇数
}

问题

有点冗余，因为刚开始不是最好思路。

C

题意

有一间公寓由 n房间组成，每个房间的灯最初都是关闭的。
为了控制这些房间的灯光，公寓的主人决定在房间里安装芯片，这样每个房间就只有一个芯片，而且芯片是在不同的时间安装的。具体来说，这些时间由数组 a1,a2,…,an 表示，其中 ai是在 i房间中安装芯片的时间（以分钟为单位）。
一旦安装了芯片，它就每隔 k 分钟改变房间的光状态-它打开光 k 分钟，然后在接下来的 k 分钟关闭它，然后在接下来的 k 分钟重新打开它，等等。换句话说，对于第 i 光状态在分钟 ai 、 ai+k、 ai+2k 、 ai+3k改变。
公寓内所有房间的灯最早在什么时候打开？

思路

只看最大的那个灯的那部分时间段的情况。让前面小的都加到那之前最后“亮”的时间。看：如果最小亮和最大亮的时间差大于等于k,不行。要么，就输出最大亮的时间。

代码

有点冗余，因为刚开始不是最好思路。

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
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
    cin >> a[i];
    sort(a.begin(), a.end());
    int max = a[n - 1];
    for (int i = 0; i < n-1;i++){
        int beishu = max - a[i];
        beishu = beishu / k;
        if(beishu %2 == 1)
        beishu++;
        a[i] += beishu * k;
    }
    sort(a.begin(), a.end());
    int cha = a[n - 1] - a[0];
    if(cha >= k){
        cout << "-1" << endl;
        return;
    }
    else {
        cout << a[n - 1] << endl;
    }
    // for(int i = 0;i < n;++i)
    //     cout << a[i] << " ";
    // cout << endl;
}

D

题意

给数组长度n和每次删的长度k。每次可以删长度为k的一个子区间里的数字。问删到不能删后中位数最大值。

思路

关键点1：找到不排序找中位数的方法。
关键点2：找到最后剩下的数组的规律。
由于每次删长度为连续的k。最终留下来的方案可以理解为：从左到右选择，先选择一个模k为1的位置的数，再选择一个模k为2的未知的数·····

代码

官方

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int, int>
const int N = 500005;

int n, k, a[N];
int dp[N], b[N];

bool check(int med)
{
    for (int i = 0; i < n; i++)
    {
        if (a[i] >= med)
        {
            b[i] = 1;
        }
        else
        {
            b[i] = -1;
        }
    }

    dp[0] = b[0];
    for (int i = 1; i < n; i++)
    {
        if (i % k == 0)
        {
            dp[i] = max(dp[i - k], b[i]);
        }
        else
        {
            dp[i] = dp[i - 1] + b[i];
            if (i > k)
            {
                dp[i] = max(dp[i], dp[i - k]);
            }
        }
    }

    return dp[n - 1] > 0;
}

void solve()
{
    cin >> n >> k;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    int lo = 1, hi = 1e9;
    while (lo <= hi)
    {
        int mid = lo + hi >> 1;
        if (check(mid))
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }

    cout << hi << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();

    /*code by achen_Karma*/
}

问题

还是有点没懂这dp。而且这题时间复杂度太恶心了。