情况

时间：2024年7月1日 星期一 17:15
完成情况：

题解

A. Alice and Books

题意

将数分成两堆，选取每堆”最大数字”的书读。

思路

读题类题目，认真读了快十分钟做出来···，都以为是最大页数。最大数字必定看，因此找出最小到第二大数字中最大页数的书。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 101;
int main()
{
    int t;
    cin >> t;
    while(t--){
        int n;
        int c[N];
        cin >> n;
        for (int i = 0;i<n;i++)
            cin >> c[i];
        sort(c, c+n-1);
        int ans = 0;
        ans = c[n - 1] + c[n - 2];
        cout << ans << endl;
    }
    return 0;
}

B. New Bakery

题意

卖东西，分为正常价格a和活动价格b，第k个活动价格为b−i+1。问最大的利润。

思路

初中函数题目，写出二次方程方程式：
$w=-(0.5) * k^2 + (0.5 - a + b) * k + n * a$
当k=（0.5-a+b)时候最大。
直接在周边几个整数比较大小。
分情况讨论：
先看是否b - n + 1 > a，也就是说活动价永远比正常价格好。如果是，所有物品都用活动价卖出，k=n;
如果不是这样：

  1. 最大值的k小于等于0，k=0;
  2. 最大值的k大于0，k取（0.5-a+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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
 
const int N = 100000;
 
LL func(LL a, LL b, LL n, LL k)
{
    return -(0.5) * k * k + (0.5 - a + b) * k + n * a;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        LL n, a, b;
        cin >> n >> a >> b;
        if (0.5 - a + b > 0 && b - n + 1 < a)
        {
            LL ans = max(func(a, b, n, (0.5 - a + b)), func(a, b, n, (1.5 - a + b)));
            ans = max(ans, (LL)func(a, b, n, (-0.5 - a + b)));
            cout << ans << endl;
        }
        else if (b - n + 1 >= a)
        {
            cout << func(a, b, n, n) << endl;
        }
        else
        {
            cout << func(a, b, n, 0) << endl;
        }
    }
    return 0;
}

问题

这题耽误太多时间（40分钟）的原因就是第一个if少了个b-n+1<a，导致都用第一个算，有一个样例一直过大。要注意if条件对应的情况，划分要清楚。

C. Manhattan Permutations

题意

一种算法，交换1,2,3,4,5···的顺序从而使|p1−1|+|p2−2|+…+|pn−n|=一个值k。如果可行，输出Yes和交换后的顺序。如果不可行，输出No。

思路

先讨论：

  1. k为奇数永远不可能，直接no
  2. k为偶数：

计算此时能表示的最大值（数学推等差数列）
如果k大了，no
如果没有大，进入下一阶段：
在原封不动的情况下，交换一次增长的值是2*交换两者下表的差。
因此直接依据此贪心，每个位置最多交换一次，用双指针从开头和结尾向中间遍历，进行交换，并更新到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
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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 200001;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        LL n, k;
        cin >> n >> k;
        LL max = 0;
        if (n % 2 == 0)
        {
            max = (n * 0.5) * (n * 0.5) * 2;
        }
        else
        {
            max = (n + 1) * 0.5 * ((n + 1) * 0.5 - 1) * 2;
        }
        if (k % 2 == 1)
        {
            cout << "No" << endl;
        }
        else if (k > max)
        {
            cout << "No" << endl;
        }
        else
        {
            LL need = 0.5 * k;
            cout << "Yes" << endl;
            int r = n, l = 1; // 双指针
            int ans[N] = {0};
            for (int i = 1; i <= n; ++i)
            {
                ans[i] = i;
            }
             while (r - l <= need)
             {
                int t =ans[l];
                ans[l] = ans[r];
                ans[r] = t;
                
                     need =need- r + l;
                     l++;
                     r--;
                     if(need == 0){
                         break;
                     }
             }
              while (need != 0){
               l++;
               if (r - l == need){
               swap(ans[l], ans[r]);
               need -= r - l;}
               }
             for (int i = 1; i <= n; ++i)
             {
                 cout << ans[i] << " ";
            }
            cout << endl;
        }
    }
    return 0;
}

问题

这个过程耗时最大的就是第一个while一直输出不出来，直到后来在循环中加了一个break检测：

1
2
3
if(need == 0){
  break;
}

也就是一阶段就成功的情况没考虑，导致第一个用例就过不了。后面也是极限救场了，凭感觉写的贪心哭着也要写完。

D. Elections

赛后补一题。1600分。赛中也没来得及开。用时1小时，还挺满意的做出来了。

题意

有选举者按序号排序，每个选举者有固定票（粉丝）和犹豫票。犹豫者刚开始就有，会把票给序号最小（最左）者；排除一个选举者，他的粉丝全部变成犹豫票。
问你：如何排除最小数量的选举者，从而赢得选举？

思路

全是贪心，做烂了。
先遍历一遍，找到最大值所在处max。顺便搞个前缀和数组。
然后遍历选举者，分情况讨论：

  1. 当前位置是max：
    1. 第一位fans[1]加上犹豫者，fans[1]+c小于max，则一个也不用去掉，输出0；
    2. 第一位就是最大值，也输出0，不用去掉
    3. fans[1]+c大于max，遍历maxwhere（max的位置,也就是现在看的位置)之前的选举者
      1. 遍历过程中若发现c + sum[j] < max，遍历结束，即去掉j之前的选举者，输出j-1
      2. 遍历到头，那就输出maxwhere-1，把之前的都去掉。
  2. 当前位置不是max，前面肯定都得去掉
    1. 如果max的位置在这之前，那去掉了直接变成新的max，输出当前位置之前，i-1;
    2. 否则，在这之后，要考虑用不用把max去了，计算c + sum[i] >= max
      1. 是，则证明不用去，输出i-1
      2. 否，则证明还是得把max去掉，输出i

代码

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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 200001;
LL fans[N];
LL c; // undecided
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        LL sum[N] = {0};
        cin >> n >> c;
        for (int i = 1; i <= n; ++i)
        {
            cin >> fans[i];
            sum[i] = sum[i - 1] + fans[i];
        }
        LL max = fans[1];
        int maxwhere = 1;
        for (int i = 1; i <= n; ++i)
        {
            if (max < fans[i])
            {
                max = fans[i];
                maxwhere = i;
            }
        }
        for (int i = 1; i <= n; ++i)
        {
            if (i == maxwhere)
            {
                if (c + fans[1] < max || maxwhere == 1)
                {
                    cout << 0 << " ";
                }
                else
                {
                    int yes = 0;
                    for (int j = 1; j < maxwhere; j++)
                    {
                        if (c + sum[j] >= max)
                        {
                            continue;
                        }
                        else
                        {
                            cout << j - 1 << " ";
                            yes = 1;
                        }
                    }
                    if (yes != 1)
                    {
                        cout << maxwhere - 1 << " ";
                    }
                }
            }
            else
            {
                if (maxwhere < i)
                {
                    cout << i - 1 << " ";
                }
                else
                {
                    if (c + sum[i] >= max)
                    {
                        cout << i - 1 << " ";
                    }
                    else
                        cout << i << " ";
                }
            }
        }
        cout << endl;
    }
    return 0;
}

问题

令人感慨做的还挺丝滑的，不过就是忘开LL导致wa了一次，看了测试用例情况。要是比赛遇到不知道能不能反映过来···