CSPS模拟86-87
分类:
IT文章
•
2022-05-16 15:05:09
模拟86
T1，烧水，按位统计贡献，利用某种sao操作避免数位dp
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 const int mod=1000000007;
6 using namespace std;
7 int n,m;
8 int dp1[40],sum[40];
9 int bin[40];
10 inline void get1(int x)
11 {
12 memset(dp1,0,sizeof(dp1));
13 if(x<0)return;
14 for(int i=29;~i;--i)
15 {
16 dp1[i]=(x>>(i+1))+1;
17 if(x&bin[i])dp1[i]=1ll*bin[i]*dp1[i]%mod;
18 else{
19 dp1[i]=1ll*(x>>(i+1))*bin[i]%mod;
20 dp1[i]+=(x&(bin[i]-1));++dp1[i];
21 if(dp1[i]>=mod)dp1[i]-=mod;
22 }
23 }
24 }
25 int main()
26 {
27 for(int i=0;i<=30;++i)bin[i]=1<<i;
28 int T;scanf("%d",&T);
29 while(T--)
30 {
31 scanf("%d%d",&m,&n);
32 memset(sum,0,sizeof(sum));
33 get1(n);
34 for(int i=0;i<=30;++i)sum[i]+=dp1[i];
35 get1(m-1);
36 for(int i=0;i<=30;++i)sum[i]-=dp1[i];
37 int ans=0;const int num=n-m+1;
38 for(int i=0;i<=30;++i)
39 {
40 ans+=2ll*sum[i]%mod*(num-sum[i])%mod*bin[i]%mod;
41 if(ans>=mod)ans-=mod;
42 }
43 ans=((ans%mod)+mod)%mod;
44 cout<<ans<<endl;
45
46 }
47 }
View Code
T2，博弈，考场上推出了最小为0时的答案，以为能找出规律，连暴力都没打，kuku
正解为用必败状态筛必胜状态来保证复杂度。%%%脸哥压表，处理出不合法状态hash掉，最后在数组里lower_bound即可。
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #define re register
6 using namespace std;
7 int n,m;
8 int a[5];
9 char dp[301][301][301];
10 int main()
11 {
12 for(re short i=0;i<=300;++i)
13 {
14 for(re short j=0;j<=300;++j)
15 {
16 for(re short k=0;k<=300;++k)
17 {
18 if(dp[i][j][k])continue;
19 for(re short o=1;o+i<=300;++o)dp[i+o][j][k]=1;
20 for(re short o=1;o+j<=300;++o)dp[i][j+o][k]=1;
21 for(re short o=1;o+k<=300;++o)dp[i][j][k+o]=1;
22 for(re short o=1;o+i<=300&&o+j<=300;++o)dp[i+o][j+o][k]=1;
23 for(re short o=1;o+i<=300&&o+k<=300;++o)dp[i+o][j][k+o]=1;
24 for(re short o=1;o+k<=300&&o+j<=300;++o)dp[i][j+o][k+o]=1;
25 for(re short o=1;o+i<=300&&o+k<=300&&o+j<=300;++o)dp[i+o][j+o][k+o]=1;
26 }
27 }
28 }
29 int T;scanf("%d",&T);
30 while(T--)
31 {
32 scanf("%d%d%d",&a[1],&a[2],&a[3]);
33 if(dp[a[1]][a[2]][a[3]])puts("Yes");
34 else puts("No");
35 }
36 }
View Code
T3，dp，对前缀和取max优化。考场上想出了第三维表示四个状态（顶峰，底端，上升，下降），然而没想到转移。
在最外层枚举区间数，对四种状态用4个变量分别维护最优点转移即可。%%%WWB_star，rnb，milk_feng让我认识到自己的错误
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #define N 30040
6 using namespace std;
7 int n,K,ans;
8 int a[N],sum[N],dp[205][N][5];
9 const int inf=0x3f3f3f3f;
10 int main()
11 {
12 memset(dp,-0x3f,sizeof(dp));
13 scanf("%d%d",&n,&K);
14 for(int i=1;i<=n;++i)
15 scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
16 int mi=0,ma=0,mi2=0,ma2=0;
17 for(int i=1;i<=n;++i){
18 dp[1][i][2]=sum[i]-mi;
19 dp[1][i][1]=ma-sum[i];
20 dp[1][i][0]=dp[1][i][2];
21 dp[1][i][3]=dp[1][i][1];
22 mi=min(mi,sum[i]);ma=max(ma,sum[i]);
23 }
24 for(int j=2;j<K;++j){
25 mi=ma=mi2=ma2=-inf;
26 for(int i=j-1;i<=n;++i)
27 {
28 dp[j][i][2]=max(dp[j][i][2],ma+2*sum[i]);
29 dp[j][i][1]=max(dp[j][i][1],mi-2*sum[i]);
30
31 dp[j][i][0]=max(dp[j][i][0],mi2);
32 dp[j][i][3]=max(dp[j][i][3],ma2);
33 mi=max(mi,dp[j-1][i][2]+sum[i]*2);
34 mi=max(mi,dp[j-1][i][0]+sum[i]*2);
35
36 ma=max(ma,dp[j-1][i][1]-sum[i]*2);
37 ma=max(ma,dp[j-1][i][3]-sum[i]*2);
38
39 ma2=max(ma2,dp[j-1][i][1]);
40 ma2=max(ma2,dp[j-1][i][3]);
41
42 mi2=max(mi2,dp[j-1][i][2]);
43 mi2=max(mi2,dp[j-1][i][0]);
44 }
45 }
46 mi=ma=mi2=ma2=-inf;
47 for(int i=K-1;i<=n;++i)
48 {
49 dp[K][i][2]=max(dp[K][i][2],ma+sum[i]);
50 dp[K][i][1]=max(dp[K][i][1],mi-sum[i]);
51
52 dp[K][i][0]=max(dp[K][i][0],mi2);
53 dp[K][i][3]=max(dp[K][i][3],ma2);
54
55 mi=max(mi,dp[K-1][i][2]+sum[i]);
56 mi=max(mi,dp[K-1][i][0]+sum[i]);
57
58 ma=max(ma,dp[K-1][i][1]-sum[i]);
59 ma=max(ma,dp[K-1][i][3]-sum[i]);
60
61 ma2=max(ma2,dp[K-1][i][1]);
62 ma2=max(ma2,dp[K-1][i][3]);
63
64 mi2=max(mi2,dp[K-1][i][2]);
65 mi2=max(mi2,dp[K-1][i][0]);
66
67 ans=max(ans,dp[K][i][2]);
68 ans=max(ans,dp[K][i][1]);
69 }
70 printf("%d
",ans);
71 }
View Code
| 300 |
145 |
120 |
50 |
110 |
220 |
122 |
160 |
130 |
这个故事告诉我们：rp是个好东西（别败光了）
模拟87，新的开始，勉强苟住位置（抢到Dybala的第八）
T1，（妹子）maze
考场上想了半天才想到是二分答案。然后就疯狂码码码，打了个代码测时长，发现极限数据甚至会达到十几秒，然后疯狂卡常
最后当我手打堆打到一半，发现我的结构体重载运算符重载反了，赶紧改过来，发现还剩1分钟，慌的一比。。。
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<bitset>
6 #include<vector>
7 #include<cmath>
8 #include<queue>
9 #define N 105
10 using namespace std;
11 const double eps=1e-5;
12 const int dx[]={1,-1,0,0};
13 const int dy[]={0,0,1,-1};
14 int n,m,sx,sy,tx,ty;
15 bool vst[N][N];
16 double dis[N][N],s;
17 int a[N][N];
18 struct node{
19 int x;
20 int y;
21 double z;
22 friend bool operator <(const node &a,const node &b)
23 {return a.z>b.z;}
24 };
25 /*
26 struct QAQ{
27 node a[100500];
28 int tot;
29 inline int size(){return tot;}
30 inline void clear(){tot=0;}
31 inline node top(){return a[1];}
32 inline void pop()
33 {
34 a[1]=a[tot++];int i=1,j;
35 while(1)
36 {
37 j=i<<1;
38 if(j>tot)return;
39 if(a[j+1]<a[j])
40 }
41 }
42
43 }
44 */
45 priority_queue<node>q;
46 inline void init()
47 {
48 for(register int i=1;i<=n;++i)
49 for(register int j=1;j<=m;++j)
50 dis[i][j]=1000000.0;
51 }
52 inline node mknd(int x,int y,double z)
53 {
54 node a;a.x=x,a.y=y,a.z=z;return a;
55 }
56 inline void dijk(double val)
57 {
58 while(q.size())q.pop();init();
59 dis[sx][sy]=0.0;
60 q.push(mknd(sx,sy,0.0));
61 int xx,yy,x,y;double z;
62 while(q.size())
63 {
64 x=q.top().x;y=q.top().y;z=q.top().z;q.pop();
65 if(z!=dis[x][y])continue;if(x==tx&&y==ty)return;
66 for(register int i=3;~i;--i)
67 {
68 xx=x+dx[i];yy=y+dy[i];
69 if(a[xx][yy])continue;
70 if(dx[i])
71 {
72 if(dis[xx][yy]>z+val)
73 {
74 dis[xx][yy]=z+val;
75 q.push(mknd(xx,yy,dis[xx][yy]));
76 }
77 }
78 else
79 {
80 if(dis[xx][yy]>z+1.0)
81 {
82 dis[xx][yy]=z+1.0;
83 q.push(mknd(xx,yy,dis[xx][yy]));
84 }
85 }
86 }
87 }
88 }
89 inline void work()
90 {
91 double l=0.0,r=s,mid;
92 while(r-l>3e-4){
93 mid=(l+r)*0.5;dijk(mid);
94 if(dis[tx][ty]-s>0.0)r=mid;
95 else l=mid;
96 if(fabs(dis[tx][ty]-s)<5e-4){l=mid;break;}
97 // printf("%.10lf %.10lf
",l,r);
98 }
99 printf("%.3lf
",l);
100 }
101 int main()
102 {
103 // freopen("da.in","r",stdin);//freopen("my.out","w",stdout);
104 scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&tx,&ty);
105 for(int i=1;i<=n;++i)
106 for(int j=1,x;j<=m;++j)
107 scanf("%d",&x),a[i][j]=x;
108
109 a[sx][sy]=a[tx][ty]=0;
110 dijk(1.0);if(dis[tx][ty]>100000.0)return 0;
111 for(int i=1;i<=n;++i)a[i][0]=a[i][m+1]=1;
112 for(int i=1;i<=m;++i)a[0][i]=a[n+1][i]=1;
113 scanf("%lf",&s);work();return 0;
114 }
115 /*
116 4 4
117 1 1 4 4
118 0 0 1 1
119 1 0 0 0
120 0 0 1 0
121 0 0 0 0
122 5
123 */
View Code
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<bitset>
6 #include<vector>
7 #include<queue>
8 #define N 500050
9 using namespace std;
10 int n,m;
11 vector<int>v[N];
12 int sum[N],dp[N];
13 struct node{
14 int l,r;
15 }q[100050];
16 int A,ans;
17 int ma[N<<2],tag[N<<2];
18 inline void upd(int g){ma[g]=max(ma[g<<1],ma[g<<1|1]);}
19 inline void down(int g)
20 {
21 tag[g<<1]+=tag[g];
22 ma[g<<1]+=tag[g];
23 tag[g<<1|1]+=tag[g];
24 ma[g<<1|1]+=tag[g];
25 tag[g]=0;
26 }
27 inline void add(int g,int l,int r,int x,int y,int v)
28 {
29 if(l>y||r<x)return;
30 if(l>=x&&r<=y){ma[g]+=v;tag[g]+=v;return;}
31 if(tag[g])down(g);
32 const int m=l+r>>1;
33 add(g<<1,l,m,x,y,v);add(g<<1|1,m+1,r,x,y,v);
34 upd(g);
35 }
36 inline int ask(int g,int l,int r,int x,int y)
37 {
38 if(l>y||r<x)return 0;
39 if(l>=x&&r<=y)return ma[g];
40 if(tag[g])down(g);
41 const int m=l+r>>1;
42 const int a1=ask(g<<1,l,m,x,y),a2=ask(g<<1|1,m+1,r,x,y);
43 if(a1>a2)return a1;return a2;
44 }
45 int main()
46 {
47 scanf("%d%d",&n,&m);
48 for(int i=1,l,r;i<=n;++i)
49 {
50 scanf("%d%d",&l,&r);
51 if(r<0)continue;
52 if(l<0)l=0;
53 v[r+1].push_back(l);
54 if(r>A)A=r;
55 ++sum[l];
56 }
57 ++A;int al=0;
58 for(int i=0;i<=A;++i)
59 {
60 al+=sum[i];
61 for(int j=0;j<v[i].size();++j)
62 add(1,0,A,v[i][j],i-1,1),--al;
63 dp[i]=ask(1,0,A,0,i-m);
64 ans=max(ans,dp[i]+al);
65 add(1,0,A,i,i,dp[i]);
66 }
67 cout<<ans<<endl;
68 return 0;
69 }
