EducationalCodeforcesRound46(Div2)(A~G)

目录

• A.Codehorses T-shirts
• B.Light It Up
• C.Covered Points Count(差分)
• D.Yet Another Problem On a Subsequence(DP)
• E.We Need More Bosses(圆方树)
  • \(Description\)
  • \(Solution\)
• F.One Occurrence(线段树)
  • \(Description\)
  • \(Solution\)
• G.Two-Paths(树形DP)
  • \(Description\)
  • \(Solution\)

比赛链接

CF的第1000场比赛。。
在学校熬到12点半打CF而不是看他们打联盟真是。。rating差点掉真是难受啊。

A.Codehorses T-shirts

因为长度固定，所以看着分就好了...
当然其实只需要map。

#include 
#include 
#include 
#include 
#define gc() getchar()
const int N=105;

int n,have[4][3],sum[4][3],ref[2333];//x:0~3 S/L

inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}

int main()
{
    n=read(); char s[233];
    ref['S']=0, ref['L']=1, ref['M']=2;
    for(int l,i=1; i<=n; ++i)
    {
        scanf("%s",s+1), l=strlen(s+1);
        ++have[l-1][ref[s[l]]];
    }
    for(int l,i=1; i<=n; ++i)
    {
        scanf("%s",s+1), l=strlen(s+1);
        ++sum[l-1][ref[s[l]]];
    }
    int res=0;
    for(int i=0; i<=3; ++i)
    {
        int tmp=0;
        for(int j=0; j<=2; ++j) tmp+=std::abs(have[i][j]-sum[i][j]);
        res+=tmp>>1;
    }
    printf("%d",res);

    return 0;
}

B.Light It Up

对于要开的和要灭的要放的最优位置是确定的，有不同的贡献。枚举一下放在哪就行了。
漏了一个-A[i-1]还过了4个点 WA了三遍。。aaaaaa

#include 
#include 
#include 
#define gc() getchar()
typedef long long LL;
const int N=1e5+7;

LL n,m,A[N],sum[N],suf[N];

inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}

int main()
{
    n=read(),m=read();
    for(int i=1; i<=n; ++i) A[i]=read();
    for(int i=1; i<=n; i+=2) sum[i+1]=sum[i]=sum[i-1]+A[i]-A[i-1];
    if(n&1){
        for(int i=n-1; i>0; i-=2) suf[i-1]=suf[i]=suf[i+1]+A[i+1]-A[i];
    }
    else{
        A[n+1]=m;
        for(int i=n; i>0; i-=2) suf[i-1]=suf[i]=suf[i+1]+A[i+1]-A[i];
    }
//  for(int i=1; i<=n; ++i) printf("%d:pre:%I64d suf:%I64d\n",i,sum[i],suf[i]);
    LL ans=sum[n];
    if(!(n&1)) ans+=m-A[n];
    if(n&1) A[++n]=m;
    for(LL i=1; i<=n; ++i)
        if(A[i]-A[i-1]>1){
            if(i&1) ans=std::max(ans,sum[i-1]+A[i]-A[i-1]-1+m-A[i]-suf[i]);
            else ans=std::max(ans,sum[i-1]+A[i]-A[i-1]-1+m-A[i]-suf[i]);
        }
    printf("%I64d",ans);

    return 0;
}

C.Covered Points Count(差分)

离散化，差分。每个区间拆成4个点，即在修改前计算一遍。
Ans原本开的longlong，但是WA了一次发现，我怎么用%d输出longlong了？遂改int Ans[]。。

数据范围好像有问题啊mmp
好像没问题。。那为什么我N=2e5+7会RE啊
噢 val也是4N。。

#include 
#include 
#include 
#define gc() getchar()
typedef long long LL;
const int N=2e5+7;

int n,cnt,val[N*4];
LL ref[N*4],L[N],R[N],Ans[N];

inline LL read()
{
    LL now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}
inline int Find(LL x)
{
    int l=1, r=cnt, mid;
    while(l>1]>=x) r=mid;
        else l=mid+1;
    return l;
}

int main()
{
    n=read(); int tot=0;
    for(int i=1; i<=n; ++i) L[i]=ref[++tot]=read(), ref[++tot]=L[i]-1, R[i]=ref[++tot]=read(), ref[++tot]=R[i]+1;

    std::sort(ref+1,ref+1+tot), cnt=1;
    for(int i=2; i<=tot; ++i) if(ref[i]!=ref[i-1]) ref[++cnt]=ref[i];

    for(int i=1; i<=n; ++i) ++val[Find(L[i])], --val[Find(R[i]+1)];
    ref[0]=ref[1]-1;
    for(int now=0,i=1; i<=cnt; ++i)
    {
        now+=val[i];
        Ans[now]+=ref[i]-ref[i-1];
    }
    for(int i=1; i<=n; ++i) printf("%I64d ",Ans[i]);

    return 0;
}

