2019牛客暑期多校训练营（第二场）

题目

链接：https://ac.nowcoder.com/acm/contest/882

A Eddy Walker （概率思维）

题意： n 个点构成一个环，标记为 $0,\dots,n-1$ 。小明会随机往前走，或者往后走。当每个点都被走过至少一次时，就会停止，问最终落在 m 点的概率是多少。

思路：

设 $f (n, m)$ 是最终结束走到 m 点的概率。那么可以得到两个关系： $f(n,m)=\frac {f(n,m-1)+f(n,m+1)}{2}$ ，且 $f (n, m) = f (n, n - m)$ 。由此可以得到每个点的概率相同。
特判一下特殊情况： n=1 ,m=0 时，概率为 1 。n >1 ,m=0 时，概率为 0 。因为 0 这个点一开始就被访问了，最后不可能落在 0 点上面。
题目要求的概率，是每次询问概率的累乘。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5,mod=1e9+7;
int t,n,m;
int qpow(int b,int n,int mod)
{
    int res=1;
    while(n)
    {
        if(n&1) res=1ll*res*b%mod;
        b=1ll*b*b%mod;
        n>>=1;
    }
    return res;
}
int main()
{
    scanf("%d",&t);
    int ans=1;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        if(n==1) printf("%d\n",ans);
        else
        {
            if(m==0) ans=0;
            else ans=1ll*ans*qpow(n-1,mod-2,mod)%mod;
            printf("%d\n",ans);
        }
    }
    return 0;
}

B Eddy Walker 2 （线性递推）

题意：一个人随机往前走 $[1, k]$ 步，任意一种概率是 $\frac 1k$ 。问最后落在 n 点的概率是多少。 n = -1 时，表示求无穷远处的概率是多少。

思路：

求无穷远处的概率：步长的期望值是： $\frac {1+2+\dots+k} {k}=\frac {k+1}{2}$ 。那么走一步的概率就是 $\frac 2{k+1}$ ，那么走到无穷远处的概率就是 $\frac 2{k+1}$ 。
求落在 n 点的概率，设 dp[i] 表示落在 i 点的概率，递推可得：
$dp[i]=\frac 1{k}\sum_{j=1}^k dp[i-j]$

-对这个式子用BM递推就好了。时间复杂度是 $k^2logn$ ，如果用矩阵快速幂时间复杂度是 $k^3logn$

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;

#define rep(i,a,n) for (long long i=a;i<n;i++)
#define per(i,a,n) for (long long i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((long long)(x).size())
typedef vector<long long> VI;
typedef pair<long long,long long> PII;
const ll mod=1e9+7;
ll powmod(ll a,ll b)
{
    ll res=1;
    a%=mod;
    assert(b>=0);
    for(; b; b>>=1)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
    }
    return res;
}

namespace linear_seq
{
    const long long N=10010;
    ll res[N],base[N],_c[N],_md[N];
    vector<long long> Md;
    void mul(ll *a,ll *b,long long k)
    {
        rep(i,0,k+k) _c[i]=0;
        rep(i,0,k) if (a[i]) rep(j,0,k)
            _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
        for (long long i=k+k-1; i>=k; i--) if (_c[i])
                rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
        rep(i,0,k) a[i]=_c[i];
    }
    long long solve(ll n,VI a,VI b)// a 系数 b 初值 b[n+1]=a[0]*b[n]+...
    {
        ll ans=0,pnt=0;
        long long k=SZ(a);
        assert(SZ(a)==SZ(b));
        rep(i,0,k) _md[k-1-i]=-a[i];
        _md[k]=1;
        Md.clear();
        rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
        rep(i,0,k) res[i]=base[i]=0;
        res[0]=1;
        while ((1ll<<pnt)<=n) pnt++;
        for (long long p=pnt; p>=0; p--)
        {
            mul(res,res,k);
            if ((n>>p)&1)
            {
                for (long long i=k-1; i>=0; i--) res[i+1]=res[i];
                res[0]=0;
                rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
            }
        }
        rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
        if (ans<0) ans+=mod;
        return ans;
    }
    VI BM(VI s)
    {
        VI C(1,1),B(1,1);
        long long L=0,m=1,b=1;
        rep(n,0,SZ(s))
        {
            ll d=0;
            rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
            if (d==0) ++m;
            else if (2*L<=n)
            {
                VI T=C;
                ll c=mod-d*powmod(b,mod-2)%mod;
                while (SZ(C)<SZ(B)+m) C.pb(0);
                rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
                L=n+1-L;
                B=T;
                b=d;
                m=1;
            }
            else
            {
                ll c=mod-d*powmod(b,mod-2)%mod;
                while (SZ(C)<SZ(B)+m) C.pb(0);
                rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
                ++m;
            }
        }
        return C;
    }
    long long gao(VI a,ll n)
    {
        VI c=BM(a);
        c.erase(c.begin());
        rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
        return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
    }
};

