2019ZJOIday1试题

2024年浙江省省队选拔赛——第一试。

overview

礼物(gift)

题目描述】小白的生日就要到了，小蓝决定送一件自己亲手做的手工艺品使自己的礼物与众不同。具体来说，小蓝已经通过某种方式制作出了一个p×q×r的木块（由pqr个单位小木块组成）。但由于小蓝手艺不精，现在这个木块中的有些单位小木块是有问题的(有裂缝、里面是空心等等)，这样的礼物小蓝是不可能直接送出去的。

于是小蓝决定在这个木块中再挖出一个a×a×b的子木块(即要求挖出的长方体木块存在两条长度相等的相邻边)，当然这个子木块中是不能包含有问题的单位小木块的。为了使这个木块上能包含更多的图案，小蓝希望从所有可行的方案中挑取4ab的值最大的方案。但小蓝光检测木块中哪些地方有问题就已经耗尽了体力，作为小蓝的好友，你能帮帮小蓝吗？

输入说明】每个输入文件中仅包含一个测试数据。

第一行包含三个由空格隔开的正整数，p,q,r。

接下来有pq行，每行包含r个字符，每个字符只可能是’p’(poor)或者’n’(nice)，表示该单位小木块有问题或者没问题。具体的说，第1+(yp+x-p)行的第z个字符描述的是坐标为(x,y,z)的小木块情况。(1<=x<=p,1<=y<=q,1<=z<=r)

输出说明】输出文件仅包含一个整数，表示最佳方案的4ab的值。样例输入】

pnnnnpnnnn

nppnppnnnp

nnnnpppnnp样例输出】

数据范围】对于100%的数据，0看电影(movie)

题目描述】到了难得的假期，小白班上组织大家去看电影。但由于假期里看电影的人太多，很难做到让全班看上同一场电影，最后大家在一个偏僻的小胡同里找到了一家电影院。但这家电影院分配座位的方式很特殊，具体方式如下：

1. 电影院的座位共有k个，并被标号为1…k，每个人买完票后会被随机指定一个座位，具体来说是从1…k中等可能的随机选取一个正整数，设其为l。

2. 如果编号l的座位是空位，则这个座位就分配给此人，否则将l加一，继续前面的步骤。

3. 如果在第二步中不存在编号l的座位，则该人只能站着看电影，即所谓的站票。

小白班上共有n人（包括小白自己），作为数学爱好者，小白想知道全班都能够有座位的概率是多少。

输入说明】输入文件第一行有且只有一个正整数t，表示测试数据的组数。

第2～t+1行，每行两个正整数n,k，用单个空格隔开，其含义同题目描述。

输出说明】输出文件共包含t行。

第i行应包含两个用空格隔开的整数a,b，表示输入文件中的第i组数据的答案为a/b。（注意，这里要求将答案化为既约分数）样例输入】

样例输出】

数据范围】对于20%的数据 n,k<=10

对于100%的数据 t<=50,n,k<=200

最小割(mincut)

题目描述】小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话：

对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t不在同一个部分中，则称这个划分是关于s,t的割。

对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而s,t的最小割指的是在关于s,t的割中容量最小的割”

现给定一张无向图，小白有若干个形如“图中有多少对点它们的最小割的容量不超过x呢”的疑问，小蓝虽然很想回答这些问题，但小蓝最近忙着挖木块，于是作为仍然是小蓝的好友，你又有任务了。

输入说明】输入文件第一行有且只有一个正整数t，表示测试数据的组数。

对于每组测试数据，第一行包含两个整数n,m，表示图的点数和边数。

下面m行，每行3个正整数u,v,c(1<=u,v<=n,0<=c<=106)，表示有一条权为c的无向边(u,v)

接下来一行，包含一个整数q，表示询问的个数。

下面q行，每行一个整数x，其含义同题目描述。

输出说明】对于每组测试数据，输出应包括q行，第i行表示第i个问题的答案。对于点对(p,q)和(q,p)，只统计一次（见样例）。样例输入】

样例输出】

数据范围】对于30%的数据 n<=40,m<=400,q<=10

对于100%的数据 t<=10,n<=150,m<=3000,q<=30，x在32位有符号整数类型范围内。

图中两个点之间可能有多条边。

2019ZJOIday1试题

2019模拟1试题

工程材料 2024年模拟试题1 1 1

2024年测量试题 1

其他用户还读了