余姚培训每日题解-解题报告

· · 个人记录

4.17

A

给定一个无向图，求给每条边定向的方案数，使得图中没有环。n\le 20

DAG计数的套路，我们还是枚举出度为0的点的集合，但是这样可能会重复枚举，所以要套一个-1的系数。

于是我们要做形如：

f(S)=\sum _{T\subseteq S,T\neq\emptyset} g(T)f(S-T)

的卷积，类比<州区划分>的做法，我们多记一维f(i,S),cnt[S]=i就可以用FMT做交集为空的or卷积了。

B

这是一道...我也不知道该如何评价的题。

首先一个性质，连续的1的长度最多是$\log n$。 如果我们把$x,2x,4x...(x\mod 2=1)$视为一条“链”的话，那么填1就是沿着链走，0就是跳着走。发现链的长度只有1-6，我们可以状压下每种长度的链的个数。 然后转移的话，就是枚举沿着当前的链走，还是到别的链去。注意，我们每到链上的一个点，就相当于把链断成前后两半。 ```cpp int dp(int x,int len,int pos,LL S) { if(x==n+1) return 1; if(rem[x][len][pos].count(S)) return rem[x][len][pos][S]; int &r=rem[x][len][pos][S]; int cnt[7]= {0}; unzip(S,cnt); --cnt[len],++cnt[pos-1],++cnt[len-pos]; LL nxt=zip(cnt); ++cnt[len],--cnt[pos-1],--cnt[len-pos]; if(s[x]=='1') { if(pos>1) inc(r,dp(x+1,pos-1,pos-1,nxt)); // go down the chain if(pos<len) inc(r,dp(x+1,len-pos,1,nxt)); // go up the chain return r; } // jump down the chain for(ri i=1; i<pos-1; ++i) inc(r,dp(x+1,pos-1,i,nxt)); // jump up the chain for(ri i=pos+2; i<=len; ++i) inc(r,dp(x+1,len-pos,i-pos,nxt)); // go to another chain for(ri i=1; i<=6; ++i) { int ret=cnt[i]-(len==i); if(!ret) continue; for(ri j=1; j<=i; ++j) inc(r,mul(ret,dp(x+1,i,j,nxt))); } return r; } ``` ## C 找到字典序最小的排列P，使得$\forall i\in[1,n],\exists j\in[l_i,r_i],P_j=i

经典的字典序贪心，考虑[l_i,r_i]的限制条件什么时候会限制我们，比如现在考虑到了i，那么当且仅当sum[R]-R\ge sum[i-1]-i+1，其中sum[i]=\sum_j [r_j\le i]。当取到>时无解；=时，我们放置的数的r必须小于限制的R，这些都可以用线段树和STL维护。

4.18

A

首先把题意转化为每个点有权值，然后区间覆盖，询问没有覆盖过的点的权值和，支持撤销一次覆盖。

我们对询问进行，拆分，然后树剖，然后...？我就看题解去了。发现，我们只需要覆盖次数为0的地方的值——这是什么？这是覆盖次数的区间最小值！我们可以用线段树维护区间最小值的出现次数，这样就可以修改了！

B

需要前置知识：类欧。学习去了。看<类欧-学习笔记>吧

C

我们把当前区间的状态转化为一个点(l,r)，我们把一次奖励看成两个点(x-k+1,x),(x,x+k-1)，它们从下方和右方到达分别有奖励，每个点可以往左上走，于是就变成经典的二维偏序+DP了，可持久化扫描线的话可以强制在线。

4.17

A

显然的贪心，如何去掉log？我们从大到小枚举，用并查集找到最深的包含他的点。注意一个点可能有多个顾客！

B

论NTT被n^2爆踩

有一些性质：

我们选的图不会有环，因为这样就肯定可以去掉一条正边。假设正负数都有，那么每个正数一定会和负数连，然后负数之间相互连（因为每个点必须有边，所以不能都和最小的负数连）。把负数按绝对值从小到大排序，正数一定匹配的是一段后缀，我们枚举这段后缀的长度，正数从小到大依次匹配，多余的都和最后的负数匹配。

然后我们要处理前边cnt-i或cnt-i+1（后缀的第一个的负数可能之前的一起连边）。如果它们组成一个联通块，那么肯定是都和第一个（绝对值最小）的负数匹配。否则一定是(((()))))))，也就是前边对称着连边，后边都和第一个连，我们暴力枚举中间点DP即可。

C

有m个区间，你可以在[l_i,r_i]中选一个位置+1，最大化每个位置的平方的和，m\le 400

一道提高组的题目...感觉我好傻...首先我们可以处理出每个可行的区间，然后我们直接DP！dp[l][r]表示只考虑[l,r]完全包含的区间的最优解，枚举中间点k，让所有[l,r]内和k有交的区间都放在k，然后递归两边。

遇到贡献与若干区间有关的问题，难以处理区间相交的决策，尝试区间DP，只考虑被[l,r]完全包含的区间的贡献。

