模拟赛题讲解[20]

来自 AprilGrimoire 2022-08-09 noi.ac #2775

题目描述：

小 Z 想出几道送分题。

小 Z 有一列脑洞（共 $m(m \leq 10^9)$ 个）。脑洞分为白色与黑色，白色脑洞会让题目难度降低，黑色脑洞会让题目难度提高。因为小 Z 很懒，她决定将脑洞分为连续的若干段，将每段缝合成一道送分题。为了达到雨露均沾的送分效果，小 Z 希望每段中黑色脑洞所占的比例相同。小 Z 想知道她最多能缝合出几道题？

输入格式：

第一行一个整数 $n(n \leq 10^6)$

接下来 $n$ 行按顺序描述了小 Z 的脑洞。其中第 $i$ 行一个正整数 $r_i$ 和字符 $w_i$。这表示接下来有连续 $r_i$个颜色为 $w_i$ 的脑洞（ W 代表白色，B 代表黑色）。

输出格式：

一行一个整数，表示小 Z 最多能缝合出的题目数。

输入1：

1 B
1 W
2 W
2 B
1 W
1 B

输出1：

输入2：

1 W
2 W
1 B
2 B
1 W
4 B
1 B
2 B
1 B
1 B

输出2：

输入3：

1 B
1 B
1 W
1 W
1 B
1 B
1 B
1 W
1 B
1 W
1 B
1 B
1 W
1 W
1 W
1 B
1 W
1 B
1 B
1 B

输出3：

数据规模与约定：

时空限制：1s,512MiB

对于所有数据，保证 $n \leq 10^6$

子任务一（25pts）：满足 $n \leq 20, r_i=1$

子任务二（25pts）：满足 $n \leq 1000, r_i=1$

子任务三（20pts）：满足 $n \leq 1000$

子任务四（30pts）：无特殊约定

题解：

注意到其实这个比例是固定的，我们直接暴力扫即可

也就是说，每一段的比例等于整个序列的比例

一个比较有趣的理解是，

DNA双链上，每一条链都有 $20\%$ 的 $A$ ，那么整个双链就有 $20\%$ 的 $A$

那就直接从左往右扫，然后每ok就立刻分为一段

这里用gcd什么的可以更精确，但是我选择double

时间复杂度 $O(n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define double long double
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e6+15)

const double eps=1e-13;
int n,s1,s2,t1,t2,res=0;
struct node{int x; char c;}a[N];
int dcmp(double x)
{
    if(fabs(x)<=eps) return 0;
    return x>eps?1:-1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; char ch;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i].x >> a[i].c;
        if(a[i].c=='W') s1+=a[i].x;
        if(a[i].c=='B') s2+=a[i].x;
    }
    if(!s1) return cout << s2 << '\n',0; // no w
    if(!s2) return cout << s1 << '\n',0; // no b
    double k=1.0*s1/s2;
    for(int i=1; i<=n+1; i++)
    {
        if(t1&&t2&&!dcmp(1.0*t1/t2-k))
            ++res,t1=t2=0;
        if(a[i].c=='W') t1+=a[i].x;
        else t2+=a[i].x;
    }
    cout << res << '\n';
    return 0;
}