比赛链接

官方讲解

这场简单，没考什么算法，感觉有点水。D是个分组01背包，01背包的一点小拓展，没写过的可以看看，这个分类以及这个题目本身都是很板的。E感觉就是排名放高了导致没人敢写，本质上是个找规律然后分类讨论。F是个数学算期望的题，纯数学，连取模都没用就用的浮点数。

---

A 小红进地下城

思路：

签到，比较一下两个串是否相同即可。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;string s1,s2;int main(){cin>>s1>>s2;puts((s1==s2)?"Yes":"No");return 0;
}

---

B 小红打怪

思路：

找到小红的位置，然后往她面对的方向走，看有几个怪就行了，很签到。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1005;int n,m;
char mp[maxn][maxn];
int fx[]={-1,1,0,0},fy[]={0,0,-1,1};int sx,sy,st;int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>mp[i]+1;for(int j=1;j<=m;j++)if(mp[i][j]>='A' && mp[i][j]<='Z'){sx=i;sy=j;if(mp[i][j]=='W')st=0;else if(mp[i][j]=='S')st=1;else if(mp[i][j]=='A')st=2;else if(mp[i][j]=='D')st=3;}}int x=sx,y=sy,ans=0;do{
//		printf("(%d,%d)\n",x,y);ans+=(mp[x][y]=='*');x+=fx[st];y+=fy[st];}while(x>=1 && x<=n && y>=1 && y<=m);cout<<ans<<endl;return 0;
}

---

C 小红的排列构造

思路：

对第 $i$ 个位置，$a_i$ 一定是由 $p_i$ 或 $q_i$ 给出，除此之外就没有什么限制了。

所以我们可以提出一个很简单的构造方法：先让 $p$ 序列这个位置凑出 $a_i$，如果 $p$ 序列没有这个数了（已经凑给其他位置了），那我们就让 $q$ 序列去凑，如果都没有就无解。否则我们就得到了已经凑出了一部分的 $p$ 和 $q$。剩下的数没有限制，就依次补在空缺的位置上即可。

在一个序列剩余的数中查找还有没有某个数，并在给出这个数后把这个数删掉。我们可以用 $set$ 来模拟这个过程，这题本质是个数据结构题。

code：

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int maxn=1e5+5;int n,a[maxn];
int p[maxn],q[maxn];
set<int> s1,s2;int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];s1.insert(i);s2.insert(i);}for(int i=1;i<=n;i++){if(s1.find(a[i])!=s1.end()){p[i]=a[i];s1.erase(a[i]);}else if(s2.find(a[i])!=s2.end()){q[i]=a[i];s2.erase(a[i]);}else {cout<<-1;return 0;}}for(int i=1,x;i<=n;i++){if(p[i])x=p[i];else {x=*s1.begin();s1.erase(s1.begin());}cout<<x<<" \n"[i==n];}for(int i=1,x;i<=n;i++){if(q[i])x=q[i];else {x=*s2.begin();s2.erase(s2.begin());}cout<<x<<" \n"[i==n];}return 0;
}

---

D 小红升装备

思路：

换个思路，我们把一件武器看成是一组物品，这组物品包含：不购买它，购买它，购买它并升若干级的所有情况的武器，这样就变成了分组背包问题（有 $N$ 组，每一组你至多选择一个物品(也可以不选),每个物品都有自己的体积和价值，现在给你一个容里为 $M$ 的背包，让你用这个背包装物品，使得物品价值总和最大）

但是一把武器你有可能升很多级，导致这把武器可能有很多种情况，但是发现我们的钱是有限的，只有 $300$，每升一级还至少要花一块钱，因此我们最多只用升 $300$ 级，多了也没用，反正也买不起。这样我们枚举一组之内的武器时，只枚举到能买得起的武器等级就行了。

