AtCoder Beginner Contest 381-E

发表于 阅读次数： 本文字数： 856 阅读时长 ≈ 3 分钟

Problem

一个长度为奇数、最中间的那个字符是 /、左边所有字符都是都是 1、右边所有字符都是 2 的字符串被称为11/22 字符串。

更加严谨的定义：

当一个字符串 $T$ 满足以下所有条件时，它被称为11/22 字符串：

  • $|T|$ 是奇数。这里， $|T|$ 表示 $T$ 的长度。
  • 从第 $1$ 到第$(\frac{|T|+1}{2} - 1)$ 个字符都是 1。
  • 第 $(\frac{|T|+1}{2})$ 个字符是/。
  • 从第 $(\frac{|T|+1}{2} + 1)$ 到第 $|T|$ 的字符都是 2。

例如，11/22、111/222和/是 11/22 字符串，但1122、1/222、11/222、22/11和/2/2/211则不是。

给定由1、2和/组成的字符串 $S$ ，$|S|=N$。有 $Q$ 次询问：给定 $L$ 和 $R$，设 $T$ 是 $S$ 的从第 $L$ 个字符到第 $R$ 个字符组成的子串。请找出 $T$ 的最长子序列使得该子序列是一个 11/22 字符串。如果不存在这样的子序列，则打印 “0”。

Constraints

  • $1 \leq N \leq 10^5$
  • $1 \leq Q \leq 10^5$
  • $S$ is a string of length $N$ consisting of 1, 2, and /.
  • $1 \leq L \leq R \leq N$
  • $N$, $Q$, $L$, and $R$ are integers.

Solution

考虑预处理出所有/的位置，记作 $pos_i$。

使用前缀和后缀和计算“每一个字符之前有多少个1”和“每一个字符之后有多少个2”，分别记作 $left1_i$ 和 $right2_i$。

对于每次询问，一个简单暴力的算法就是，枚举在该区间内的所有/，并看看其左右分别有多少个1和2，则选择该/作为11/22子串的中间的那个/能够找出的最长子序列长度为

即可以利用预处理的信息，在$O(1)$的时间复杂度内计算出选择某个/时的答案。

并且可以通过二分 $pos_i$ 来得到需要枚举的 $i$ 的范围。

但是这样还是需要枚举 $[L,R]$ 内的所有/，如果/很多就寄了。

观察上式可以发现，随着 $posi$ 增大，$left1{posi}-left1_L$ 单调递增，$right2{pos_i}-right2_R$ 单调递减。$\min{增函数,减函数}$ 一定是一个开口向下的单峰函数，所以可以使用三分来确定最佳的 $pos_i$。

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
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
#define N 1000010


int left1[N],left2[N],right1[N],right2[N];
int n,q;
string str;
int pos[N],cnt;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
//    cin>>t;
    while(t--)
    {
        cin>>n>>q;
        cin>>str;
        str=" "+str;
//        pos[++cnt]=0;
        for(int i=1;i<=n;i++)
        {
            if(str[i]=='/')
            {
                pos[++cnt]=i;
            }
        }
        pos[++cnt]=n+1;
        int pre1=0,pre2=0;
        for(int i=1;i<=n;i++)
        {
            left1[i]=pre1;
            left2[i]=pre2;
            if(str[i]=='1') pre1++;
            if(str[i]=='2') pre2++;
        }	
        pre1=pre2=0;
        for(int i=n;i>=1;i--)
        {
            right1[i]=pre1;
            right2[i]=pre2;
            if(str[i]=='1') pre1++;
            if(str[i]=='2') pre2++;
        }
        
        while(q--)
        {
            int a,b,ans=0;cin>>a>>b;
            // 确定左右边界，即找到最远的一对杠但是在[a,b]之内
            int l=lower_bound(pos+1,pos+cnt+1,a)-pos;
            int r=upper_bound(pos+1,pos+cnt+1,b)-pos-1;
//            DEBUG1(l);
//            DEBUG1(r);
            while(l+3000<r)
            {
                int mid1=l+(r-l)/3;
                int mid2=r-(r-l)/3;
                int p1=pos[mid1],p2=pos[mid2];
                int s1=min(left1[p1]-left1[a],right2[p1]-right2[b]);
                int s2=min(left1[p2]-left1[a],right2[p2]-right2[b]);
                if(s1<s2)
                {
                    l=mid1;
                }
                else{
                    r=mid2;
                }
            }
            for(int i=l;i<=r;i++)
            {
                int p=pos[i];
                if(str[p]=='/')
                {
//                    cout<<"calc "<<i<<endl;
//                    cout<<min(left1[p]-left1[a],right2[p]-right2[b])<<endl;
                    ans=max(ans,1+2*min(left1[p]-left1[a],right2[p]-right2[b]));
                }
            }
            cout<<ans<<endl;
        }
        
    }
    return 0;
}