非酋yyf的sif之旅题解

# ~~本篇题解格式参照ION2018~~ ## [肝活动](https://www.luogu.org/problemnew/show/P4851) 就是一道纯模拟题..玩过sif的可以秒切了，没玩过的照着“形式化说明”就可以写了。 怎么说，其实也能算是一道入门难度的贪心？ 能进行操作 $1$ 就进行操作 $1$ ，否则进行操作 $2$ ，直到活动 $\mathrm{pt} \ge y$ ~~假装这是一道贪心题~~，贪心策略的证明就是先进行操作 $1$ 可以提高 $\mathrm{LP}$ 上限，然后操作 $2$ 能恢复的 $\mathrm{LP}$ 就会变多 时间复杂度：$O(\text{能过})$ 期望得分：$100$ 分 ~~代码注释被形式化说明吃了~~ ### 赛后补充 > 由于你可以选择在任意时候打歌且打歌不计时间，每小时恢复和一开始就恢复是等价的... 本来以为有了形式化说明这里不会有问题的... 另外看不懂的真的可以只看形式化说明... 另外本来这题数据是纯随机的，后来我突然想试着卡一卡，就造了两个如果按大于（没有等于）做会WA的点，竟然真的卡到了好多人.. 然而除了0/96/100的其它分我是真的没想到.. ### UPD 我知道78分是怎么回事了..有的点会无限升级从而有无限lp，有lp无限打歌的算法就挂了 ### 标程 ``` #include <iostream> using namespace std; int main() { int a,b,c,d,e,f,g,h,k,x,y,pt=0,ans=0; cin>>a>>b>>c>>d>>e>>f>>g>>h>>k>>x>>y; d+=x; while (pt<y) { if (d>=b) { pt+=a; f+=g; if (f>=e) { d=d-b+c+h; c+=h; f-=e; e+=k; } else { d-=b; } } else { ++ans; d+=c; } } cout<<ans; return 0; } ``` ## [抽卡牌](https://www.luogu.org/problemnew/show/P4852) 为了方便下文中设 $s=n*c+m$ ### 算法一（纯暴力） 暴力枚举所有方案。 时间复杂度：$O(C^{\,n}_{\;s})$，然而实际上有一堆剪枝，剪完之后复杂度会不会下一个数量级呢？出题人懒得算，反正数据这么小，暴力20分肯定稳的。 期望得分：$20$ 分 ### 算法二（d=m） 因为 $d=m$ ，可以不管 $d$ 的限制 设 $f(i,j)$ 表示前 $i$ 张卡中连抽 $j$ 次的最大欧气，则可以得到方程： $f(i,j)=\max(f(i-1,j)+a[i],f(i-c,j-1)+a[i-c+1])$ 两种转移分别代表第 $i$ 张卡是单抽/一次连抽的结尾。 输出方案：记录一下每个 $f(i,j)$ 是由谁转移来的，算完dp之后从 $n$ 倒回去，如果倒回去的过程中某两张卡的间隔是 $c$ 代表这两张卡之间有一次连抽 时间复杂度：$O(sn)$ 期望得分：$20$ 分 ### 算法三（无优化dp） 选一组牌 $[l,r]$ 连抽其实就是使欧气总和减少了 $\sum\limits_{i=l+1}^ra_i$ ，所以预处理出 $b_i=\sum\limits_{j=i+1}^{i+c-1}a_j\ (i∈[1,s-c+1])$ ，题目就变成了选择 $n$ 个 $b_i$ ，它们两两的下标之差大于等于 $c$ 且小于等于 $c+d$，求它们的和的最小值。特别地，选择的第一个 $b_i$ 下标要小于等于 $d+1$，最后一个 $b_i$ 下标要大于等于 $s-c-d+1$（不这样转化也能做，但出题人感觉转化之后方便一些） 设 $f(i,j)$ 为在 $b_{[1,i]}$ 中选择 $j$ 个且选择 $b_i$ 的最小和，可以得到： $f(i,j)=\min\limits_{k∈[i-c-d,i-c]}(f(k,j-1))+b[i]$ 时间复杂度：$O(snd)$ 期望得分：$50$ 分 ### 算法四（数据分治） ~~使用数据分治结合算法二和算法一/三，可以获得更高的分数。~~ 时间复杂度：$O(d==m?sn:C^{\,n}_{\;s}||snd)$ 期望得分：$40/70$ 分 ### 算法五（不会输出方案） ~~看出题人多么仁慈还给你准备了部分分~~ 时间复杂度：$O(?)$ 期望得分：$12$~$60$ 分 ### 算法六（单调队列优化dp） 看这玩意 → $k∈[i-c-d,i-c]$ 嗯用单调队列优化一下就好了 不会单调队列？[~~如果一个人比你小，还比你强，那你就永远打不过他了~~](https://sweetlemon.blog.luogu.org/dan-diao-dui-lie) 输出方案：记录一下每个 $f(i,j)$ 由谁转移而来，就说明选了这个 $b_i$ ，而选了某个 $b_i$ 就说明 $i$ 是某一次连抽的起始 时间复杂度：$O(sn)$ 期望得分：$100$ 分 ### Bonus ~~在~~[~~我用v4评测机的第一次提交的编译信息~~](https://www.luogu.org/record/show?rid=9924927)~~里可以看到出题人的良心提示：~~ ``` if (sta[i]<1||sta[i]>s-c+1||i>1&&(sta[i]-sta[i-1]<c||sta[i]-sta[i-1]>c+d)) ``` 从这一行可以看出两次连抽的起始下标之差要在 $[c,c+d]$ 内。 实际上是v4评测机神仙到能显示spj的warning...然而并不知道为什么之后的提交就没有这个waring了. ### 标程 ``` #include <iostream> using namespace std; const int N=45,M=80005,C=3005; const int S=N*C+M; int n,m,c,d,s,a[S],b[S],f[S][N],p[S][N],q[N][S][2],head[N],tail[N],sum,ans[N],anss,ansi; //其实可以只开一个单调队列，然而出题人懒 int main() { int i,j; cin>>n>>m>>c>>d; s=n*c+m; for (i=1;i<=s;++i) { cin>>a[i]; sum+=a[i]; } for (i=2;i<=c;++i) { b[1]+=a[i]; //先算出b1 } for (i=2;i<=s-c+1;++i) { b[i]=b[i-1]-a[i]+a[i+c-1]; //然后O(1)算出剩下的b } for (i=1;i<=n;++i) { head[i]=1; //将所有单调队列初始化为空队 } for (i=1;i<=s-c+1;++i) { if (i<=c) { f[i][1]=b[i]; //i<=c时之前必然没有连抽，只有f(i,1)有定义，而此时队列还是空的，所以直接赋为bi就好了 } else { for (j=(i+c-2)/(c+d)+1;j<=(i+c-1)/c&&j<=n;++j) //应该是f(i,j)有定义的准确范围，自己手推一下就可以推出来了，然而两个验题的都没有把范围卡死就过了 { if (head[j-1]<=tail[j-1]&&q[j-1][head[j-1]][1]<i-c-d) { ++head[j-1]; //将下标小于i-c-d的b出队 } if (j-1>=(i-2)/(c+d)+1&&j-1<=(i-1)/c) //如果f(i-c,j-1)有定义就将其入队 { while (head[j-1]<=tail[j-1]&&q[j-1][tail[j-1]][0]>=f[i-c][j-1]) { --tail[j-1]; } q[j-1][++tail[j-1]][0]=f[i-c][j-1]; q[j-1][tail[j-1]][1]=i-c; } f[i][j]=q[j-1][head[j-1]][0]+b[i]; p[i][j]=q[j-1][head[j-1]][1]; //记录f(i,j)由谁转移而来 if (i>=s-c+1-d&&j==n&&anss<sum-f[i][j]) //只有下标大于等于s-c+1-d的时候才能用f(i,n)更新答案 { anss=sum-f[i][j]; ansi=i; } } } } cout<<anss<<endl; for (j=n;j>=1;--j) { ans[j]=ansi; ansi=p[ansi][j]; } for (j=1;j<=n;++j) { cout<<ans[j]<<' '; } return 0; } ``` ## [打歌曲](https://www.luogu.org/problemnew/show/P4853) ### 关于精度问题 赛时由于spj相关bug精度限制是绝对误差0.001，然后卡到了某些不该卡的..其实是少数，很多人都是直接cout没有precision被卡的. 现已修复。 ### 算法一（输出答案） 第一个点可以手算出答案为 $1003000$ 恭喜@Fee_cle6418 第一个拿到输出答案分！ 时间复杂度：$O(1)$ 期望得分：$5$ 分 ### 算法二（无技能） 直接模拟即可。 时间复杂度：$O(n)$ 期望得分：$10$ 分 ### 算法三（有加分） 当连击数不为零且为 $c_i$ 的倍数时，这个技能在这次击打中对答案的贡献为 $p_i*s_i$，所以扫一遍判断一下哪些技能的 $c$ 能整除当前连击数，把贡献加起来就好了。 时间复杂度：$O(\mathrm{score*n})$ 期望得分：$25$ 分 ### 算法四（蒟蒻ouuan第一次想到的dp） 用 $f[i][j][k]$ 表示打 $i$ 之前连击为 $j$ ，“强判定效果”持续到 $k$ ，打完 $[i,n]$ 后的期望得分 转移的时候用二进制枚举子集来枚举一下每个技能是否触发，然后算出这种情况发生的概率，乘上这种情况的得分，加起来。 时间复杂度：$O(\mathrm{n^3*2^{score+judge}*(score+judge)})$ 期望得分：$15$~$25$ 分 ### 算法五（数据分治） ~~使用数据分治结合算法三和算法四，可以获得更高的分数。~~ 因为用算法四前 $5$ 个点会爆空间，所以当 $n>50$ 时就用算法三 时间复杂度：$O(\mathrm{n>50?score*n:n^3*2^{score+judge}*(score+judge)})$ 期望得分：$40$~$50$ 分 ### 算法六（dew惨遭ouuan卡掉的dp） 用 $f[i][j][k]$ 表示打 $i$ 之前连击为 $j$ ，“强判定效果”剩余持续时间为 $k$ ，打完 $[i,n]$ 后的期望得分 这样第三维的大小就从 $O(n)$ 变成了 $O(maxt)$，时间复杂度也相应减少。 除此之外每次枚举子集之前可以先处理出哪些改判技能满足连击数为 $c$ 的倍数，只用枚举这些技能就好了。而加分技能用算法三的方法来处理。 然而这样做会被第 $15$ 和/或第 $16$ 个点卡掉。 最坏情况时间复杂度：$O(\mathrm{n^2*maxt*(judge*2^{judge}+score)})$ 期望得分：$70$~$75$ 分 ### 算法七（在dew的启发下ouuan~~最终~~想出的dp） 还是用 $f[i][j][k]$ 表示打 $i$ 之前连击为 $j$ ，“强判定效果”剩余持续时间为 $k$ ，打完 $[i,n]$ 后的期望得分。 注意到每次枚举子集得到的结果只跟连击数有关，所以可以预处理出不同连击数的期望加分和改判不同次数的概率。 时间复杂度：$O(\mathrm{n*score+n*judge*2^{judge}+n^2*maxt^2})$ 期望得分：$80$ 分 ### 算法八（wjyyyjulao的优化） 就在比赛前一天，wjyyy突然提出了一种优化...本来我是本着μ's只有9个人的原则不想增强数据的..后来想着不增强的话太水了估计有一堆AK..~~反正学园偶像又不只是μ's~~ （赛后补充：打脸，一个30+都没有） （赛后后补充：还是有两位julao赛后20分钟内AC了Orz） 思路其实很简单，就是把改判技能按 $t$ 降序排序，然后前面的改判发动了后面的改判就没用了，所以 $\mathrm{judge*2^{judge}}$ 都被优化成了 $\mathrm{judge}$. 然后就可以愉快地过掉最后 $20$ 分了。 而且算法四加了这个优化就稳 $25$ 了，算法六加了这个优化就稳 $80$ 了。 时间复杂度：$O(\mathrm{n*score+n*judge+n^2*maxt^2})$ 期望得分：$100$ 分 ### [~~算法九~~](https://www.luogu.org/blog/20782/SolutionT3) ### 标程 ``` #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N=1005; const int T=6; const int S=1005; const int J=1005; struct Judge { int c,p,t; bool operator<(Judge& b) { return t>b.t; } } jud[J]; int n,a[N],sco[S][3],score,judge; double f[N][N][T],scor[N],judg[N][T]; int main() { int i,j,k,l,maxt=0; double pos; cin>>n>>score>>judge; for (i=0;i<score;++i) { cin>>sco[i][0]>>sco[i][1]>>sco[i][2]; } for (i=0;i<judge;++i) { cin>>jud[i].c>>jud[i].p>>jud[i].t; maxt=max(maxt,jud[i].t); } sort(jud,jud+judge); //把改判技能按t排序 for (i=0;i<n;++i) //枚举击打前连击为i次（也就是打完后连击是i+1次） { scor[i]=2.0*(i+2); //得分 for (j=0;j<score;++j) { if ((i+1)%sco[j][0]==0) { scor[i]+=sco[j][1]*sco[j][2]/100.0; //期望加分 } } pos=1.0; for (j=0;j<judge;++j) //按序枚举改判技能 { if ((i+1)%jud[j].c==0) { judg[i][jud[j].t]+=jud[j].p/100.0*pos; //若发动则这次改判一定持续当前枚举的t pos*=1.0-jud[j].p/100.0; //不发动的概率 } } judg[i][0]=pos; //一次都不发动 } for (i=1;i<=n;++i) { cin>>a[i]; } for (i=n;i>=1;--i) { for (j=0;j<i;++j) { for (k=0;k<=maxt;++k) { if (a[i]==0) { f[i][j][k]=f[i+1][0][max(0,k-1)]; //若a[i]=0则下次连击必定为0，改判持续时间为max(0,k-1) } else if (a[i]==2||k>0) { f[i][j][k]=scor[j]; //得分+期望加分 for (l=0;l<=maxt;++l) { f[i][j][k]+=f[i+1][j+1][max(l,k-1)]*judg[j][l]; //用改判不同次数进行转移 } } else { f[i][j][k]=f[i+1][0][max(0,k-1)]+1.0; //与a[i]=0的不同在于还能得1分 } } } } printf("%.6lf",f[1][0][0]); return 0; } ``` ## Bonus  ~~看！dew就是欧皇！实锤了！~~ 最后祝大家天天出~~U~~R，次次肝前排！（然而我已经是半退坑咸鱼了Orz） $\color{Orange}μ's\color{Lavender}ic\ \color{RoyalBlue}f\color{OrangeRed}o\color{Gold}r\color{LimeGreen}e\color{Magenta}v\color{BlueViolet}e\color{Cyan}r\color{Black}!$ P.S.如果有需要部分分参考程序的直接在本篇博客下评论（可能会咕咕咕） P.P.S.蒟蒻国服sifid771824315，如比赛中所说真的几乎退坑了，偶尔玩一下QAQ ### T2 算法二 ``` #include <iostream> #include <algorithm> using namespace std; int n,m,c,d,a[200010],f[200010][50],p[200010][50],ans[50]; int main() { int i,j,s; cin>>n>>m>>c>>d; s=n*c+m; for (i=1;i<=s;++i) { cin>>a[i]; } for (i=1;i<=s;++i) { for (j=0;j<=i/c;++j) { if (i>c&&j>0) { if (f[i-1][j]+a[i]<f[i-c][j-1]+a[i-c+1]) { p[i][j]=i-c; f[i][j]=f[i-c][j-1]+a[i-c+1]; } else { p[i][j]=i-1; f[i][j]=f[i-1][j]+a[i]; } } else { f[i][j]=f[i-1][j]+a[i]; p[i][j]=i-1; } } } cout<<f[s][n]<<endl; i=s; j=n; while (j>0) { if (i-p[i][j]==1) { --i; } else { ans[j]=p[i][j]+1; i=p[i][j--]; } } for (i=1;i<=n;++i) { cout<<ans[i]<<' '; } return 0; } ``` ### T2 算法三 ``` #include <iostream> using namespace std; const int N=45,M=100005,C=10005; const int S=N*C+M; int n,m,c,d,s,a[S],b[S],f[S][N],p[S][N],sum,ans[N],anss,ansi; int main() { int i,j,k; cin>>n>>m>>c>>d; s=n*c+m; for (i=1;i<=s;++i) { cin>>a[i]; sum+=a[i]; } for (i=2;i<=c;++i) { b[1]+=a[i]; } for (i=2;i<=s-c+1;++i) { b[i]=b[i-1]-a[i]+a[i+c-1]; } for (i=1;i<=s-c+1;++i) { if (i<=c) { f[i][1]=b[i]; } else { for (j=(i+c-2)/(c+d)+1;j<=(i+c-1)/c&&j<=n;++j) { if (j>1) { f[i][j]=0x7fffffff; for (k=max(i-c-d,1);k<=i-c;++k) { if ((k+c-2)/(c+d)+1<=j-1&&(k+c-1)/c>=j-1) { if (f[i][j]>f[k][j-1]+b[i]) { f[i][j]=f[k][j-1]+b[i]; p[i][j]=k; } } } } else { f[i][j]=b[i]; } if (i>=s-c+1-d&&j==n&&anss<sum-f[i][j]) { anss=sum-f[i][j]; ansi=i; } } } } cout<<anss<<endl; for (j=n;j>=1;--j) { ans[j]=ansi; ansi=p[ansi][j]; } for (j=1;j<=n;++j) { cout<<ans[j]<<' '; } return 0; } ```