4.19

A

刚写完string状压牛逼，然后sbczy就改时限重测了

把10^{24}以内的数的每个质因数的指数取出来sort一遍，不同的序列只有大约200000个。这道题的转移，再多维护一个高维前缀和即可。

B

很多细节的贪心和模拟，咕了。

C 最大子段和

移项，讨论max的取向。发现在每个负数之间，是单调的，用一个指针指即可。

#define N 5005
const int inf=1e9;
int n,K;
int a[N],sum[N];
int dp[N][N]; // j = cnt of -1; [1...i]
signed main()
{
#ifdef M207
    freopen("in.in","r",stdin);
    // freopen("ot.out","w",stdout);
#endif
    in(n,K);
    if(n==1)
    {
        puts("0");
        return 0;
    }
    for(ri i=1; i<=n; ++i) in(a[i]);
    int s; dp[0][1]=s=max(a[1],0);
    for(ri i=2; i<=n; ++i)
    {
        dp[0][i]=max(dp[0][i-1],s+K+max(a[i],0));
        if(a[i]<0) s=0;
        else s+=K+a[i];
    }
    sum[1]=a[1];
    for(ri i=2; i<=n; ++i) sum[i]=sum[i-1]+K+a[i];
    for(ri j=1; j<n; ++j)
    {
        for(ri i=1; i<=j; ++i) dp[j][i]=inf;
        int lst=j,mxp=j+1;
        for(ri i=j+1; i<=n; ++i)
        {
            s=sum[i]-(a[i]<0?a[i]:0);
            dp[j][i]=max(dp[j-1][i-1],a[i]); // place -1 between i-1 and i
            ckmin(dp[j][i],max(dp[j][lst],s-sum[lst])); // not place -1
            while(mxp<i&&dp[j-1][mxp-1]<=s-sum[mxp]+a[mxp]) ++mxp;
            if(mxp-1>lst) ckmin(dp[j][i],s-sum[mxp-1]+a[mxp-1]);
            if(mxp<i) ckmin(dp[j][i],dp[j-1][mxp-1]);
            if(a[i]<0) lst=i,mxp=i+1;
        }
    }
    s=sum[n]-(a[1]<0?a[1]:0)-(a[n]<0?a[n]:0);
    int ans=s-dp[0][n];
    for(ri i=1; i<n; ++i) ckmax(ans,s-i*(K+1)-dp[i][n]);
    out(ans);
    return 0;
}

4.20

今天的题好自闭啊

B 幻方

我也不会证明，记一下结论：

在大部分情况下，

ans=m^{n^2-2n}

当n=4且m是偶数时，答案要乘2

C 再放送

疯狂讨论题。

int f[N],g[N],h[N]; // first come no fa; second come no fa; first come with fa
int w[N]; // into x, back to fa
void dfs(int x,int _fa)
{
    for(solid v:E[x])
    {
        if(v==_fa) continue;
        dfs(v,x);
        inc(w[x],mul(iv[du[v]],iv[du[x]])); // immediately go back
        inc(w[x],mul(w[v],iv[du[x]-1])); // ban the son
    }
    w[x]=mul(w[x],iv[du[x]]); // choose one son to go
}
void efs(int x,int _fa)
{
    if(!sn[x])
    {
        f[x]=g[x]=val[x];
        return;
    }
    int sf=0;
    for(solid v:E[x])
    {
        if(v==_fa) continue;
        efs(v,x); inc(sf,f[v]);
    }
    for(solid v:E[x])
    {
        if(v==_fa) continue;
        // f
        // immediately go back
        inc(f[x],mul(iv[du[v]],iv[sn[x]],add(g[v],sf,md-f[v])));
        // into the son & no back
        inc(f[x],h[v]);
        // into the son & back (ban the son)
        inc(f[x],mul(w[v],iv[sn[x]-1],sub(sf,f[v])));
        if(sn[x]==1) inc(f[x],mul(w[v],val[x]));
        // g
        // into the son & no back
        inc(g[x],f[v]);
        // h
        // immediately go back
        inc(h[x],mul(iv[du[v]],iv[du[x]],add(g[v],sf,md-f[v])));
        // into the son & no back
        inc(h[x],h[v]);
        // into the son & back (ban the son)
        inc(h[x],mul(w[v],iv[du[x]-1],sub(sf,f[v])));
    }
    f[x]=mul(f[x],iv[sn[x]]);
    g[x]=mul(g[x],iv[sn[x]]);
    h[x]=mul(h[x],iv[du[x]]);
}

4.21

A

又是rho和exgcd拼起来。这里我们知道pq的差较小，我们可以枚举x,y，尝试把n分解为(x+y)(x-y)=n，也就是y^2=x^2-n。分解完之后，我们求一下c在phi下的逆元即可。

剩下俩题是计算几何...

4.22

A

线性基水题

BC摸了。