AtCoder Beginner Contest 207

A-Repression

水题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#include <iostream>
using namespace std;
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int ans = max(a + b, b + c);
    ans = max(a + c, ans);
    cout << ans << endl;
    return 0;
}

B-Hydrate

水题，当$ b \ge C \times D$时无解；否则设答案为T $$ D \geqslant \frac{A + T \times B}{C \times T} \Rightarrow T \geqslant \frac{A}{D \times C - B} $$ 则输出 $\left \lceil \frac{A}{D \times C - B} \right \rceil $

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <cmath>
#include <iostream>

using namespace std;
typedef long long ll;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (b >= c * d)
        puts("-1");
    else
        printf("%lld\n", (ll)ceil(a / (d * c - b)));
    return 0;
}

C-Many Segments

暴力法, 每两段区间直接进行判断 $O(N ^ {2}) $; 对 4 种区间情况，进行了一点小处理

 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
#include <algorithm>
#include <cstring>
#include <iostream>
#define x first
#define y second

using namespace std;
typedef long long ll;

const int M = 2021;

typedef pair<int, int> PII;
PII num[M];
int t[M];

void f(int op, double &a, double &b) { //处理区间开闭
    if (op == 2)
        b -= 0.1;
    else if (op == 3)
        a += 0.1;
    else if (op == 4) {
        a += 0.1, b -= 0.1;
    }
}

bool cheak(int i, int j) { //判断函数
    double a = num[i].x, b = num[i].y, c = num[j].x, d = num[j].y;
    f(t[i], a, b);
    f(t[j], c, d);
    if (a <= c && b >= c)
        return true;
    else if (c <= a && d >= a)
        return true;
    return false;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &t[i], &num[i].x, &num[i].y);

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (cheak(i, j)) {
                cnt++;
            }
        }
    }
    printf("%d\n", cnt);
    return 0;
}

还可以用离散化 + 扫描线法 ${\large O}(N \log{N}) $; 预处理区间边界，用 map 实现离散化，再扫描线求出答案；

 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
#include <iostream>
#include <map>
#define x first
#define y second

using namespace std;
typedef long long ll;

const int M = 2021;
typedef pair<ll, ll> Pll;
typedef pair<int, int> PII;
Pll num[M];
int t[M];

void f(int op, ll &a, ll &b) { //处理区间边界
    a *= 10, b *= 10;
    if (op == 2)
        b -= 1;
    else if (op == 3)
        a += 1;
    else if (op == 4) {
        a += 1; b -= 1;
    }
}

int main() {
    int n, cnt = 0;
    scanf("%d", &n);
    map<ll, PII> mp;
    for (int i = 1; i <= n; i++) {
        scanf("%d%lld%lld", &t[i], &num[i].x, &num[i].y);
        f(t[i], num[i].x, num[i].y);
        mp[num[i].x].x++, mp[num[i].y].y++; //记录线段的始，末
    }

    int last = 0;  // 当前“延续”的线段

    for (auto i : mp) {
        cnt += last * i.y.x;  //计算新出现的与旧的线段的交叉
        cnt += (i.y.x - 1) * (i.y.x) / 2;//计算新线段之间的交叉
        last += i.y.x - i.y.y;
    }

    printf("%d\n", cnt);
    return 0;
}

思考：如果是三条线段重叠，则每次更新可能是 $$ \binom{last}{1} \binom{new}{2} + \binom{last}{2}\binom{new}{1} + \binom{new}{3} $$ 依此类推……

E - Mod 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
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;
typedef long long ll;

const ll MOD = 1e9 + 7, M = 3030;
ll num[M], S[M], dp[M][M], r[M];

int main(){
  int N;
  scanf("%d", &N);
  for (int i = 1; i <= N; i++)
    scanf("%lld", &num[i]);

  for (int i = 1; i <= N; i++){
    S[i] = S[i - 1] + num[i];
  }

  ll ans = 0;
  dp[0][0] = 1;
  for (int i = 1; i <= N; i++){
    memset(r, 0, sizeof r);
    for (int j = 0; j <= N; j++){
      dp[i][j] = r[S[j] % i];
      r[S[j] % i] += dp[i - 1][j];
      r[S[j] % i] %= MOD;
    }
    ans += dp[i][N];
    ans %= MOD;
  }

  printf("%lld\n", ans);
  return 0;
}