多校冲刺 noip 10.27

多校冲刺 noip 10.27

满意??不可能

最后两个题仍然是一点点的思路都没有

所以我只能去做前两个题

这就是我三分钟看题并打出树剖\(LCA\)的理由??

因为\(LCA\)的深度忘记乘二了,导致最后一题爆零了

T1 宝藏

这个我仍然简单做法,依旧是用\(STL\)水掉了别人用各种树过掉的题

所以是否可以枚举中位数判断

于是我们有了一种二分的做法

二分中位数的位置,对左右两边进行排序,分别取最小的\(\frac{x}{2}\)个

这样的话,复杂度远远不够

发现单调性:中位数随着个数的增加而减少

这样我们可以用双指针了,不需要二分了

那么排序可不可以省略呢??

我们可以用一个按照时间排序的\(set\)

只需要维护前\(\frac{x}{2}\)里时间最大的那个,动态更新时间和就好了

AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=3e5+5;
int n,q,T,ans[N];
struct node{
    int w,t,id;
    node(){}
    node(int x,int y,int z){w=x;t=y;id=z;}
    bool operator < (node a)const{
        if(t==a.t)return id<a.id;
        return t<a.t;
    }
    bool operator <= (node a)const{
        if(t==a.t)return id<=a.id;
        return t<=a.t;
    }
}sca[N];
bool com(node a,node b){return a.w==b.w?a.id<b.id:a.w<b.w;}
set<node> lef,rig;
signed main(){
    freopen("treasure.in","r",stdin);
    freopen("treasure.out","w",stdout);
    scanf("%lld%lld%lld",&n,&T,&q);
    fo(i,1,n)scanf("%lld%lld",&sca[i].w,&sca[i].t),sca[i].id=i;
    sort(sca+1,sca+n+1,com);
    fo(i,1,n-1)lef.insert(sca[i]);
    int now=n,le=0,ri=0;
    node ml=node(0,0,0),mr=node(0,0,0);
    lef.insert(ml);rig.insert(mr);
    set<node>::iterator it;
    bool flag=false;
    for(int x=1;x<=n;x+=2){
        //cout<<x<<endl;
        if(next(lef.find(ml))==lef.end()&&flag){ans[x]=-1;continue;}
        while(le+ri+sca[now].t>T&&now){
            rig.insert(sca[now]);
            it=rig.find(mr);
            if(sca[now]<=mr)ri+=sca[now].t-mr.t,mr=*--it;
            now--;
            it=lef.find(ml);
            if(sca[now]<=ml){
                if(++it!=lef.end())ml=*it;
                else {flag=true;break;}
                le+=ml.t-sca[now].t;
            }
            lef.erase(sca[now]);
        }
        //cout<<"SBV"<<endl;
        if(++lef.find(ml)==lef.end()&&flag){ans[x]=-1;continue;}
        ans[x]=sca[now].w;
        it=rig.find(mr);//cout<<"fuck"<<endl;
        if(next(it)==rig.end()){
            rig.insert(sca[now]);
            it=rig.find(mr);
            if(sca[now]<=mr)ri+=sca[now].t-mr.t,mr=*--it;
            now--;
            it=lef.find(ml);
            if(sca[now]<=ml){
                if(++it!=lef.end())ml=*it;
                else {flag=true;continue;}
                le+=ml.t-sca[now].t;
            }
            lef.erase(sca[now]);
        }
        it=rig.find(mr);mr=*next(it);ri+=mr.t;
        it=lef.find(ml);
        if(next(it)!=lef.end())ml=*next(it),le+=ml.t;
        else flag=true;
    }
    //cout<<"SBV"<<endl;
    fo(i,1,q){
        int x;scanf("%lld",&x);
        printf("%lld\n",ans[x]);
    }
    return 0;
}

T2 寻找道路

其实考场上的时候,我直接打了个最短路,取模比大小,呵呵呵

只要将所有为0的点先放到队列中,跑\(bfs\)

这样我们可以一直保证队列中的数是有序的,那么每一个点第一次被更新就是最小值

记得取队首的时候,要把所有距离相等的都取出来一起更新

AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=1e6+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f3f3f3f3f;
int ksm(int x,int y){
    int ret=1;
    while(y){
        if(y&1)ret=ret*x%mod;
        x=x*x%mod;y>>=1;
    }return ret;
}
int n,m;
struct node{
    int to,nxt,val;
}e[N*2];
int head[N],rp;
void add_edg(int x,int y,int z){
    e[++rp].to=y;
    e[rp].val=z;
    e[rp].nxt=head[x];
    head[x]=rp;
}
queue<int> q;
int dis[N],dep[N],ji[N],cnt;
bool vis[N];
void dfs(int x){
    dis[x]=0;dep[x]=0;vis[x]=true;
    for(int i=head[x],y;i;i=e[i].nxt){
        if(e[i].val)continue;
        y=e[i].to;
        if(vis[y])continue;
        dfs(y);
    }
}
signed main(){
    freopen("path.in","r",stdin);
    freopen("path.out","w",stdout);
    memset(dis,0x3f,sizeof(dis));
    memset(dep,0x3f,sizeof(dep));
    scanf("%lld%lld",&n,&m);
    for(int i=1,x,y,z;i<=m;i++){
        scanf("%lld%lld%lld",&x,&y,&z);
        add_edg(x,y,z);
    }
    dfs(1);
    fo(i,1,n)if(dis[i]==0)q.push(i);
    int las,now;
    while(!q.empty()){
        las=dep[q.front()];now=dis[q.front()];cnt=0;
        while(dep[q.front()]==las&&dis[q.front()]==now&&!q.empty())ji[++cnt]=q.front(),q.pop();
        fo(s,1,cnt){
            int x=ji[s];
            for(int i=head[x],y;i;i=e[i].nxt){
                if(e[i].val)continue;
                y=e[i].to;
                if(vis[y])continue;
                dis[y]=(dis[x]*2+e[i].val)%mod;
                dep[y]=dep[x]+1;
                q.push(y);vis[y]=true;
            }
        }
        fo(s,1,cnt){
            int x=ji[s];
            for(int i=head[x],y;i;i=e[i].nxt){
                if(!e[i].val)continue;
                y=e[i].to;
                if(vis[y])continue;
                dis[y]=(dis[x]*2+e[i].val)%mod;
                dep[y]=dep[x]+1;
                q.push(y);vis[y]=true;
            }
        }
    }
    fo(i,2,n)printf("%lld ",dis[i]==inf?-1:dis[i]);
    return 0;
}

T3 猪国杀

看到这个题的题目时我心态崩了

但是看完题心态没了

所以我一直在想一个可以拿到部分分的\(dp\)

然而我发现我的\(dp\)算重了,于是没有办法,就打了个暴力走人了

正解确实是\(dp\),不过好像不是我能力范围之内可以推出来的

首先有一个经典转化,对答案加上某一个数,相当于把这个数拆成很多个一,分散到方案数中

那么我们设\(f_i\)表示选取的牌数大于\(i\)的方案数,这样选了几张牌就会加几遍

考虑如何求出来这个数组

因为我们选取的牌一定是最小的那几张,所以我们直接按照牌的点数大小排序

同样是按照这个顺序去\(dp\),这样就可以很方便的做了

但是转移的时候别忘了乘上可重集排列的组合数

首先我们枚举已经确定的序列的最大值,然后枚举当前的最大值有多少个,然后后面就直接乘上瞎选的方案数就好了

枚举当前最大值以及个数,那么我们就确定了前面的值的最大值以及他们的和的上界

设\(g_{i,j,k}\)表示有多少个⻓度为\(i\)的正整数序列满足每一个数字不大于\(j\)且所有数字总和不超过\(k\)的方案数

这个是可以容斥的

\(g_{i,j,k}=\sum\limits_{t=0}^{i}(-1)^t {i \choose t} {k-t*(j-1) \choose i}\)

这个请读者自行理解

最终的式子就是

\(f_i=\sum\limits_{j=1}^{A}\sum\limits_{k=1}^{n-i}g_{i,j-1,m-kj}{n\choose i}\sum\limits_{t=k}^{n-i}{n-i \choose t}(A-j)^{n-i-t}\)

\(ans*A^n=\sum\limits_{i=0}^{n}f_i\)

直接带入求值就行了,但是注意剪枝,没有贡献的地方直接停止

AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=105;
const int M=1005;
const int mod=998244353;
int ksm(int x,int y){
    int ret=1;
    while(y){
        if(y&1)ret=ret*x%mod;
        x=x*x%mod;y>>=1;
    }return ret;
}
int n,m,A,ans;
int jc[M],inv[M],km[M][M];
int C(int n,int m){
    if(n<0||m<0||n<m)return 0;
    return jc[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
    freopen("legend.in","r",stdin);
    freopen("legend.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&A);
    jc[0]=1;fo(i,1,1000)jc[i]=jc[i-1]*i%mod;
    inv[0]=1;inv[1000]=ksm(jc[1000],mod-2);
    fu(i,999,1)inv[i]=inv[i+1]*(i+1)%mod;
    km[0][0]=1;
    fo(i,1,A){
        km[i][0]=1;
        fo(j,1,n)km[i][j]=km[i][j-1]*i%mod;
    }
    fo(i,0,n)fo(j,1,A)fo(k,1,n-i){
        if(m<j*k)continue;
        int bas=1,res1=0,res2=0;
        fo(t,0,i)res1=(res1+C(i,t)*C(m-k*j-t*(j-1),i)%mod*bas+mod)%mod,bas=-bas;
        fo(t,k,n-i)res2=(res2+C(n-i,t)*km[A-j][n-i-t]%mod)%mod;
        ans=(ans+res1*res2%mod*C(n,i))%mod;
    }
    printf("%lld",ans*ksm(ksm(A,n),mod-2)%mod);
    return 0;
}

T4 数树

这个??不会,树形\(dp\)忒难

看代码吧

AC_code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=3005;
const int M=15;
const int mod=998244353;
int ksm(int x,int y){
    int ret=1;
    while(y){
        if(y&1)ret=1ll*ret*x%mod;
        x=1ll*x*x%mod;y>>=1;
    }return ret;
}
int n,m;
int ans,sum;
struct graph1{
    int fa[N];
    vector<int> e[N];
    void add_edg(int x,int y){
        e[x].push_back(y);
        e[y].push_back(x);
    }
}t1;
struct graph2{
    int fa[M],son[M];
    vector<int> e[M];
    void add_edg(int x,int y){
        e[x].push_back(y);
        e[y].push_back(x);
    }
    void dfs(int x,int f){
        fa[x]=f;son[x]=(1<<x-1);
        for(int y:e[x])if(y!=f)dfs(y,x),son[x]|=son[y];
    }
}t2;
int f[N][1<<10],tmp[1<<10];
void dp(int x,int fa){
    fo(i,1,m)f[x][1<<i-1]=1;
    for(int y:t1.e[x]){
        if(y==fa)continue;
        dp(y,x);
        fo(i,1,(1<<m)-1)tmp[i]=f[x][i];
        fo(s,1,(1<<m)-1){
            if(!f[x][s])continue;
            fo(i,1,m){
                if(s&t2.son[i])continue;
                if(!f[y][t2.son[i]])continue;
                f[x][s|t2.son[i]]=(f[x][s|t2.son[i]]+1ll*tmp[s]*f[y][t2.son[i]]%mod)%mod;
            }
        }
    }
    ans=(1ll*ans+f[x][(1<<m)-1])%mod;
}
int p[M];
vector<int> now[N];
const bool operator == (vector<int> &a,vector<int> &b){
    if(a.size()!=b.size())return false;
    for(int i=0;i<a.size();i++)if(a[i]!=b[i])return false;
    return true;
}
signed main(){
    freopen("count.in", "r", stdin);
    freopen("count.out", "w", stdout);
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        t1.add_edg(x,y);
    }
    scanf("%d",&m);
    for(int i=1,x,y;i<m;i++){
        scanf("%d%d",&x,&y);
        t2.add_edg(x,y);
    }
    fo(i,1,m){
        fo(x,1,n)fo(s,1,(1<<m)-1)f[x][s]=0;
        t2.dfs(i,0);dp(1,0);
    }
    fo(i,1,m)p[i]=i;
    fo(i,1,m)sort(t2.e[i].begin(),t2.e[i].end());
    do{
        fo(i,1,m)now[p[i]]=t2.e[i];
        fo(i,1,m){
            for(int &j:now[i])j=p[j];
            sort(now[i].begin(),now[i].end());
        }
        bool flag=true;
        fo(i,1,m)if(!(now[i]==t2.e[i])){flag=false;break;}
        if(flag)sum++;
    }while(next_permutation(p+1,p+m+1));
    ans=1ll*ans*ksm(sum,mod-2)%mod;
    printf("%d",ans);
}
上一篇:Noip模拟78 2021.10.15


下一篇:noip模拟76[失落]