4.9 模拟赛

T1 luogu 5070

题目大意：

现在给你一个长度为$n$的序列，有$m$次询问

每次询问一个区间$[l,r]$排序去重后的序列中长度为1到10的条件的区间个数

满足条件的区间满足每项是前一项数+1的极长区间

思路：

发现每个数$x$只对$[x-10,x+10]$这个区间有影响

直接莫队维护一下数的出现次数判一下左右的情况可以获得暴力分（但码内O2可以A掉管老师的数据

 1 #pragma GCC optimize("O2")
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<algorithm>
 8 #include<queue>
 9 #include<vector>
10 #include<map>
11 #include<set>
12 #define ll long long
13 #define db double
14 #define inf 2139062143
15 #define MAXN 2001000
16 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)
17 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)
18 #define ren for(register int i=fst[x];i;i=nxt[i])
19 #define pb(i,x) tot[i].push_back(x)
20 #define pls(a,b) (a+b)%MOD
21 #define mns(a,b) (a-b+MOD)%MOD
22 #define mul(a,b) (1LL*(a)*(b))%MOD
23 using namespace std;
24 inline int read()
25 {
26     int x=0,f=1;char ch=getchar();
27     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
28     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
29     return x*f;
30 }
31 int n,m,g[MAXN],bl[MAXN],sz;
32 int ans[MAXN][11],res[11],cnt[MAXN];struct ask{int l,r,id;}q[MAXN];
33 bool cmp(ask a,ask b){return bl[a.l]<bl[b.l]||(bl[a.l]==bl[b.l]&&a.r<b.r);}
34 void add(int x)
35 {
36     int r=g[x],l=g[x];if(cnt[g[x]]!=0) {cnt[g[x]]++;return ;}
37     rep(i,g[x]+1,min(g[x]+11,1000001)) if(!cnt[i]) {r=i;break;} 
38     dwn(i,g[x]-1,max(g[x]-11,0)) if(!cnt[i]) {l=i;break;}
39     if(r!=g[x]) res[r-g[x]-1]-=(cnt[g[x]]==0);
40     if(l!=g[x]) res[g[x]-l-1]-=(cnt[g[x]]==0);
41     if(r!=g[x]&&l!=g[x]&&r-l-1<=10) res[r-l-1]+=(cnt[g[x]]==0);
42     cnt[g[x]]++;
43 }
44 void del(int x)
45 {
46     int r=g[x],l=g[x];if(cnt[g[x]]!=1) {cnt[g[x]]--;return ;}
47     rep(i,g[x]+1,min(g[x]+11,1000001)) if(!cnt[i]) {r=i;break;} 
48     dwn(i,g[x]-1,max(g[x]-11,0)) if(!cnt[i]) {l=i;break;}
49     if(r!=g[x]) res[r-g[x]-1]+=(cnt[g[x]]==1);
50     if(l!=g[x]) res[g[x]-l-1]+=(cnt[g[x]]==1);
51     if(r!=g[x]&&l!=g[x]&&r-l-1<=10) res[r-l-1]-=(cnt[g[x]]==1);
52     cnt[g[x]]--;
53 }
54 int main()
55 {
56     n=read(),m=read(),sz=sqrt(n);rep(i,1,n) g[i]=read(),bl[i]=(i-1)/sz;
57     int l,r;rep(i,1,m) l=read(),r=read(),q[i]=(ask){l,r,i};
58     sort(q+1,q+m+1,cmp);l=q[1].l,r=q[1].l-1;rep(i,1,m)
59     {
60         while(l<q[i].l) del(l++);while(r<q[i].r) add(++r);
61         while(r>q[i].r) del(r--);while(l>q[i].l) add(--l);
62         memcpy(ans[q[i].id],res,sizeof(res));
63     }
64     rep(i,1,m) {rep(j,1,10) printf("%d",ans[i][j]%10);puts("");}
65 }

View Code

正解将所有询问离线下来按照右端点排序，从左到右考虑每个数进来的影响

记录$las_x$表示$x$这个数上次出现的位置

因为只有$[x-11,x+11]$这些数有用，找到这些数中位置在$[las_a[x],i]$的数（因为如果不在肯定没有影响

