[考试反思]1026csp-s模拟测试88：发展

不用你们说，我自己来：我颓闪存我没脸。

昨天的想法，

今天的回答。

生存，

发展。

总分榜应该稍有回升，但是和上面的差距肯定还是很大。

继续。

为昨天的谬误，承担代价。

T2和T3都值得张记性。

T2因为上次输出了"-0.00"在文本比较下与"0.0"不同导致WA，所以这次输出的时候把答案加了0.005

但是加的太多了，在四舍五入下恰好进位了导致WA。

为了防止输出"-0.0"要将答案加一个1e-9级别的数，不要太小也不要太大。

T3算错上限没打高精。

考虑极端情况。考试时不要用__int128（CSP-S不认可）

我不喜欢RP守恒。

我想稳在rank5以内。遥不可及。

T1：军训队列。

一个明显的斜率优化dp。但是考场上推了一会没有推出来。

然而这题用不到，因为身高最多有6001种，所以$O(6001*6001*k)$可过

但是要注意把所有人身高压起来后n可能小于k，判掉。

斜率优化的假单调栈可以当成是一个剪枝。

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 double dp[][],h[];int n,k,q[],qh,qt;

 double fab2(double x){return x*x;}

 double cal(int j,int k,int f){return (dp[j][f-]-dp[k][f-])/(h[j+]-h[k+])+h[j+]+h[k+];}

 int main(){

     scanf("%d%d",&n,&k);

     for(int i=;i<=n;++i)scanf("%lf",&h[i]);

     sort(h+,h++n);n=unique(h+,h++n)-h-;h[n+]=1e9;

     for(int i=;i<=n;++i)dp[i][]=fab2(h[i]-h[]);

     for(int j=;j<=k;++j){

         q[qt=qh=]=;

         for(int i=;i<=n;++i){

             dp[i][j]=1e18;

             while(qt-qh>=&&cal(q[qh+],q[qh],j)<h[i]*)qh++;

             for(int p=qh;p<=qt;++p)dp[i][j]=min(dp[i][j],dp[q[p]][j-]+fab2(h[i]-h[q[p]+]));

             q[++qt]=i;

         }

     }printf("%.2lf\n",dp[n][k]);

 }

然而当然也可以打一个真正的斜率优化。

转移式是$dp[i][f]=min(dp[j][f-1]+(h[j+1])^2+(h[i])^2-2\times h[j+1] \times h[i])$

然后接下来与i有关的项都可以提出来，剩下的是常数。

然后就可以得到一个关于$h[i]$的一次函数（直线）。

因为在这道题里h是单调的，所以斜率是单调的，取值的横坐标也是单调的。

所以就是一堆直线，可以维护凸包了。

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 double dp[][],h[],k[],b[];int n,K,q[],qh,qt;

 double fab2(double x){return x*x;}

 double cal(int j,double x){return b[j]+k[j]*x;}

 double jd(int j,int i){return (b[j]-b[i])/(k[i]-k[j]);}

 int main(){

     scanf("%d%d",&n,&K);

     for(int i=;i<=n;++i)scanf("%lf",&h[i]);

     sort(h+,h++n);n=unique(h+,h++n)-h-;h[n+]=1e9;

     for(int i=;i<=n;++i)dp[i][]=fab2(h[i]-h[]);

     for(int j=;j<=K;++j){

         q[qt=qh=]=j-;k[j-]=-*h[j];b[j-]=dp[j-][j-]+fab2(h[j]);

         for(int i=j;i<=n;++i){

             k[i]=-*h[i+];b[i]=dp[i][j-]+fab2(h[i+]);

             while(qt-qh>=&&cal(q[qh],h[i])>cal(q[qh+],h[i]))qh++;

             while(qt-qh>=&&jd(q[qt-],i)>jd(q[qt],i))qt--;

             dp[i][j]=dp[q[qh]][j-]+fab2(h[i]-h[q[qh]+]);

             q[++qt]=i;

         }

     }printf("%.2lf\n",dp[n][K]);

 }

