牛客周赛 Round 28

发表于 更新于 分类于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 7 分钟
All it takes is faith and trust.

A. 小红的新周赛

思路：

  • 求和即可

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::array<int, 6> a {};
    for (int &i : a) {
        std::cin >> i;
    }

    std::cout << std::accumulate(a.begin(), a.end(), 0) << "\n";
    
    return 0;
}

B. 小红的字符串

思路：

  • 我们将 的后 个字符接到 ​ 后面(注意奇偶)，然后遍历即可

时间复杂度：

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string s;
    std::cin >> s;

    int n = s.size();

    std::string tmp;
    tmp = s.substr(1);

    if (n & 1) s.pop_back();
    s += tmp;

    std::vector<std::string> a;
    for (int i = 0; i + 2 <= s.size(); i += 2) {
        a.push_back(s.substr(i, 2));
    }

    std::sort(a.begin(), a.end());

    for (int i = 0; i < a.size(); i++) {
        std::cout << a[i] << "\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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m, k;
    std::cin >> n >> m >> k;

    std::map<int, int> h;
    for (int i = 1; i <= m; i++) {
        h[i] = n;
    }

    for (int i = 0; i < k; i++) {
        int x, y;
        std::cin >> x >> y;
        x = n - x + 1;
        int hight = h[y];
        if (x <= hight) {
            h[y]--;
        }
    }

    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= m; j++) {
            if (h[j] < i) {
                std::cout << ".";
            } else {
                std::cout << "*";
            }
        }
        std::cout << "\n";
    }

    return 0;
}

D. 小红统计区间（easy）

思路：

  • 二分或者双指针，因为 ​ 都是正整数，所以和是递增的，具有单调性

时间复杂度：

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    i64 k;
    std::cin >> n >> k;

    std::vector<int> a(n);
    std::vector<i64> s(n + 1);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        s[i + 1] = s[i] + a[i];
    }

    s.push_back(0);
    i64 ans = 0;
    for (int i = 1; i <= n; i++) {
        int l = i, r = n + 1;
        while (l <= r) {
            int mid = l + r >> 1;
            auto check = [&](int x) {
                i64 sum = s[x] - s[i - 1];
                return sum < k;
            };
            if (check(mid)) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (l > n) continue ;
        ans += n - l + 1;
    }
    std::cout << ans << "\n";

    return 0;
}

E. 小红的好数组

思路：

  • 首先看一下好数组的性质

    • 连续3个数的子数组之和都是偶数，那么可以发现，只能是3个偶数或者2个奇数和1个偶数，这两种情况，具体证明是

    • 也就是说任意下标mod 3相同的数的奇偶性是相同的

  • 那么数组只能有以下四种型式

    • [偶, 偶, 偶...]
    • [奇, 偶, 奇...]
    • [奇, 奇, 偶...]
    • [偶, 奇, 奇...]

  • 统计每种形式的数量即可，需要使用乘法原理进行统计，并使用快速幂进行加速。

时间复杂度：

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template<i64 P>
struct MLong {
    i64 x;
    constexpr MLong() : x{} {}
    constexpr MLong(i64 x) : x{norm(x % getMod())} {}
    
    static i64 Mod;
    constexpr static i64 getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(i64 Mod_) {
        Mod = Mod_;
    }
    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr i64 val() const {
        return x;
    }
    explicit constexpr operator i64() const {
        return x;
    }
    constexpr MLong operator-() const {
        MLong res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MLong inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MLong &operator*=(MLong rhs) & {
        x = mul(x, rhs.x, getMod());
        return *this;
    }
    constexpr MLong &operator+=(MLong rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MLong &operator-=(MLong rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MLong &operator/=(MLong rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MLong operator*(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MLong operator+(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MLong operator-(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MLong operator/(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
        i64 v;
        is >> v;
        a = MLong(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MLong lhs, MLong rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MLong lhs, MLong rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;

template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}
    
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 1000000007;
using Z = MInt<P>;

// std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    i64 k;
    std::cin >> n >> k;

    Z even = k / 2, odd = (k + 1) / 2;

    // 全部都是偶数
    Z ans = power(even, n);
    // 两个奇数一个偶数
    Z mul = power(odd * odd * even, n / 3);

    if (n % 3 == 1) {
        mul *= (odd * 2 + even);
    } else if (n % 3 == 2) {
        mul *= (odd * odd + odd * even * 2);
    } else {
        mul *= 3;
    }
    ans += mul;

    std::cout << ans << "\n";

    return 0;
}
/*
4 2

2 2

1 1 2 1
1 2 1 1
2 1 1 2
2 2 2 2

*/

F. 小红统计区间（hard）

思路：

  • 在 的基础上，增加了负数，那么这个前缀和数组的单调性就不在了，需要考虑新的解法
  • 枚举 ，我们需要统计存在多少个 ，那么可以查询有多少个 满足这个条件，然后再将 加入树状数组中
  • 离散化，将数据范围从

时间复杂度：

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
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    /* 数组a为处理后的数组，下标从1开始，a[i]即原数组arr[i]位置和前lowbit(i) - 1个元素
    的和（即总长度为lowbit(i)）*/
    void add(int x, const T &v) { // 更新下标为x 的元素值加v
        for (int i = x; i < n; i += i & -i) { // n为当前数组长度
            a[i] = a[i] + v; // lowbit(i) 父节点
        }
    }
    
    T sum(int x) {
        T ans{}; // 求前x个的元素的和，1~x(包含x)
        for (int i = x; i > 0; i -= i & -i) { // 前缀和
            ans = ans + a[i];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    i64 k;
    std::cin >> n >> k;

    std::vector<int> a(n);
    std::vector<i64> s(n + 1);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        s[i + 1] = s[i] + a[i];
    }
    //将前缀和进行离散化
    std::vector<i64> v;
    for (int i = 0; i <= n; i++) {
        v.push_back(s[i]);
    }

    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());

    //反向映射离散化数组
    std::map<i64, i64> mp;
    for (int i = 0; i < v.size(); i++) {
        mp[v[i]] = i + 1;
    }

    Fenwick<i64> fen(n + 1);
    fen.add(mp[0], 1); //将初始前缀和（即sum[0]=0）对应的离散化下标插入树状数组

    i64 res = 0;
    for (int i = 1; i <= n; i++) {
        // 要寻找从位置i开始的区间和大于k的区间，则寻找前缀和小于等于sum[i]-k的位置之前的所有元素个数
        int p = std::upper_bound(v.begin(), v.end(), s[i] - k) - v.begin();
        if (p <= n) {
            res += fen.sum(p);
        }
        fen.add(mp[s[i]], 1);
    }
    std::cout << res << "\n";

    return 0;
}