首页 > 其他 > 详细

The Preliminary Contest for ICPC Asia Shanghai 2019

时间:2019-09-15 20:48:19      阅读:73      评论:0      收藏:0      [点我收藏+]

 

传送门

 

B.Light bulbs(思维)

•题意

  有 n 个灯泡,初始全部为关闭状态;

  有 m 个操作,每次操作给出 [l,r],让你将区间 [l,r] 的灯泡反转。

  问最终有多少灯泡是亮着的;

  其中有 T 组数据,T ≤ 1000 , n ≤ 106 , m ≤ 1000;

•题解

  刚开始想着差分,这样的话,O(n) 就可以解出这道题;

  但是,题干中并没有说 $\sum_{1}^{T} n \le 10^8$,所以,很有可能有 1000 组数据,每组数据的 n = 106 的情况;

  这样的话,O(n) 的做法就凉凉;

  T 了几发后,换思路;

  想到了扫描线,对于输入的 m 个 [l,r],离线处理,存到如下数据结构中:

1 struct Data
2 {
3     int x;///l or r
4     int f;///f=1:x为l , f=-1:x为r
5     bool operator < (const Data &obj) const
6     {
7         return x < obj.x;
8     }
9 }a[4*maxn];

  $a[++k]=\{l,1\}\ ,\ a[++k]=\{r,-1\}$

  并额外存储如下信息:

  $a[++k]=\{l-1,0\}\ ,\ a[++k]=\{r+1,0\}$

  即用 f = 0 代表存入的是额外加入的信息;

  首先按照 x 升序排列;

  然后,求出所有不同的 x 对应的反转次数,最后统计一下答案即可;

•Code

  2019ICPC上海网络赛B.cpp

 

J.Stone game(背包???)

•题意

  有 n 堆($n \le 300$)石子,第 i 堆有 ai 个($a_i \le 500$)石子;

  让你从这 n 堆石子中任意抽取出 x 堆(第$p_1,p_2,\cdots ,p_x$),使得满足如下条件:

    (1)$define\ sum_1=\sum_{i=1}^{x}a_{p_i}\ ,\ sum_2 = \sum_{i=1}^{n}a_i \ - sum_1$

    (2)$sum_1 \ge sum_2\ \&\& \ sum_1 - a_{p_t} \le sum_2\ ,\ t \in [1,x]$

  求满足条件的取法对 $10^9 +7$ 取模的结果;

•题解

  看到这个题的时候,看了一下 n ,才 300,想了想,会不会是区间DP;

  找了一会转移方程,没找到,然后,觉得,如果这道题是区间DP的话,为什么 $a_i$ 还那么小;

  算了一下 $max(\sum_{i=1}^{n}a_i )\le 150000$,并且此题还给开了 3s;

  然后,想了一下,最大的 sum 都可以用数组存下,会不会需要开个这么大的数组存储所有的可能出现的加和;

  然后,就有了如下想法;

  首先,按照 a 升序排列;

  假设将这 n 堆石子划分成了 u,v 两堆,$|u|=sum_1\ ,\ |v|=sum_2$;

  定义 dp[ i ] 表示 $a_i$ 作为 u 堆中的最小的那一堆石子时的总方案数;

  定义 b[ i ][ j ] 表示 [i+1,n] 堆石子可以组成 j 个石子的方案数;

  类似于背包问题,按照 a 降序的方向处理即可;

•Code

  2019ICPC上海网络赛J.cpp

 

The Preliminary Contest for ICPC Asia Shanghai 2019

原文:https://www.cnblogs.com/violet-acmer/p/11523777.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!