T2：山屋惊魂

规模不是很大的模拟。虽说也不小。

预处理一下dize[i][j]表示用i个骰子得到j的概率。（骰子的英语不是dize。。。打脸。。。但是我懒得改了）

然后。。我也不知道该讲什么。。。模拟好像真的没办法讲。。。

按照题目说的就是了。不要读错题

其实我不是很明白为什么会打的那么长，并没有感觉这个模拟比以前的模拟难很多。。。

 #include<cstdio>

 #include<string>

 #include<iostream>

 #include<map>

 using namespace std;

 map<string,int>M;

 long double dize[][],pos[][],fail,ans[][],lim[][][];

 int n,st[],s[],c1[],c2[],num;

 string bar[],knd,opt;

 int chg(int S,int p,int w){return (S^S&<<p*)|w<<p*;}

 int main(){//freopen("betrayal.in","r",stdin);

     dize[][]=;

     for(int i=;i<=;++i)for(int j=;j<=i<<;++j)

         dize[i+][j]+=dize[i][j]/,dize[i+][j+]+=dize[i][j]/,dize[i+][j+]+=dize[i][j]/;

     for(int i=;i<;++i)cin>>bar[i]>>st[i],st[i]--;

     cin>>n;

     pos[][st[]|st[]<<|st[]<<|st[]<<]=;

     M["Might"]=;M["Speed"]=;M["Sanity"]=;M["Knowledge"]=;

     for(int i=;i<n;++i){

         cin>>knd>>opt;

         if(opt=="<"){

             cin>>num;

             for(int j=;j<=;++j)for(int k=;k<=;++k)lim[i][M[knd]][j]+=(dize[bar[M[knd]][j]-''][k]*(k>=num));

             cin>>knd>>opt;

         }else if(opt=="<="){

             cin>>num;

             for(int j=;j<=;++j)for(int k=;k<=;++k)lim[i][M[knd]][j]+=(dize[bar[M[knd]][j]-''][k]*(k> num));

             cin>>knd>>opt;

         }else if(opt==">"){

             cin>>num;

             for(int j=;j<=;++j)for(int k=;k<=;++k)lim[i][M[knd]][j]+=(dize[bar[M[knd]][j]-''][k]*(k<=num));

             cin>>knd>>opt;

         }else if(opt==">="){

             cin>>num;

             for(int j=;j<=;++j)for(int k=;k<=;++k)lim[i][M[knd]][j]+=(dize[bar[M[knd]][j]-''][k]*(k< num));

             cin>>knd>>opt;

         }

         s[i]=M[knd];

         if(opt[]=='+')if(opt.length()==)c2[i]+=opt[]-'';

             else c1[i]+=opt[]-'';

         if(opt[]=='-')if(opt.length()==)c2[i]-=opt[]-'';

             else c1[i]-=opt[]-'';//printf("%d %d %d\n",s[i],c1[i],c2[i]);

     }

     for(int i=;i<n;++i)for(int S=;S<<<;++S){

         int state[]={S&,S>>&,S>>&,S>>&};

         double rp=pos[i][S];

         for(int j=;j<;++j)rp*=(-lim[i][j][state[j]]);

         pos[i+][S]+=pos[i][S]-rp;

         if(c1[i]){

             state[s[i]]+=c1[i];state[s[i]]=min(state[s[i]],);

             if(state[s[i]]<)fail+=rp;

             else pos[i+][chg(S,s[i],state[s[i]])]+=rp;

         }else if(c2[i]>=){

             for(int r=;r<=;++r){

                 double P=rp*dize[c2[i]][r];

                 int nw=state[s[i]]+r;nw=min(nw,);

                 pos[i+][chg(S,s[i],nw)]+=P;

             }

         }else{

             for(int r=;r<=;++r){

                 double P=rp*dize[-c2[i]][r];

                 int nw=state[s[i]]-r;

                 if(nw<)fail+=P;

                 else pos[i+][chg(S,s[i],nw)]+=P;

             }

         }ed:;

     }

     printf("%.2Lf\n",fail*+0.0001);

     for(int i=;i<<<;++i)for(int k=;k<;++k)ans[k][bar[k][i>>k*&]-'']+=pos[n][i];

     for(int k=;k<;++k,puts(""))for(int i=;i<;++i)printf("%.2Lf ",ans[k][i]*+0.0001);

 }

