求助 ICPC 2019 Mid-Atlantic D
  • 板块题目总版
  • 楼主rharry
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/4/8 20:13
  • 上次更新2023/11/5 00:51:41
查看原帖
求助 ICPC 2019 Mid-Atlantic D
507148
rharry楼主2021/4/8 20:13

原题链接:https://mausa19.kattis.com/problems/pixelated

概要:LCD显示屏是由横纵电线组成的网格,像素点位于电线交点。给出n个脉冲,h表示从左侧向右发射的横向脉冲,v表示从底部向上发射的纵向脉冲。在该方向上第a根电线上的脉冲于时间t接触电线上第一个像素点,长度为m,沿电线每单位时间前进一个像素。横纵方向上的脉冲同时通过像素点会激活该像素点。求被激活的像素点数量。

1<=n,t,m<=2105,1<=a<=1051<=n,t,m<=2*10^5, 1<=a<=10^5,时间限制5s。

尝试了对通过每根电线上脉冲时间离散化,但似乎只要遍历横纵脉冲的所有交会O(n2)O(n^2)就会TLE。求提供思路。

2021/4/8 20:13
加载中...