开灯

洛谷·深入浅出 · 代码 · cpp · 难度 4/5 · 共 639 字

按 a 的倍数位置拨开关，输出最后亮着的灯编号

洛谷
练习

正文

// 原题：https://oj.yecheng.tv/p/1407
// 题意：n 次操作，每次按编号为 floor(a),floor(2a)...floor(ta) 的灯开关；最后恰一盏亮，求其编号。
// 思路：用数组记录每盏灯被拨次数（奇偶），最后奇数为亮的灯。
// 复杂度：O(总次数 T)，T<=2e6。
// 易错点：用 floor(k*a)；灯编号可能为 0？题目保证最终唯一亮灯，统计奇数即可。
#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    bool lamp[2000005] = {false};
    for(int op = 0; op < n; op++){
        double a;
        int t;
        cin >> a >> t;
        for(int k = 1; k <= t; k++){
            int id = (int)(k * a);
            lamp[id] = !lamp[id];
        }
    }
    for(int i = 0; i <= 2000000; i++)
        if(lamp[i]){ cout << i << endl; return 0; }
    return 0;
}

开灯

正文

洛谷·深入浅出的其它内容