int t,k;
ll n;
int dp[10010],pref[10010];

int qpow(int b,int n,int mod)
{
    int res=1;
    while(n)
    {
        if(n&1) res=1ll*res*b%mod;
        b=1ll*b*b%mod;
        n>>=1;
    }
    return res;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%lld",&k,&n);
        if(n==-1)
        {
            int ans=2ll*qpow(k+1,mod-2,mod)%mod;
            printf("%d\n",ans);
            continue;
        }
        dp[0]=pref[0]=1;
        int invk=qpow(k,mod-2,mod);
        for(int i=1; i<=k; ++i)
        {
            dp[i]=1ll*pref[i-1]*invk%mod;
            pref[i]=(1ll*pref[i-1]+dp[i])%mod;
        }
        for(int i=k+1; i<=3*k+1; ++i)
        {
            dp[i]=(1ll*pref[i-1]-pref[i-k-1]+mod)*invk%mod;
            pref[i]=(1ll*pref[i-1]+dp[i])%mod;
        }
        vector<ll> v;
        for(int i=0; i<=3*k+1; ++i) v.push_back(dp[i]);
        printf("%lld\n",linear_seq::gao(v,n));
    }
    return 0;
}

D Kth Minimum Clique （bitset 维护团）

题意：给定一个 n 个带点权的无向图，求权值第 k 小的团。空集算第一小的团。 $(1\le n \le 100 ,1\le k \le 10^6)$

思路：用 bitset 来维护向一个团中加点的操作。

首先将空集压入优先队列中。然后每次弹出一个团，向它加入新的点，如果构成了新的团，那么就继续压入优先队列中。
加点操作：比如当前团第 i 位为 0，加看一下第 i 个点，能不能加入构成一个新的团，即 (bs & mp[i])==bs 。如果第 i 个点在 bs 取 1 的位置都存在边，则结果还是 bs 。
为了加点不重复，每次都可以从当前的团中，找到一个位置 p，bs[p]为 0，且 p 后面没有任何的 1 （也就是从后面开始加点），往前加会产生重复。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=110;
struct Node
{
    ll val;
    bitset<110> bs;
    bool operator<(const Node& b) const
    {
        return val>b.val;
    }
};
int n,k,val[maxn];
char s[110];
bitset<110> mp[110];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; ++i) scanf("%d",&val[i]);
    for(int i=1; i<=n; ++i)
    {
        scanf("%s",s+1);
        for(int j=1; j<=n; ++j) mp[i][j]=s[j]-'0';
    }
    priority_queue<Node> pq;
    bitset<110> t;
    pq.push({0,t});

    while(!pq.empty())
    {
        auto t=pq.top();
        pq.pop();
        k--;
        if(k==0)
        {
            printf("%lld\n",t.val);
            return 0;
        }
        int pos=1;
        for(int i=1; i<=n; ++i)
            if(t.bs[i]) pos=i+1;

        for(int i=pos; i<=n; ++i)
        {
            if(t.bs[i]==0&&((t.bs&mp[i])==t.bs))
            {
                t.bs[i]=1;
                pq.push({t.val+val[i],t.bs});
                t.bs[i]=0;
            }
        }
    }
    puts("-1");
    return 0;
}

