2017 10 08 NOIP2017模拟赛

时间：2022-12-17 12:05:35

这次考的还不错哈
可惜第二题输入的数据忘开longlong了。。。只有80分

弹钢琴 1794

这题的情景描述还是比较坑的
其实讲的就是从n个数中取k个，将所有情况里的最大值加起来

只要排序一下（从小到大）
就可以发现每个数只要是和它前面的组合，这样它就是组合的最大值
用前缀和维护一下1~k的组合数量就可以了

不过这题用逆元结合下费马小定理也能直接算出来

删除数字 2988

又是一道状压DP
我们只需要计录一下当前行的数的状态
就可以转移了，当然，别忘了开longlong。。。

如果直接枚举上一层状态，再加上枚举当前状态，时间复杂度显然超了
其实可以发现在寻找上一层的状态的时候
只有那些小于或者等于当前状态的数是合法的

那么就可以将每一层可以生成的数都sort一遍
转移状态的时候二分查找一下就能在log的时间里找到
当然，这么做要将dp数组维护一下前缀和

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

#define FOR(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;++i)
#define DOR(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;--i)
#define INF 0x3f3f3f3f
#define LL long long
#define N 105
#define P 1000000007

void chkmx(int &a,int b){if(a<b)a=b;}
void chkmi(int &a,int b){if(a>b)a=b;}
int MAX(int a,int b){return a>b?a:b;}
int MIN(int a,int b){return a<b?a:b;}

int Num[N][1<<13],l[N];
LL ans,dp[N][1<<13],A[N],Sum[N][1<<13];
int n;

void Init(){
    FOR(i,0,n){
        LL t=A[i];
        while(t) Num[i][l[i]++]=t%10,t/=10;
        FOR(j,1,(1<<l[i])-1){
            LL &sum=Sum[i][j],h=1;
            FOR(k,0,l[i]-1) if(j&(1<<k)) sum+=Num[i][k]*h,h*=10;
        }
    }
    FOR(i,0,n) sort(Sum[i]+1,Sum[i]+(1<<l[i]));
}
LL Find(int i,LL sum){
    int L=0,R=(1<<l[i])-1,mid,tmp=0;
    while(L<=R){
        mid=L+R>>1;
        if(Sum[i][mid]<=sum) tmp=mid,L=mid+1;
        else R=mid-1;
    }
    return dp[i][tmp];
}
int main(){
// freopen("num.in","r",stdin);
// freopen("num.out","w",stdout);
    cin>>A[0]>>n;
    FOR(i,1,n) A[i]=A[i-1]+1;
    Init();
    FOR(i,1,(1<<l[0])-1) dp[0][i]=1+dp[0][i-1];
    FOR(i,1,n) FOR(j,1,(1<<l[i])-1){
        dp[i][j]=Find(i-1,Sum[i][j]);
        dp[i][j]=(dp[i][j]+dp[i][j-1])%P;
    }
    cout<<dp[n][(1<<l[n])-1]<<endl;
    return 0;
}

其实还有一种方法效率更高
排完序后，可以利用类似归并排序的方法直接转移
这就能实现在线性时间内完成一行的状态转移

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

#define FOR(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;++i)
#define DOR(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;--i)
#define INF 0x3f3f3f3f
#define LL long long
#define N 105
#define P 1000000007

void chkmx(int &a,int b){if(a<b)a=b;}
void chkmi(int &a,int b){if(a>b)a=b;}
int MAX(int a,int b){return a>b?a:b;}
int MIN(int a,int b){return a<b?a:b;}

int Num[N][1<<13],l[N];
LL ans,dp[N][1<<13],A[N],Sum[N][1<<13];
int n;

void Init(){
    FOR(i,0,n){
        LL t=A[i];
        while(t) Num[i][l[i]++]=t%10,t/=10;
        FOR(j,1,(1<<l[i])-1){
            LL &sum=Sum[i][j],h=1;
            FOR(k,0,l[i]-1) if(j&(1<<k)) sum+=Num[i][k]*h,h*=10;
        }
    }
    FOR(i,0,n) sort(Sum[i]+1,Sum[i]+(1<<l[i]));
}
void Add(LL &a,LL b){
    a=(a+b)%P;
}
void Merge(int i){
    int s=1;
    FOR(j,1,(1<<l[i])-1){
        dp[i][j]=dp[i][j-1];
        while(s<(1<<l[i-1])&&Sum[i][j]>=Sum[i-1][s]) Add(dp[i][j],dp[i-1][s++]);
    }
}
int main(){
// freopen("num.in","r",stdin);
// freopen("num.out","w",stdout);
    cin>>A[0]>>n;
    FOR(i,1,n) A[i]=A[i-1]+1;
    Init();
    FOR(i,1,(1<<l[0])-1) dp[0][i]=1;
    FOR(i,1,n) Merge(i);
    FOR(i,1,(1<<l[n])-1) Add(ans,dp[n][i]);
    cout<<ans<<endl;
    return 0;
}

本题也可以滚动数组，但显然没必要

四点旅行 2989

这题其实不怎么难
按照题意模拟下来我们可以发现复杂度都堆在找最短路上
其实可以发现这道题的边权都是1
那么，直接bfs就好了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

#define FOR(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;++i)
#define DOR(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;--i)
#define INF 0x3f3f3f3f
#define LL long long
#define M 2005
#define N 5005
#define P 1000000007

void chkmx(int &a,int b){if(a<b)a=b;}
void chkmi(int &a,int b){if(a>b)a=b;}
int MAX(int a,int b){return a>b?a:b;}
int MIN(int a,int b){return a<b?a:b;}

int d[M][M];
struct node{int maxl[2],s[2],cnt[2];}A[M];
vector<int>es[N];
struct W {int x,v;};
int n,m,ans;
queue<W> Q;
void bfs(int s){
    Q.push((W){s,0});
    while(!Q.empty()){
        W q=Q.front();Q.pop();
        int x=q.x;
        if(d[s][x]!=INF) continue;
        d[s][x]=q.v;
        FOR(i,0,es[x].size()-1){
            int y=es[x][i];
            if(d[s][y]!=INF) continue;
            Q.push((W){y,q.v+1});
        }
    }
}
int main(){
// freopen("four.in","r",stdin);
// freopen("four.out","w",stdout);
    memset(d,INF,sizeof(d));
    cin>>n>>m;
    FOR(i,1,m){
        int a,b;
        scanf("%d%d",&a,&b);
        es[a].push_back(b); 
    }
    FOR(i,1,n) bfs(i);

    FOR(i,1,n)FOR(j,1,n){
        if(d[i][j]==INF||i==j)continue;
        if(d[i][j]>A[i].maxl[0])
            A[i].s[0]=j,A[i].cnt[0]=1,A[i].maxl[0]=d[i][j];
        else if(d[i][j]==A[i].maxl[0]) A[i].cnt[0]++;
        if(d[i][j]>A[j].maxl[1])
            A[j].s[1]=i,A[j].cnt[1]=1,A[j].maxl[1]=d[i][j];
        else if(d[i][j]==A[j].maxl[1]) A[j].cnt[1]++;
    }

    FOR(i,1,n)FOR(j,1,n){
        if(d[i][j]==INF||!A[i].cnt[1]||!A[j].cnt[0]||i==j)continue;
        if(A[i].s[0]==A[j].s[1]&&A[i].cnt[0]==1&&A[j].cnt[1]==1) continue;
        chkmx(ans,A[i].maxl[1]+d[i][j]+A[j].maxl[0]);
    }
    cout<<ans<<endl;
    return 0;   
}
标签：

相关文章