当前位置:   article > 正文

AtCoder Beginner Contest 359 A~F_atcoder 359

atcoder 359

A.Count Takahashi

题意

给出 N N N个字符串,每个字符串为以下两种字符串之一:

  • "Takahashi"

  • "Aoki"

请你统计"Takahashi"出现了多少次。

分析

输入并统计即可。

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s[0] == 'T') ans++;
    }
    cout << ans << endl;
}

int main() {
    solve();
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

B. Couples

题意

N N N对人,每队人身上都穿着相同颜色的衣服,保证每种颜色只会出现两次(即只有同一对人才能拥有相同颜色)。

问:存在多少个人,同时与两个相同颜色衣服的人相邻?

分析

输入后依次判断是否存在第 i i i个人和第 i − 2 i - 2 i2个人衣服颜色相同即可。

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 3e5 + 5e2;
int a[N];

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= 2 * n; i++) {
        cin >> a[i];
        if (i >= 3 && a[i] == a[i - 2]) ans++;
    }
    cout << ans << endl;
}

int main() {
    solve();
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

C.Tile Distance 2(思维)

题意

有一个由大小为 2 × 1 2 \times 1 2×1的瓷砖铺成的平面,其中使用 ( x , y ) (x, y) (x,y)表示位于坐标 ( x + 0.5 , y + 0.5 ) (x + 0.5, y + 0.5) (x+0.5,y+0.5)的网格所在的位置。

问,从瓷砖 ( S x , S y ) (S_{x}, S_{y}) (Sx,Sy)走到瓷砖 ( T x , T y ) (T_{x}, T{y}) (Tx,Ty)最少仅需要经过多少个瓷砖(不包含起点)?

分析

不难发现,每块瓷砖的左半部分的 x , y x, y x,y坐标之和必然为偶数,右半部分的 x , y x, y x,y坐标之和必然为奇数。因此,为了便于处理,可以将输入的两个坐标均移动到瓷砖的左半边,此时不需要经过其他瓷砖。

然后考虑怎么移动最优,可以想到,每次向上或向下移动后,均可以再横向移动一次,此时也不需要经过其他瓷砖,即一次移动可以使两个瓷砖的行列坐标均接近 1 1 1,那么只需要经过 m i n ( ∣ S x − T x ∣ , ∣ S y − T y ∣ ) min(|S_x - T_x|, |S_y - T_y|) min(SxTx,SyTy)次操作,就能保证其中一个坐标相等了。

然后考虑此时的两种情况:

  1. x x x坐标不相等,需要当前的 x x x坐标之差除以二的操作次数

  2. y y y坐标不相等,需要当前的 y y y坐标之差的操作次数

X , Y X, Y X,Y为两个点的 x , y x, y x,y坐标之差的绝对值。

对于情况1,不难发现每次操作均能使两个点的曼哈顿距离接近 2 2 2,共需 X + Y 2 \frac{X + Y}{2} 2X+Y次操作。

对于情况2,不难发现需要的操作次数为 Y Y Y,为便于计算,将操作次数变为 Y + Y 2 \frac{Y + Y}{2} 2Y+Y

两式结合,操作次数变为 m a x ( X , Y ) + Y 2 \frac{max(X, Y) + Y}{2} 2max(X,Y)+Y,按公式计算输出即可。

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 3e5 + 5e2;
int a[N];

void solve() {
    ll sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    if (sx + sy & 1) sx--;
    if (tx + ty & 1) tx--;
    ll x = abs(sx - tx);
    ll y = abs(sy - ty);
    ll ans = (y + max(x, y)) / 2;
    cout << ans << endl;
}

int main() {
    solve();
    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.Avoid K Palindrome(动态规划)

题意:

给你一个长度为 N N N的字符串 S S S,由字符AB?组成。

同时给你一个正整数 K K K。如果满足以下条件,那么由AB组成的字符串 T T T就是一个好字符串

  • T T T中,长度为 K K K的连续子串不是回文。

q q q S S S中的?字符数量,用AB替换 S S S中的每个?,可以得到 2 q 2^q 2q个字符串。请找出其中有多少个字符串是好字符串。

这个数目可能非常大,答案对 998244353 998244353 998244353取模。

分析:

从左到右考虑每个字符,如果当前是?,则考虑其变为 A A A, B B B,是否出现长度为 k k k的回文串。

我们需要知道该? k − 1 k−1 k1位的情况,加上该字母,就可以判断出新增的子串是不是回文串。

即设 d p i , j dp_{i,j} dpi,j表示考虑前 i i i位字符,其中?都已经替换成 A A A B B B后,且后 9 9 9位的字符状态为 j j j(因为只有 A B AB AB两种,可以编码成 01 01 01,用二进制压缩表示)。

然后考虑当前位的情况,如果取值为 A A A 0 0 0,则判断 j < < 1 j<<1 j<<1状态是不是回文串,不是的话则有 d p i + 1 , ( j < < 1 ) & m a s k + = d p i , j dp_{i+1,(j<<1) \&mask}+=dp_{i,j} dpi+1,(j<<1)&mask+=dpi,j,否则就状态非法,不转移。因为 j < < 1 j<<1 j<<1是后 10 10 10个字符的状态信息,而 j j j的含义是后 9 9 9位,所以 & m a s k \&mask &mask是把第 10 10 10位去掉。

同理,取值为 B B B的话,即 1 1 1,则判断 ( j < < 1 ) ∣ 1 (j<<1)|1 (j<<1)∣1是不是回文串,不是的话就转移,否则不转移。事先预处理每个状态是否是回文串,然后当 i ≥ k i≥k ik时再考虑转移的合法性。

代码:

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const int MOD = 998244353;

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    int up = (1 << k);
    vector<int> p(up);
    for (int i = 0; i < up; i++) {
        vector<int> bit(k);
        int num = i;
        for (int j = 0; j < k; j++) {
            bit[j] = (num & 1);
            num >>= 1;
        }
        auto rev = bit;
        reverse(rev.begin(), rev.end());
        p[i] = rev == bit;
    }

    up = 1 << (k - 1);
    int mask = up - 1;
    vector<int> dp(up, 0);
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        int chr = s[i];
        vector<int> dp2(up, 0);
        for (int j = 0; j < up; j++) {
            if (chr == '?') {
                if (i + 1 < k || !p[j << 1]) {
                    int nxt = (j << 1) & mask;
                    dp2[nxt] = (dp2[nxt] + dp[j]) % MOD;
                }
                if (i + 1 < k || !p[j << 1 | 1]) {
                    int nxt = (j << 1 | 1) & mask;
                    dp2[nxt] = (dp2[nxt] + dp[j]) % MOD;
                }
            } else {
                if (i + 1 < k || !p[j << 1 | (chr - 'A')]) {
                    int nxt = (j << 1 | (chr - 'A')) & mask;
                    dp2[nxt] = (dp2[nxt] + dp[j]) % MOD;
                }
            }
        }
        dp.swap(dp2);
    }
    LL ans = 0;
    for (int i = 0; i < up; i++) {
        ans = (ans + dp[i]) % MOD;
    }
    cout << ans << 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
  • 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

E.Water Tank(单调栈)

题意:

给你一个长度为 N N N的正整数序列: H = ( H 1 , H 2 , … , H N ) H=(H_1,H_2,\dotsc,H_N) H=(H1,H2,,HN)

有一个长度为 N + 1 N+1 N+1的非负整数序列: A = ( A 0 , A 1 , … , A N ) A=(A_0,A_1,\dotsc,A_N) A=(A0,A1,,AN)。最初为 A 0 = A 1 = ⋯ = A N = 0 A_0=A_1=\dotsb=A_N=0 A0=A1==AN=0

A A A重复进行以下运算:

  1. A 0 A_0 A0的值增加 1 1 1
  2. 依次对 i = 1 , 2 , … , N i=1,2,\ldots,N i=1,2,,N进行以下操作:
    • 如果 A i − 1 > A i A_{i-1}\gt A_i Ai1>Ai A i − 1 > H i A_{i-1}\gt H_i Ai1>Hi,则将 A i − 1 A_{i-1} Ai1的值减少 1 1 1,并将 A i A_i Ai的值增加 1 1 1

求每个 i = 1 , 2 , … , N i=1,2,\ldots,N i=1,2,,N A i > 0 A_i\gt 0 Ai>0第一次成立之前的运算次数。

分析:

观察样例,模拟一下,很容易发现如果要求第 i i i位的答案,则要求之前的第 i − 1 i−1 i1位装满,即和柱子 a i a_i ai高度一样,而高度一样要求 i − 2 , i − 3 , … i−2,i−3,\dots i2,i3,位高度也一样。观察上述会发现,假设前面比柱子 a i a_i ai还高的柱子是 a j a_j aj,那么 j , j + 1 , … , i − 1 j,j+1,\dots,i−1 j,j+1,,i1位的水高都必须是 a i a_i ai

因此,求解第 i i i位的答案,则需要 i − 1 , i − 2 , … , j i−1,i−2,\dots,j i1,i2,,j位与 a i a_i ai高度相同,然后 j − 1 , j − 2 , … , k j−1,j−2,\dots,k j1,j2,,k a j a_j aj高度相同, k − 1 , k − 2 , … k−1,k−2,\dots k1,k2, a k a_k ak高度相同,其中 a i ≤ a j ≤ a k a_i≤a_j≤a_k aiajak,需要维护一个从左到右,柱子高度单调递减的序列,可以用单调栈进行维护,栈底是最左边,栈顶是最右边。在维护递减高度时,同时维护每个递减区间的水高度总和即可。

代码:

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const int MOD = 998244353;
int n;

int main() {
    cin >> n;
    LL ans = 1;
    vector<pair<int, int>> f;
    f.emplace_back(0, INT_MAX);
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        int lst, lx;
        while (f.back().second <= x) {
            lst = f.back().first;
            lx = f.back().second;
            f.pop_back();
            ans -= 1ll * (lst - f.back().first) * lx;
        }
        ans += 1ll * x * (i - f.back().first);
        f.emplace_back(i, x);
        cout << ans << " ";
    }
    cout << 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
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

F.Tree Degree Optimization(树、优先队列)

题意:

问题陈述

给你一个整数序列 A = ( A 1 , … , A N ) A=(A_1,\ldots,A_N) A=(A1,,AN)。对于一棵有 N N N个顶点的树 T T T,定义 f ( T ) f(T) f(T)如下:

  • d i d_i di T T T中顶点 i i i的度数。那么, f ( T ) = ∑ i = 1 N d i 2 A i f(T)=\sum\limits_{i=1}^N{d_i}^2 A_i f(T)=i=1Ndi2Ai

f ( T ) f(T) f(T)的最小可能值。

约束条件保证答案小于 2 63 2^{63} 263

分析:

由于是一棵树,则满足:

  • ∀ 1 ≤ i ≤ n , d i ≥ 1 ∀1≤i≤n,d_i≥1 ∀1in,di1
  • ∑ d i = 2 n − 2 , 1 ≤ d i ≤ n − 1 \sum d_i=2n−2,1≤d_i≤n−1 di=2n2,1din1

对于任意满足上述条件的 d i d_i di,都可以构造出对应的树,使得每个点的度数都是 d i d_i di。构造方法为每次选择度数为 1 1 1和非 1 1 1的点连边,然后更新剩余度数。

下面考虑如何分配这些度数。

如果给点 1 1 1分配一个度,是其 d 1 = 1 → 2 d_1=1→2 d1=12,则代价是 4 a 1 − a 1 4a_1−a_1 4a1a1,而如果是 d 1 = 2 → 3 d_1=2→3 d1=23,则代价是 9 a 1 − 4 a 1 9a_1−4a_1 9a14a1

我们考虑贪心的做法,直接先把全部 d i d_i di赋上 1 1 1的权值,然后把剩下的 n − 2 n−2 n2个度分配给每个点,使得代价最小,每次仅分配 1 1 1的度,贪心的将其分配给代价最小的点。用优先队列维护上述代价即可。

代码:

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 200005;
const int MOD = 998244353;

int n, a[N], d[N];
LL ans;
priority_queue<pair<LL, int>, vector<pair<LL, int> >, greater<pair<LL, int> > > q;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ans += a[i];
        d[i] = 1;
        q.emplace(3ll * a[i], i);
    }
    for (int i = 1; i <= n - 2; i++) {
        int id = q.top().second;
        ans += q.top().first;
        q.pop();
        d[id]++;
        q.emplace(a[id] * (d[id] * 2ll + 1), id);
    }
    cout << ans << 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
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

赛后交流

在比赛结束后,会在交流群中给出比赛题解,同学们可以在赛后查看题解进行补题。

群号: 704572101,赛后大家可以一起交流做题思路,分享做题技巧,欢迎大家的加入。

本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/煮酒与君饮/article/detail/877198
推荐阅读
相关标签
  

闽ICP备14008679号