E MAZE （线段树上维护矩阵中DP值的转移）

题意：给定一张 $\times m$ 的有 $01$ 组成的地图， $0$ 表示可以通行， $1$ 表示有墙。从一个点开始，可以往下、往左、往右走。维护 $q$ 个操作，一共两种类型：

q = 1 时，修改 $m p [x] [y]$ 的状态
q = 2 时，询问从 $(1, x)$ 走到 $(n, y)$ 的方案数

思路：

矩阵中 $a [i] [j]$ 表示从当前这些行中，从第 $i$ 列走到第 $j$ 列的方案数。

#include <bits/stdc++.h>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define ll long long
using namespace std;
const int maxn=50010,mod=1e9+7;
int n,m,q;
int b[maxn][11];
char s[20];
struct Matrix
{
    int a[11][11];
    friend Matrix operator*(const Matrix& a,const Matrix& b)
    {
        Matrix res;
        memset(res.a,0,sizeof(res.a));
        for(int i=1; i<=m; ++i)
            for(int j=1; j<=m; ++j)
                for(int k=1; k<=m; ++k)
                    res.a[i][j]=(1ll*res.a[i][j]+1ll*a.a[i][k]*b.a[k][j])%mod;
        return res;
    }
} st[maxn<<2];

void solve(int b[11],Matrix& x)
{
    memset(x.a,0,sizeof(x.a));
    for(int i=1; i<=m; ++i)
    {
        int j=i;
        while(j>=1&&b[j]!=1) x.a[i][j]=1,j--;
        j=i;
        while(j<=m&&b[j]!=1) x.a[i][j]=1,j++;
    }
}
void build(int rt,int L,int R)
{
    if(L==R)
    {
        solve(b[L],st[rt]);
        return;
    }
    int mid=(L+R)>>1;
    build(ls,L,mid);
    build(rs,mid+1,R);
    st[rt]=st[ls]*st[rs];
}
void update(int rt,int pos,int L,int R)
{
    if(L==R)
    {
        solve(b[L],st[rt]);
        return;
    }
    int mid=(L+R)>>1;
    if(pos<=mid) update(ls,pos,L,mid);
    else update(rs,pos,mid+1,R);
    st[rt]=st[ls]*st[rs];
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1; i<=n; ++i)
    {
        scanf("%s",s+1);
        for(int j=1; j<=m; ++j) b[i][j]=s[j]-'0';
    }
    build(1,1,n);
    while(q--)
    {
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)
        {
            b[x][y]^=1;
            update(1,x,1,n);
        }
        else printf("%d\n",st[1].a[x][y]);
    }
    return 0;
}

F Partition problem （dfs + 优化）

题意：有 2n 个人，任意两个人之间有竞争值 $v [i] [j]$ 。将这 2n 个人分成两组，每组 n 个人，使得两组之间的竞争值最大。即计算： $\sum_{i=1}^{2n} \sum_{j=i+1}^{2n} v[i][j]$ （且 i 、j 不在同一个队伍中）。

思路：首先有 $C_{2n}^n$ 种选择方法，然后权值计算需要 $2n)^2$ ，总复杂度为 $C_{2n}^n (2n)^2$ 。

这样会TLE，考虑在选择的时候就计算权值。
因此记录团队当前选择的所有人的权值，然后每次加一个人将相应地加上或者减去权值。
这样复杂度就变成了 $C_{2n}^n (2n)$

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int n,v[30][30];
ll ans=0;
void dfs(int p,int mask,int k,ll val)
{
    if(k==n)
    {
        ans=max(ans,val);
        return;
    }
    for(int i=p; i<=2*n; ++i)
    {
        ll tmp=val;
        for(int j=1; j<=2*n; ++j)
        {
            if(mask>>j-1&1) tmp-=v[i][j];
            else tmp+=v[i][j];
        }
        dfs(i+1,mask|(1<<i-1),k+1,tmp);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=2*n; ++i)
        for(int j=1; j<=2*n; ++j)
            scanf("%d",&v[i][j]);
    ll val=0;
    for(int i=1; i<=2*n; ++i) val+=v[1][i];
    dfs(2,1,1,val);
    printf("%lld\n",ans);
    return 0;
}

