比赛链接
官方讲解
这场简单，没考什么算法，感觉有点水。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 i i 个位置， a i a_i ai 一定是由 p i p_i pi 或 q i q_i qi 给出，除此之外就没有什么限制了。
所以我们可以提出一个很简单的构造方法：先让 p p p 序列这个位置凑出 a i a_i ai，如果 p p p 序列没有这个数了（已经凑给其他位置了），那我们就让 q q q 序列去凑，如果都没有就无解。否则我们就得到了已经凑出了一部分的 p p p 和 q q q。剩下的数没有限制，就依次补在空缺的位置上即可。
在一个序列剩余的数中查找还有没有某个数，并在给出这个数后把这个数删掉。我们可以用 s e t set 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 N N 组，每一组你至多选择一个物品(也可以不选),每个物品都有自己的体积和价值，现在给你一个容里为 M M M 的背包，让你用这个背包装物品，使得物品价值总和最大）
但是一把武器你有可能升很多级，导致这把武器可能有很多种情况，但是发现我们的钱是有限的，只有 300 300 300，每升一级还至少要花一块钱，因此我们最多只用升 300 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 n 为偶数的条件。
不难想到，如果两种类型的砖都能填满矩阵的话，我们肯定用砖的平均价值最大的类型来填，这样总数是确定的，总价值就是最大的。
不过并不一定两种类型的砖都能填满矩阵。由于 n n n 是偶数的条件， 2 ∗ 2 2*2 2∗2 的砖一定可以填满，但是 L L L 型的不一定。
进一步研究发现， 当 n n n 为 6 6 6 的倍数的时候，一定可以用 L L L 型砖块填满。一种可行的策略如下：我们用两个 L L L 型砖块合成一个 2 ∗ 3 2*3 2∗3 矩形形状的方块，它又可以组合成 6 ∗ 6 6*6 6∗6 形状的方块，因此一定可以填满 n n n 为 6 6 6 的倍数的情况。
当 n n n 不为 6 6 6 的倍数的时候，我们可以参考上面的填充方式，把整个方阵拆分成一个最大的边长为 6 6 6 的倍数的方阵和两个长为 6 6 6 的倍数的矩形，以及一个小方阵。如下图（1为边长为 6 6 6 的倍数的方阵，23为长为 6 6 6 的倍数的矩形，4为小方阵）
我们还是用两个
L
L
L 型砖块合成一个
2
∗
3
2*3
2∗3 矩形形状的砖块来对上面的图形进行填充。因为
n
n
n 为偶数，而且还不是
6
6
6 的倍数，所以 23 的宽，以及 4 的边长要么是
2
2
2，要么是
4
4
4。123很明显可以
2
∗
3
2*3
2∗3 的矩形来填充。然后剩下一个
2
∗
2
2*2
2∗2 或者
4
∗
4
4*4
4∗4 的小方阵。
如果只用 L L L 型砖块来填充，一定会剩下一个格子。我们可以选择把一个 L L L 型砖块替换成 2 ∗ 2 2*2 2∗2 型砖块来利用上这个空闲的格子，不过如果 L L L 型砖块价值很高的话，这里也可能不替换会更优。
所以可能出现的情况我们已经全部讨论出来了。总结如下：
- 当
n
n
n 为
6
6
6 的倍数的时候，有两种选择：
- 用 L L L 型砖块填充满。
- 用 2 ∗ 2 2*2 2∗2 型砖块填充满。
- 当
n
n
n 不为
6
6
6 的倍数的时候，有三种选择：
- 用 L L L 型砖块填充满，这时剩一个空闲格子。
- 用 2 ∗ 2 2*2 2∗2 型砖块填充满。
- 用 L L L 型砖块填充满，再把一个 L L L 型砖块替换成 2 ∗ 2 2*2 2∗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 小红拿宝箱
思路：
发现只取两个宝箱，而且只有一次不取的机会。情况很小，所以我们可以直接人力分情况讨论，分别计算期望。
我们取宝箱只有三种情况，
- 不取，取，取
- 取，不取 取
- 取，取
当只取一个宝箱的时候，使不使用不取的权利的时机还是比较好确定的，就是高于期望就取，否则就不取，重新抽卡。但是还能取两个宝箱的时候就不好说了。所以我们第一步是否取宝箱先分类讨论。分成不取和取的情况，如果不取，那么后面就只能随便取两个宝箱了，不能不取。如果取，那么后面可以取，也可以不取然后再取。
这样情况讨论就变成了：
- 不取
- 取，取
- 取
- 不取 取
- 取
先讨论第一步取了，现在我们不使用不取宝箱的权利（或者说我们已经用完了不取宝箱的权利），随便取两个宝箱的话，期望计算：
在 n n n 个数中随便取两个的方法数为 C n 2 C_n^2 Cn2，每个取法平分取到的概率，因此一种取法的概率就是 1 C n 2 \dfrac1{C_n^2} Cn21。计算每个取法的价值比较困难，但是所有取法的价值总和可以算。我们计算期望的时候可以先把概率提公因式，然后先计算所有取法的价值总和。
如果我们钦定第一个数取了 a 1 a_1 a1，另一个数可以取剩下的 n − 1 n-1 n−1 个数，这样第一个数取 a 1 a_1 a1 的所有取法之和就为 s u m 1 = ( n − 1 ) ∗ a 1 + ( a 2 + a 3 + ⋯ + a n ) sum_1=(n-1)*a_1+(a_2+a_3+\dots+a_n) sum1=(n−1)∗a1+(a2+a3+⋯+an)，假设所有数之和 t o t = ∑ i = 1 n a i tot=\sum_{i=1}^{n}a_i tot=∑i=1nai，那么式子可以写为： s u m 1 = ( n − 2 ) ∗ a 1 + t o t sum_1=(n-2)*a_1+tot sum1=(n−2)∗a1+tot，同理其他数作为第一个数，所以可以得到所有取法的总和 s u m = ∑ i = 1 n s u m i = ( n − 2 ) ∗ ( a 1 + a 2 + ⋯ + a n ) + n ∗ t o t = 2 ∗ ( n − 1 ) ∗ t o t sum=\sum_{i=1}^n{sum_i}=(n-2)*(a_1+a_2+\dots+a_n)+n*tot=2*(n-1)*tot sum=∑i=1nsumi=(n−2)∗(a1+a2+⋯+an)+n∗tot=2∗(n−1)∗tot。
因为我们计算的时候为了方便是钦定了取数顺序的，但是实际上取数是没有顺序的，因此我们要消除排序的影响，对一种可行的方案，我们由于有顺序，所以得到的所有方案相当于对原本的取数方案进行了一次全排列，一个方案分裂成了全排列个数个方案。比如这里的 a 1 , a 3 a_1,a_3 a1,a3 的一个取数方案就变成 a 1 , a 3 a_1,a_3 a1,a3 和 a 3 , a 1 a_3,a_1 a3,a1 一共 A 2 2 A_2^2 A22 个方案。因此我们对整个方案除以一个 A 2 2 = 2 A_2^2=2 A22=2 就可以消除掉排序的影响了。因此总的取法之和就是 s u m = ( n − 1 ) ∗ t o t sum=(n-1)*tot sum=(n−1)∗tot。于是期望就是 ( n − 1 ) ∗ t o t C n 2 = t o t / n ∗ 2 \dfrac{(n-1)*tot}{C_n^2}=tot/n*2 Cn2(n−1)∗tot=tot/n∗2。
如果第一步取了，假设取了 a i a_i ai，现在随机取一个宝箱的期望就是 t o t − a i n − 1 \dfrac{tot-a_i}{n-1} n−1tot−ai。如果我们下一步取到的宝箱价值大于等于期望，就取它，否则如果小于期望，就重新随机抽取。为了快速算出有多少宝箱的价值大于期望，我们可以给宝箱价值从小到大排个序，然后二分查找第一个大于等于期望的位置，这样后面的宝箱价值都大于等于期望，前面的都小。
假设第 i d id id 个宝箱就是第一个大于等于期望的位置。那么后面 i d id id 个宝箱不重抽，每个的期望是 a j n − 1 ( j ≥ i d ) \dfrac{a_j}{n-1}\quad(j\ge id) n−1aj(j≥id)，前 i d − 1 id-1 id−1 个宝箱要重新抽取，每个的期望就是 t o t − a i n − 1 n − 1 \dfrac{\frac{tot-a_i}{n-1}}{n-1} n−1n−1tot−ai，不过需要注意的是，两种情况中有一个会包含进 a i a_i ai ，判断一下然后减去即可。期望之和就是 1 n − 1 ∗ ( ∑ j = i d n a j + ( i d − 1 ) ∗ t o t − a i n − 1 − ( i ≥ i d ? a i : t o t − a i n − 1 ) ) \dfrac{1}{n-1}*(\sum_{j=id}^{n}a_j+(id-1)*\frac{tot-a_i}{n-1}-(i\ge id\,?a_i:\frac{tot-a_i}{n-1})\,) n−11∗(∑j=idnaj+(id−1)∗n−1tot−ai−(i≥id?ai:n−1tot−ai))。这里 ∑ j = i d n a j \sum_{j=id}^{n}a_j ∑j=idnaj 可以预处理后缀和来快速查询。
上面两个讨论分别代表了取与不取第一个数的后续的期望，我们两个总的期望取大的即可。
注意特判 n = 1 n=1 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;
}
