CSP 七连测 day1 比赛反思 – 蓝鸢尾笺の博客

没打比赛，这次是赛后补题的反思。就直接放思路了。

T1 起始标记

本题思路总结请见题解：题解：ZROI #3265 兼CSP7连测T1 起始标记 – 蓝鸢尾笺の博客

T2 前缀进位

本题思路小总结：

由题意，最终答案要求所有数的按位与最大，考虑采用从高位到低位的贪心策略来确定每一位能否取1。
那么对于当前构造的答案前缀 $M$ ，问题转化为能否通过不超过 $K$ 次前缀加操作，使所有数都包含 $M$ 的二进制位。
利用前缀操作叠加的特性，倒序遍历数组，维护当前所需的累计操作次数 $c$ 。
对于当前数 $a_i$ ，若 $a_i + c$ 已包含 $M$ 的所有位则无需增加，否则调用函数 $g$ 求出包含 $M$ 且不小于 $v=a_i+c$ 的最小数值。
该最小数值的构造策略为：找到缺失的最高位，将其置1并将更低位置0，再补上 $M$ 的低位部分，从而保证增量最小。
若所需增量大于 $K$ 则当前 $M$ 不可行；否则更新累计次数 $c$ 为该增量，且因为是从后往前操作，该增量单调不减。
最后若累计次数 $c \le K$ ，则该位可以取1，继续枚举下一位，最终得出最大值。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1000005;
int n,K;
int a[maxn];
inline int g(int v,int M)
{
    int bad=M&(~v);
    if(bad==0)
    {
        return v;
    }
    int h=63-__builtin_clzll((unsigned long long)bad);
    return (v&(~((1LL<<(h+1))-1)))|(1LL<<h)|(M&((1LL<<h)-1));
}
inline int check(int M)
{
    int c_next=0;
    for(int i=n;i>=1;--i)
    {
        int v=a[i]+c_next;
        int target=g(v,M);
        int c_cur=target-a[i];
        if(c_cur>K)
        {
            return -1;
        }
        c_next=c_cur;
    }
    if(c_next<=K)
    {
        return 1;
    }
    return -1;
}
signed main(){
    scanf("%lld %lld",&n,&K);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
    }
    int ans=0;
    for(int bit=60;bit>=0;--bit)
    {
        int M=ans|(1LL<<bit);
        if(check(M)!=-1)
        {
            ans=M;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

T3 留白

由题意，总方案数为 $3 \times 2^{n-1}$ ，所求期望转化为“所有方案的最大白色连通块大小之和”除以总方案数。
观察到 $n \le 500$ ，采用动态规划，定义 $dpa[s][m]$ 与 $dpb[s][m]$ 分别表示连通块处于延续与断开的状态。
其中 $s$ 代表当前延伸的白色连通块大小， $m$ 代表历史中出现的最大连通块大小，并用滚动数组优化空间。
初始状态根据第一列黑格的所在行分类讨论，分别记录最大连通块大小为 $2$ 与 $1$ 的情况。
转移时枚举下一列黑格的合法位置，若该列未阻断连通块则 $s$ 增加 $1$ 或 $2$ ；若阻断则将当前 $s$ 与 $m$ 取最大值后重置 $s$ 。
最终将所有状态下的最大连通块 $m$ 乘以对应方案数并累加，得到总贡献。
最后乘上总方案数在模 $998244353$ 意义下的逆元，即可得出最终的期望答案。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1005;
const int mod=998244353;
int n;
int dpa[2][maxn][maxn];
int dpb[2][maxn][maxn];
int qpow(int x,int k)
{
    int res=1;
    while(k)
    {
        if(k&1)
        {
            res=res*x%mod;
        }
        x=x*x%mod;
        k>>=1;
    }
    return res;
}
signed main(){
    scanf("%lld",&n);
    if(n==1)
    {
        int inv3=qpow(3,mod-2);
        printf("%lld\n",5*inv3%mod);
        return 0;
    }
    int cur=0;
    int nxt=1;
    dpa[cur][2][2]=2;
    dpb[cur][1][1]=1;
    for(int col=1;col<n;++col)
    {
        for(int s=1;s<=2*n;++s)
        {
            for(int m=s;m<=2*n;++m)
            {
                int vala=dpa[cur][s][m];
                if(vala)
                {
                    int ns=s+2;
                    int nm=(m>ns)?m:ns;
                    dpa[nxt][ns][nm]+=vala;
                    if(dpa[nxt][ns][nm]>=mod)
                    {
                        dpa[nxt][ns][nm]-=mod;
                    }
                    ns=s+1;
                    nm=(m>ns)?m:ns;
                    dpb[nxt][ns][nm]+=vala;
                    if(dpb[nxt][ns][nm]>=mod)
                    {
                        dpb[nxt][ns][nm]-=mod;
                    }
                }
                int valb=dpb[cur][s][m];
                if(valb)
                {
                    if(s>1)
                    {
                        int ns=s+2;
                        int nm=(m>ns)?m:ns;
                        dpa[nxt][ns][nm]+=valb;
                        if(dpa[nxt][ns][nm]>=mod)
                        {
                            dpa[nxt][ns][nm]-=mod;
                        }
                        ns=3;
                        nm=(m>ns)?m:ns;
                        dpa[nxt][ns][nm]+=valb;
                        if(dpa[nxt][ns][nm]>=mod)
                        {
                            dpa[nxt][ns][nm]-=mod;
                        }
                    }
                    else
                    {
                        int ns=3;
                        int nm=(m>ns)?m:ns;
                        dpa[nxt][ns][nm]+=2*valb;
                        dpa[nxt][ns][nm]%=mod;
                    }
                }
            }
        }
        swap(cur,nxt);
        memset(dpa[nxt],0,sizeof(dpa[nxt]));
        memset(dpb[nxt],0,sizeof(dpb[nxt]));
    }
    int s_sum=0;
    for(int s=1;s<=2*n;++s)
    {
        for(int m=s;m<=2*n;++m)
        {
            s_sum=(s_sum+m*dpa[cur][s][m]+m*dpb[cur][s][m])%mod;
        }
    }
    int total=3*qpow(2,n-1)%mod;
    int ans=s_sum*qpow(total,mod-2)%mod;
    printf("%lld\n",ans);
    return 0;
}

T4 单线巡查

本题思路小总结：

由题意，问题等价于统计连续区间 $[L, r]$ ，使得区间内站在原树上的诱导子图满足度数不超过 $2$ 且连通（即单线路径）。
利用双指针（滑动窗口）枚举右端点 $r$ ，依次加入新节点 $p[r]$ 并动态维护当前窗口的状态。
当新加入节点导致树中出现度数达到 $3$ 的节点（产生分叉）时，右移左端点 $L$ 并剔除节点，直至窗口内所有点的度数不超过 $2$ 。
利用线段树维护前缀区间上的某种计数值，通过给区间 $[1, r]$ 加 $1$ 和给区间内邻居位置减 $1$ 的差分技巧，实现节点度数的动态变化。
线段树维护区间最小值 $minv$ 与个数 $cnt$ ，当窗口处于合法状态时，查询 $[L, r]$ 中 $minv=1$ 的点数量。
该数量对应当前窗口内单线路径的端点个数（长度为 $1$ 时为孤立点），累加所有右端点对应的合法片段数量即为答案。
总时间复杂度为 $O(n \log n)$ ，满足 $n \le 2 \times 10^5$ 的数据范围要求。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=200005;
int n;
int p[maxn],pos[maxn];
vector<int> e[maxn];
int deg[maxn],in[maxn];
int L,cnt3;
struct node{
    int minv,cnt;
    int lazy;
}tree[maxn<<2];
void push_up(int rt)
{
    tree[rt].minv=min(tree[rt<<1].minv,tree[rt<<1|1].minv);
    tree[rt].cnt=0;
    if(tree[rt].minv==tree[rt<<1].minv)
    {
        tree[rt].cnt+=tree[rt<<1].cnt;
    }
    if(tree[rt].minv==tree[rt<<1|1].minv)
    {
        tree[rt].cnt+=tree[rt<<1|1].cnt;
    }
}
void push_down(int rt)
{
    if(tree[rt].lazy)
    {
        tree[rt<<1].minv+=tree[rt].lazy;
        tree[rt<<1|1].minv+=tree[rt].lazy;
        tree[rt<<1].lazy+=tree[rt].lazy;
        tree[rt<<1|1].lazy+=tree[rt].lazy;
        tree[rt].lazy=0;
    }
}
void build(int rt,int l,int r)
{
    tree[rt].lazy=0;
    if(l==r)
    {
        tree[rt].minv=0;
        tree[rt].cnt=1;
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    push_up(rt);
}
void update(int rt,int l,int r,int ql,int qr,int val)
{
    if(ql<=l&&r<=qr)
    {
        tree[rt].minv+=val;
        tree[rt].lazy+=val;
        return;
    }
    push_down(rt);
    int mid=(l+r)>>1;
    if(ql<=mid)
    {
        update(rt<<1,l,mid,ql,qr,val);
    }
    if(qr>mid)
    {
        update(rt<<1|1,mid+1,r,ql,qr,val);
    }
    push_up(rt);
}
int query(int rt,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)
    {
        return (tree[rt].minv==1)?tree[rt].cnt:0;
    }
    push_down(rt);
    int mid=(l+r)>>1;
    int ans=0;
    if(ql<=mid)
    {
        ans+=query(rt<<1,l,mid,ql,qr);
    }
    if(qr>mid)
    {
        ans+=query(rt<<1|1,mid+1,r,ql,qr);
    }
    return ans;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<n;++i)
    {
        int u,v;
        scanf("%lld %lld",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&p[i]);
        pos[p[i]]=i;
    }
    L=1;
    build(1,1,n);
    long long ans=0;
    for(int r=1;r<=n;++r)
    {
        int u=p[r];
        update(1,1,n,1,r,1);
        for(int v:e[u])
        {
            if(pos[v]<r)
            {
                update(1,1,n,1,pos[v],-1);
            }
        }
        in[u]=1;
        for(int v:e[u])
        {
            if(in[v])
            {
                if(deg[u]==2)
                {
                    cnt3++;
                }
                if(deg[v]==2)
                {
                    cnt3++;
                }
                deg[u]++;
                deg[v]++;
            }
        }
        while(cnt3>0)
        {
            int x=p[L];
            in[x]=0;
            for(int v:e[x])
            {
                if(in[v])
                {
                    if(deg[x]==3)
                    {
                        cnt3--;
                    }
                    if(deg[v]==3)
                    {
                        cnt3--;
                    }
                    deg[x]--;
                    deg[v]--;
                }
            }
            L++;
        }
        ans+=query(1,1,n,L,r);
    }
    printf("%lld\n",ans);
    return 0;
}

T1 起始标记

T2 前缀进位

T3 留白

T4 单线巡查

发送评论 编辑评论

发送评论编辑评论