[NOIP模拟25]题解

客官°小女子只卖身不卖艺 2021-10-30 08:14 352阅读 0赞

# A.字符串 #

Catalan数不能再裸了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    const ll mod=20100403;
    const int N=2000005;
    ll n,m;
    ll fac[N];
    ll qpow(ll a,ll b)
    {
        ll res=1;a=a%mod;
        while(b)
        {
            if(b&1)res=res*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return res;
    }
    ll C(ll x,ll y)
    {
        if(y>x)return 0;
        return fac[x]*(qpow(fac[y]*fac[x-y]%mod,mod-2))%mod;
    }
    ll lucas(ll x,ll y)
    {
        if(!y)return 1;
        return C(x%mod,y%mod)*lucas(x/mod,y/mod)%mod;
    }
    void ini()
    {
        fac[0]=1;
        for(ll i=1;i<=m+n;i++)
            fac[i]=fac[i-1]*1LL*i%mod;
        
    }
    int main()
    {
        scanf("%lld%lld",&n,&m);
        ini();
        ll ans=(lucas(m+n,m)-lucas(m+n,m-1)+mod)%mod;
        cout<<ans<<endl;
        return 0;
    }

# B.乌鸦喝水 #

很能开阔思路的乱搞题。对于每一个缸算出它最多下降的次数，连同它所在的位置进行二元组排序。设rest表示剩下多少缸还能喝，now表示过了几轮，total表示一共喝了多少次水，num\[\]表示每个缸喝的次数。显然所求即为$\\sum num\[i\]$

对于每一个缸，二分它还能被喝几轮，如果第i个缸还能喝cnt轮，后面(排序后)的缸自然也可以喝cnt轮。易得$num\[i\]=now+cnt$，之后用树状数组判断位置在i之前的缸能否让它再喝一次，即剩下的次数是否大于等于在该缸之前(包括)的缸数，如果是的话now和num\[\]都要++。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<cstdlib>
    using namespace std;
    typedef long long ll;
    #define pa pair<ll,ll>
    const int N=100005;
    int n,m,tot,rest,now;
    ll x,w[N],a[N],num[N],cnt,total,ans;
    pa bu[N];
    namespace bit
    {
        ll c[N];
        int lb(int x){
         return x&-x;}
        void add(int x)
        {
            for( ;x<=n;x+=lb(x))
                c[x]++;
        }
        int ask(int x)
        {
            int res=0;
            for( ;x;x-=lb(x))
                res+=c[x];
            return res;
        }
    }
    int main()
    {
        scanf("%d%d%lld",&n,&m,&x);
        for(int i=1;i<=n;i++)
            scanf("%lld",&w[i]);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++)
            if(x>=w[i])bu[++tot]=make_pair((x-w[i])/a[i]+1,tot);
        sort(bu+1,bu+tot+1);
        rest=tot;
        for(int i=1;i<=tot;i++)
        {
            int l=0,r=m-now;
            while(l<=r)
            {
                int mid=l+r>>1;
                if(1LL*rest*mid<bu[i].first-total)l=mid+1,cnt=mid;
                else r=mid-1;
            }
            if(now+cnt==m)
            {
                ans+=(tot-i+1)*m;
                cout<<ans<<endl;
                exit(0);
            }
            num[i]=now+cnt;
            int pre=bu[i].second-bit::ask(bu[i].second);
            bit::add(bu[i].second);
            if(bu[i].first-rest*cnt-total>=pre)total++,num[i]++;
            total+=cnt*rest,now+=cnt;
            rest--;
            ans+=num[i];
        }
        cout<<ans<<endl;
        return 0;
    }

# C.所驼门王的宝藏 #

十分不敢相信居然会有这么水的省选题……

可以发现跳过去再跳过来的情况对统计答案造成了困难，所以考虑缩点。把整张图缩成一个森林之后我们要让它经过的点尽量多，所以找联通的最长链。

