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

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

题图&文字来源:蔚蓝档案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的运行逻辑如下。

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

有且只有一个存档位aa,初始为空。

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

  1. 阅读节点ii:花费viv_i秒,跳转到一个与ii相连的节点(不能为faifa_i)。
  2. 存档:仅当aa为空时,将ii赋给aa
  3. 读档:仅当aa不为空时,跳转至编号为aa的节点。
  4. 重开:跳转至编号为11的节点,并清空aa

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

输入格式

第一行一个整数nn表示点的个数。

第二行n1n-1个整数faifa_i(ii从2开始)表示点ii的父亲。

第三行nn个整数viv_i表示阅读点ii需要花费的秒数。

输出格式

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

样例1

输入
1
2
3
7
1 1 2 2 4 4
5 10 4 3 8 1 1
输出
1
55

一种可能最短时间方案: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
57460

数据范围

1n1051\le n \le 10^5

1vi1041\le v_i \le 10^4

Hint

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

1
2
3
4
5
6
7
8
9
10
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);//并输出
}

题解

  1. 在不存档的情况下,花费时间ansans就是所有叶子节点到根节点的距离和(设一个点ii到根节点的距离为b[i]b[i])。

  2. 考虑存档对答案的影响,如果存档的是ii,ii为根的子树有leafcnt[i]leafcnt[i]个叶子节点,则ansans减少了(leafcnt[i]1)(b[fa[i]])(leafcnt[i]-1)*(b[fa[i]])

  3. 考虑存档之间的影响,不难发现两个存档不可以同时在一个叶子节点到根节点的路径上。

  4. dp[i]dp[i]为存档点已经在以ii为根节点的子树用掉时,ansans减少的最大值。

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

递归过程中计算dpdp即可

std代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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角色的期望抽卡次数ansans相比,看看自己脸到底有多黑。

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

题目描述

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

抽一次出SSR角色的概率是p1p_1。如果抽了nn次还没有出SSR角色,则接下来每次抽卡时概率将会提升p2p_2(提升可以累积),直到抽出SSR(概率大于等于1视为一定抽出SSR),抽出SSR后出SSR角色的概率重回p1p_1

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

输入格式

一行用空格分开的三个数p1,n,p2p_1,n,p_2。其中p1p_1p2p_2是保留小数点后三位的小数,nn是整数。

输出格式

一行一个保留小数点后六位的小数ansans

你的答案ans1ans_1被认为和正确答案ansans是一致的,仅当ans1ansans104\frac{|ans_1-ans|}{ans}\le 10^{-4}

样例1

输入
1
0.02 50 0.02
输出
1
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
输出
1
62.297332

样例3

输入
1
0.007 299 1
输出
1
125.491217

数据范围

0p111n10000.001p210 \le p_1\le 1\\1\le n \le 1000\\0.001 \le p_2 \le 1

题解

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

法零:随机游走

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

法一:手动模拟

aia_i为连续抽ii次还不出SSR的概率,则我们的目标是1a0\frac 1 {a_0}有以下式子:

a0=a1=(1p1)a0a2=(1p1)a2an=(1p1)an1an+1=(1p1p2)anan+2=(1p12p2)an+1an+k=(1p1kp2)an+k1Until 1p1(k+1)p20\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

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

法二:继续化简

继续写上述式子

a0=a1=(1p1)a0a2=(1p1)a1=(1p1)2a0an=(1p1)an1=(1p1)na0an+1=(1p1p2)an=(1p1)n(1p1p2)a0an+2=(1p12p2)an+1=(1p1)n(1p1p2)(1p12p2)a0an+k=(1p1kp2)an+k1=(1p1)n()a0Until 1p1(k+1)p20\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

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

std代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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;
}

夏季大三角

题面

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

题目背景

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

image-20211216003830477

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

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

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

image-20211216003217970

世界将在7月20日终结

世界回归天空的日子

万物被天空侵染的日子

回归天空的日子

世界必须回归

世界的极限

世界的尽头

世界的终结

Alt text

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

题目描述

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

星等(英语:magnitude),为天文学术语,是指星体在天空中的相对亮度。在地球上看起来越明亮的星体,其视星等数值就越

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

image-20211216102840225
夏季大三角基形状示意图(颜色越深,星等越高,亮度越小;黑色表示没有星星)

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

image-20211216103705198
夏季大三角形状示意图(颜色越深,星等越高,亮度越小;黑色表示没有星星)

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

输入格式

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

22行到n+1n+1行有mm个由0099的整数字符构成的字符串。表示这一张星空照片。

输出格式

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

样例1

输入
1
2
3
4
5
6
5 5
88488
89998
88488
89998
88488
输出
1
8

样例2

输入
1
2
3
4
5
6
5 5
99559
99955
92295
29299
12999
输出
1
5

数据范围

1n,m2×1031\le n,m\le 2\times 10^3

题解

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

std代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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;
}