答案为:f[i]*C(i,k)(i=k..n),端点最多2n个,利用前缀差分.一段一段算即可(同一段中的点被覆盖次数相同)
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; const int N=2e5+20; ll n,k,l,r,f[N],inv[N]; ll powmod(ll x,ll n) { ll s=1; while(n) { if(n&1) s=(s*x)%mod; n>>=1,x=(x*x)%mod; } return s; } void init() { f[0]=inv[0]=1; for(int i=1;i<N;i++) f[i]=(f[i-1]*i)%mod,inv[i]=powmod(f[i],mod-2)%mod; } ll Comb(ll n,ll k) { ll res=(f[n]*inv[n-k])%mod; return (res*inv[k])%mod; } map<ll,ll> mp; int main() { init(); while(cin>>n>>k) { mp.clear(); for(int i=0;i<n;i++) { scanf("%I64d%I64d",&l,&r); mp[l]++,mp[r+1]--; } int l=mp.begin()->first; ll sum=0,ans=0; map<ll,ll>::iterator it; for(it=mp.begin();it!=mp.end();it++) { ll num=it->first-l; if(sum>=k) ans=(ans+(num*Comb(sum,k))%mod)%mod; sum+=it->second; l=it->first; } printf("%lld\n",ans); } return 0; }P.A
把0改成11,枚举起点后,可以由序列相邻点算出x,y方向偏差值,判断是否合法即可.
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e3+20; int x[N],y[N],n; string s; bool check(int x,int y) { if(x<0||x>=3) return false; if(y<0||y>=4) return false; if(y==3&&x!=1) return false; return true; } int main() { while(cin>>n>>s) { int t; for(int i=0;s[i];i++) { if(s[i]=='0') t=11; else t=s[i]-'0'; t--; y[i]=t/3; x[i]=t%3; } int cnt=0; for(int i=0;i<3;i++) { for(int j=0;j<4;j++) { int tx=i,ty=j,ok=1; ok&=check(tx,ty); for(int k=0;k<n-1;k++) { tx+=x[k+1]-x[k]; ty+=y[k+1]-y[k]; ok&=check(tx,ty); } if(ok) cnt++; } } //cout<<cnt<<endl; if(cnt==1) puts("YES"); else puts("NO"); } return 0; } P.B 题意:起点为1,从点i到点j花费|i-j|,有n条捷径a[i]代表从i->a[i]花费1,其中i<=a[i]<=a[i+1]. n<=2e5,问从1出发到k的最短距离 k=1,2,3...n. 建图:i-j连边距离为|i-j|,i->a[i]连边距离为1. 这样边数太大,因为任意一个距离>1的边 都可以用若干条相邻边来代替,所以只连相邻边即可. 图中每条边代价都为1,跑一遍BFS即可. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+20; const int inf=0x3f; int n,a[N],dis[N]; vector<int> e[5*N]; queue<int> q; void bfs(int s) { memset(dis,inf,sizeof(dis)); dis[s]=0,q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<e[u].size();i++) { int v=e[u][i]; if(dis[v]>dis[u]+1) { dis[v]=dis[u]+1; q.push(v); } } } } int main() { while(cin>>n) { for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(i!=a[i]) e[i].push_back(a[i]); if(i!=n) e[i].push_back(i+1); if(i!=1) e[i].push_back(i-1); } bfs(1); for(int i=1;i<=n;i++) printf("%d%c",dis[i],i==n?'\n':' '); } return 0; }P.D题意:两个序列a,b.问有多少个区间[l,r]满足max(a[l],a[l+1]..a[r])=min(b[l],b[l+1]..b[r])? n<=2e5,a[i],b[i]<=1e9. 枚举区间的开头L,r越大,a的最大值越大,b的最小值越小.结尾点有单调性. rmq预处理后 枚举L,二分r:最后一次mx<mn,第一次mx>mn.则这两个中间的就为mx==mn
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+20; int n,a[N],b[N]; int mx[N][32],mn[N][32]; void init() { for(int i=1;i<=n;i++) mx[i][0]=a[i],mn[i][0]=b[i]; for(int j=1;(1<<j)<=n;j++) { for(int i=1;i+(1<<j)-1<=n;i++) { mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]); mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]); } } } int query(int l,int r,int op) { int k=0; while(r-l+1>=(1<<(k+1))) k++; if(op==1) return max(mx[l][k],mx[r-(1<<k)+1][k]); return min(mn[l][k],mn[r-(1<<k)+1][k]); } int main() { while(cin>>n) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); init(); ll ans=0; for(int i=1;i<=n;i++) { int l=i,r=n,r1,r2; while(l<=r) { int mid=l+r>>1; int c=query(i,mid,1),d=query(i,mid,0); if(c<d) l=mid+1; else r=mid-1; } r1=l-1; l=i,r=n; while(l<=r) { int mid=l+r>>1; int c=query(i,mid,1),d=query(i,mid,0); if(c>d) r=mid-1; else l=mid+1; } r2=r+1; ans+=max(0,(r2-r1-1)); } printf("%lld\n",ans); } return 0; }