20181017多校联测


T1题意


给你N个区间和M个点,问有几个点能有被包含的区间(一个区间和一个点只能用一次)


Solution


典型贪心,按线段右端点排序,然后拿STL随便瞎搞就出来了


Code
#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 200100
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
int n,m,d,ans;
struct node{int l,r;
    inline void add(){read(l),read(r);}
    inline int operator <(const node&oth)const{
        return r<oth.r;
    }
}e;
vector<node> s;
multiset<int> t;
int main(){
    read(n);read(m);
    for (int i=1; i<=n; ++i) e.add(),s.push_back(e);
    for (int i=1; i<=m; ++i) read(d),t.insert(d);
    sort(s.begin(),s.end());
    for (int i=0; i<n; ++i){ it=t.lower_bound(s[i].l);
        if (it!=t.end()&&*it<=s[i].r)ans++,t.erase(it);
    }
    wt(ans,'\n');
    return 0;
}


T2题意


给你N个点,求拿这N个点构成的树的深度的期望并对P取模(保证P为质数)


Solution


预处理dp[i][j]表⽰i个点的森林,有j个点在第⼀棵树的概率,转移考虑第i个点是否在第⼀棵⼦树中,我们有状态转移⽅程

令f[i][j]表⽰有i个点的树,深度不超过j的概率,g[i][j]表⽰有i个点的森林,深度不超过j的概率,f[i][j]直接从g[i-1][j-1]转移来;g[i][j]考虑枚举第⼀棵树的⼤⼩k,从⼀棵树和⼀个森林转移来,同时还要乘上第⼀棵⼦树⼤⼩为k的概率,我们有状态转移⽅程:

最后只要⽤f[n][j]-f[n][j-1]就可以得到深度为j的树的概率。


Code
#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 250
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
template<typename T> inline void pow(T a,T b,T p,T&ret){
    ret=1,a%=p;while(b){if (b&1) (ret*=a)%=p;a=(a*a)%p;b>>=1;}
}
ll n,p,ans,dp1[maxn][maxn],dp2[maxn][maxn],dp3[maxn][maxn],res[maxn],inv[maxn];
inline ll DP2(int x,int y);
inline ll DP1(int x,int y){
    if (dp1[x][y]!=-1) return dp1[x][y];
    dp1[x][y]=DP2(x-1,y-1);return dp1[x][y];
}
inline ll DP2(int x,int y){
    if (y<0) return 0;if (x==0) return 1;
    if (dp2[x][y]!=-1) return dp2[x][y];
    dp2[x][y]=0;for (int k=1; k<=x; k++)
        dp2[x][y]=(dp2[x][y]+((DP1(k,y)*DP2(x-k,y))%p*dp3[x][k])%p)%p;
    return dp2[x][y];
}
inline void pre(){
    if (n==1) puts("0"),exit(0);inv[1]=1,dp3[1][1]=1;
    for (ll i=2; i<=n; ++i) pow(i,p-2,p,inv[i]);
    memset(dp1,-1,sizeof dp1);memset(dp2,-1,sizeof dp2);
    for (int i=2; i<=n; ++i) for (int j=1; j<=i; ++j)
        dp3[i][j]=(((dp3[i-1][j-1]*1ll*(1ll*j-1ll))%p*inv[i])%p+((dp3[i-1][j]*1ll*(1ll*i-1ll*j))%p*inv[i])%p)%p;
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    read(n),read(p);pre();
    for (int i=2; i<=n; ++i) res[i]=DP1(n,i);res[1]=0;
    for (int i=2; i<=n; ++i) ans=(ans+(((res[i]-res[i-1])%p)*i)%p)%p;
    wt((ans-1+p)%p,'\n');
    return 0;
}


T3题意


给你一棵树,每次将编号在区间[l,r]的点染成黑色(每次染色前每个点都为白色),求每次染色后黑点的联通块个数。


Solution


二维偏序
对于每个询问,我们只要知道两端点都没被影响到的边的数量,就能很好地算出联通块的个数。
将边按编号排序,将询问按右端点排序,再用树状数组维护左端点。
据说能拿主席树写,不会


Code
#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 200100
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
struct node{
    int l,r,t,d;
    inline void add(){read(l),read(r);}
    inline int operator <(const node&oth)const{
        return l!=oth.l?l>oth.l:r!=oth.r?r<oth.r:t<oth.t;
    }
}t[maxn<<1];
int ans[maxn],tr[maxn],n,q,cnt;
inline void ins(int x){for (; x<=n; x+=lowbit(x)) tr[x]++;}
inline int find(int x){int ret=0;for (; x; x-=lowbit(x)) ret+=tr[x];return ret;}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    read(n),read(q);
    for (int i=1; i<n; ++i) t[++cnt].add();
    for (int l,r,i=1; i<=q; ++i){
        read(l),read(r);ans[i]=r-l+1;++cnt;
        t[cnt].l=l,t[cnt].r=r,t[cnt].t=1,t[cnt].d=i;
    }
    sort(t+1,t+cnt+1);
    for (int i=1; i<=cnt; ++i)
        if (!t[i].t) ins(t[i].r);
        else ans[t[i].d]-=find(t[i].r);
    for (int i=1; i<=q; ++i) wt(ans[i],'\n');
    return 0;
}

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s