[考试反思]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();
}