2.4k，可写

 #include<cstdio>

 #include<string>

 #include<iostream>

 #include<map>

 using namespace std;

 map<string,int>M;

 double dize[][],pos[][],fail,ans[][],lim[][][];

 int n,st[],s[],c1[],c2[],num;

 string bar[],knd,opt;

 int chg(int S,int p,int w){return (S^S&<<p*)|w<<p*;}

 int abs(int a){return a>?a:-a;}

 int nt(int a){return a>?:-;}

 int OPT(string s,int a,int b){return s=="<="?a>b:(s=="<"?a>=b:(s==">="?a<b:a<=b));}

 int main(){

     dize[][]=;

     for(int i=;i<;++i)for(int j=;j<=i*;++j)

         dize[i+][j]+=dize[i][j]/,dize[i+][j+]+=dize[i][j]/,dize[i+][j+]+=dize[i][j]/;

     for(int i=;i<;++i)cin>>bar[i]>>st[i],st[i]--;

     cin>>n; pos[][st[]|st[]<<|st[]<<|st[]<<]=;

     M["Speed"]=;M["Sanity"]=;M["Knowledge"]=;

     for(int i=;i<n;++i){

         cin>>knd>>opt;

         if(opt[]!='+'&&opt[]!='-'){

             cin>>num;

             for(int j=;j<;++j)for(int k=;k<=;++k)

                 lim[i][M[knd]][j]+=(dize[bar[M[knd]][j]-''][k]*OPT(opt,k,num));

             cin>>knd>>opt;

         }

         s[i]=M[knd];

         if(opt.length()==)c2[i]+=(opt[]-'')*(opt[]=='+'?:-);

         else c1[i]+=(opt[]-'')*(opt[]=='+'?:-);

     }

     for(int i=;i<n;++i)for(int S=;S<<<;++S){

         int state[]={S&,S>>&,S>>&,S>>&}; double rp=pos[i][S];

         for(int j=;j<;++j)rp*=(-lim[i][j][state[j]]);

         pos[i+][S]+=pos[i][S]-rp;

         if(c1[i]){

             state[s[i]]+=c1[i];state[s[i]]=min(state[s[i]],);

             if(state[s[i]]<)fail+=rp;

             else pos[i+][chg(S,s[i],state[s[i]])]+=rp;

         }else for(int r=;r<=;++r){

             double P=rp*dize[abs(c2[i])][r];

             int nw=state[s[i]]+nt(c2[i])*r;nw=min(nw,);

             if(nw<)fail+=P;else pos[i+][chg(S,s[i],nw)]+=P;

         }

     }

     printf("%.2lf\n",fail*+1e-);

     for(int i=;i<<<;++i)for(int k=;k<;++k)ans[k][bar[k][i>>k*&]-'']+=pos[n][i];

     for(int k=;k<;++k,puts(""))for(int i=;i<;++i)printf("%.2lf ",ans[k][i]*+1e-);

 }

1.8k，压行

压行后的代码不存在任何的复制粘贴了，可以简单扩展了。

T3：彩球问题

记忆化搜索/dp

状态4维，12/12/12/4，分别表示还有1/2/3个的球有几种颜色，且上一次用的球还剩下0/1/2个

然后又是模拟？

