day1

这玩意不是期望DP,而是计数DP....

计数DP一般的计算方式就是通过枚举一个确定含有某个值的小状态,与除这个小状态的其他状态进行一些玄学的操作,之后归到一个大状态上。

这道题可以考虑枚举子树大小,以及深度来进行求解。

初始状态:$f_{1,1}=1,f_{2,2}=1$

观察到$2$一定是$1$的子节点,那么单独来看,以$2$为根的时候,就是一个独立子问题。

外层枚举整棵树的大小,以及深度。

那么可以内层枚举一些点与$2$形成一棵子树,并枚举以$2$为根的子树深度(注意深度限制)。

求出答案后,带个权再除以总方案数,就是期望深度。

day2

$(i,j)->(i+1,j)$的代价,也就是判断$(a_i==b_j)$是否等于$(a_{i+1}==b_{j})$,与$b_j$无关 ,因此竖着的边的代价可以简化为$bool$表达式$[a_i\ne a_{i+1}] $。
$(i,j)->(i,j+1)$的代价,也就是判断($a_i==b_j$)是否等于$(a_i==b_{j+1})$,与$a_i$无关 ,因此横着的边的代价可以简化为$bool$表达式$[b_j\ne b_{j+1}]$ 。

对于同一行或者同一列,可以考虑用前缀和记录$1\sim i$中相邻的不同对数。
拓展到两维,由于可能路径可能宛转如流水,但竖着的边与横着的边的数量都是固定的,且互不影响(用简化的bool表达式子看,容易理解为什么互不影响) ,可以把它掰直$233$,掰成两条线段。
因此可以考虑(竖看一个环,横看一个环)环的一端走向另外一端有两条路径,分别取最小的就好了。

dayinf

一道贪心好题。

把$C$当作$1$,把$T$当作$-1$

考虑一种朴素的贪心思路,尽量地去匹配$C$,$T$。对于任意的后缀,从前往后线性扫,若碰到$-1$,使得和为$-1$,那么删掉,和变为$0$,同理,也对前缀进行一遍,答案就为两个取$max$。

由于是多组询问,考虑离线。

使右端点单调递增,边扫边处理后缀,删掉一些$T$,使得任意的后缀都满足$\ge 0$。

用栈把可能要删掉的$T$储存起来,如果碰到一个$C$,则取出栈顶,消掉。

考虑这样做的正确性,由于删掉的$T$的位置是最靠后的,对前缀的影响是最小的,因此更有利于答案的贡献。

之后打个线段树去维护每一个前缀就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
const int N=5e5+5;
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar(x%10+48);
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct Seg{int mn,ad;}t[N<<2];//线段树维护前缀。
inline void pushdown(int p)
{
    t[p<<1].mn+=t[p].ad,t[p<<1|1].mn+=t[p].ad;
    t[p<<1].ad+=t[p].ad,t[p<<1|1].ad+=t[p].ad;
    t[p].ad=0;
}
void change(int p,int l,int r,int x,int val)
{
    if(l==r){t[p].mn+=val;return ;}
    int mid=l+r>>1;
    pushdown(p);
    if(x<=mid)change(p<<1,l,mid,x,val);
    else change(p<<1|1,mid+1,r,x,val);
    t[p].mn=min(t[p<<1].mn,t[p<<1|1].mn);
}
void change(int p,int l,int r,int ql,int qr,int val)
{
    if(ql<=l&&qr>=r){t[p].ad+=val;t[p].mn+=val;return;}
    pushdown(p);
    int mid=l+r>>1;
    if(ql<=mid)change(p<<1,l,mid,ql,qr,val);
    if(qr>mid)change(p<<1|1,mid+1,r,ql,qr,val);
    t[p].mn=min(t[p<<1].mn,t[p<<1|1].mn);
}
int query(int p,int l,int r,int x)
{
    if(l==r)return t[p].mn;
    int mid=l+r>>1;
    pushdown(p);
    if(x<=mid)return query(p<<1,l,mid,x);
    return query(p<<1|1,mid+1,r,x);
}
int query(int p,int l,int r,int ql,int qr)
{
    if(ql<=l&&qr>=r)return t[p].mn;
    pushdown(p);int mid=l+r>>1,val=0x3f3f3f3f;
    if(ql<=mid)val=min(val,query(p<<1,l,mid,ql,qr));
    if(qr>mid)val=min(val,query(p<<1|1,mid+1,r,ql,qr));
    return val;
}
struct node{int l,p;node(int l=0,int p=0):l(l),p(p){}};
vector<node>vec[N];
int n,m;
char s[N];int d[N],sta[N],top,ans[N];
//sta里面存的是可能要删掉的T。 
inline int get(int val)
{
    int l=1,r=top;
    while(l<r)
    {
        int mid=l+r>>1;
        if(sta[mid]<val)l=mid+1;
        else r=mid;
    }
    if(sta[l]<val)++l;
    return l;
}
int main()
{
    freopen("dayinf.in","r",stdin);
    freopen("dayinf.out","w",stdout);
    qr(n);scanf("%s",s+1);
    for(int i=1;i<=n;i++)d[i]=(s[i]=='C'?1:-1);
    qr(m);
    for(int i=1;i<=m;i++)
    {
        int l,r;qr(l),qr(r);
        vec[r].push_back(node(l,i));
    }
    top=0;
    for(int i=1,s=0;i<=n;i++)//s表示前缀和 
    {
        s+=d[i];
        if(d[i]==-1)++s,change(1,1,n,i,s),sta[++top]=i;
        else
        {
            if(top)change(1,1,n,sta[top],i-1,-1),--s,--top;//使C与T一一对应,保证任意的后缀都>=0,且影响的前缀数量最少。 
            change(1,1,n,i,s);    
        }
        for(int j=0;j<vec[i].size();j++)
        {
            int p=vec[i][j].p,l=vec[i][j].l;
            int si=0;
            if(top)si=top-get(l)+1;//找到>=l的第一个栈元素,就是必定要删的(否则维护不了[l,r]所有后缀和>=0) 
            int g=query(1,1,n,l,i);if(l-1)g-=query(1,1,n,l-1);
            if(g<0)//说明最小的前缀和出现了T>C的情况,需要回减多一部分的T,使得前缀和满足>=0。 
                si-=g;
            ans[p]=si; 
        }
    }
    for(int i=1;i<=m;i++)
        qw(ans[i]),puts("");
    return 0;
}