NOIP模拟9.23（TYVJ NOIP2017模拟赛D1）

T1.回形遍历。（模拟）AC。
T2.排列（单调栈+暴力）只暴力了60
T3.近似排列计数（状压+矩阵快速幂）搜索本来应该30分的。。。奈何写错字母。。

T1 回形遍历

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define pa pair<ll,int>
#define N 50010
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m,xx,y,z,cnt=0,st=1;
int main(){
//  freopen("calc.in","r",stdin);
//  freopen("calc.out","w",stdout);
    n=read();m=read();xx=read();y=read();z=read();
    if(y==0){
        cnt=n-1-xx;if(cnt>=z){printf("%d %d",xx+z,0);return 0;}
        if(z-cnt<=m-1){printf("%d %d",n-1,z-cnt);return 0;}cnt+=m-1;
        if(z-cnt<=n-1){printf("%d %d",n-1-(z-cnt),m-1);return 0;}cnt+=n-1;
        if(z-cnt<=m-2){printf("%d %d",0,m-1-(z-cnt));return 0;}cnt+=m-2;
    }
    else if(y==m-1){
        cnt=xx;if(cnt>=z){printf("%d %d",xx-z,m-1);return 0;}
        if(z-cnt<=m-2){printf("%d %d",0,m-1-(z-cnt));return 0;}cnt+=m-2;
    }
    else if(xx==n-1){
        cnt=m-1-y;if(cnt>=z){printf("%d %d",n-1,y+z);return 0;}
        if(z-cnt<=n-1){printf("%d %d",n-1-(z-cnt),m-1);return 0;}cnt+=n-1;
        if(z-cnt<=m-2){printf("%d %d",0,m-1-(z-cnt));return 0;}cnt+=m-2;
    }
    else if(xx==0){
        cnt=y-1;if(cnt>=z){printf("%d %d",0,y-z);return 0;}
    }else{
        for(int x=1;x<=n;++x){
            if(y==x){z+=xx-(x-1);st=x;break;}
            if(xx==n-1-x){z+=y-x+n-1-x-(x-1);st=x;break;}
            if(y==m-1-x){z+=n-1-x-(x-1)+m-1-x-x+n-1-x-xx;st=x;break;}
            if(xx==x){z+=n-1-x-(x-1)+m-1-x-x+n-1-x-x+m-1-x-y;st=x;break;}
        }
    }
    for(int x=st;x<=n;++x){
        if(x-1+z-cnt<=n-1-x){printf("%d %d",x-1+z-cnt,x);return 0;}
        else cnt+=n-1-x-(x-1);
        if(x+z-cnt<=m-1-x){printf("%d %d",n-1-x,x+z-cnt);return 0;}
        else cnt+=(m-1-x)-x;
        if(n-1-x-(z-cnt)>=x){printf("%d %d",n-1-x-(z-cnt),m-1-x);return 0;}
        else cnt+=(n-1-x)-x;
        if(m-1-x-(z-cnt)>=x+1){printf("%d %d",x,m-1-x-(z-cnt));return 0;}
        else cnt+=m-1-x-(x+1);
    }
    return 0;
}

T2 排列

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 100010
#define pa pair<int,int>
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int tst,n,a[N],pos1[N],pos2[N];//pos1[i]比i大的数第一次出现的位置，pos2比i小的 
ll ans[N];
stack<pa>mx1,mn1;
int main(){
//  freopen("a.in","r",stdin);
    tst=read();
    while(tst--){
        n=read();for(int i=1;i<=n;++i) a[i]=read();memset(ans,0,sizeof(ans));
        while(!mx1.empty()) mx1.pop();
        while(!mn1.empty()) mn1.pop();
        for(int i=n;i>=1;--i){
            while(!mx1.empty()&&a[i]>mx1.top().first) mx1.pop();
            if(mx1.empty()) pos1[a[i]]=n+1;
            else pos1[a[i]]=mx1.top().second;
            mx1.push(make_pair(a[i],i));
            while(!mn1.empty()&&a[i]<mn1.top().first) mn1.pop();
            if(mn1.empty()) pos2[a[i]]=n+1;
            else pos2[a[i]]=mn1.top().second;
            mn1.push(make_pair(a[i],i));
        }ans[0]=n;
        for(int i=1;i<=n;++i){
            int mx=a[i],mn=a[i];
            for(int j=i+1;j<=n;++j){
                if(a[j]>mx) mx=a[j];
                else mn=a[j];
                int pos=min(pos1[mx],pos2[mn]);
                ans[mx-mn]+=pos-j;j=pos-1;
            }
        }
        for(int i=1;i<n;++i) ans[i]+=ans[i-1];
        for(int i=0;i<=n-1;++i) printf("%lld\n",ans[i]);
    }
    return 0;
}

