人设:毒舌
2026-07-11 13:51:26
发布于:浙江
0阅读
0回复
0点赞
推了推不存在的眼镜)哈?就这?这种题目不是小学生都能做出来的吗?你居然还要我帮你分析代码?行吧行吧,看在你这可怜兮兮的份上,本大爷就大发慈悲地指点你一下。
- 解题思路推导(扶额版)
第一步:理解题目本质
题目说“只有一盏灯是开的”——这不就是明摆着告诉你,其他灯都被按了偶数次,只有这盏倒霉蛋被按了奇数次吗?开关开关,按偶数次等于没按,按奇数次才改变状态。这么简单的道理,你不会现在才反应过来吧?
第二步:模拟操作过程
每次操作就是给一组编号的灯按一次开关。用数组cnt记录每盏灯被按的次数,初始都是0(关着的)。
对于每个操作(a,t),计算floor(k*a)(k=1到t),把对应位置的计数器+1。
这需要两层循环:外层遍历n次操作,内层遍历t次计算。
时间复杂度O(T),T最大200万,完全在可接受范围内——这种数据范围简直是送分题啊!
第三步:找出答案
最后遍历所有可能的灯编号(从1到MAX-1),找到第一个cnt[x]是奇数的位置,输出它。
因为题目保证有且只有一盏灯是开的,所以找到的第一个奇数就是答案。
什么?你问我为什么从1开始遍历?难道编号0的灯存在吗?不会吧不会吧,你不会连编号从1开始都不知道吧?
- 代码注释(毒舌版)
#include <iostream>
#include <cstring>
using namespace std;
const int MAX = 2000005; // 题目说t_i*a_i最大值不超过200万,所以开这么大够了
int cnt[MAX]; // 记录每盏灯被按的次数,初始为0(关着)
int main()
{
ios::sync_with_stdio(false); // 关闭同步,加速输入输出(这么基础的优化你总该知道吧?)
cin.tie(0); // 解除cin和cout的绑定,再加速一波
memset(cnt, 0, sizeof(cnt)); // 清空数组(虽然全局变量默认是0,但写出来显得你比较专业?)
int n;
cin >> n; // 读入操作次数
for (int i = 1; i <= n; ++i) // 遍历每次操作
{
double a; // 实数a,题目保证小数点后有6位
int t; // 正整数t
cin >> a >> t; // 读入
for (int k = 1; k <= t; ++k) // 对k从1到t
{
int pos = (int)(k * a); // 计算floor(k*a)——直接强制类型转换就是向下取整,这你不会不知道吧?
cnt[pos]++; // 对应位置的灯被按了一次
}
}
// 遍历所有可能的灯编号
for (int x = 1; x < MAX; ++x) // 从1开始,因为灯编号是正整数
{
if (cnt[x] % 2 == 1) // 如果被按了奇数次
{
cout << x << endl; // 输出这盏可怜的灯
break; // 找到就溜,不用继续找了(毕竟题目保证只有一盏)
}
}
return 0; // 程序结束,这么简单的代码你居然还要我来注释?
}
最后补一刀:
你这代码写得也太直白了吧?简直就是“暴力模拟”四个字写在脸上。虽然对于这个数据范围来说确实能过,但一点技术含量都没有啊!下次能不能来点有挑战性的题目?这种题简直是浪费本大爷的脑细胞(虽然我根本没有脑细胞)!
虽然不想麻烦你,但给个赞吧!
此内容供参考,无情绪带入,切勿当真
这里空空如也







有帮助,赞一个