传送门
Input 3 3 0 2 2 3 0 1 2 3 0 2 3 Output 2 4 0
题意：t组测试样例，开头一个n，下面是n个数，分别为前i个数的最大值和最小值之差，问：1~n有几种排列方法满足条件
思路：首先特别判定一下a[0]应该等于零，a[i]>=a[i-1],a[i]<n;满足这三个前提条件后有两种情况： 1：a[i]>a[i-1]此时前i个数的最大值或最小值更新，总数乘以2，最大值更新他们中间数（最大值和最小值中间还未用到的数）的总数增加，计算他们中间的数 2：a[i]==a[i-1]说明前i个数最大值最小值都没有更新，此时从中间数中去一个放在这个位置，总数*此时的中间数，中间数-1； 具体看代码
#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<map> #include<sstream> #include<queue> #include<stack> using namespace std; #define ll long long const int mod=1e9+7; int n; void solve() { ll p,q,flag=1; scanf("%lld",&n); scanf("%lld",&p);//第一个数p下一个数q if(p!=0)flag=0; ll ans=1,cnt=0;//ans为总数，cnt为中间数 for(int i=0;i<n-1;i++) {scanf("%lld",&q); if(q<p||q>=n)flag=0; if(q>p)//1 {cnt=(cnt+q-p-1)%mod; ans=(ans*2)%mod;} else if(q==p)//2 {ans=(ans*cnt)%mod; cnt=(cnt-1)%mod;} p=q; } if(flag)printf("%lld\n",ans); else printf("0\n"); } int main() { int t; scanf("%d",&t); while(t--) { solve(); } }比较疑惑的是用cin为什么过不了…，找了好大会bug最后发现问题出现在cin，欢迎大佬指点，下面附上超时代吗
#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<map> #include<sstream> #include<queue> #include<stack> using namespace std; #define ll long long const int mod=1e9+7; int n; void solve() { ll p,q,flag=1; cin>>n; cin>>p; if(p!=0)flag=0; ll ans=1,cnt=0; for(int i=0;i<n-1;i++) {cin>>q; if(q<p||q>=n)flag=0; if(q>p) {cnt=(cnt+q-p-1)%mod; ans=(ans*2)%mod;} else if(q==p) {ans=(ans*cnt)%mod; cnt=(cnt-1)%mod;} p=q; } if(flag)printf("%lld\n",ans); else printf("0\n"); } int main() { ios::sync_with_stdio(0); int t; cin>>t; while(t--) { solve(); } }