剩下就是分组背包，很板。

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=305;int n,x;
ll dp[maxn][maxn];int main(){cin>>n>>x;for(int i=1,a1,c1,c2,a2,mx;i<=n;i++){cin>>a1>>c1>>c2>>a2>>mx;for(int j=0;j<=x;j++)dp[i][j]=dp[i-1][j];for(int j=0,cst,val;j<=mx && c1+j*c2<=x;j++){cst=c1+j*c2;val=a1+j*a2;for(int k=cst;k<=x;k++)dp[i][k]=max(dp[i][k],dp[i-1][k-cst]+val);}}ll ans=0;for(int i=0;i<=x;i++)ans=max(ans,dp[n][i]);cout<<ans;return 0;
}

---

E 小红的矩阵划分

思路：

注意题面上 $n$ 为偶数的条件。

不难想到，如果两种类型的砖都能填满矩阵的话，我们肯定用砖的平均价值最大的类型来填，这样总数是确定的，总价值就是最大的。

不过并不一定两种类型的砖都能填满矩阵。由于 $n$ 是偶数的条件，$2\ast 2$ 的砖一定可以填满，但是 $L$ 型的不一定。

进一步研究发现， 当 $n$ 为 $6$ 的倍数的时候，一定可以用 $L$ 型砖块填满。一种可行的策略如下：我们用两个 $L$ 型砖块合成一个 $2\ast 3$ 矩形形状的方块，它又可以组合成 $6\ast 6$ 形状的方块，因此一定可以填满 $n$ 为 $6$ 的倍数的情况。

当 $n$ 不为 $6$ 的倍数的时候，我们可以参考上面的填充方式，把整个方阵拆分成一个最大的边长为 $6$ 的倍数的方阵和两个长为 $6$ 的倍数的矩形，以及一个小方阵。如下图（1为边长为 $6$ 的倍数的方阵，23为长为 $6$ 的倍数的矩形，4为小方阵）

我们还是用两个 $L$ 型砖块合成一个 $2\ast 3$ 矩形形状的砖块来对上面的图形进行填充。因为 $n$ 为偶数，而且还不是 $6$ 的倍数，所以 23 的宽，以及 4 的边长要么是 $2$，要么是 $4$。123很明显可以 $2\ast 3$ 的矩形来填充。然后剩下一个 $2\ast 2$ 或者 $4\ast 4$ 的小方阵。

如果只用 $L$ 型砖块来填充，一定会剩下一个格子。我们可以选择把一个 $L$ 型砖块替换成 $2\ast 2$ 型砖块来利用上这个空闲的格子，不过如果 $L$ 型砖块价值很高的话，这里也可能不替换会更优。

所以可能出现的情况我们已经全部讨论出来了。总结如下：

1. 当 $n$ 为 $6$ 的倍数的时候，有两种选择：
   1. 用 $L$ 型砖块填充满。
   2. 用 $2\ast 2$ 型砖块填充满。
2. 当 $n$ 不为 $6$ 的倍数的时候，有三种选择：
   1. 用 $L$ 型砖块填充满，这时剩一个空闲格子。
   2. 用 $2\ast 2$ 型砖块填充满。
   3. 用 $L$ 型砖块填充满，再把一个 $L$ 型砖块替换成 $2\ast 2$ 型砖块。

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;ll n,x,y;int main(){cin>>n>>x>>y;if(n%3==0)cout<<max(n*n/3*x,n*n/4*y);else cout<<max(max(n*n/3*x,n*n/3*x-x+y),n*n/4*y);return 0;
} 

---

F 小红拿宝箱

思路：

发现只取两个宝箱，而且只有一次不取的机会。情况很小，所以我们可以直接人力分情况讨论，分别计算期望。

我们取宝箱只有三种情况，

1. 不取，取，取
2. 取，不取 取
3. 取，取

当只取一个宝箱的时候，使不使用不取的权利的时机还是比较好确定的，就是高于期望就取，否则就不取，重新抽卡。但是还能取两个宝箱的时候就不好说了。所以我们第一步是否取宝箱先分类讨论。分成不取和取的情况，如果不取，那么后面就只能随便取两个宝箱了，不能不取。如果取，那么后面可以取，也可以不取然后再取。

这样情况讨论就变成了：

1. 不取
   1. 取，取
2. 取
   1. 不取 取
   2. 取

---

