『模拟赛』CSP-S模拟4-牛翰网

『模拟赛』CSP-S模拟4

点击查看代码

一般

A. 商品

说不上是思维题还是啥,jijidawang 和 5k 讲的没太懂,于是选择了最喜欢的线段树。

赛时想了好~ 久~ 好~ 久~,考虑过二分,随机化,线段树,最后发现都是假的就只打了 30pts 暴力。赛后才想到动态开点线段树。考虑如何维护,发现只有选取的区间包括 \(a_i\)\(a_{i-1}\) 之间的点时才有贡献,容易想到可以在线段树上将两数之差这段区间做区间加法,复杂度是 \(\mathcal{O(n\log M)}\) 的,\(M\) 为值域。

找答案时,容易证明区间越大答案越优,且只有选取区间的边界上有点时才有可能成为最优答案。因此我们对每个点考虑让其成为一次上下边界求两次区间和,比较求出答案即可,可以开 map 记一下,不记时间也差不多,复杂度是 \(\mathcal{O(n\log M)}\) 的。

因为 \(n\) 的范围只有 \(2\times 10^5\),所以根本开不了几个点,况且这道题给的空间限制为 1024MB,直接往大了开就行。

注意如果区间权左移到点上做区间修改时,需要判断左边界是否小于有边界,否则在 \(a_i=a_{i+1}=1\) 时会 GG。

