Atcoder Beginner Contest 236

By xiaruize 2022年1月23日

A - chukodai

Method & Code

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;

int main()
{
  string s;
  cin>>s;
  int a,b;
  cin>>a>>b;
  swap(s[a-1],s[b-1]);
  cout<<s<<endl;
  return 0;
}

B - Who is missing?

Method & Code

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
#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <bitset>
#include <valarray>
#include <algorithm>
#include <functional>
#include <numeric>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
using namespace std;
#define int long long
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define pis pair<int,string>
#define sec second
#define ll long long
#define fir first
#define sz(a) int((a).size())
#define double long double
#define INF 0x3f3f3f3f
const int N=1e5+10;

int n;
int a[N];
int cnt[N];

signed main()
{
 	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n;
	for(int i=1;i<=n*4-1;i++)
	{
		cin>>a[i];
		cnt[a[i]]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(cnt[i]==3)
		{
			cout<<i<<endl;
			break;
		}
	}
	return 0;
}

C - Route Map

Method

map维护暴力统计

Code

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
// Problem: C - Route Map
// Contest: AtCoder - AtCoder Beginner Contest 236
// URL: https://atcoder.jp/contests/abc236/tasks/abc236_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// TestType: single
//
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define ll long long
#define fir first
#define sz(a) int((a).size())
#define double long double
#define INF 0x3f3f3f3f
#define debug(c, x) cerr << c << ':' << x << endl;
const int N = 1e5 + 10;

// bool st;
int n, m;
string s[N];
map<string, bool> mp;
// bool en;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    for (int i = 1; i <= m; i++)
    {
        string p;
        cin >> p;
        mp[p] = true;
    }
    for (int i = 1; i <= n; i++)
    {
        if (mp[s[i]])
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

D - Dance

Method

暴力出奇迹

Code

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
78
// Problem: D - Dance
// Contest: AtCoder - AtCoder Beginner Contest 236
// URL: https://atcoder.jp/contests/abc236/tasks/abc236_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// TestType: single
//
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define ll long long
#define fir first
#define sz(a) int((a).size())
#define double long double
#define INF 0x3f3f3f3f
#define debug(c, x) cerr << c << ':' << x << endl;
const int N = 1e5 + 10;

// bool st;
int n;
int a[20][20];
bool vis[20];
int ans = 0;
// bool en;

void calc(int x, int now)
{
    // cerr << x << ' ' << now << endl;
    if (x == 2 * n + 1)
    {
        ans = max(ans, now);
    }
    if (vis[x])
    {
        calc(x + 1, now);
        return;
    }
    for (int i = x + 1; i <= n * 2; i++)
    {
        if (!vis[i])
        {
            vis[x] = vis[i] = true;
            calc(x + 1, now ^ a[x][i]);
            vis[x] = vis[i] = false;
        }
    }
    return;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n;
    for (int i = 1; i <= 2 * n; i++)
    {
        for (int j = i + 1; j <= 2 * n; j++)
        {
            cin >> a[i][j];
        }
    }
    calc(1, 0);
    cout << ans << endl;
    return 0;
}

E - Average and Median

Method

本题分为两个部分：平均值和中位数

Part 1：平均值

明显满足单调性，可以二分

O(logn)O(logn)的复杂度

∴\therefore 需要O(N) checkO(N)\ check

考虑dpi,0/1dp_{i,0/1}表示当前到第ii个数，0/1为当前数选或不选

有转移方程，其中xx为当前checkcheck的数：

dpi,1=max(dpi−1,0,dpi−1,1)+ai−xdpi,0=dpi−1,1dp_{i,1}=max(dp_{i-1,0},dp_{i-1,1})+a_{i}-x\\ dp_{i,0}=dp_{i-1,1}

Part 2:中位数

模仿平均数，见代码。。。

Code

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// Problem: E - Average and Median
// Contest: AtCoder - AtCoder Beginner Contest 236
// URL: https://atcoder.jp/contests/abc236/tasks/abc236_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// TestType: single
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define double long double
#define INF 0x3f3f3f3f
#define debug(c, x) cerr << c << ':' << x << endl;
const int N = 1e5 + 10;

// bool st;
int n;
int a[N];
double b[N];
int c[N];
double dp[N][3];
int d[N];
int f[N][3];
// bool en;

bool check1(double x)
{
    for (int i = 1; i <= n; i++)
    {
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]) + b[i];
        dp[i][0] = dp[i - 1][1];
    }
    if (max(dp[n][0], dp[n][1]) >= 0)
        return true;
    return false;
}

bool check2(int x)
{
    for (int i = 1; i <= n; i++)
    {
        if (a[i] >= c[x])
            d[i] = 1;
        else
            d[i] = -1;
    }
    f[0][0] = f[0][1] = -1;
    for (int i = 1; i <= n; i++)
    {
        f[i][0] = f[i - 1][1];
        f[i][1] = max(f[i - 1][1], f[i - 1][0]) + d[i];
    }
    if (max(f[n][1], f[n][0]) >= 0)
        return true;
    return false;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], c[i] = a[i];
    sort(c + 1, c + n + 1);
    double l = 1.0, r = 1e9 * 1.0;
    while (r - l >= 1e-6)
    {
        double mid = (r + l) / 2;
        for (int i = 1; i <= n; i++)
            b[i] = a[i] - mid;
        if (check1(mid))
            l = mid;
        else
            r = mid;
    }
    int ll = 1, rr = n;
    while (ll < rr)
    {
        int mid = (ll + rr + 1) >> 1;
        if (check2(mid))
            ll = mid;
        else
            rr = mid - 1;
    }
    cout << l << endl << c[ll] << endl;
    return 0;
}