第一次接触到输入挂
namespace IO //超级读入挂 { const int len=4e7;char buf[len];int sz,p; //4e7大概大小为44M，可以放得下38M的输入 void begin(){p=0;sz=fread(buf,1,len,stdin);} inline bool read(LL &x) { if (p==sz)return 0;int f=1,d=0;char s=buf[p++]; while(s<'0'||s>'9'&&p<sz){if(s=='-') f=-1;s=buf[p++];} while(s>='0'&&s<='9'&&p<sz){d=d*10+s-'0';s=buf[p++];} x=f*d; return p!=sz; } inline void writeln(LL x) { if(x==0){putchar('0');putchar('\n');return;} if(x<0)putchar('-'),x=-x;int len=0,buf[20]; while(x)buf[len++]=x%10,x/=10;int i=len-1; while (i>=0){putchar(buf[i--]+'0');}putchar('\n');return; } }知道输入挂后可以不用一直TLE了，其他的还算简单； 本题的破题关键点在于区间满足的条件：if and only if（当且仅当）。所以说，对于一个数字i，它是区间[li,ri]的最小值，这个li和ri不能扩大或者缩小，即a[li-1]和a[ri+1]都比a[i]小。有了这个我们就可以知道，所有的区间，要么是相互包含的，要么没有交集，不会出现有相交的情况。这个如何解释呢？我们们用反证法，假设区间[li,ri]与[lj,rj]相交，对于li
#include<bits/stdc++.h> #define mod 1000000007 #define LL long long #define N 1001000 using namespace std; namespace IO //超级读入挂 { const int len=4e7;char buf[len];int sz,p; //4e7大概大小为44M，可以放得下38M的输入 void begin(){p=0;sz=fread(buf,1,len,stdin);} inline bool read(LL &x) { if (p==sz)return 0;int f=1,d=0;char s=buf[p++]; while(s<'0'||s>'9'&&p<sz){if(s=='-') f=-1;s=buf[p++];} while(s>='0'&&s<='9'&&p<sz){d=d*10+s-'0';s=buf[p++];} x=f*d; return p!=sz; } inline void writeln(LL x) { if(x==0){putchar('0');putchar('\n');return;} if(x<0)putchar('-'),x=-x;int len=0,buf[20]; while(x)buf[len++]=x%10,x/=10;int i=len-1; while (i>=0){putchar(buf[i--]+'0');}putchar('\n');return; } } struct node { LL l,r,id; }arr[N]; bool cmp(node a,node b) { return a.l==b.l?a.r>b.r:a.l<b.l; } LL f[N],n,m; bool flag; LL fastpow(LL x,LL n) { LL ret=1; while (n) { if (n&1) ret=ret*x%mod; x=x*x%mod; n>>=1; } return ret; } LL c(LL n,LL m) { LL ret=1; ret=ret*f[n]*fastpow(f[m]*f[n-m]%mod,mod-2)%mod; return ret; } LL dfs(LL l,LL r) { if (l>r) return 1LL; node now=arr[++m]; if (now.l!=l||now.r!=r||flag) { flag=1; return 0LL; } if (l==r) return 1LL; LL res=c(now.r-now.l,now.id-now.l)*dfs(now.l,now.id-1)%mod; res=res*dfs(now.id+1,now.r)%mod; return res; } int main() { IO::begin(); int T=0; f[0]=1; for(int i=1;i<N;i++) f[i]=f[i-1]*(LL)i%mod; while(IO::read(n)) { for(int i=1;i<=n;i++) IO::read(arr[i].l); for(int i=1;i<=n;i++) IO::read(arr[i].r),arr[i].id=i; sort(arr+1,arr+1+n,cmp); printf("Case #%d: ",++T); m=0; flag=0; IO::writeln(dfs(1,n)); } }