阿里笔试0427

单选，多选记不太清了。

1. 给$n\times mn\backslash times\; m$ 0/1矩阵，要求放置$kk$个大小为$22$的联通块，$m\times n-2km\backslash times\; n-2k$个大小为$11$的联通块，输出任意一种方案,$n,\mathrm{ }m\mathrm{ }\le \mathrm{ }500n, m \backslash le 500$。结论就是$kk$要么是$nn$的倍数，要么是$mm$的倍数，否则无解。剩下的就是模拟下是横着放还是竖着放。
2. 对于一个序列，$a_i\mathrm{ }\mathrm{\ne }\mathrm{ }{a}_{i\mathrm{ }-\mathrm{ }1}a\_i \backslash ne a\_\{i - 1\}$并且$a_i\mathrm{ }=\mathrm{ }{a}_{i\mathrm{ }-\mathrm{ }2}a\_\{i\} = a\_\{i - 2\}$ 那么它是一个长城序列，求长度为$nn$的的序列中有多少个长城子序列(连续)。$n\mathrm{ }\le \mathrm{ }2\ast 10^{5}n \backslash le 2*10^5$。结论是两个极长的长城最多只有收尾会重叠一位。那么我们从前往后依次找出所有极长的长城序列后用等差数列求和即可。由于最多只会重叠一位，所以复杂度是线性的。
3. 给定$nn$个点，$mm$条边的无向带权连通图，最多可以删去$kk$条边，要求删完边后图依旧是联通的，求删除的边权和最大是多少。$n,m,k\le 10^{5}n,\; m,\; k\; \backslash le\; 10^5$。保证联通，我们可以想到生成树，由于要求删除的边权和最大，我们可以求个最小生成树，如果$m-n+1\ge km-n+1\backslash ge\; k$，那我们就从小到大继续加边。然后剩下的边权和就是答案。用Kruskal求最小生成树复杂度是$O(m\log m)O(m\backslash log\; m)$的。

前几天一面完还要我笔试，不知道是啥情况，希望能有二面！！！！TAT