点击查看代码

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch=getchar();lx x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int,int>
#define fi first
#define se second
const int Ratio=0*1;
const int N=2e5+5;
const int mod=998244353;
int n,d,L,R;
int a[N];
int rot,son[(N<<1)*50][2];
ll ans,v[(N<<1)*50],lazy[(N<<1)*50];
namespace Wisadel
{
    #define ls (son[rt][0])
    #define rs (son[rt][1])
    #define mid ((l+r)>>1)
    void Wpushup(int rt)
    {
        v[rt]=v[ls]+v[rs];
    }
    void Wpushdown(int rt,int l,int r)
    {
        if(!ls) ls=++rot;
        if(!rs) rs=++rot;
        v[ls]+=(mid-l+1)*lazy[rt];
        v[rs]+=(r-mid)*lazy[rt];
        lazy[ls]+=lazy[rt],lazy[rs]+=lazy[rt];
        lazy[rt]=0;
    }
    void Wupd(int rt,int l,int r,int x,int y)
    {
        if(x<=l&&r<=y)
        {
            v[rt]+=1ll*(r-l+1);lazy[rt]++;
            return;
        }
        if(lazy[rt]) Wpushdown(rt,l,r);
        if(x<=mid)
        {
            if(!ls) ls=++rot;
            Wupd(ls,l,mid,x,y);
        }
        if(y>mid)
        {
            if(!rs) rs=++rot;
            Wupd(rs,mid+1,r,x,y);
        }
        Wpushup(rt);
    }
    ll Wq(int rt,int l,int r,int x,int y)
    {
        if(!rt) return 0;
        if(x<=l&&r<=y) return v[rt];
        if(lazy[rt]) Wpushdown(rt,l,r);
        ll res=0;
        if(x<=mid) res+=Wq(ls,l,mid,x,y);
        if(y>mid) res+=Wq(rs,mid+1,r,x,y);
        return res;
    }
    short main()
    {
        freopen("goods.in","r",stdin),freopen("goods.out","w",stdout);
        n=qr,d=qr;
        rot=1;
        int maxn=1e9;
        fo(i,1,n) a[i]=qr,maxn=max(maxn,a[i]);
        fo(i,2,n)
        {
            int aa=min(a[i],a[i-1]),bb=max(a[i],a[i-1])-1;
            if(aa<=bb) Wupd(1,1,maxn,aa,bb);
        }
        fo(i,1,n)
        {
            L=a[i],R=L+d-1;
            if(L<=0||R>maxn) continue;
            ans=max(ans,Wq(1,1,maxn,L,R));
        }
        fo(i,1,n)
        {
            R=a[i]-1,L=R-d+1;
            if(L<=0||R>maxn) continue;
            ans=max(ans,Wq(1,1,maxn,L,R));
        }
        printf("%lld\n",ans);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

B. 价值

树形dp 大分讨题。

挺牛的一道题,赛时完全推不出任何有价值的东西,只能拉成序列跑 \(\mathcal{O(2^n)}\) 暴力 30pts。

学了 Qyun 的做法,设 \(f_{x,i,j,k}\)\(i\) 表示是否存在于匹配(是否连边),\(j\)\(k\) 分别表示该点最小/大叶子:

  • 0:为连边;
  • 1:会连边,但目前未连;
  • 2:已连边。

跑两边 dp,一遍不考虑 \((u_m,u_1)\) 这条边,另一遍钦定一定选该边,然后大力分讨即可,情况写注释里了,不多赘述一遍了。

点击查看代码

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch=getchar();lx x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int,int>
#define fi first
#define se second
const int Ratio=0;
const int N=1e5+5;
const int mod=998244353;
int n,minn=1e9,maxx;
int fa[N];
ll f[N][2][3][3],g[2][3][3],ans;
// int hh[N],ne[N],to[N],cnt;
vector<int>e[N];
namespace Wisadel
{
    inline void Wadd(int u,int v){/*to[++cnt]=v,ne[cnt]=hh[u],hh[u]=cnt*/e[u].push_back(v);}
    void Wdfs(int u){if(!e[u].size()){minn=min(minn,u),maxx=max(maxx,u);return;} for(int v:e[u]) Wdfs(v);}
    void Wdo(int u,bool fla)
    {
        if(fla&&(u==minn||u==maxx)){f[u][1][2][2]=(minn!=maxx);/*链*/return;}
        if(!e[u].size()){f[u][0][0][0]=f[u][1][1][2]=f[u][1][2][1]=1;return;}
        for(int v:e[u]) Wdo(v,fla);
        int v=e[u][0];// 最小
        fo(j,0,2) fo(k,0,2) f[u][0][j][k]=(f[v][0][j][k]+f[v][1][j][k])%mod,
                            f[u][1][j][k]=f[v][0][j][k];// 连
        fo(i,1,e[u].size()-1)
        {
            v=e[u][i];
            fo(j,0,2) fo(k,0,2)
                // 由于子节点是按dfs序升序便利的
                // 二者只在当前节点的最大叶子和子节点的最小叶子之间有联系
                // ↓:求出当前节点构成匹配(连边)的方案数
                g[1][j][k]=(f[u][1][j][0]*f[v][0][0][k]%mod+
                            // 当前节点最大叶子和子节点最小叶子都不连
                            f[u][1][j][1]*f[v][0][1][k]%mod+
                            // 当前节点最大叶子和子节点最小叶子相连
                            f[u][1][j][2]*f[v][0][2][k]%mod+
                            // 当前节点最大叶子和子节点最小叶子已连接但不是彼此
                            f[u][1][j][2]*f[v][0][0][k]%mod+
                            // 当前节点最大叶子已连,子节点最小叶子未连
                            f[u][1][j][0]*f[v][0][2][k]%mod+
                            // 当前节点最大叶子未连,子节点最小叶子已连
                            // ↑:当前节点已经和编号较小的其他子节点有连边+子节点没有
                            f[u][1][j][0]*f[v][1][0][k]%mod+
                            f[u][1][j][1]*f[v][1][1][k]%mod+
                            f[u][1][j][2]*f[v][1][2][k]%mod+
                            f[u][1][j][2]*f[v][1][0][k]%mod+
                            f[u][1][j][0]*f[v][1][2][k]%mod+
                            // ↑:当前节点已经和编号较小的子节点有连边+子节点也已连边
                            f[u][0][j][0]*f[v][0][0][k]%mod+
                            f[u][0][j][1]*f[v][0][1][k]%mod+
                            f[u][0][j][2]*f[v][0][2][k]%mod+
                            f[u][0][j][2]*f[v][0][0][k]%mod+
                            f[u][0][j][0]*f[v][0][2][k]%mod
                            // ↑:当前节点和该子节点连边
                            )%mod,
                // ↓:求出当前节点未连边的方案数
                g[0][j][k]=(f[u][0][j][0]*f[v][0][0][k]%mod+
                            f[u][0][j][1]*f[v][0][1][k]%mod+
                            f[u][0][j][2]*f[v][0][2][k]%mod+
                            f[u][0][j][2]*f[v][0][0][k]%mod+
                            f[u][0][j][0]*f[v][0][2][k]%mod+
                            // ↑:当前节点和该子节点均未连边
                            f[u][0][j][0]*f[v][1][0][k]%mod+
                            f[u][0][j][1]*f[v][1][1][k]%mod+
                            f[u][0][j][2]*f[v][1][2][k]%mod+
                            f[u][0][j][2]*f[v][1][0][k]%mod+
                            f[u][0][j][0]*f[v][1][2][k]%mod
                            // ↑:当前节点未连边+该子节点已连边
                            )%mod;
            fo(op,0,1) fo(j,0,2) fo(k,0,2)
                f[u][op][j][k]=g[op][j][k];
        }
    }
    short main()
    {
        freopen("value.in","r",stdin),freopen("value.out","w",stdout);
        n=qr;
        fo(i,2,n) fa[i]=qr,Wadd(fa[i],i);
        fo(i,1,n) sort(e[i].begin(),e[i].end());// 排序,保证子节点遍历顺序升序
        Wdfs(1);
        Wdo(1,0);
        ans=(f[1][0][2][0]+f[1][0][0][2]+f[1][0][2][2]+f[1][0][0][0]+
            f[1][1][2][0]+f[1][1][0][2]+f[1][1][2][2]+f[1][1][0][0])%mod;
        memset(f,0,sizeof f);
        Wdo(1,1);
        ans=(ans+f[1][0][2][2]+f[1][1][2][2])%mod;
        printf("%lld\n",ans);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

C. 货币

网络流,先欠着。

D. 资本

生成函数,先欠着。

这场强度好高啊啊啊,早晚被模拟赛打昏过去。

开场扫一眼 T1 没思路,然后看 T2 也没思路,然后非常恼,状态不太行,前 3h 光想这个了觉得切不掉就垫底,最终还是只打出俩暴力。后面只留了一个小时给 T3 T4,估么着自己不可能场切,也只打了暴力。

庆幸的是最近都没咋挂分,暴力越打越稳了,(正解也得打啊,别最后只会暴力了。

上了体育课,爽。搬书摆桌子酸奶没了,不爽。

md 题难改+上了一节体育+摆了一节课桌子导致就剩 40min 给昨天 T4 了,不多写了还债去了。


完结撒花~

请登录后发表评论

    没有回复内容