【7.21-26】代码源 - 【平方计数】【字典序最小】【“Z”型矩阵】

#607. 平方计数

题意：从序列 $M$ 个数中顺序选出 $N(n\le 10^6)$ 个不同的数, 使得这 $N$ 个数的字典序最小。

题解：(倍数遍历) 代码源每日一题 Div1 平方计数

思路：如果点对 $(i,j)$ 满足 $a_i^2+a_j$ 为完全平方数，那么 $a_j=(x+a_i)\times (x-a_i)$ 。我们可以枚举 $a_j$ 的因子对，然后就能得到满足条件的 $a_i$ 是多少。

这里要用到上一个文章里类似的优化。筛一个数的因子的方法：

1. 暴力根号枚举，时间复杂度 $O(0\sim \sqrt{n})$
2. 埃氏筛优化，枚举每个数的倍数，那么该数一定是倍数的因子，就能得到一个因子对。时间复杂度 $O(n\times \log n\sim \log n)$

这道题用的是第二个优化。不过代码实现的话没有必要储存起来因子对。

    rep(i, 1, 1000000){
        for(int j = i; j <= 1000000; j += i){
        	if(j / i - i < 0) continue;
            // (i, j / i) 即为一对因子对
        }
    }
1
2
3
4
5
6

AC代码：http://oj.daimayuan.top/submission/301674

---

#608. 字典序最小

题意：从序列 $M$ 个数中顺序选出 $N$ 个不同的数, 使得这 $N$ 个数的字典序最小。$(n,m\le 10^6,1\le a_i\le N)$ ，数据保证 $[1,N]$ 范围内每个数至少出现一次。

题解：(单调栈) 代码源每日一题 Div1 字典序最小

思路：和上一场的 div2 的题的贪心思路很像。首先我们要向最小字典序去靠近，也就是 $[1,N]$ 原排列。于是我们维护一个栈，向后扫，把栈尾部所有比新来的数大的数弹出来，新数放进去。这样能贪心的向最小字典序靠拢。但是我们的决策可能出现问题，如果后面没有和要弹出的数相等的元素，就会无解。因此，预处理每个数后面是否还有数，如有数则当前数可弹出；否则不可弹出，因为会造成无解。

AC代码：http://oj.daimayuan.top/submission/292414

---

#614. “Z”型矩阵

题意：问一个矩阵有多少个子矩阵满足矩阵形状为 z 。

题解：(离线/树状数组)代码源每日一题 Div1“Z”型矩阵

思路：枚举矩阵端点是 $O(n^4)$ 的。如何优化？我们在对角线上求解。对于每个对角线，上面的每一个点都有左向线、右向线，我们从右上向左下扫对角线，扫的过程中按照左向线的长度维护，存到树状数组里。因为每个左向线都有一个生存周期，我们标记每个左向线的结束时间。对于右向线，能和当前右向线匹配的一定是长度小于等于右向线的仍然存活的左向线，查询树状数组即可。

AC代码：http://oj.daimayuan.top/submission/301109