按照出现次数降序排序，依次加入每个数，算出对当前位置的影响，在这个位置到下一个数的位置之前有影响

在处理完这些数之后，每个右端点的询问查询左端点的答案即可

维护一个区间修改，单点查询的树状数组即可

为什么我这么慢啊（人菜自带大常数

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #define ll long long
12 #define db double
13 #define inf 2139062143
14 #define MAXN 1001000
15 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)
16 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)
17 #define ren for(register int i=fst[x];i;i=nxt[i])
18 #define pls(a,b) (a+b)%MOD
19 #define mns(a,b) (a-b+MOD)%MOD
20 #define mul(a,b) (1LL*(a)*(b))%MOD
21 using namespace std;
22 inline int read()
23 {
24     int x=0,f=1;char ch=getchar();
25     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
26     while(isdigit(ch)) {x=x*10+(ch&15);ch=getchar();}
27     return x*f;
28 }
29 int n,m,g[MAXN],c[11][MAXN],ans[MAXN][11],las[MAXN],cnt[30],len;
30 void mdf(int k,int x,int val) {if(!k) return ;for(;x<=n;x+=x&-x) c[k][x]+=val;}
31 void query(int *res,int x) {rep(i,1,10) for(int t=x;t;t^=t&-t) res[i]+=c[i][t];}
32 #define pii pair<int,int>
33 #define mp(a,b) make_pair(a,b)
34 #define pb(x) push_back(x)
35 #define pos first
36 #define val second
37 #define id second
38 vector<pii> q[MAXN];pii tmp[MAXN];
39 int main()
40 {
41     n=read(),m=read();rep(i,1,n) g[i]=read();
42     int l,r;rep(i,1,m) l=read(),r=read(),q[r].pb(mp(l,i));
43     rep(t,1,n)
44     {
45         len=0;rep(i,max(g[t]-11,1),min(g[t]+11,MAXN-1000))
46             if(las[i]>las[g[t]]) tmp[++len]=(mp(las[i],i-g[t]+15));
47         tmp[++len]=(mp(las[g[t]],-1));tmp[++len]=(mp(t,15)),l=r=15;
48         sort(tmp+1,tmp+len+1);dwn(i,len,2)
49         {
50             cnt[tmp[i].val]=1;while(cnt[l-1]) --l;while(cnt[r+1]) ++r;
51             if(l>=5) mdf(15-l,tmp[i-1].pos+1,-1),mdf(15-l,tmp[i].pos+1,1);
52             if(r<=25) mdf(r-15,tmp[i-1].pos+1,-1),mdf(r-15,tmp[i].pos+1,1);
53             if(r-l<10) mdf(r-l+1,tmp[i-1].pos+1,1),mdf(r-l+1,tmp[i].pos+1,-1);
54         }
55         memset(cnt,0,sizeof(cnt));las[g[t]]=t;rep(i,0,q[t].size()-1)
56             query(ans[q[t][i].id],q[t][i].pos);
57     }
58     rep(i,1,m) {rep(j,1,10) putchar('0'+ans[i][j]%10);putchar('
');}
59 }

View Code

T2 bzoj 3652

题目大意：

一个人在$[0,n)$中随机一个数，有$P$的概率使另一个人看到这个数

若看到，则另一个人会在$[0,n)$中选择一个数使这两个数异或值最大

若没有看到，另一个人也会在$[0,n)$中随机选择一个数，求异或的期望值

思路：

很明显要分开考虑，对于不能看到的情况，对每一位只需要统计有多少个数在该位为1

从高位向低位考虑，令该数为$axb$的形式，其中x为该位，则在$a00$这么多数中，有一半这一位是1

若$x==1$，则剩下的$b$这么多数中，该位都是1，这一位的贡献很容易计算

对于可以看到的情况，设一开始所有数都可以异或一个数得到最大值

从高位向低位贪心，假设还有$t$个数未被处理

在$x$位时，若$x$为1，则这一位可以随便取，不去管它

若$x$为0，则对于这一位为0的数，无法满足条件

统计有多少个这种数，即前面为0的位取$0/1$以及后面随便取的个数（在纸上写一写非常明显

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #define ll long long
12 #define db double
13 #define ldb long double
14 #define inf 2139062143
15 #define MAXN 10001000
16 #define MOD 1000000007
17 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)
18 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)
19 #define ren for(register int i=fst[x];i;i=nxt[i])
20 #define Fill(x,t) memset(x,t,sizeof(x))
21 #define pls(a,b) (a+b)%MOD
22 #define mns(a,b) (a-b+MOD)%MOD
23 #define mul(a,b) (1LL*(a)*(b))%MOD
24 using namespace std;
25 inline ll read()
26 {
27     ll x=0,f=1;char ch=getchar();
28     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
29     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
30     return x*f;
31 }
32 ll n,g[70],m;ldb ans,res;db P;
33 int main()
34 {
35     n=read()-1;scanf("%lf",&P);for(ll x=n;x;x>>=1) g[++m]=x&1LL;ll t=0,p;
36     dwn(i,m,1)
37     {
38         p=t*(1LL<<i-1);if(g[i]) p+=(n&((1LL<<i-1)-1))+1;
39         ans+=(2.0*p*(n+1-p)*(1LL<<i-1)),t<<=1,t+=g[i];
40     }ans=ans/(n+1)/(n+1),t=1LL<<m,res=1.0*(n+1)*(t-1);
41     dwn(i,m,1) if(g[i]) t>>=1;else res-=1.0*(t>>1)*(1LL<<i-1);
42     res/=(n+1),ans=ans*(1-P)+res*P;printf("%.6lf",(db)ans);
43 }

