实小社团练习赛12

本文总阅读量次

3118,7887,2842,7880

T1

数学模拟
周期问题。
假设到达时间为 $x$ ，一只狗的狂躁时间为 $A$ ，平静时间为 $B$ 。
那么我们可以把 $A + B$ 看成一个周期，如果 $x % (A + B)$ 的余数小于或等于 $A$ ，则被攻击，反之不会被攻击。
另一只狗处理方式一样。

T2

模拟
会用 $m a p$ ，代码量会少很多，不会也没事，数据规模很小，全部扫描也不会超时。
$m a p$ 做法：
1.定义map

map<string,double> d;

2.打表记录广告价格

for...
{
    cin>>广告>>价格;
    d[广告]=价格;
}

3.根据访问的广告，累加价格即可。

T3

贪心、枚举
首先想到基础的枚举
如果枚举输入的温度，则20000×20000=4亿，显然要超时。
阶段1：状态-->所有的给定的温度
阶段2：状态-->所有的奶牛

for n只奶牛的温度区间{
    当前产奶量初始化为0
   for 枚举n只奶牛的温度区间
       根据区间是否重叠，计算出产奶量
    当前方案产奶量跟之前的最优产奶量比较
}

换个角度思考， $n$ 个区间， $n$ 个 $A_{i}$ 和 $n$ 个 $B_{i}$ ，把左右端点拆散后，可以组成 $n^{2}$ 个区间,当然我们不打算枚举这些区间，因为要超时。
但是我们可以用类似垃圾装袋的思路（慈溪市2016年第三题）。
先对左端点和右端点都进行从小到大排序，然后比较左右端点，会有以下几种情况（首先做好初始化，认为所有奶牛觉得冷，即产量总和初值为 $N X$ ，擂主的初值也为 $N X$ ）：
(1)当 $A_{i} <= B_{j}$ ，因为 $A_{i}$ 和 $B_{j}$ 都来自于 $N$ 头奶牛，所以满足这个条件的时候，我们认为奶牛是舒适的，可以把 $B_{j}$ 看成舒适的温度，所以能够产 $Y$ 单位的奶，那么产奶总量重新计算，即当前产奶总量=产奶总量+Y-X。
(2)当 $A_{i} > B_{j}$ 时，因为 $B_{j}$ 属于其中一头奶牛且题中温度范围为 $A_{i} <= B_{i}$ ，所以这时候 $A_{i} > B_{j}$ ， $B_{j}$ 这头奶牛显然过热了，产奶总量需重新计算，即当前产奶总量=产奶总量+Z-Y，因为 $Z < Y$ ,所以相当于产量减少到 $Z$ 。
重复1~2操作，直到扫描完所有的端点。
伪代码
算法核心代码

当前产奶总量 = N*X;
擂主 = N*X;
  while (i<=N || j<=N) {
    if (A[i] <= B[j]) {     //把B[j]看成适宜温度的最大值
      当前产奶总量 += Y-X;   
      i++;
    } else {                //寻找新的B[j]
      当前产奶总量 += Z-Y;
      j++;
    }
    if (当前产奶总量 > 擂主) 
      擂主 = 当前产奶总量;
  }

整个算法时间复杂度为 $O (N)$ ，这样寻找区间的方法，避免了很多不必要的计算，例如当前选择的左端点 $A_{i} > B_{j}$ 时，那些 $B_{j} <= A_{i}$ 的端点就不用考虑了，效率就提升了。

T4

BFS
模板题，区别是起点很多，如果只有一个起点，很多人马上就明白如何去宽搜，那么当起点多个的时候，其实就是都塞到队列中即可。

    for(int i = 1,x,y; i <= A; i++){
        cin>>x>>y;
        v[x][y]=1; //标记为不可访问
        q.push(make_pair(x,y));
    }

最后，根据询问的情况，输出对应坐标的步数（感染瘟疫时间），所以BFS需要打表记录每个位置的步数。