AtCoder Beginner Contest 194_atcodder begginer contest 194

导读：
简单的题目，只说明题意，或者直接说明结论
下面的难题，会做详细的解释和证明
立个flag，在座的大佬们做个见证：一个月刷60场ABC，现在2021/6/19，第四天，已打卡六场。

A - I Scream

根据题意直接写即可

void work()
{
  int a, b; cin >> a >> b;
  a += b;
  if (a >= 15 && b >= 8) cout << 1 << endl;
  else if (a >= 10 && b >= 3) cout << 2 << endl;
  else if (a >= 3) cout << 3 << endl;
  else cout << 4 << endl;
}
1
2
3
4
5
6
7
8
9

B - Job Assignment

n只有1000，完全可以暴力

#include <iostream>
#define rep(i, n) for (int i = 0; i < n; ++ i)
const int N = 1010;
void work()
{
  int n; cin >> n;
  int a[N], b[N];
  rep(i, n) cin >> a[i] >> b[i];
  int ans = 1e9;
  rep(i, n) rep(j, n) if (i == j) ans = min(ans, a[i] + b[j]); else ans = min(max(a[i], b[j]), ans);
  cout << ans << endl;
}
int main(void)
{
   work();
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

C - Squared Error

将公式展开变形，有很多种变形方式，我在这里放两个代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 300005;
int n;
ll a[N];
ll s[N];
int main()
{
  cin >> n;
  for (int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
  for (int i = 1; i <= n; i ++ )
    s[i] = s[i - 1] + a[i];
  ll sum = 0;
  for (int i = 1; i <= n; i ++ )
    sum += (n - 1) * a[i] * a[i] - 2 * a[i] * (s[n] - s[i]);
  cout << sum << '\n';
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 300005;
int n;
ll a[N];
ll s[N], ss[N];
int main()
{
  cin >> n;
  for (int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
  for (int i = 1; i <= n; i ++ )
    s[i] = s[i - 1] + a[i];
  for (int i = 1; i <= n; i ++ )
    ss[i] = ss[i - 1] + a[i] * a[i];
  ll sum = 0;
  for (int i = 2; i <= n; i ++ )
    sum += (i - 1) * a[i] * a[i] - 2 * a[i] * (s[i - 1]) + ss[i - 1];
  cout << sum << endl;
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

D - Journey

额，没懂怎么做的，看题解没看懂，抱歉抱歉

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <limits.h>
#include <sstream>
#include <cctype>
#include <numeric>
#include <bitset>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inlin")

using namespace std;

#define ios ios::sync_with_stdio(false) , cin.tie(0),cout.tie(0)
#define rep(i, n) for (int i = 0; i < n; ++ i)
#define x first
#define y second

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

const int N = 100010, INF = 0x3f3f3f3f, mod = 1e9 + 7, base = 131;
const double eps = 1e-6, PI = acos(-1);


void work()
{
  int n; cin >> n;
  double ans = 0;
  for (int i = 1; i <= n - 1; i ++ )
    ans += (double)n / i;
  printf("%.6lf\n", ans);
}

int main(void)
{
  //ios;
  int T = 1;
  // cin >> T;
  while (T -- )
  {
    work();
  }

  return 0;
}

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

E - Mex Min

以前做过这种题目，但是现在上手还是感到生疏
题意：给定要给长度为n的序列，现在我们从i~i+m - 1这m个数中，找到第一个不存在的非负整数，然后在这n+m-1个值中输出最小值
我们发现，一个长度为m的序列中，如果0~m-1这m个数字都有且只出现一次的话，我们的整数会是m，但如果不然，一定会导致0~m-1这m个数字中至少缺少一个数字，而那个缺的最小的数字，就是我们当前求的区间的最小值。
同时，也等价于在一个长度为m+1的连续序列中，如果某个数字x没有出现两次的话，就相当于在这情况下，会出现一个长度为m的串中没有出现1次x。
由此，我们可以将问题转化为，判断当前出现的数字x的所有出现的位置，如果出现相邻两个间距大于m，那一定是缺的就是它。如果我们从小到大枚举x的话，第一次出现这种情况的一定就是他了。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; i ++ )
int n, m;
vector<int> v[1500005];
int main(void)
{
  cin >> n >> m;
  rep(i, 0, n)
  {
    int x; scanf("%d", &x);
    if (x < m) v[x].push_back(i);
  }
  rep(i, 0, m + 1)
  {
    // cout << v[i].size() << endl;
    if (v[i].empty())
    {
      cout << i << "\n";
      return 0;
    }
    bool flag = false;
    int last = -1;
    for (int it : v[i])
    {
      if (it - last <= m) last = it;
      else 
      {
        flag = true;
        break;
      }
    }
    if (n - last > m) flag = true;
    if (flag) {cout << i << "\n"; return 0;}
  }
  return 0;
}

```

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