======Atcoder Beginner Contest 177======

=====A - Don't be late=====

====题目大意====

给出$D,T,S$，求$\lceil \frac{D}{S} \rceil$是否小于等于$T$

====数据范围====

$1 \le D,S,T \le 1000$

====解题思路====

直接判断

=====B - Substring=====

====题目大意====

给出字符串$s,t$，问$t$最少修改几个字符可以变成$s$的一个子串

====数据范围====

$1 \le |t| \le |s| \le 1000$

====解题思路====

直接$O(|t|^2)$暴力判断即可

=====C - Sum of product of pairs=====

====题目大意====

给出$N$个数$A_1 ... A_n$，求$\sum_{1 \le i < j \le N} A_i * A_j$ mod $10^9+7$

====数据范围====

$2 \le N \le 2 \times 10^5$，$A_i \le 10^9$

====解题思路====

直接求一个后缀和然后乘起来就行

=====D - Friends=====

====题目大意====

有$N$个人$M$对朋友关系，朋友的朋友也是朋友，问最少分几组可以让每个组内都没有相互是朋友的人

====数据范围====

$2 \le N,M \le 2 \times 10^5$

====解题思路====

并查集处理然后看最大的集合有多少个人就是答案

=====E - Coprime=====

====题目大意====

给出$N$个数$A_1 ... A_n$，如果任意两个数都互质就称为pairwise coprime，如果整体最大公约数是1就称为setwise coprime，否则就称为not coprime，判断是哪种情况

====数据范围====

$N,A_i \le 10^6$

====解题思路====

先筛出每个数的最小质因子，然后查每个数的质因子，如果没有重复就是第一种情况，如果有重复判断是否整体最大公约数是1

=====F - I hate Shortest Path Problem=====

====题目大意====

有一个$(H+1) \times W$的矩形，你可以从第一行任意一个点出发，只能向下或向右走，但是对于每一行$i$，这一行的第$A_i$到$B_i$个格子不能向下走，问对于$2$到$H+1$，到达这些行最短走几格，如果不能走到输出-1

====数据范围====

$1 \le H,W \le 2 \times 10^5$

====解题思路====

首先走到第$i$行肯定要向下走$i-1$，所以我们考虑最小化往右走的次数，在一开始所有格子的开始和结束位置都是自己，因为可以从任意一个格子开始，往右走最小步数是0，但是对于第$i$行的区间$[A_i,B_i]$，里面所有格子的结束位置是$B_i+1$，因为这些格子不能往下走，而我们发现，一但很多个格子的结束位置相同，我们就不用考虑远的那些，直接考虑最后面那个就行了，所以我们用一个set维护格子，一但有格子结束位置一样我们就删到只剩最后一个，然后每次找向右走步数最少的格子输出，如果格子都被删光了就无法走到，输出-1