2022新生赛题目&std数据&题解（鳖在这里发电，交叉坐标的星尘,无限梦境的概率理论,夏季大三角)

发表于 2023-03-04 更新于 2023-03-06 分类于题解本文字数： 8.3k 阅读时长 ≈ 8 分钟

大人的义务，就是帮学生们实现，他们的梦

题图&文字来源：蔚蓝档案Vol3 CG

Upd: 交叉坐标的星尘题面有修改

但是他是个强迫症，每次存档之后都会在重开前把所有能阅读到的节点都阅读完，而且这些节点都是存档前没被阅读过的

鳖在这里发电因为太水不在线呈现，其题目、数据、题解、std请下载压缩包查看。

许多人鳖在这里发电判断输入结束直接用的(xxx=getchar())!='\n'，输入没保证最后一个字符为'\n'。请使用gets或者getline等函数替代。

2022新生赛题目&std数据&题解（鳖在这里发电，交叉坐标的星尘,无限梦境的概率理论,夏季大三角）.zip

以下是在线版，如需数据请下载解压压缩包，数据就位于*/data/文件夹。

链接: https://pan.baidu.com/s/1jLzACeVc_1pXXbcckVV2ww?pwd=wwqp 提取码: wwqp

交叉坐标的星尘

题面

注：跳过题目背景不影响理解题意

题目背景

黄色的树林里分出两条路，

可惜我不能同时去涉足，

我在那路口久久伫立，

我向着一条路极目望去，

直到它消失在丛林深处。

但我却选了另外一条路，

它荒草萋萋，十分幽寂，

显得更诱人、更美丽，

虽然在这两条小路上，

都很少留下旅人的足迹，

虽然那天清晨落叶满地，

两条路都未经脚印污染。

呵，留下一条路等改日再见！

但我知道路径延绵无尽头，

恐怕我难以再回返。

也许多少年后在某个地方，

我将轻声叹息把往事回顾，

一片树林里分出两条路，

而我选了人迹更少的一条，

从此决定了我一生的道路。

题目描述

您想要速通一个galgame，经研究发现这个galgame的运行逻辑如下。

有 $n$ 个节点，编号1到n。除了1号节点每个节点有一条边连着另一个节点，表示它的父亲 $fa_i$ 。每个节点可以经过一些边到达任意一个其他节点。每一个节点 $i$ 有一个权值 $v_i$ 表示阅读该点需要花费的时间。换句话说这是一颗有根带点权的树。

有且只有一个存档位 $a$ ，初始为空。

您将从1号节点出发，设当前所在节点为 $i$ ，每次能进行下面四个操作中的一个

阅读节点 $i$ ：花费 $v_i$ 秒，跳转到一个与 $i$ 相连的节点（不能为 $fa_i$ ）。
存档：仅当 $a$ 为空时，将 $i$ 赋给 $a$ 。
读档：仅当 $a$ 不为空时，跳转至编号为 $a$ 的节点。
重开：跳转至编号为 $1$ 的节点，并清空 $a$ 。

只有1操作花费 $v_i$ 秒，其余操作均为瞬间完成，求阅读所有节点最少花费多少秒数。

输入格式

第一行一个整数 $n$ 表示点的个数。

第二行 $n-1$ 个整数 $fa_i$ ( $i$ 从2开始)表示点 $i$ 的父亲。

第三行 $n$ 个整数 $v_i$ 表示阅读点 $i$ 需要花费的秒数。

输出格式

一个整数表示花费时间的最小值。

样例1

输入

1
2
3

7
1 1 2 2 4 4
5 10 4 3 8 1 1

输出

一种可能最短时间方案：1-2-4-存档-6-读档(4)-7-重开(1)-2-5-重开(1)-3。共55秒。

样例2

输入

1
2
3

7
1 2 1 1 3 4
6436 2173 8477 4835 8653 5816 8198

输出

数据范围

$1\le n \le 10^5$

$1\le v_i \le 10^4$

Hint