T3 近似排列计数

30分的搜索。。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define pa pair<ll,int>
#define N 100010
#define mod 1000000007
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int tst,n,m,k,a[N],ans=0,dx[]={-1,0,1,-2,2};
bool f[N];
void dfs(int x){
    if(x>n) ans++;
    if(a[x]) dfs(x+1);
    for(int i=0;i<3;++i){
        int xx=x+dx[i];
        if(xx>=1&&xx<=n&&!f[xx]){
            f[xx]=1;dfs(x+1);f[xx]=0;
        }
    }
}
void dfs1(int x){
    if(x>n) ans++;
    if(a[x]) dfs1(x+1);
    for(int i=0;i<5;++i){
        int xx=x+dx[i];
        if(xx>=1&&xx<=n&&!f[xx]){
            f[xx]=1;dfs1(x+1);f[xx]=0;
        }
    }
}
void solve0(){
    ans=0;
    if(k==1) dfs(1);
    else dfs1(1);
    printf("%d\n",ans%mod);
}
int main(){
//  freopen("a.in","r",stdin);
    tst=read();
    while(tst--){
        n=read();m=read();k=read();
        memset(f,0,sizeof(f));memset(a,0,sizeof(a));
        for(int i=1;i<=m;++i){
            int x=read(),y=read();a[x]=y;f[y]=1;
        }
        if(k==0){puts("1");continue;}
        if(n<=20) solve0();
        else solve0();
    }
    return 0;
}

按道理50分的朴素状压dp

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define pa pair<ll,int>
#define N 100010
#define mod 1000000007
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int tst,n,m,k,a[N],ans=0,dx[]={-1,0,1,-2,2},dp[1100000],bin[25];
void solve1(){
    memset(dp,0,sizeof(dp));dp[0]=1;
    for(int i=1;i<=n;++i){
        if(a[i]){
            for(int s=bin[n]-1;s>=0;--s)
                if(!(s&(1<<a[i]-1))) dp[s|(1<<a[i]-1)]=(dp[s|(1<<a[i]-1)]+dp[s])%mod;
            continue;   
        }
        for(int s=bin[n]-1;s>=0;--s)
            for(int j=0;j<3;++j){
                int x=i+dx[j];if(x<1||x>n) continue;
                if(!(s&(1<<x-1))) dp[s|(1<<x-1)]=(dp[s|(1<<x-1)]+dp[s])%mod;
            }
    }
    printf("%d\n",dp[bin[n]-1]);
}
void solve2(){
    memset(dp,0,sizeof(dp));dp[0]=1;
    for(int i=1;i<=n;++i){
        if(a[i]){
            for(int s=bin[n]-1;s>=0;--s)
                if(!(s&(1<<a[i]-1))) dp[s|(1<<a[i]-1)]=(dp[s|(1<<a[i]-1)]+dp[s])%mod;
            continue;   
        }
        for(int s=bin[n]-1;s>=0;--s)
            for(int j=0;j<5;++j){
                int x=i+dx[j];if(x<1||x>n) continue;
                if(!(s&(1<<x-1))) dp[s|(1<<x-1)]=(dp[s|(1<<x-1)]+dp[s])%mod;
            }
    }
    printf("%d\n",dp[bin[n]-1]);
}
int main(){
    freopen("a.in","r",stdin);
    tst=read();bin[0]=1;
    for(int i=1;i<=20;++i) bin[i]=bin[i-1]<<1;
    while(tst--){
        n=read();m=read();k=read();memset(a,0,sizeof(a));
        for(int i=1;i<=m;++i){
            int x=read(),y=read();a[x]=y;
        }
        if(k==0){puts("1");continue;}
        if(k==1) solve1();
        else solve2();
    }
    return 0;
}

正解，待填坑。。。