View Code

T3 bzoj 5323

题目大意：

有所有在$[L,R]$之间的数，每次标记了一个数就会标记所有这个区间里它的倍数（一个数被选择一次

当所有数都被标记后，立刻结束整个过程，求对于所有标记顺序的标记次数之和

思路：

思考一个排列对答案的贡献，即这个顺序中最后一个不能被别的数标记的数的位置

我们可以预处理这些不能被别的数表示的数即满足其最大约数不在$[L,R]$中

因为$g_max=x/pi_min$，预处理出每个数的最小质因子即可，设这些数总数为$m$，$n=R-L-1$

那么我们枚举最后一个数出现的位置得到$sumlimits_{i=m}^n i*m*A_{i-1}^{m-1}*(n-m)!$

提出来之后得$m*(n-m)! sumlimits_{i=m}^n frac{i!}{(i-m)!}$

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #define ll long long
12 #define db double
13 #define inf 2139062143
14 #define MAXN 10001000
15 #define MOD 1000000007
16 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)
17 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)
18 #define ren for(register int i=fst[x];i;i=nxt[i])
19 #define Fill(x,t) memset(x,t,sizeof(x))
20 #define pls(a,b) (a+b)%MOD
21 #define mns(a,b) (a-b+MOD)%MOD
22 #define mul(a,b) (1LL*(a)*(b))%MOD
23 using namespace std;
24 inline int read()
25 {
26     int x=0,f=1;char ch=getchar();
27     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
28     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
29     return x*f;
30 }
31 int n,m,ntp[MAXN],p[MAXN],tot,L,R,fac[MAXN],ifac[MAXN];
32 void pre()
33 {
34     rep(i,2,R)
35     {
36         if(!ntp[i]) p[++tot]=i;
37         rep(j,1,tot) if(i*p[j]>R) break;
38             else {ntp[i*p[j]]=p[j];if(!(i%p[j])) break;}
39     }
40 }
41 int main()
42 {
43     L=read(),R=read(),n=R-L+1;pre();fac[0]=ifac[0]=fac[1]=ifac[1]=1;
44     rep(i,2,R) fac[i]=mul(i,fac[i-1]),ifac[i]=mul(MOD-MOD/i,ifac[MOD%i]);
45     rep(i,1,R) ifac[i]=mul(ifac[i-1],ifac[i]);ll ans=0;
46     if(L==1) m=1;else rep(i,L,R) if(!ntp[i]||i/ntp[i]<L) m++;
47     rep(i,m,n) ans=pls(ans,mul(fac[i],ifac[i-m]));
48     printf("%d
",mul(mul(fac[n-m],m),ans));
49 }

View Code