[考试反思]1107csp-s模拟测试104: 速度
分类:
IT文章
•
2022-08-26 12:40:45
20分钟能做什么?
不粘排行榜,没意义,第一机房集体重启,我侥幸找回了两个文件才有分。
实际得分应该是70+100+60,第二机房rank1。。。放在第一机房就不知道了
T1:中间值
比较喜欢题解的第二种做法。
考虑分治。现在要求出a[l,r],b[L,R]之内的第k小值。
递归边界:如果k==1,那么就是min(a[l],b[L])。如果一个区间为空,直接返回另一个区间的第k小值。
否则我们在a和b中分别取出一些元素,与k的一半取min,然后比较这个元素
即设t=min(k>>1,r-l+1).
那么我们可以比较a[l+t]与b[L+k-t]。较小的一边就可以排除了,继续递归解决即可。
1 #include<cstdio>
2 #include<algorithm>
3 using namespace std;
4 int n,m,a[500005],b[500005];
5 int read(){
6 register int p=0,nt=0;register char ch=getchar();
7 for(;ch<'0'||ch>'9';ch=getchar())nt=ch=='-';
8 for(;ch>='0'&&ch<='9';p=(p<<3)+(p<<1)+ch-48,ch=getchar());
9 return nt?-p:p;
10 }
11 int chk(int l,int r,int L,int R,int k){//printf("%d %d %d %d %d
",l,r,L,R,k);
12 if(k==1)return min(a[l],b[L]);
13 if(l>r)return b[L+k-1];
14 if(L>R)return a[l+k-1];
15 int t=min(min(r-l+1,R-L+1),k>>1);
16 if(a[l+t-1]>b[L+t-1])return chk(l,r,L+t,R,k-t);
17 else return chk(l+t,r,L,R,k-t);
18 }
19 int main(){
20 freopen("median.in","r",stdin);freopen("median.out","w",stdout);
21 scanf("%d%d",&n,&m);
22 for(int i=1;i<=n;++i)a[i]=read();
23 for(int i=1;i<=n;++i)b[i]=read();
24 while(m--){
25 int opt;scanf("%d",&opt);
26 if(opt==1){
27 int x=read(),y=read(),z=read();
28 if(!x)a[y]=z;else b[y]=z;
29 }else{
30 int l=read(),r=read(),L=read(),R=read(),cnt;
31 printf("%d
",chk(l,r,L,R,R-L+r-l+3>>1));
32 }
33 }
34 }
View Code
T2:最小值
感觉像单调栈,但是单调栈里的值都可能是最优决策。
发现转移值与当前点位置无关,所以直接把转移值放进set。弹栈时删除。
1 #include<cstdio>
2 #include<set>
3 using namespace std;
4 #define inf -12345678901234567
5 multiset<long long>S;
6 long long A,B,C,D,dp[200005],val[200005];int n,x[200005],s[200005],tp;
7 long long cal(int x){return A*x*x*x+B*x*x+C*x+D;}
8 struct Segment_Tree{
9 long long w[800005];
10 void modify(int p,int pos,long long v,int cl=0,int cr=n){
11 if(cl==cr){w[p]=v;return;}
12 if(pos<=cl+cr>>1)modify(p<<1,pos,v,cl,cl+cr>>1);
13 else modify(p<<1|1,pos,v,(cl+cr>>1)+1,cr);
14 w[p]=max(w[p<<1],w[p<<1|1]);
15 }
16 long long ask(int p,int l,int r,int cl=0,int cr=n){
17 if(l<=cl&&cr<=r)return w[p];
18 return max(l<=cl+cr>>1?ask(p<<1,l,r,cl,cl+cr>>1):inf,r>cl+cr>>1?ask(p<<1|1,l,r,(cl+cr>>1)+1,cr):inf);
19 }
20 }T;
21 int main(){
22 freopen("min.in","r",stdin);freopen("min.out","w",stdout);
23 scanf("%d%lld%lld%lld%lld",&n,&A,&B,&C,&D);
24 for(int i=1;i<=n;++i)scanf("%d",&x[i]);
25 for(int i=1;i<=n;++i){
26 while(tp&&x[s[tp]]>x[i])S.erase(S.find(val[tp])),tp--;
27 s[++tp]=i;val[tp]=T.ask(1,s[tp-1],i-1)+cal(x[i]);S.insert(val[tp]);
28 dp[i]=*(--S.end());T.modify(1,i,dp[i]);
29 }printf("%lld
",dp[n]);
30 }
View Code
T3:最大值
写的不是题解思路,稍麻烦,码量较大,思维量较大,较麻烦,常数也稍大(需要zkw+fread+取模优化并且还不能乱开long long才能卡过。。。)
可以发现,因为不包含,所以询问按左端点排序之后,右端点也就单调了。
所以其实可以两个单调指针扫一遍,操作就类似于莫队了。
每个魔法阵内部的各种取值的概率比较好计算,从小到大依次考虑,每个元素的概率就是前面所有项$1-p$的乘积再乘这个取值的p。
对于剩下的概率,还要加入一个0。
关键在于魔法阵之间的影响。
暴力的思路就是把区间内的魔法阵都加入set,然后按照和上面一样的方法依次考虑。
只不过要注意,对于任意一个可能值,它的概率都不会受到他自己来源的魔法阵的影响,需要除去。
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define int long long
4 #define mod 1000000007
5 #define ip(p) (1000000008-p)
6 int qpow(int b,int t,int a=1){for(;t;t>>=1,b=b*b%mod)if(t&1)a=a*b%mod;return a;}
7 #define inv(p) qpow(p,mod-2)
8 struct P{
9 int w,p,b;
10 friend bool operator<(P a,P b){return a.w<b.w;}
11 }p;
12 struct Q{
13 int l,r;
14 friend bool operator<(Q a,Q b){return a.l<b.l;}
15 }qs[200005];
16 vector<P>v[200005],V[200005];
17 multiset<P>S;
18 int n,m,q,alpos[200005],ans;
19 main(){freopen("max.in","r",stdin);freopen("max.out","w",stdout);
20 scanf("%lld%lld%lld",&n,&m,&q);
21 for(int i=1;i<=m;++i)scanf("%lld%lld%lld",&p.b,&p.w,&p.p),v[p.b].push_back(p);
22 for(int i=1;i<=n;++i){
23 sort(v[i].begin(),v[i].end());
24 int rpos=1;
25 for(int j=0;j<v[i].size();++j)V[i].push_back((P){v[i][j].w,v[i][j].p*rpos%mod,i}),rpos=rpos*ip(v[i][j].p)%mod;
26 V[i].push_back((P){0,rpos,i});
27 }
28 for(int i=1;i<=q;++i)scanf("%lld%lld",&qs[i].l,&qs[i].r);
29 sort(qs+1,qs+1+q);qs[0].l=1;
30 for(int i=1;i<=q;++i){
31 for(int j=qs[i-1].r+1;j<=qs[i].r;++j)for(int k=0;k<V[j].size();++k)S.insert(V[j][k]);
32 for(int j=qs[i-1].l;j<qs[i].l;++j)for(int k=0;k<V[j].size();++k)S.erase(S.find(V[j][k]));
33 int rpos=1;
34 for(int j=qs[i].l;j<=qs[i].r;++j)alpos[j]=1;
35 for(set<P>::reverse_iterator it=S.rbegin();it!=S.rend();++it){P It=*it;
36 rpos=(rpos*inv(alpos[It.b]))%mod;
37 ans=(ans+rpos*It.p%mod*It.w)%mod;
38 alpos[It.b]=(mod+alpos[It.b]-It.p)%mod;
39 rpos=rpos*alpos[It.b]%mod;
40 }
41 }printf("%lld
",ans);
42 }
60分暴力
要注意一些地方:一个晶石并不会对来自与同一魔法阵的晶石产生影响,但是乘法标记是区间一起打上的不能区分,所以在进行区间加的时候,还要除以以前来自同一魔法阵所打上的乘法标记。
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define ll long long
4 #define mod 1000000007
5 int Mod(ll x){return x>=mod?x-mod:x;}
6 const int L=1<<20|1;
7 char buffer[L],*S,*Q;
8 #define getchar() ((S==Q&&(Q=(S=buffer)+fread(buffer,1,L,stdin),S==Q))?EOF:*S++)
9 const int maxn=100000+5;
10 int read(){
11 register int p=0;register char ch=getchar();
12 while(ch<'0'||ch>'9')ch=getchar();
13 while(ch>='0'&&ch<='9')p=(p<<3)+(p<<1)+ch-48,ch=getchar();
14 return p;
15 }
16 ll qpow(ll b,int t,ll a=1){for(;t;t>>=1,b=b*b%mod)if(t&1)a=a*b%mod;return a;}
17 struct P{
18 ll w,p;int b,rk;
19 friend bool operator<(P a,P b){return a.w<b.w;}
20 }p;
21 struct N{
22 ll w;int ord;
23 friend bool operator<(N a,N b){return a.w<b.w||(a.w==b.w&&a.ord<b.ord);}
24 }W[300005];
25 ll inv(ll p){return p?qpow(p,mod-2):-1;}
26 ll ip(ll p){return (mod+1-p)%mod;}
27 vector<P>v[200005],V[200005];
28 int n,m,q,K,k,l[100005],r[100005];ll ans;
29 struct Segment_Tree{
30 ll w[1200005],lz[1200008];int NONE[1200008];
31 int cal(int p){return NONE[p]?0:lz[p]*w[p]%mod;}
32 int bit;
33 void build(){
34 for(bit=1;bit<=k+1;bit<<=1);
35 for(int i=1;i<=bit+bit;++i) lz[i]=1;
36 }
37 void mult(int l,int r,ll v){
38 for(l+=bit-1,r+=bit+1;l^r^1;){
39 if(~l&1){
40 if(v>0) lz[l^1]=lz[l^1]*v%mod;
41 else if(!v)NONE[l^1]++;
42 else NONE[l^1]--;
43 }
44 if(r&1){
45 if(v>0) lz[r^1]=lz[r^1]*v%mod;
46 else if(!v)NONE[r^1]++;
47 else NONE[r^1]--;
48 }
49 l>>=1; r>>=1;
50 w[l]=Mod(cal(l<<1)+cal(l<<1|1));
51 w[r]=Mod(cal(r<<1)+cal(r<<1|1));
52 }
53 for(l>>=1;l;l>>=1) w[l]=Mod(cal(l<<1)+cal(l<<1|1));
54 }
55 void add(int p,ll v){
56 p+=bit; w[p]=(w[p]+v*W[p-bit].w)%mod;
57 for(p>>=1;p;p>>=1) w[p]=Mod(cal(p<<1)+cal(p<<1|1));
58 }
59 }T;
60 bool com(P a,P b){return a.w>b.w;}
61 main(){
62 freopen("max.in","r",stdin);
63 freopen("max.out","w",stdout);
64 scanf("%d%d%d",&n,&m,&q);
65 for(int i=1;i<=m;++i)p.b=read(),p.w=read(),p.p=read(),v[p.b].push_back(p);
66 for(int i=1;i<=n;++i){
67 sort(v[i].begin(),v[i].end());
68 ll rpos=1;
69 for(int j=0;j<v[i].size();++j)V[i].push_back((P){v[i][j].w,v[i][j].p*rpos%mod,i,++K}),rpos=rpos*ip(v[i][j].p)%mod;
70 V[i].push_back((P){0,rpos,i,++K});
71 }
72 for(int i=1;i<=n;++i)for(int j=0;j<V[i].size();++j)W[++k]=(N){V[i][j].w,V[i][j].rk};
73 sort(W+1,W+1+k);T.build();
74 for(int i=1;i<=n;++i)for(int j=0;j<V[i].size();++j)V[i][j].w=lower_bound(W+1,W+1+k,(N){V[i][j].w,V[i][j].rk})-W;
75 for(int i=1;i<=n;++i)sort(V[i].begin(),V[i].end(),com);
76 for(int i=1;i<=q;++i)l[i]=read(),r[i]=read();
77 l[0]=1;
78 for(int i=1;i<=q;++i){
79 for(int j=r[i-1]+1;j<=r[i];++j){
80 ll totpos=0;
81 for(int k=0;k<V[j].size();++k){
82 if(V[j][k].p==0)continue;
83 ll TP=totpos;totpos=Mod(totpos+V[j][k].p);
84 T.mult(1,V[j][k].w-1,ip(totpos));
85 if(k)T.mult(1,V[j][k].w,inv(ip(TP)));
86 T.add(V[j][k].w,V[j][k].p);
87 }
88 }
89 for(int j=l[i-1];j<l[i];++j){
90 ll totpos=0;
91 for(int k=0;k<V[j].size();++k){
92 if(V[j][k].p==0)continue;
93 totpos=Mod(totpos+V[j][k].p);
94 T.mult(1,V[j][k].w-1,inv(ip(totpos)));
95 if(k)T.mult(1,V[j][k].w-1,ip(totpos-V[j][k].p));
96 T.add(V[j][k].w,mod-V[j][k].p);
97 }
98 }
99 ans=(ans+T.w[1]*T.lz[1])%mod;
100 }printf("%lld
",ans);
101 }