您可能不会存图，这里推荐一种简单的方式存图(C++)：

vector<int> G[100];//能够存放编号为[0,100)的节点的数据结构
G[u].push_back(v);//添加一条u->v的边
G[u].size();//从u为起点的边的数量
for (int i=0;i<G[u].size();i++){
    int v=G[u][i];
    //遍历所有从u开始的边u->v(方式1)
}
for (auto v:G[u]){//遍历所有从u开始的边u->v(方式2)(需要在编译参数里添加-std=c++11,OJ上已添加)
    printf("%d\n",v);//并输出
}

题解

在不存档的情况下，花费时间 $ans$ 就是所有叶子节点到根节点的距离和(设一个点 $i$ 到根节点的距离为 $b[i]$ )。
考虑存档对答案的影响，如果存档的是 $i$ , $i$ 为根的子树有 $leafcnt[i]$ 个叶子节点，则 $ans$ 减少了 $(leafcnt[i]-1)*(b[fa[i]])$
考虑存档之间的影响，不难发现两个存档不可以同时在一个叶子节点到根节点的路径上。
设 $dp[i]$ 为存档点已经在以 $i$ 为根节点的子树用掉时， $ans$ 减少的最大值。

\text{dp}[u]=\max(\sum_{v \text{ is son of }u}\text{dp}[v],(\text{leafcnt}[u]-1)*\text{b}[\text{fa}[u]])

递归过程中计算 $dp$ 即可

std代码

#include <bits/stdc++.h>
using namespace std;
#define N (100000+10)
int n;
vector<int> G[N];
int a[N],b[N],leafcnt[N],v[N],fa[N];
long long ans;
void dfs0(int u){
  b[u]+=v[u];
  if (G[u].size()==0){
    ans+=b[u];
    leafcnt[u]=1;
  }
  for (auto v:G[u]){
    b[v]+=b[u];
    dfs0(v);
    leafcnt[u]+=leafcnt[v];
  }
}
int dfs1(int u){
  int t=0;
  for (auto v:G[u])
    t+=dfs1(v);
  return a[u]=max(t,(leafcnt[u]-1)*b[fa[u]]);
}
int main(){
  scanf("%d",&n);
  for (int i=2;i<=n;i++){
    scanf("%d",&fa[i]);
    G[fa[i]].push_back(i);
  }
  for (int i=1;i<=n;i++){
    scanf("%d",&v[i]);
  }
  dfs0(1);
  dfs1(1);
  cout << ans-a[1] << endl;
}

无限梦境的概率理论

题面

注：跳过题目背景不影响理解题意

题目背景

一个二次元手游的资深玩家抽了150发还没出SSR，这是他的大脑发生的变化。

NP是一个24岁的高三学生，在某天下午游戏刚更新后怎么都进不去服务器。遂决定先去陪朋友过生日，喝到了意识模糊、醉生梦死。爬回家打开了游戏以及美好的梦境OBS，寻找大群的呼唤。

emiya- meaning rabbit but not donkey,42- meaning 42 originites but not surtr,didi- meaning skadi but not weedy.

随后一觉醒来发现微信里只有几十块钱。但是好歹还是出SSR了。

为了平衡心理，NP调出了自己的抽卡记录，算出了自己平均多少抽出ssr，NP想跟理论上游戏抽卡出SSR角色的期望抽卡次数 $ans$ 相比，看看自己脸到底有多黑。

但是他数学不怎么好，于是求 $ans$ 的任务就交给你了。

题目描述

这个手游里的角色分为两种稀有度：SSR和其他。角色只能通过抽卡获取，一抽获得一个角色。这个手游的抽卡概率模型如下：

抽一次出SSR角色的概率是 $p_1$ 。如果抽了 $n$ 次还没有出SSR角色，则接下来每次抽卡时概率将会提升 $p_2$ （提升可以累积），直到抽出SSR（概率大于等于1视为一定抽出SSR），抽出SSR后出SSR角色的概率重回 $p_1$ 。

