Atcoder Beginner Contest 365

A.Leap Year(模拟)

    判断$n$是否为闰年，根据题意直接模拟即可.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int y, d;
    cin >> y;
    if(y % 4)
        d = 365;
    else if(y % 100)
        d = 366;
    else if(y % 400)
        d = 365;
    else
        d = 366;
    cout << d << endl;
    return 0;
}

B.Second Best(结构体排序)

    求给定数组次大值的下标，使用结构体排序实现查找.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
struct node{
    int val, idx;
    bool operator<(const node x)const{
        return val > x.val;
    }
} a[105];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n;i++)
        cin >> a[i].val, a[i].idx = i;
    sort(a + 1, a + n + 1);
    cout << a[2].idx << endl;
    return 0;
}

C.Transportation Expenses(二分)

题意

    给定$n$个数，第$i$个数的费用是$a_i$,同时给定最高限额$x$和给定最大预算$M$，求$x$的最大值，若$x$的最大值是无穷大，则输出”infinite”.

数据范围

  • $1 \le n \le 2 \times 10^5$
  • $1 \le M \le 2 \times 10^{14}$
  • $1 \le a_i \le 10^9$

思路

    原题可转化为求$\sum\limits_{i=1}^{n} min(a_i,x) \le M$中$x$的最大值；不难发现，当$\sum a_i \le M$时，$x$的值不影响结果，此时可取到无穷大，反之，可通过二分答案的方式求得满足条件的最值.

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
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n;
    i64 m, sum = 0;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n;i++)
        cin >> a[i], sum += a[i];
    if(sum<=m){
        cout << "infinite" << endl;
        return 0;
    }
    i64 l = 1, r = 1E15, ans;
    auto check = [&](i64 x) -> bool
    {
        i64 res = 0;
        for (int i = 1; i <= n;i++)
            res += min(x, (i64)a[i]);
        return res <= m;
    };
    while(l<=r){
        i64 mid = l + r >> 1;
        if(check(mid))
            l = mid + 1, ans = mid;
        else
            r = mid - 1;
    }
    cout << ans << endl;
    return 0;
}

D.AtCoder Janken 3(动态规划)

题意

    Takahashi和Aoki正在玩石头剪刀布，给定一串长度为$n$的字符串表示Aoki在第$i$局游戏中的动作，其中$’R’$表示石头，$’P’$表示布，$’S’$表示剪刀，要求Takahashi的每一局动作必须满足：

  • Takahashi从未输过Aoki
  • Takahashi连续两局的动作必须不同

    求Takahashi最多赢得的局数.

数据范围

  • $1 \le n \le 2 \times 10^5$

思路

    因为当前一局的动作一定与上局有关，并且各个子问题有重叠，所以考虑用动态规划求解。设$dp[i][0/1/2]$表示当前第$i$局使用石头/布/剪刀的最大获胜次数。
    因为当前动作与上一局动作必须不同，转移方程可表示为：

  • $dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + (s[i] == ‘S’);$
  • $dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + (s[i] == ‘R’);$
  • $dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + (s[i] == ‘P’);$

    又因为每一局必不能输，所以当出现状态被$s[i]$”克制“的情况下，将当前状态的$dp$值设为负无穷大，表示无效状态.

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
#include<bits/stdc++.h>
#define inf 1E9
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n;
    string s;
    cin >> n;
    cin >> s;
    s = " " + s;
    vector<vector<int>> dp(n + 1, vector<int>(3, -inf));
    //dp[i][0/1/2]表示当前第i局以石头/布/剪刀结束的最大获胜局数
    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    for (int i = 1; i <= n;i++){
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + (s[i] == 'S');
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + (s[i] == 'R');
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + (s[i] == 'P');
        if(s[i]=='R')
            dp[i][2] = -inf;
        else if(s[i]=='P')
            dp[i][0] = -inf;
        else
            dp[i][1] = -inf;
    }
    cout << max({dp[n][0], dp[n][1], dp[n][2]}) << endl;
    return 0;
}

E.Xor Sigma Problem(位运算)

题意

    给定长度为$N$的正整数序列$A=(A_1,…,A_N)$，求下列式子的值：

数据范围

  • $2 \le n \le 2 \times 10^5$
  • $1 \le A_i \le 10^8$

思路

    位运算的经典思路就是拆位算贡献，因为每一位都是相互独立的。题目求的是区间异或和的总和，对于每一位的二进制值，能产生贡献的区间就是当前区间的异或和等于1，设前$i$个数的第$j$位前缀异或和为$pre[i][j]$，则区间$[l,r] (l<r)$的异或和为$pre[r][bit] \oplus pre[l-1][bit]$.
    由异或的性质知，当两数不同时，异或值才会取得1；枚举右端点$r$，因为$l \le r-1 \Rightarrow l-1 \le r-2$，所以遍历右端点$r$的时候需要知道前$r-2$个数的前缀异或值等于$pre[r][bit] \oplus 1$的数量，最后计数的时候应乘以位权值$(1<<bit)$.
    注意，当$i=0$时，前缀异或值为0的数量为1而不是0！！！

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
#include <bits/stdc++.h>
#define endl '\n'
using i64 = long long;
using namespace std;
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<vector<int>> pre(n + 1, vector<int>(32));  //pre[i][j] 前i个数第j位的前缀异或和
    vector<vector<int>> cnt0(n + 1, vector<int>(32, 1)); //初始化数量必须为1
    vector<vector<int>> cnt1(n + 1, vector<int>(32)); 
    //cnt[i][j] 前i个数第j位前缀值为0/1的个数
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= 30; j++){
            pre[i][j] = pre[i - 1][j];
            cnt0[i][j] = cnt0[i - 1][j];
            cnt1[i][j] = cnt1[i - 1][j];
            pre[i][j] ^= ((a[i] >> j) & 1);
            if (pre[i][j])
                cnt1[i][j]++;
            else
                cnt0[i][j]++;
        }
    }
    i64 ans = 0;
    for (int i = 2; i <= n;i++)
        for (int j = 0; j <= 30;j++)
            ans += (pre[i][j] ? cnt0[i - 2][j] : cnt1[i - 2][j]) * (1LL << j);
    cout << ans << endl;
    return 0;
}