[ABC 172]

发表于 | 更新于 | 分类于 ，
本文字数： 12k

链接

\(\text{ABC172}\)

C

题意

  给两个\(Stack\)，\(A、B\)。\(A、B\)中分别有\(N、M\)个物品，每个物品分别有一个价值，\(A[i]、B[j]\)。现在给定一个\(K\)，现在需要从A、B中将物品从栈拿出来（每次从最上面拿），一次拿一个，要求所拿出来的物品的价值的总价值不大于\(K\)，求最多可以拿出来多少个物品；

  输入格式：第一行\(N、M、K\)，第二行\(N\)个数表示序列\(A\)，第三行\(M\)个数表示序列\(B\)。

  数据范围：\(1\leq N，M\leq 200000，1\leq K\leq 10^9，1\leq A_i,B_i\leq 10^9\).

  输出格式：输出一个整数，代表最多可以拿出来的物品的个数。

分析

  即求满足\(sumA[i]+sumB[j]\leq K\)的\(\max(i+j)\)，那么我们枚举\(i\)（\(j\)也可以），对每个\(i\)，找到二分找到满足\(sumA[i]+sumB[j]\leq K\)的最大的\(j\)，然后取\(\max(i+j)\)即可；

代码

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
#include <queue>
#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include  <vector>
#define clr(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;
const int maxn = 200005;

int n, m;
ll k;

ll s1[maxn], s2[maxn];

int find(ll x) {
    int l = -1, r = m + 1;
    while (l < r - 1) {
        int mid = (l + r) >>1 ;
        if (x + s2[mid] <= k)
            l = mid;
        else
            r = mid;
    }
    return l;
}

int main() {
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    cin >> n >> m >> k;
    int t;
    for (int i = 1; i <= n; i++)
        cin >> t, s1[i] = s1[i - 1] + t;
    for (int j = 1; j <= m; j++)
        cin >> t, s2[j] = s2[j - 1] + t;
    int res = 0, maxm = 0;
    for (int i = 0; i <= n; i++) {
        if (s1[i] > k) break;
        maxm = i;
        int pos = find(s1[i]);
        maxm += pos;
        res = max(maxm, res);
    }
    cout << res;
}

D

题意

  定义\(f(x)\)为\(x\)的因子的个数，如\(f(4)=3\)，现在，给定一个\(N\)需要求\(\sum_{x=1}^{N}x\times f(x)\);

  数据范围：\(1\leq N \leq10^7\)

分析

  对于第\(i\)个数来说，它对\(\sum_{x=1}^{N}x\times f(x)\)的贡献为\(\frac{t*(t+1)*i}{2}\)，其中\(t=N/i\)；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#define clr(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;
const int maxn = 200005;

ll res;
int n;
int main() {
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        int t = n / i;
        res += 1ll * t * (t + 1) / 2 * i;
    }
    cout << res << endl;
}