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

『模拟赛』CSP-S模拟3

因为正式集训所以不叫加赛了。

Rank

Upd:非常 数据,掉分掉 Rank。

还行,其实是 Rank6,其实其实是 Rank4(丁真说正式比赛不会改数据。

A. 奇观

简单题(?)。

赛时琢磨了一会想到了 \(Ans=C\cdot C\cdot F\),打出了 \(m=0\) 性质和 \(O(n^2)\) dp 的暴力一共 80pts。

赛后发现在我做法的基础上很难又进一步的优化,于是从头学正解。丁真的做法:找每个点的出边数,即 “—” 的数量 \(cb_i\);找总出边数减去该点的出边以及删去的与该点相邻的点的出边,即 “¬” 的数量 \(cbcb_i\)。如下图:

枚举两种形状中位于位置 2 的点,则有 \(C=\sum_{i=1}^n cb_i\times cbcb_i\)\(F=\sum_{i=1}^n cb_i\times cb_i\times cbcb_i\),然后就做完了。

点击查看代码

#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=2e5+5;
const int mod=998244353;
int n,m;
int hh[N],to[N<<2],ne[N<<2],cnt;
ll ans1,ans2,S,cbcb[N],cb[N];
namespace Wisadel
{
    void Wadd(int u,int v)
    {
        to[++cnt]=v;
        ne[cnt]=hh[u];
        hh[u]=cnt;
    }
    short main()
    {
        freopen("a.in","r",stdin),freopen("a.out","w",stdout);
        n=qr,m=qr;
        memset(hh,-1,sizeof hh);
        fo(i,1,n) cb[i]=n-1;
        fo(i,1,m){int a=qr,b=qr;cb[a]--,cb[b]--;Wadd(a,b),Wadd(b,a);}
        fo(i,1,n) S=(S+cb[i])%mod;
        fo(i,1,n)
        {
            ll res=cb[i];
            for(int j=hh[i];j!=-1;j=ne[j]) res=(res+cb[to[j]])%mod;
            cbcb[i]=((S-res)%mod+mod)%mod;
        }
        fo(i,1,n)
        {
            ans1=(ans1+cb[i]*cbcb[i]%mod+mod)%mod;
            ans2=(ans2+cb[i]*cb[i]%mod*cbcb[i]%mod+mod)%mod;
        }
        printf("%lld\n",ans1*ans1%mod*ans2%mod);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

B. 铁路

简单题。

唐氏评测机跑得还没爬得快,加上 5k 的超级数据,直接给我卡掉 5pts。

问题可能出现在了求 LCA 上,倍增求常数还是太大了,于是请丁真打了个用 dfs 序的求法过了。

思路比较暴力,找到 lca 后两点向上跳,若跳到某点仍存在则答案减一并标记,跳到 lca 为止。记录每次合并后的点所对应的真实的树上的点,记成 lca 最有效,然后就结束了。

思路肯定是正确的,只是做法有点暴力,但跑得比其他做法都不慢,不知道为什么。

点击查看代码

#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=5e5+5;
const int mod=998244353;
int n,m,tot,ans;
int dep[N],st[20][N],tr[N<<1],dc,dfn[N];
int hh[N],to[N<<1],ne[N<<1],cnt;
bool yz[N<<1];
namespace Wisadel
{
    int get(int x,int y){return dfn[x]>dfn[y]?y:x;}
    void Wadd(int u,int v)
    {
        to[++cnt]=v;
        ne[cnt]=hh[u];
        hh[u]=cnt;
    }
    void Wdfs(int u,int fa)
    {   
        dfn[u]=++dc;
        dep[u]=dep[fa]+1;
        st[0][dfn[u]]=fa;
        for(int i=hh[u];i!=-1;i=ne[i])
        {
            int v=to[i];
            if(v==fa) continue;
            Wdfs(v,u);
        }
    }
    int Wlca(int x,int y)
    {
        if(x==y)return x;
        if((x=dfn[x])>(y=dfn[y]))std::swap(x,y);
        int d=std::__lg(y-x++);
        return get(st[d][x],st[d][y-(1<<d)+1]);
    }
    short main()
    {
        freopen("a.in","r",stdin),freopen("a.out","w",stdout);
        memset(hh,-1,sizeof hh);
        n=qr,m=qr;ans=n;
        fo(i,1,n-1)
        {
            int a=qr,b=qr;
            Wadd(a,b),Wadd(b,a);
        }
        Wdfs(1,0);
        for(int i=1;i<=__lg(n);++i)
            for(int j=1;j+(1<<i)-1<=n;++j)
                st[i][j]=get(st[i-1][j],st[i-1][j+(1<<i-1)]);
        fo(i,1,n) tr[i]=i,yz[i]=1;
        fo(i,1,m)
        {
            int a=qr,b=qr;
            a=tr[a],b=tr[b];
            int lca=Wlca(a,b);
            tr[n+i]=lca;
            while(a!=lca)
            {
                if(yz[a]) ans--,yz[a]=0;
                a=st[0][dfn[a]];
            }
            while(b!=lca)
            {
                if(yz[b]) ans--,yz[b]=0;
                b=st[0][dfn[b]];
            }
            printf("%d\n",ans);
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}

C. 光纤

简单题(?)。

不是很会凸包,只拿了送的 \(n\le 2\) 的 10pts。

D. 权值

碱啖题。

神秘数据结构,std 300 多行,赛时甚至没打出 20pts 暴力。

打得还行(指换数据前感觉),正睿的题都这么抽象吗?

T1 干了快 1.5h,T2 近 1h,T3 没看,剩下时间都在看 T4。时间都是利用上了,不知道是题偏难还是实力偏弱(。

不过做到了凸包就去学学吧,学完了回来补 T3,不咕咕。


完结撒花~

请登录后发表评论

    没有回复内容