最后的答案貌似有$10^{33}$级别？

 #include<cstdio>

 #define dp re[c1][c2][c3][lst]

 __int128 ans,re[][][][];int cnt[],n,x;

 __int128 sch(int c1,int c2,int c3,int lst){

     if(dp!=-)return dp;

     dp=;

     if(c1==&&c2==&&c3==)return ;

     if(lst==){

         if(c1)dp+=c1*sch(c1-,c2,c3,);

         if(c2)dp+=c2*sch(c1+,c2-,c3,);

         if(c3)dp+=c3*sch(c1,c2+,c3-,);

     }else if(lst==){

         if(c1>)dp+=(c1-)*sch(c1-,c2,c3,);

         if(c2)dp+=c2*sch(c1+,c2-,c3,);

         if(c3)dp+=c3*sch(c1,c2+,c3-,);

     }else if(lst==){

         if(c1)dp+=c1*sch(c1-,c2,c3,);

         if(c2>)dp+=(c2-)*sch(c1+,c2-,c3,);

         if(c3)dp+=c3*sch(c1,c2+,c3-,);

     }return dp;

 }

 int main(){

     scanf("%d",&n);

     while(n--)scanf("%d",&x),cnt[x]++;

     for(int i=;i<;++i)for(int j=;j<;++j)for(int k=;k<;++k)for(int l=;l<;++l)re[i][j][k][l]=-;

     __int128 x=sch(cnt[],cnt[],cnt[],);

     if(x/1000000000000000000ll)printf("%lld",(long long)(x/1000000000000000000ll));

     printf("%lld\n",(long long)(x%1000000000000000000ll));

 }

你可以用int128水过

 #include<cstdio>

 #define dp re[c1][c2][c3][lst]

 struct LL{

     long long x[];

     #define mod 100000000

     friend void operator+=(LL &a,LL b){

         for(int i=;i<;++i)a.x[i]+=b.x[i];

         for(int i=;i<;++i)a.x[i+]+=a.x[i]/mod,a.x[i]%=mod;

     }

     void print(int i=){

         for(;~i;--i)if(x[i]){printf("%lld",x[i]);break;}

         for(--i;~i;--i)printf("%08lld",x[i]);

     }

     friend LL operator*(int x,LL a){

         for(int i=;i<;++i)a.x[i]*=x;

         for(int i=;i<;++i)a.x[i+]+=a.x[i]/mod,a.x[i]%=mod;

         return a;

     }

     friend bool operator!=(LL a,int x){return a.x[]!=-;}

     void operator=(int p){x[]=p;}

 };

 LL ans,re[][][][];int cnt[],n,x;

 LL sch(int c1,int c2,int c3,int lst){

     if(dp!=-)return dp;

     dp=;

     if(c1==&&c2==&&c3==)return dp=,dp;

     if(lst==){

         if(c1)dp+=c1*sch(c1-,c2,c3,);

         if(c2)dp+=c2*sch(c1+,c2-,c3,);

         if(c3)dp+=c3*sch(c1,c2+,c3-,);

     }else if(lst==){

         if(c1>)dp+=(c1-)*sch(c1-,c2,c3,);

         if(c2)dp+=c2*sch(c1+,c2-,c3,);

         if(c3)dp+=c3*sch(c1,c2+,c3-,);

     }else if(lst==){

         if(c1)dp+=c1*sch(c1-,c2,c3,);

         if(c2>)dp+=(c2-)*sch(c1+,c2-,c3,);

         if(c3)dp+=c3*sch(c1,c2+,c3-,);

     }return dp;

 }

 int main(){

     scanf("%d",&n);

     while(n--)scanf("%d",&x),cnt[x]++;

     for(int i=;i<;++i)for(int j=;j<;++j)for(int k=;k<;++k)for(int l=;l<;++l)re[i][j][k][l]=-;

     sch(cnt[],cnt[],cnt[],).print();

 }

但是显然作为一个有脸的人还是要写一次高精的

因为真正CSP-S上也不能用__int128，所以就算是模拟赛写高精也是很有必要的。

态度必须要有，天人不相欺。

巴特西

[考试反思]1026csp-s模拟测试88：发展

最新文章

热门文章