比赛结束后

D.Yet Another Problem On a Subsequence(DP)

Good Sequence是可以拼接的吧。于是考虑倒着\(O(n^2)\)dp。
枚举要接在i后面的子序列j(\(i，\(A[i]>0\))。A[i]已知 i这个子序列就已知，且有\(C_{j-i-1}^{A[i]+1-1}\)种构成i的方案(并不需要它连续)。
i单独成一个也可以，要加上自己构成的\(C_{n-i}^{A[i]}\)种。可以令f[n+1]=1，j枚举到n+1。

//31ms  3800KB
#include 
#include 
#define gc() getchar()
#define mod (998244353)
typedef long long LL;
const int N=1005;

int n,C[N][N],A[N],f[N];

inline int read()
{
    int now=0,f=1;register char c=gc();
    for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now*f;
}
void Init()
{
    for(int i=1; i<=n; ++i)
    {
        C[i][0]=C[i][i]=1;
        for(int j=1; j=mod)&&(C[i][j]-=mod);
    }
}

int main()
{
    n=read(), Init();
    for(int i=1; i<=n; ++i) A[i]=read();
    f[n+1]=1;
    for(int i=n; i; --i)
    {
        if(A[i]<=0) continue;
        LL tmp=0;
        for(int j=i+1+A[i]; j<=n+1; ++j) tmp+=1ll*C[j-i-1][A[i]]*f[j]%mod;
        f[i]=(int)(tmp%mod);
    }
    LL ans=0;
    for(int i=1; i<=n; ++i) ans+=f[i];
    printf("%d\n",(int)(ans%mod));

    return 0;
}

略一优化：C()可以预处理阶乘和阶乘逆元线性求，可以省个\(n^2\)。但时间没变就空间优化了。。
以前真是闲。。

//31ms  0KB
int n,A[N],f[N],sum[N],inv[N];

inline int FP(LL x,int k)
{
    LL t=1;
    for(; k; k>>=1, x=x*x%mod)
        if(k&1) t=t*x%mod;
    return t;
}
inline int C(int n,int m){
    return 1ll*sum[n]*inv[m]%mod*inv[n-m]%mod;
}

int main()
{
    n=read(), inv[0]=sum[0]=1;
    for(int i=1; i<=n; ++i) A[i]=read();
    for(int i=1; i<=n; ++i) sum[i]=1ll*sum[i-1]*i%mod, inv[i]=1ll*inv[i-1]*FP(i,mod-2)%mod;
    f[n+1]=1;
    for(int i=n; i; --i)
    {
        if(A[i]<=0) continue;
        LL tmp=0;
        for(int j=i+1+A[i]; j<=n+1; ++j) tmp+=1ll*C(j-i-1,A[i])*f[j]%mod;
        f[i]=(int)(tmp%mod);
    }
    LL ans=0;
    for(int i=1; i<=n; ++i) ans+=f[i];
    printf("%d\n",(int)(ans%mod));

    return 0;
}

E.We Need More Bosses(圆方树)

\(Description\)

给定一张无向图。你可以任选两个点S,T(S≠T)作为起点终点，记v为S->T必须经过的边的数量，求最大的v。
(such that连用时such就是个代词啊 学到了)

\(Solution\)

圆方树缩环，方点与圆点之间的边边权为0，圆点之间的边边权为1，求直径。
不想在圆点间再建方点。。

官方题解：与答案有关的边一定是桥。把所有之间没有桥的点合并为1个点，建出一棵新树。求这棵树的直径。反正就这样了。

圆方树还跑了个时间Rank1 就是空间略大233

//93ms  38500KB
#include 
#include 
#include 
#define gc() getchar()
const int N=3e5+5;

int n,m,tot,Index,dfn[N],low[N],Max,V,top,sk[N];
struct Edge
{
    int Enum,H[N<<1],nxt[N<<2],to[N<<2],val[N<<2];//Square point...
    inline void AddEdge(int u,int v)
    {
        to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
        to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
    }
    inline void AddTreeEdge(int u,int v,int w)
    {
        to[++Enum]=v, nxt[Enum]=H[u], val[Enum]=w, H[u]=Enum;
        to[++Enum]=u, nxt[Enum]=H[v], val[Enum]=w, H[v]=Enum;
    }
}G,T;

inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}
void Tarjan(int x,int f)
{
    low[x]=dfn[x]=++Index, sk[++top]=x;
    for(int i=G.H[x],v; i; i=G.nxt[i])
        if(!dfn[v=G.to[i]])
        {
            Tarjan(v,x), low[x]=std::min(low[x],low[v]);
            if(dfn[x]==low[v])
            {
                T.AddTreeEdge(x,++tot,0);
                do{
                    T.AddTreeEdge(tot,sk[top--],0);
                }while(sk[top+1]!=v);
            }
            else if(dfn[x]Max) Max=d, V=x;
    for(int i=T.H[x]; i; i=T.nxt[i])
        if(T.to[i]!=f) DFS(T.to[i],x,d+T.val[i]);
}

int main()
{
    tot=n=read(),m=read();
    for(int i=1; i<=m; ++i) G.AddEdge(read(),read());
    Tarjan(1,1);
    DFS(1,1,0), DFS(V,V,0);
    printf("%d",Max);

    return 0;
}

F.One Occurrence(线段树)

\(Description\)

给定一个长为n的序列，多次询问[l,r]中只出现一次的数，输出任意一个即可(没有输出0)。

\(Solution\)

记\(las[i],nxt[i]\)分别为\(A[i]\)上一次、下一次出现的位置，则会对区间\([l,r]\)产生贡献当且仅当\(las[i]，也就是\(A[i]\)会对\([las[i]+1,nxt[i]-1]\)产生贡献。这应该可以用线段树区间修改。
将询问离线，按右端点排序，枚举当前点\(i\)作为右端点，用线段树维护\([1,i]\)上\(las[p]\)最小的位置\(p\)。
那么如果\(\min\{las[p]\}，则\(p\)为所求解之一；否则无解。
当前\(A[i]\)的出现会消除\(1\)(\(las[las[i]])\sim las[i]\)上\(las[i]\)的贡献，直接将线段树上\(las[i]\)的值(\(las[las[i]]\))改为INF即可。
不知道直接莫队+set能不能过。不过看过了的莫队(套权值分块/vector)感觉set应该没问题。

有个加强版的题见这儿。

//421ms 29184KB(Rank1了233)
#include 
#include 
#include 
#define gc() getchar()
const int N=5e5+5,INF=10000000;

int n,Q,A[N],pre[N],las[N],Ans[N];
struct Ques{
    int l,r,id;
    inline bool operator <(const Ques &x)const{
        return r>1;
            Build(ToL), Build(ToR);
            Update(rt);
        }
    }
    void Modify(int l,int r,int rt,int p)//Modify t[p] to INF
    {
        if(l==r) mn[rt]=INF;
        else
        {
            int m=l+r>>1;
            if(p<=m) Modify(ToL,p);
            else Modify(ToR,p);
            Update(rt);
        }
    }
    void Query(int l,int r,int rt,int L,int R)
    {
        if(L<=l && r<=R){
            if(mn[rt]>1;
            if(L<=m) Query(ToL,L,R);
            if(m

//545ms 33600KB
#include 
#include 
#include 
#define gc() getchar()
typedef long long LL;
const int N=3e5+5;

int n,Q,A[N],Enum,H[N],to[N<<1],nxt[N<<1],val[N<<1],sz[N],son[N],fa[N],dep[N],top[N];
LL f[N],fe[N],sub[N],sum[N],up[N];

inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}
inline void AddEdge(int w,int u,int v)
{
    to[++Enum]=v, nxt[Enum]=H[u], val[Enum]=w, H[u]=Enum;
    to[++Enum]=u, nxt[Enum]=H[v], val[Enum]=w, H[v]=Enum;
}
inline int LCA(int u,int v)
{
    while(top[u]!=top[v]) dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];
    return dep[u]>dep[v]?v:u;
}
void DFS1(int x)
{
    int mx=0; sz[x]=1, sub[x]=A[x];
    for(int v,i=H[x]; i; i=nxt[i])
        if((v=to[i])!=fa[x])
        {
            fa[v]=x, dep[v]=dep[x]+1, fe[v]=val[i], DFS1(v), sz[x]+=sz[v], sub[x]+=f[v];
            if(sz[v]>mx) mx=sz[v], son[x]=v;
        }
    f[x]=std::max(0ll,sub[x]-2ll*fe[x]);
}
void DFS2(int x,int tp)
{
    top[x]=tp;
    sum[x]=sub[fa[x]]-f[x]-fe[x];
    up[x]=std::max(0ll,up[fa[x]]+sum[x]-fe[x]);//up[fa[x]]+sub[fa[x]]-f[x]-2*fe[x]
    sum[x]+=sum[fa[x]];
    if(son[x])
    {
        DFS2(son[x],tp);
        for(int i=H[x]; i; i=nxt[i])
            if(to[i]!=fa[x]&&to[i]!=son[x]) DFS2(to[i],to[i]);
    }
}

int main()
{
    n=read(), Q=read();
    for(int i=1; i<=n; ++i) A[i]=read();
    for(int i=1; i