Skip to content

0420 C组模拟赛 题解

传送门

T1 题解

首先容易发现具体填哪些数并不影响期望，我们就不考虑这一部分。

考虑权值 $2^{R+C}$ 的意义。

发现等价于当前情况包含哪几种其余情况。

所以权值和等价于所有情况总共被多少种情况包含。

枚举 $R,C,k$ 利用组合数求解（$k$ 为矩阵中涂黑多少个格子，上下界很容易算）。

$$\sum\limits_{R=0}^n\sum\limits_{C=0}^n\dbinom{n}{R}\cdot\dbinom{n}{C}\cdot\dbinom{n\times n -(R+C)\times n+R\times C }{k-(R+C)\times n+R\times C}$$

预处理 $\binom{n}{i}$ 和 $\binom{n\times n-i}{k-i}$ 即可，复杂度 $O(n^2)$

code

code 
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#define mem(a,b) memset(a,b,sizeof(a))
#include<vector>
#define pbk(a) emplace_back(a)
#define forup(i,s,e) for(register int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(register int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=305; 
long double Cn[N],Cmk[N*N],ans;
int n,m,k;
signed main()
{
    n=read(),m=read(),k=read();
    Cn[0]=1;
    forup(i,1,n){
        Cn[i]=Cn[i-1]*(n-i+1)/i;        
    }
    Cmk[0]=1;
    forup(i,1,k){
        Cmk[i]=Cmk[i-1]*(k-i+1)/(m-i+1);        
    }
    forup(i,0,n){
        forup(j,0,n)
        {
            int zy=i*n+j*n-i*j;
            if(zy>k) continue;
            ans+=Cn[i]*Cn[j]*Cmk[zy];
        }       
    }
    if(ans>=1e99) ans=1e99;
    printf("%.15Lf",ans);
}

T2 题解

首先我们可以进行离散化，先把安全点排序。对于每种矿物，预处理出可以采到它的安全点左右端点，这一步可以利用二分 $O(m\log m+n \log m)$ 解决。

接下来我们考虑如何不重不漏地计算列表数，容易想到，可以利用某种方法将矿物排序后，对于每种矿物，计算出一定包含它，且仅包含编号小于等于它的矿物的列表数量。假设当前矿物与编号小于它的 $k$ 种矿物相交，那么它产生的贡献就是 $2^{k}$ 。

接下来考虑如何计算 $k$，这是一个类似于二维偏序的过程，我们把矿物按 $l$ 升序排列，利用一个树状数组维护每个矿物影响的安全点。每次查询时，只需要查询点 $l_i$ 和几个区间重合，因为按 $l$ 升序后就不会出现前面的区间与当前矿物有交，但不覆盖点 $l$ 的情况了。

复杂度 $O(n\log n)$

code

code 
#include<iostream>
#include<algorithm>
#include<string.h>
#define mem(a,b) memset(a,b,sizeof(a))
#include<vector>
#include<set>
#define pbk(a) emplace_back(a)
#define forup(i,s,e) for(register int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(register int i=(s);i>=(e);i--)
#define abs(x) (((x)^((x)>>63))-((x)>>63))
using namespace std;
#define gc getchar()
inline int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f,mod=998244353;
int n,m,a[N],ans;
int ksm(int a,int b){
    int c=1;
    while(b){
        if(b&1) c=(1ll*a*c)%mod;
        a=(1ll*a*a)%mod;
        b>>=1;
    }
    return c;
}
struct Node{
    int l,r;
}s[N];
bool cmp(Node a,Node b){
    if(a.l!=b.l) return a.l<b.l;
    return a.r<b.r;
}
struct Tree{
    int c[N];
    void upd(int x,int k){for(;x<=m;x+=x&-x)c[x]=(c[x]+k)%mod;}
    int sum(int x){int res=0;for(;x>0;x-=x&-x)res=(res+c[x])%mod;return res;}
}mt;
signed main(){
    n=read();m=read();
    forup(i,1,n){
        s[i].l=read();s[i].r=read();
    }
    forup(i,1,m){
        a[i]=read();
    }
    sort(a+1,a+m+1);
    m=unique(a+1,a+m+1)-a-1;
    forup(i,1,n){
        s[i].l=lower_bound(a+1,a+m+1,s[i].l)-a;
        s[i].r=upper_bound(a+1,a+m+1,s[i].r)-a-1;
    }
    sort(s+1,s+n+1,cmp);
    forup(i,1,n){
        if(s[i].l>s[i].r) continue;
        ans=(ans+ksm(2,mt.sum(s[i].l)))%mod;
        mt.upd(s[i].l,1);mt.upd(s[i].r+1,-1);
    }
    printf("%d",ans);
}

T3 题解

20pts

暴搜。

40pt

区间 DP，设 $dp_{i,j}$ 表示区间 $[i,j]$ 能否转换，转移方程很好推，不细讲。

70pts

考虑我们如何判断一整个字符串能否转换。

容易想到，用一个栈来维护，从前往后遍历一遍，每次读到元素和栈顶不同就入栈，相同就出栈。假如读完一个字符串栈空了说明可以转化。

推广一下，假如 $i$ 处的栈和 $j$ 处的相同（$j < i$）那么区间 $[j+1,i]$ 就是一个可转化的区间。

我们用哈希维护一下没个位置的栈，对于每个位置，$O(n)$ 地扫一遍前面的看有没有一样的栈，每有一个答案就加一，复杂度 $O(n^2)$。

100pts

用一个 map 来维护一下每个哈希值出现的次数，类似于 $70$ 分做法，复杂度 $O(n\log n)$。

需要注意，这道题数据大了之后容易出现哈希冲突，可以利用 pair 用双哈希解决。

code

code 
#include<iostream>
#include<algorithm>
#include<string.h>
#define mem(a,b) memset(a,b,sizeof(a))
#include<vector>
#include<stack>
#include<map>
#define pbk(a) emplace_back(a)
#define mkp(a,b) make_pair(a,b)
#define forup(i,s,e) for(register int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(register int i=(s);i>=(e);i--)
#define abs(x) (((x)^((x)>>63))-((x)>>63))
using namespace std;
#define gc getchar()
inline int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc
using ll=long long;
const int N=1e6+5,inf=0x3f3f3f3f,P=13331,mod1=1e9+7,mod2=1e9+9;
int ksm(int a,int b,int p){
    int c=1;
    while(b){
        if(b&1) c=1ll*c*a%p;
        a=1ll*a*a%p;
        b>>=1;
    }
    return c;
}
int n;
ll ans;
char s[N];
ll hush1,hush2;
stack<char> stk;
map<pair<ll,ll>,int> mp;
signed main(){
    scanf(" %s",s+1);
    n=strlen(s+1);
    int inv1=ksm(13331,mod1-2,mod1),inv2=ksm(13331,mod2-2,mod2);
    mp[mkp(0,0)]++;
    forup(i,1,n){
        if(stk.empty()||stk.top()!=s[i]){
            stk.push(s[i]);
            hush1=1ll*(hush1*P+s[i]-'a'+1)%mod1;
            hush2=1ll*(hush2*P+s[i]-'a'+1)%mod2;
        }else{
            stk.pop();
            hush1=1ll*(hush1+mod1-(s[i]-'a'+1))*inv1%mod1;
            hush2=1ll*(hush2+mod2-(s[i]-'a'+1))*inv2%mod2;
        }
        ans+=mp[mkp(hush1,hush2)];
        mp[mkp(hush1,hush2)]++;
    }
    printf("%lld",ans);
}

Comments