A.K-divisible Sum—思维

题意：构造出一个有 n 个正整数的集合使其的和能够整除 k，同时尽可能使其中最大的正整数最小，请输出构造出的集合的最大的正整数

思路：肯定是尽可能将 k 平均分给集合中的数

  • 如果 n<=k，就是最大的正整数就是 [k/n]
  • 如果 n>k，那就不好整了为了保证集合中的数都是正整数所以集合中的数的和肯定加起来比 k 大并且是 k 的倍数，如果
    • 如果n%k==0，那这 n 个数都填最小 1 就可以满足条件了
    • 否则 n%k!=0，我们总能让一部分数为 2，一部分数为 1 即可满足条件

值得注意的是 ceil() 实际返还的还是浮点数（初衷是为了防止爆 int），所以太大的数就会以科学计数法形式表示（含自然对数 e）这次比赛好多人都因此被 hack 掉了，以后还是慎重使用吧 😱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        ll n, k;
        cin >> n >> k;
        ll ans;
        if (n <= k)
            ans = k / n + (n - 1) / n;	//向上取整模拟
        else
            ans = n % k ? 2 : 1;
        cout << ans << endl;
    }
    // system("pause");
    return 0;
}

B.Inflation—贪心+思维

题意：给出一个从下标 0 开始有 n 个数的数组 p 以及一个百分数 k ，要求我们只能选择给其中一个数加上某个数使数组对于任意的 i>=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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll a[105];
 
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    ll t;
    cin >> t;
    while (t--) {
        ll n, per;
        cin >> n >> per;
        ll sum = 0;
        for (ll i = 1; i <= n; ++i) {
            cin >> a[i];
            sum += a[i];
        }
        ll ans = 0;
        for (ll i = n; i >= 2; --i) {
            sum -= a[i];
            if (ceil(a[i] * 100 * 1.0 / per) <= sum)
                continue;
            else {
                ll cha = ceil(a[i] * 100 * 1.0 / per) - sum;
                ans += cha;
                sum += cha;
            }
        }
        cout << ans << endl;
    }
    // system("pause");
    return 0;
}

C.Longest Simple Cycle—贪心+构造

题意：给出 n 个平行竖放的链，对于第 i 个链有 c[i] 个节点连接在一起，然后从第二个链开始每个链的上端和下端分别连向前面链的第 a[i] 和 b[i] 分节点，请找出形成的图中最长的环

样例

解释

思路：很容易发现环的长度就是组成节点的个数，环可能是横向椭圆（即延伸答案更优）或者是竖向椭圆（即拉长更优），所以每两条链都有可能组成最长的环。如果暴力枚举会 TLE 6。不妨从前往后从位置 i(i>=2) 开始枚举环的右边界并计算出其能形成的环的最大长度

  • 当 i==2 或者 a[i]==b[i] 时无疑只能选择 i-1 条链作为左边界，我们计算出来这个环的长度作为暂时的最优解
  • 否则还可能以前面的链作为左边界形成环，所以我们就将 i-1 形成的最优解的环右边界拆开并延伸到当前第 i 条链作为右边界形成环去更新最优解

同时在这个过程中我们尝试更新答案取最大值就可，时间复杂度为 O(n) 成功 AC

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 100;
 
ll a[maxn], b[maxn], c[maxn], mx[maxn];  //贪心记录以当前i为右边界能形成的最大环的路径数量
 
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> c[i];
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        for (int i = 1; i <= n; ++i) {
            cin >> b[i];
            if (a[i] > b[i]) swap(a[i], b[i]);
        }
        ll ans = 0;
        for (int i = 2; i <= n; ++i) {
            mx[i] = b[i] - a[i] + 1 + c[i];  //只能以前一个链为环左边界
            if (i != 2 && a[i] != b[i])      //否则还可以继续延伸前面的最大环形成更大的环
                mx[i] = max(mx[i], mx[i - 1] - (b[i] - a[i]) + 1 + c[i]);
            ans = max(ans, mx[i]);
        }
        cout << ans << endl;
    }
    // system("pause");
    return 0;
}

D.Journey—前缀和+思维

题意：有 n+1 个城市编号从 0~n+1，并且有 n 条有方向的道路编号从 1~n 将城市连成一条线，对于第 i 条路将 i 与 i-1 城市连接在一起，如果路标记为 L 则说明该路方向为 i 指向 i+1，否则标记为 R 说明该路方向为 i-1 指向 i。现在有一个旅行者可以从任意一个城市出发，每一天他可以沿着道路走向一个城市，并且每过一天这 n 条道路方向会反向。请确定从每个城市出发，最多可以经过多少个不同的城市

思路：我们假设求初始从当前城市 i 出发一直向左走能走多远，如果他能走到 i-1，那么就统计 +1，如果恰好 i-1 城市与 i-2 城市道路初始是向右的，当我们走到 i-1 城市时恰好是向左的所以可以再到 i-2 城市继续出发，而到 i-2 城市时恰好所有道路又恢复原来的方向，相当于问题变为了再计算一下初始从 i-2 城市出发一直向左走能走多远的问题，这可以借助前缀和解决重复的问题。同理在按照上述方法求一下一直向右走的情况，最终初始从城市 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 100;
 
char s[maxn];
int L[maxn], R[maxn];  //维护一直向左走和一直向右走经过的点数
 
signed main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i <= n; ++i)	//初始化为1算上自己
            L[i] = 1, R[i] = 1;
        scanf("%s", s + 1);
        for (int i = 1; i <= n; ++i) {
            if (s[i] == 'L') {
                ++L[i];                             //先看能不能到临点
                if (i - 1 >= 1 && s[i - 1] == 'R')  //如果临点的临点和临点之间是向右那么就可以继续走
                    L[i] += L[i - 2];
            }
        }
 
        for (int i = n; i >= 1; --i) {  //同上
            if (s[i] == 'R') {
                ++R[i - 1];
                if (i + 1 <= n && s[i + 1] == 'L')
                    R[i - 1] += R[i + 1];
            }
        }
        for (int i = 0; i <= n; ++i) {
            cout << L[i] + R[i] - 1 << ' ';  //之前算了两次自己
        }
        cout << endl;
    }
    // system("pause");
    return 0;
}