AtCoder Beginner Contest 091

A

模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// LUOGU_RID: 174593368
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int a,b,c;
  cin>>a>>b>>c;//输入
  if(a+b>=c) //关键的判断
  {
     cout<<"Yes\n";//输出
  }
  else 
  {
     cout<<"No\n";//输出
  }
  return 0;
}

B

直接用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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 100;
string t[N];
int main()
{
    int n, m;
    cin >> n;
    map<string, int> mp;
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i];
        mp[t[i]]++;
       // cout << mp[t[i]] << "\n";
    }
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        string s;
        cin >> s;
        mp[s]--;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, mp[t[i]]);
    }
    cout << ans << '\n';
    return 0;
}

C

直接建边用匈牙利算法。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i64 = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
const int N = 1e3 + 100;
pii a[N];
pii b[N];
int Map[N][N];
bool vis[2 * N];
int p[2 * N];
int n;
bool match(int i)
{
    for (int j = 1; j <= n; ++j)
        if (Map[i][j] && !vis[j]) // 有边且未访问
        {
            vis[j] = true;
            // 记录状态为访问过
            if (p[j] == 0 || match(p[j]))
            // 如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
            {
                p[j] = i;
                // 当前左侧元素成为当前右侧元素的新匹配
                return true;
                // 返回匹配成功
            }
        }
    return false;
    // 循环结束，仍未找到匹配，返回匹配失败
}
int Hungarian()
{
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        memset(vis, 0, sizeof(vis)); // 重置vis数组
        if (match(i))
            cnt++;
    }
    return cnt;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].first >> a[i].second;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i].first >> b[i].second;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (a[i].first < b[j].first && a[i].second < b[j].second)
            {
                Map[i][j] = 1;
            }
        }
    }
    int ans = Hungarian();
    cout << ans << '\n';
}

D

本题可以用火车头暴力直接莽夫打法。

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
// LUOGU_RID: 174600085
// LUOGU_RID: 135210620
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
using namespace std;

int n, a[200010], b[200010], res;

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            res ^= a[i] + b[j];
    cout << res;
}

也可以用考虑数位的方法，考虑第k位的贡献，为了防止高位的影响，直接取模。

然后就是如果两个数的第k位为1就会在两个数的和有一个范围，这里详见代码。

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
// LUOGU_RID: 174603361
// LUOGU_RID: 135210620
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, a[maxn], b[maxn], c[maxn], d[maxn], ans;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int k = 0; k <= 28; k++)
    {
        long long cnt = 0;
        for (int i = 1; i <= n; i++)
            c[i] = (a[i] & ((1 << (k + 1)) - 1)), d[i] = (b[i] & ((1 << (k + 1)) - 1));
        sort(c + 1, c + 1 + n);
        sort(d + 1, d + 1 + n);
        for (int i = 1; i <= n; i++)
        {
            int l = (1 << k) - c[i], r = 2 * (1 << k) - 1 - c[i];
            cnt += upper_bound(d + 1, d + 1 + n, r) - lower_bound(d + 1, d + 1 + n, l);
            l += (1 << (k + 1)), r += (1 << (k + 1));
            cnt += upper_bound(d + 1, d + 1 + n, r) - lower_bound(d + 1, d + 1 + n, l);
        }
        if (cnt & 1)
            ans |= (1 << k);
    }
    cout << ans;
    return 0;
}