求这个游戏抽卡每出一个SSR角色的期望抽卡次数 $ans$ ，即 $\frac{1}{出SSR角色卡的概率}$ 。

输入格式

一行用空格分开的三个数 $p_1,n,p_2$ 。其中 $p_1$ 和 $p_2$ 是保留小数点后三位的小数， $n$ 是整数。

输出格式

一行一个保留小数点后六位的小数 $ans$ 。

你的答案 $ans_1$ 被认为和正确答案 $ans$ 是一致的，仅当 $\frac{|ans_1-ans|}{ans}\le 10^{-4}$ 。

样例1

输入

1	0.02 50 0.02

输出

34.594555

对于这组数据，假如持续50发没有出SSR，第51发出SSR的概率为0.04；如果到51发还没出SSR，第52发出SSR的概率为0.06；…；如果到99发还每出SSR，第100发概率为1，此时必定出SSR。

样例2

输入

1	0.006 73 0.06

输出

62.297332

样例3

输入

1	0.007 299 1

输出

1	125.491217

数据范围

$0 \le p_1\le 1\\1\le n \le 1000\\0.001 \le p_2 \le 1$

题解

灵感来自今年XCPC某道算点燃技能覆盖率的题。

法零：随机游走

循环个5e7次模拟抽卡，但是精度不够。

法一：手动模拟

设 $a_i$ 为连续抽 $i$ 次还不出SSR的概率，则我们的目标是 $\frac 1 {a_0}$ 有以下式子：

\begin{aligned} a_0& =\dots \\ a_1& =(1-p_1)a_0 \\ a_2& =(1-p_1)a_2 \\ \vdots \\ a_{n}& =(1-p_1)a_{n-1} \\ a_{n+1}& =(1-p_1-p_2)a_{n} \\ a_{n+2}& =(1-p_1-2p_2)a_{n+1} \\ \vdots \\ a_{n+k}& =(1-p_1-kp_2)a_{n+k-1} \\ \end{aligned} \\ \text{Until } 1-p_1-(k+1)p_2\le0

初始置 $a_0=1,a_i=0(i\not=0)$ ，不断计算上述式子迭代直到 $a_0$ 小于题目要求精度即可。

法二：继续化简

继续写上述式子

\begin{aligned} a_0& =\dots \\ a_1& =(1-p_1)a_0 \\ a_2& =(1-p_1)a_1=(1-p_1)^2a_0 \\ \vdots \\ a_{n}& =(1-p_1)a_{n-1}=(1-p_1)^na_0 \\ a_{n+1}& =(1-p_1-p_2)a_{n}=(1-p_1)^n(1-p_1-p_2)a_0 \\ a_{n+2}& =(1-p_1-2p_2)a_{n+1}=(1-p_1)^n(1-p_1-p_2)(1-p_1-2p_2)a_0 \\ \vdots \\ a_{n+k}& =(1-p_1-kp_2)a_{n+k-1}=(1-p_1)^n\prod(\dots)a_0 \\ \end{aligned} \\ \text{Until } 1-p_1-(k+1)p_2\le0

已知 $\sum_{i=0}^{n+k}{a_i}=1$ ，将上式最左边和最右边的等式全部加起来我们得到了 $1=ka_0$ 。此时 $k$ 就是我们的答案。

std代码

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;long double p1,p2;
  cin>>p1>>n>>p2;
  long double c=1,x=1,k=p2;
  int i=1;
  while (x>0&&i<=n){
    c+=x*=(1-p1);
    i++;
  }
  while (1-p1-k>0){
    c+=x*=(1-p1-k);
    k+=p2;
  }
  cout<<fixed<<setprecision(6)<<c<<endl;
}

夏季大三角

题面

注：跳过题目背景不影响理解题意

题目背景

欢迎大家光临天象馆，这里有着无论何时都决不会消失的，美丽无穷的光辉，满天的星星们正在等待着大家的到来。

“一直想跟你说声谢谢，我真的很感激你。”

