type
status
date
slug
summary
tags
category
icon
password
Last edited time
Apr 21, 2024 11:33 AM
AcWing第151场周赛题解
📝 主旨内容
缺勤人数
某班有 n 个学生。
上课前，老师对全班进行点名，并对出勤情况加以记录。
如果一个学生点名时到场，则记录为 1，缺勤则记录为 0。
给定全部记录，请你统计一共有多少个学生缺勤。
输入格式
第一行包含整数 n。
第二行包含 n 个用空格隔开的 0 或 1，表示所有学生的出勤情况。
输出格式
一个整数，表示缺勤学生数量。
数据范围
前 3 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤100。
输入样例：
输出样例：
题解：
直接遍历就好，签到题
序列数量
给定整数 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：
输出样例1：
输入样例2：
输出样例2：
输入样例3：
输出样例3：
题解：
说句实话，其实可以看输入输出去猜，是个组合数学的问题。但是要认真去推理的话还是挺难的。
因此答案是,减去时的一组解
下面是例题：
奶牛过马路
贝茜要通过一条宽度为 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。
输入样例：
输出样例：
题解：
计算几何的背景，但是只用到了简单的斜率比较。难点在分析
🤗 总结归纳
整体还是比较困难，签完到就下机了
📎 参考文章
- 作者:ziuch
- 链接:https://ziuch.com/article/AcWing-weekly-contest-151-solution
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。