AcWing第151场周赛题解

type

status

date

slug

summary

📝 主旨内容

缺勤人数

某班有 n 个学生。

上课前，老师对全班进行点名，并对出勤情况加以记录。

如果一个学生点名时到场，则记录为 1，缺勤则记录为 0。

给定全部记录，请你统计一共有多少个学生缺勤。

输入格式

第一行包含整数 n。

第二行包含 n 个用空格隔开的 0 或 1，表示所有学生的出勤情况。

输出格式

一个整数，表示缺勤学生数量。

数据范围

前 3 个测试点满足 1≤n≤10。

所有测试点满足 1≤n≤100。

输入样例：


5
1 1 0 1 0

输出样例：

题解：

💡

直接遍历就好，签到题


n = int(input())
res = n - sum([x for x in map(int, input().split())])
print(res)

序列数量

给定整数 n,m。

请你计算，一共有多少个长度为 m 的非负整数序列 a1,a2,…,am 满足 1≤a1+a2+…+am≤n。

由于结果可能很大，你只需要输出对 10^6+3 取模后的结果。

输入格式

共一行，包含两个整数 n,。

输出格式

一个整数，表示满足条件的非负整数序列数量对 10^6+3 取模后的结果。

数据范围

前 3 个测试点满足 1≤n,m≤5。

所有测试点满足 1≤n≤5×10^5, 1≤m≤2×10^5。

输入样例1：

5 1

输出样例1：

输入样例2：

2 2

输出样例2：

输入样例3：

3 2

输出样例3：

题解：

💡

说句实话，其实可以看输入输出去猜，是个组合数学的问题。但是要认真去推理的话还是挺难的。

因此答案是 $C_{n+m}^m$ ,减去 $a_{m+1}=n$ 时的一组解

下面是例题：


MOD = 10 ** 6 + 3

def C(n, m):
  res = 1
  for i, j in zip(range(n, -1, -1), range(1, m + 1)):
    res = res * i * pow(j, MOD - 2, MOD) % MOD # 乘法逆元
  return res

n, m = map(int, input().split())
print((C(n + m, m) - 1 + MOD) % MOD)

奶牛过马路

贝茜要通过一条宽度为 w 的无限长度的水平马路。

不妨假设马路在一个二维平面中，马路的一端为直线 y=0，另一端为直线 y=w。

马路中有一条垂直的人行横道，恰好是连接 (0,0) 和 (0,w) 的线段。

贝茜当前位于人行横道的一端 ---- (0,0) 位置处。

它要沿着人行横道到达马路对面的 (0,w) 位置处。

贝茜只能以不超过 u（单位长度/秒）的速度沿任意方向在人行横道上进行移动。

移动过程中贝茜可以随时改变自己的移动速度，甚至于停下。

马路中有一辆车正在以恒定速度 v（单位长度/秒）向 x 轴反方向（x 坐标递减的方向）移动。

该车可以视作一个 n 个顶点的凸多边形。

如果某一时刻，贝茜所在位置严格位于车凸多边形内（凸多边形的顶点和边不算内部），则意味着它被车撞了。

给定车当前的位置，请你计算贝茜在不被车撞的前提下，成功穿过马路到达点 (0,w) 所需要的最短时间（单位：秒）。

输入格式

第一行包含四个整数 n,w,v,u。

接下来 n 行，按照逆时针的顺序，每行输出一个凸多边形的顶点坐标 (xi,yi)。

保证输入凸多边形是非退化的。

输出格式

输出一个实数 t，表示最短时间。

输出结果与标准答案的绝对或相对误差不超过 10^−6 即视为正确。

数据范围

前 3 个测试点满足 3≤n≤5。

所有测试点满足 3≤n≤10000，1≤w≤10^9，1≤v,u≤1000，−109≤xi≤109，0≤yi≤w。

输入样例：

输出样例：


5.0000000000

题解：

💡

计算几何的背景，但是只用到了简单的斜率比较。难点在分析


n, w, v, u = map(int, input().split())
k, b = u / v, 0
cow_slow, cow_fast = True, True
for _ in range(n):
  x, y = rl()
  if y < k * x: cow_slow = False
  elif y > k * x: cow_fast = False
  b = min(b, y - k * x)

if cow_slow or cow_fast: 
	print(w / u)
else: 
	print((w - b) / u)