“我应该更向你道谢，给那么多人带去星星和星星的故事，非常感谢你。”

“一切都有了回报，你的一句话，我的全部努力…来吧，开始投影吧。”

世界将在7月20日终结

世界回归天空的日子

万物被天空侵染的日子

回归天空的日子

世界必须回归

世界的极限

世界的尽头

世界的终结

Alt text

让我们一起出发，共同前往那个童话故事之后的世界吧——

题目描述

您得到了一副 $n\times m$ 的星空照片。照片中每一个像素点均为 $[0,9]$ 中的整数，其中⑨表示没有星星，非⑨值表示一颗星星的星等。

星等（英语：magnitude），为天文学术语，是指星体在天空中的相对亮度。在地球上看起来越明亮的星体，其视星等数值就越低。

如果其中存在一个 $2\times 2$ 的区域，其中只含有三颗星星，且他们星等均为 $a$ 。我们称其构成了一个星等为 $a$ 的夏季大三角基 $B$ 。


夏季大三角基形状示意图（颜色越深,星等越高,亮度越小；黑色表示没有星星）

对于一个星等为 $a$ 的夏季大三角基 $B$ ，其中没有星星的像素点会指示一个斜方向。如果斜方向上存在一个星等为 $\lfloor a/2\rfloor$ 的星星 $x$ 。那么我们称 $x$ 和 $B$ 构成了一个夏季大三角。


夏季大三角形状示意图（颜色越深,星等越高,亮度越小；黑色表示没有星星）

求星空照片中所有夏季大三角的数量。

输入格式

第一行用空格分开的两个整数 $n,m$ ，表示星空照片的长和宽。

第 $2$ 行到 $n+1$ 行有 $m$ 个由 $0$ 到 $9$ 的整数字符构成的字符串。表示这一张星空照片。

输出格式

一个整数，表示星空照片中所有夏季大三角的数量。

样例1

输入

输出

样例2

输入

输出

数据范围

$1\le n,m\le 2\times 10^3$

题解

对于四个方向中的每一个方向，记录其方向上星等为 $x$ 的前缀和。检查星等为 $k$ 的夏季大三角基，答案累加上对应位置星等为 $\lfloor k/2 \rfloor$ 前缀和即可。

std代码

#include <bits/stdc++.h>
using namespace std;
int n,m;
int G[3000][3000];
int A[4][3000][3000][5];
int p1[4]={1,1,-1,-1};
int p2[4]={1,-1,1,-1};
#define inN(x) (0<=(x)&&(x)<n)
#define inM(x) (0<=(x)&&(x)<m)
int gc(){
	char c;
	while (!isdigit(c=cin.get()));
	return c-'0';
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			G[i][j]=gc();
	for (int mi=0;mi<4;mi++){
		for (int i=p1[mi]==-1?0:n-1;inN(i);i-=p1[mi])
			for (int j=p2[mi]==-1?0:m-1;inM(j);j-=p2[mi])
				for (int k=0;k<=4;k++){
					int pi=i+p1[mi],pj=j+p2[mi];
					A[mi][i][j][k]+=(inN(pi)&&inM(pj)?A[mi][pi][pj][k]:0)+
									(k==G[i][j]?1:0);
				}
	}
	long long ans=0;
	for (int mi=0;mi<4;mi++)
		for (int i=p1[mi]==-1?0:n-1;i<n&&i>=0;i-=p1[mi])
			for (int j=p2[mi]==-1?0:m-1;j<m&&j>=0;j-=p2[mi]){
				if (inN(i+2*p1[mi])&&inM(j+2*p2[mi])){
					if (G[i][j]==G[i+p1[mi]][j]&&
						G[i][j]==G[i][j+p2[mi]]&&
						G[i+p1[mi]][j+p2[mi]]==9&&
						G[i][j]!=9)
						ans+=A[mi][i+2*p1[mi]][j+2*p2[mi]][G[i][j]/2];
				}
			}
	cout << ans << endl;
}