H Second Large Rectangle （单调栈）

题意：给定 01 矩阵，求第二大的矩阵的大小。

思路：单调栈求最大矩阵 xy。同时用 (x-1)y、x(y-1)，来更新最大值和次大值

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int n,m;
int a[1010][1010],sta[1010],top,l[1010];
char s[1010];
int mx1,mx2;
void update(int x,int y)
{
    if(mx1<x*y)
    {
        mx2=mx1;
        mx1=x*y;
    }
    else mx2=max(mx2,x*y);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i)
    {
        scanf("%s",s+1);
        for(int j=1; j<=m; ++j)
		{
			a[i][j]=(s[j]=='1');
			if(a[i][j]==1) a[i][j]+=a[i-1][j];
		 } 
    }
    mx1=0,mx2=0;
    for(int i=1; i<=n; ++i)
    {
        top=0;
        a[i][m+1]=-1;
        for(int j=1; j<=m+1; ++j)
        {
            l[j]=j;
            while(top&&a[i][j]<=a[i][sta[top]])
            {
                int x=a[i][sta[top]],y=j-l[sta[top]];
                update(x,y);
                update(x-1,y);
                update(x,y-1);
                l[j]=l[sta[top]];
                top--;
            }
            sta[++top]=j;
        }
    }
    printf("%d\n",mx2);
    return 0;
}

J Subarray （思维 + 抓住小范围）

题意：给定一个长度为 1e9 且由 -1 和 1 组成的数组，给定 n 个区间 $l_i,r_i]$ 表示这一段是 1 ，且这 n 个区间的总长不超过 1e7。问有多少个区间的和大于 0 。

思路：

这 1e7 的区间是解题的关键。1e7往左、往右最多可以扩展1e7个范围，使得它们变成正区间。所以只要处理每个区间 $l_i,r_i]$ 往左往右最多能够扩展多少就好了。
然后就变成了，对区间上的每一个点查询，有多少个前缀和小于自己的数。
如果用 bit 来写，那么时间复杂度是 3e7log(3e7) 显然不合适。
抓住一个性质，它是一位一位变化的，每次只相差了 1 ，所以可以动态维护值。
pre表示前缀和，sum表示小于pre的数量，num[i] 表示前缀和为 i 的数的总个数。维护这些值，就可以计算答案了。
初始时， num[pre] 设为 1 ，表示用 pre 来代替 0 的位置
这里每次处理完一个区间之后，不用清空数组，因为下一个区间 -1 的数量足够多，可以走到 num 数组没有被上一个区间影响的位置继续更新。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5,maxm=1e7+10;

int n,l[maxn],r[maxn],L[maxn],R[maxn];
ll num[maxm*3];

int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d%d",&l[i],&r[i]);
        l[i]++,r[i]++;
    }
    R[1]=r[1]-l[1]+1;
    for(int i=2; i<=n; ++i) R[i]=max(0,R[i-1]-(l[i]-r[i-1]-1))+r[i]-l[i]+1;
    L[n]=r[n]-l[n]+1;
    for(int i=n-1; i>=1; --i) L[i]=max(0,L[i+1]-(l[i+1]-r[i]-1))+r[i]-l[i]+1;
    int pre=2e7+10;
    num[pre]=1;
    ll ans=0,sum=0;
    for(int i=1,j; i<=n; i=j+1)
    {
        j=i;
        while(j+1<=n&&R[j]+L[j+1]>=l[j+1]-r[j]-1) j++;
        int le=max(1,l[i]-L[i]),ri=min((int)1e9,r[j]+R[j]);
        int now=i;
        for(int k=le; k<=ri; ++k)
        {
            if(k>=l[now]&&k<=r[now])
            {
                pre++;
                num[pre]++;
                sum+=num[pre-1];
            }
            else
            {
                pre--;
                sum-=num[pre];
                num[pre]++;
            }
            ans+=sum;
            if(k>r[now]) now++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}