CF616(EDU5) 题解
开始将同学对号入座进题面了。
A. Comparing Two Long Integers：
考察：高精度。
题目简述：
小 I 收到了两个很大的非负整数
数据范围：
-
令
|a|,|b| 分别代表a,b 的位数，则1\le|a|,|b|\le 10^6 在小 I 的小学时学过，比较两个数大小一共分两步：
- 比较两个数的位数。
- 从高位开始逐位比较。
但他发现这一切都建立在两个数不含前导零之上，所以若包含前导零他可以先将数位少的数用前导
时间复杂度为
B. Dinner with Emma：
考察：模拟，贪心。
题目简述：
给你一个
数据范围：
-
1\le n,m\le 100 -
\forall i\in[1,n]\cap\mathbb Z,j\in[1,m]\cap\mathbb Z,1\le c_{i,j}\le 10^9 如果小 X 选好了
i ，那么小 K 一定会选择最小的一个，即\displaystyle\min_{j=1}^mc_{i,j} 。
那么小 X 选的时候肯定想最后值最大，所以最后答案为\displaystyle\max_{i=1}^n\min_{j=1}^mc_{i,j} 。
时间复杂度为\Theta(nm) ，空间复杂度可为\Theta(1) 。C. The Labyrinth：
考察：dfs。
题目简述：
小 A 收到了一个n\times m 的网格图，它由.和*组成，*指有人阻挡他，.反之。.组成的四连通块是小 A 的活动区域，但是小 A 有一个足球，它可以击中一个人的脸并将相应位置的*变为.，现在被击中的人相应位置的四连通块就变成了自己的活动区域，这样可以扩大自己的活动区域。
小 A 还不确定要击中谁，所以希望你求出击中任意一个人后活动区域的大小，同时为了排版整齐，他会让你给出一个表格，若该格本来就为.则还输出.，反之输出该格答案对10 取模的值。
数据范围： -
1\le n,m\le 1000 很明显，我们可以先跑一遍 dfs，求出每个网格所属连通块以及每个连通块的大小，然后对于每个
*，找到它的四联通格，对他们所属的连通块进行去重，累加答案即可。
时间复杂度为\Theta(nm) ，空间复杂度为\Theta(nm) 。D. Longest k-Good Segment：
考察：双指针，桶。
题目简述：
小 Z 收到了一个序列\{a_n\} 和一个整数k ，喜欢玩 Genshin 牌的他一下就来了兴趣，想要知道如果一个连续子序列的整数种类不超过k 种，那么当连续子序列长度最大时，这个连续子序列的左右端点可以是多少（给出一种即可）。
数据范围： -
1\le k\le n\le 5\times 10^5 -
\forall i\in[1,n]\cap\mathbb Z,0\le a_i\le 10^6 为了统计序列整数种类，小 Z 开了一堆桶，实时存储整数个数，当被清零时整数种类减
1 ，从零变到一时种类加1 。
然后带进双指针板子即可。
时间复杂度为\Theta(n) ，空间复杂度为\Theta(n+V) 。E. Sum of Remainders：
考察：整除分块。
题目简述：
小 L 收到了两个整数n,m ，比小 Z 还爱玩原神的他，想求：(\sum_{i=1}^mn\bmod i)\bmod(10^9+7) 数据范围：
-
1\le n,m\le 10^{13} 整除分块板子题，给原式变个形：
\begin{aligned}(\sum_{i=1}^mn\bmod i)\bmod(10^9+7)&=(\sum_{i=1}^mn-i\lfloor\frac{n}{i}\rfloor)\bmod(10^9+7)\\&=(nm-\sum_{i=1}^mi\lfloor\frac{n}{i}\rfloor)\bmod(10^9+7)\end{aligned} 后半部分上整除分块就行了。
时间复杂度为\Theta(\sqrt m) ，空间复杂度为\Theta(1) 。