一句话题解：将每个格子和它能到达的格子暴力连边，然后Tarjan缩点，最后跑一遍拓扑求树上最长链就是答案。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<vector>
    #include<queue>
    #include<algorithm>
    using namespace std;
    const int M=1000005,N=1e5+5;
    int read()
    {
        int x=0,f=1;char ch=getchar();
        while(!isdigit(ch)){
         if(ch=='-')f=-1;ch=getchar();}
        while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
        return x*f;
    }
    struct room_
    {
        int x,y,op;
    }a[N];
    int n,R,C;
    vector<int> h[M],l[M],g[N];
    int tot,head[M<<2],nxt[M<<2],to[M<<2],deg[N],ans[N];
    void add(int x,int y)
    {
        to[++tot]=y;
        nxt[tot]=head[x];
        head[x]=tot;
    }
    int dfn[N],low[N],st[N],top=0,vis[N],bel[N],scc,ind,size[N];
    void tarjan(int x)
    {
        dfn[x]=low[x]=++ind;
        vis[x]=1;
        st[++top]=x;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=to[i];
            if(!dfn[y])tarjan(y),low[x]=min(low[x],low[y]);
            else if(vis[y])low[x]=min(low[x],dfn[y]);
        }
        if(low[x]==dfn[x])
        {
            scc++;int now=0;
            do
            {
                now=st[top--];
                size[scc]++;
                bel[now]=scc;
                vis[now]=0;
            }while(now!=x);
        }
    }
    int main()
    {
        n=read();R=read();C=read();
        for(int i=1;i<=n;i++)
        {
            a[i].x=read(),a[i].y=read(),a[i].op=read();
            h[a[i].x].push_back(i);l[a[i].y].push_back(i);
        }
        for(int i=1;i<=n;i++)
        {
            int op=a[i].op;
            if(op==1)
            {
                int sz=h[a[i].x].size();
                for(int j=0;j<sz;j++)
                {
                    if(h[a[i].x][j]==i)continue;
                    add(i,h[a[i].x][j]);
                }
            }
            else if(op==2)
            {
                int sz=l[a[i].y].size();
                for(int j=0;j<sz;j++)
                {
                    if(l[a[i].y][j]==i)continue;
                    add(i,l[a[i].y][j]);
                }
            }
            else if(op==3)
            {
                int sz;
                if(a[i].x>1)
                {
                    sz=h[a[i].x-1].size();
                    for(int j=0;j<sz;j++)
                    {
                        if(a[h[a[i].x-1][j]].y>=a[i].y-1&&a[h[a[i].x-1][j]].y<=a[i].y+1)
                            add(i,h[a[i].x-1][j]);
                    }
                }
                sz=h[a[i].x].size();
                for(int j=0;j<sz;j++)
                {
                    if(h[a[i].x][j]==i)continue;
                    if(a[h[a[i].x][j]].y>=a[i].y-1&&a[h[a[i].x][j]].y<=a[i].y+1)
                        add(i,h[a[i].x][j]);
                }
                if(a[i].x<R)
                {
                    sz=h[a[i].x+1].size();
                    for(int j=0;j<sz;j++)
                    {
                        int now=h[a[i].x+1][j];
                        if(a[now].y>=a[i].y-1&&a[now].y<=a[i].y+1)
                            add(i,now);
                    }
                }
            }
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])tarjan(i);
        for(int x=1;x<=n;x++)
            for(int i=head[x];i;i=nxt[i])
            {
                int y=to[i];
                if(bel[y]!=bel[x])
                    g[bel[x]].push_back(bel[y]),deg[bel[y]]++;
            }
        
        //debug();
        //puts("----------------------------------------");
    /*    for(int i=1;i<=scc;i++)
            if(!v[i])
            {
                num=0,dfs(i);
            }*/
        queue<int> q;
        for(int i=1;i<=scc;i++)
            if(!deg[i])q.push(i),ans[i]=size[i];
        while(!q.empty())
        {
            int x=q.front();
            q.pop();int sz=g[x].size();
            for(int i=0;i<sz;i++)
            {
                int y=g[x][i];
                ans[y]=max(ans[y],ans[x]+size[y]);
                if(!(--deg[y]))q.push(y);
            }
        }
        cout<<*max_element(ans+1,ans+1+scc)<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Rorschach-XR/p/11373906.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/d291583a9af847f6a7ae7f906de1c5ed.png