P7300 [USACO21JAN] No Time to Paint S 题解

题目描述

image-20250708123508887

思路

我们可以把这道题的输入数据想象成一个一座山,有很多个山峰和山谷。

我们从左往右计算,如果正在上山,那么答案增加一。下山的时候,如果这个点在上山的时候已经出现过了,就不统计,只是消除比这个点高的点的记录(因外后面如果出现比这个点高的点,那么也不是这座山峰了),否则统计。

我们发现这个其实可以做成前缀和,如果想获得从第一个到第 $i$ 个点的答案就按前缀和去计算。

回到题目,我们发现一整座山有可能被空白的分隔成两座了,对于左边的的那座山,可以直接计算。但是对于右边的山,我们无法确定这个山有哪些点被统计过,所以这道题我们之前统计的数组没法按前缀和去计算任意区间答案,所以我们采取从后往前的前缀和来处理。

以后遇到前缀和无法计算任意区间的答案,但是可以计算从 $1$ 开始的,而且题目只需要求从第一个开始的或者从最后一个结束的,或者题目可以变幻成这样的形式的,我们都可以用两个前缀和来做。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
/*
*/
int a[1000005];
int b[1000005], p1[1000005], p2[1000005], vis[1000005];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    string s; cin >> s;
    for (int i = 1; i <= n; i ++) a[i] = s[i - 1] - 'A' + 1;
    for (int i = 1; i <= n; i ++) {
        if (a[i - 1] < a[i] || i == 1) p1[i] = 1, vis[a[i]] = 1;
        else if (a[i - 1] > a[i]) {
            p1[i] = (vis[a[i]] ? 0 : 1);
            vis[a[i]] = 1;
            for (int j = a[i] + 1; j <= 27; j ++) {
                vis[j] = 0;
            }
        }
    }
    memset(vis, 0, sizeof(vis));
    for (int i = n; i >= 1; i --) {
        if (a[i + 1] < a[i] || i == n) p2[i] = 1, vis[a[i]] = 1;
        else if (a[i + 1] > a[i]) {
            p2[i] = (vis[a[i]] ? 0 : 1);
            vis[a[i]] = 1;
            for (int j = a[i] + 1; j <= 27; j ++) {
                vis[j] = 0;
            }
        }
    }
    for (int i = n; i >= 1; i --) p2[i] += p2[i + 1];
    for (int i = 1; i <= n; i ++) p1[i] += p1[i - 1];
    for (int i = 1; i <= q; i ++) {
        int x, y; cin >> x >> y;
        int ans = 0;
        if (x != 1) ans += p1[x - 1];
        if (y != n) ans += p2[y + 1];
//      if (x == 1) ans --;
//      if (y == n) ans --;
        cout << ans << "\n";
    } 
    return 0;
}
本文链接:https://ztrztr.top/archives/1009
版权声明:本文 《P7300 [USACO21JAN] No Time to Paint S 题解》 为 ztrztr 原创。著作权归作者所有。
转载说明:联系作者或者评论区留言获得转载授权,并注明转载地址。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