先讨论第一步取了，现在我们不使用不取宝箱的权利（或者说我们已经用完了不取宝箱的权利），随便取两个宝箱的话，期望计算：

在 $n$ 个数中随便取两个的方法数为 $C_n^2$，每个取法平分取到的概率，因此一种取法的概率就是 $\frac{1}{C_n^2}$。计算每个取法的价值比较困难，但是所有取法的价值总和可以算。我们计算期望的时候可以先把概率提公因式，然后先计算所有取法的价值总和。

如果我们钦定第一个数取了 $a_1$，另一个数可以取剩下的 $n-1$ 个数，这样第一个数取 $a_1$ 的所有取法之和就为 $su{m}_1=(n-1)\ast a_1+(a_2+a_3+\cdots +a_n)$，假设所有数之和 $tot={\sum }_{i=1}^n{a}_i$，那么式子可以写为：$su{m}_1=(n-2)\ast a_1+tot$，同理其他数作为第一个数，所以可以得到所有取法的总和 $sum={\sum }_{i=1}^{n}su{m}_i=(n-2)\ast (a_1+a_2+\cdots +a_n)+n\ast tot=2\ast (n-1)\ast tot$。

因为我们计算的时候为了方便是钦定了取数顺序的，但是实际上取数是没有顺序的，因此我们要消除排序的影响，对一种可行的方案，我们由于有顺序，所以得到的所有方案相当于对原本的取数方案进行了一次全排列，一个方案分裂成了全排列个数个方案。比如这里的 $a_1,a_3$ 的一个取数方案就变成 $a_1,a_3$ 和 $a_3,a_1$ 一共 $A_2^2$ 个方案。因此我们对整个方案除以一个 $A_2^2=2$ 就可以消除掉排序的影响了。因此总的取法之和就是 $sum=(n-1)\ast tot$。于是期望就是 $\frac{(n-1)\ast tot}{C_n^2}=tot/n\ast 2$。

---

如果第一步取了，假设取了 $a_i$，现在随机取一个宝箱的期望就是 $\frac{tot-a_i}{n-1}$。如果我们下一步取到的宝箱价值大于等于期望，就取它，否则如果小于期望，就重新随机抽取。为了快速算出有多少宝箱的价值大于期望，我们可以给宝箱价值从小到大排个序，然后二分查找第一个大于等于期望的位置，这样后面的宝箱价值都大于等于期望，前面的都小。

假设第 $id$ 个宝箱就是第一个大于等于期望的位置。那么后面 $id$ 个宝箱不重抽，每个的期望是 $\frac{a_j}{n-1}(j\ge id)$，前 $id-1$ 个宝箱要重新抽取，每个的期望就是 $\frac{\frac{tot-a_i}{n-1}}{n-1}$，不过需要注意的是，两种情况中有一个会包含进 $a_i$ ，判断一下然后减去即可。期望之和就是 $\frac{1}{n-1}\ast ({\sum }_{j=id}^n{a}_j+(id-1)\ast \frac{tot-a_i}{n-1}-(i\ge id?a_i:\frac{tot-a_i}{n-1}))$。这里 ${\sum }_{j=id}^n{a}_j$ 可以预处理后缀和来快速查询。

---

上面两个讨论分别代表了取与不取第一个数的后续的期望，我们两个总的期望取大的即可。

注意特判 $n=1$ 的情况。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;int n;
double a[maxn],suf[maxn],tot;int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i],tot+=a[i];if(n==1)return cout<<tot,0;sort(a+1,a+n+1);for(int i=n;i>=1;i--)suf[i]=suf[i+1]+a[i];double s1=tot/n*2;//任取两个的期望 double ans=0;for(int i=1;i<=n;i++){double s2=(tot-a[i])/(n-1);//拿走ai后任取一个的期望 int id=lower_bound(a+1,a+n+1,s2)-a;double tmp=suf[id]+(id-1)*s2;//分子部分 if(a[i]>=s2)tmp-=a[i];else tmp-=s2;tmp/=n-1;ans+=max(s1,tmp+a[i]);}printf("%.11lf\n",ans/n);return 0;
}