[Week 18] 每日一题（C++，动态规划，线段树，数学）
[Daimayuan] T1 最长公共子序列（C++，DP，二分）
给出从 \(1\) 到 \(n\) 的两个排列 \(P_1\) 和 \(P_2\)，求它们的最长公共子序列。
输入格式
第一行是一个正整数 \(n\)。
接下来两行，每行为 \(n\) 个数，为自然数 \(1,2,…,n\) 的一个排列。
输出格式
一个数，即最长公共子序列的长度。
数据范围
\(1≤n≤10^5\)
输入样例
5
3 2 1 4 5
2 1 3 4 5
输出样例
4
解题思路
根据数据范围，我们需要一个\(O(N)\)或者\(O(NlogN)\)的算法，自然会想到动态规划。
与本题相似的题型有最长公共子序列（\(LCS\)，复杂度\(O(N^2)\)），最长上升子序列（复杂度\(O(N(N-1)/2\))
表面上看一眼好像最长公共子序列和最长上升子序列并没有什么联系（不是有公共和子序列嘛）
但实际上是有的。我们来重新审视一下最长上升子序列问题：
给定一个序列，我们需要找出一个最长的单调上升的子序列，但实际上我们找出来的并不只是一个序列，而是两个：索引单调递增、值也单调递增。
然后反观本题的题意，可以发现\(n\)个数对应\(1,...,n\)的全排列这个条件，这个条件允许我们反转值和索引的关系（与索引和值的关系一致，值和索引也都是一一对应的，并无重复）。
到这里，我们可以实现以下的代码，将本题转换为找出最长上升子序列的问题：
int n, temp;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> temp;
indices[temp] = i;//a序列值到索引的映射
}
for (int i = 0; i < n; i++) {
cin >> temp;
arr[i] = indices[temp];//arr[i]为b_i在a序列中的位置
}
但是我们之前说过了，常规的最长上升子序列的算法时间复杂度为\(O(N(N-1)/2\)，不可接受。
可以优化的地方就是常规动态规划算法中，搜索最长前缀的那部分（这里不再赘述）。
优化搜索的常用方法就是二分搜索，但是要求是问题具有单调性，接下来我们看看这个问题为什么具有单调性：
直接开始模拟我们的算法，通过模拟来理解。
维护一个前缀和数组tails与当前最长上升子序列长度len，起初，len=0, tails[0]=-NaN（-NaN即为负无穷）。
然后与常规算法思路相一致，我们首先搜索以a[0]结尾的最长上升子序列，搜索思路是找到当前有效长度tails数组中，比a[0]大的最小元素。
显然，（1）这个元素并不存在（因为有效长度len=0），所以我们扩增长度len=1。
然后继续尝试搜索以a[1]结尾的最长上升子序列，思路是一致的，但是可能会出现（2）另一种情况——a[1]<a[0]。
当出现这种情况时，我们把\(a[1]\)用\(a[0]\)覆盖，因为当上升序列长度相同的时候，我们希望结尾元素尽可能地小。
依次类推，直到所有元素都遍历完成。
接下来给出规范化的思路：
（1）搜索当前tails数组，寻找比a[i]大的元素；
（2）不存在该元素，扩增有效长度len；
（3）存在该元素，覆盖它。
实现代码如下
tails[0] = -NaN;
for (int i = 0; i < n; i++) {
int l = 0, r = len + 1, m;
while (l + 1 != r) {
m = l + r >> 1;
if (arr[i] > tails[m]) l = m;
else r = m;
}
tails[r] = arr[i];
len = max(len, r);
}
最后，AC代码如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int max_n = 1e5;
const int NaN = 0x3F3F3F3F;
int arr[max_n], indices[max_n];
int tails[max_n], len = 0;
int main() {
int n, temp;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> temp;
indices[temp] = i;
}
for (int i = 0; i < n; i++) {
cin >> temp;
arr[i] = indices[temp];
}
tails[0] = -NaN;
for (int i = 0; i < n; i++) {
int l = 0, r = len + 1, m;
while (l + 1 != r) {
m = l + r >> 1;
if (arr[i] > tails[m]) l = m;
else r = m;
}
tails[r] = arr[i];
len = max(len, r);
}
printf("%d", len);
return 0;
}
[Daimayuan] T2 喵喵序列（C++，序偶）
题目描述
给定一个含有 \(n\) 个整数的序列 \(a_1,a_2,…a_n\)，三个数 \(i,j,k\) 是可爱的当且仅当 \(i<j<k\) 且 \(a_i<a_j<a_k\)。
请你求出有多少组 \(i,j,k\) 是可爱的。
输入格式
第 \(1\) 行一个整数 \(n\) 表示序列元素个数。
第 \(2\) 行 \(n\) 个整数分别表示 \(a_1,a_2,…a_n\)。
输出格式
一行一个整数，表示所求数量。
样例输入
5
1 2 2 3 4
样例输出
7
样例说明
满足条件的有：\((1,2,3)\)，\((1,2,4)\)，\((1,2,3)\)，\((1,2,4)\)，\((1,3,4)\)，\((2,3,4)\)，\((2,3,4)\)，共 \(7\) 个。
数据范围
对于全部数据，有 \(1≤n≤3×10^4\)，\(0≤a_i<2^{63}\)。
双倍经验
解题思路：
如果没有重复元素的话，倒是有个快速的算法（复杂度\(O(NlogN)\))，这里简单说一下，不感兴趣可以跳过：
首先利用二分优化过的最长上升子序列算法找出长度\(len\)，然后答案就是\(C_{len-1}^{3}\)。
（利用组合数求和公式\(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\)，可得\(C_2^2+C_3^2+...+C_{n-1}^2=C_{n-1}^3\)）
但是本题存在重复元素，所以我们只能老老实实找出所有三元组。
与本题相似的问题是找出所有序偶（有序对），本题是以此为基础的，所以先说一下序偶问题。
对于序偶问题，采用树状数组（线段树）来实现。
我们通过模拟来理解大致的思路：
开一个大小为\(4*n\)的数组，维护每一个位置上的元素数量（采用离散化，忽略元素值，保存元素的顺序），初始化所有区间元素均为\(0\)，线段树动态更新。
然后我们遍历数组，查询第一个元素，若其顺序位置为\(i\)，则查看线段树\(1\)~\(i-1\)区间内的元素和（也就是比它小的元素的数量），此即为二元有序对的数量。
在查询结束之后，我们将这个元素添加到线段树之中。
为什么要动态更新而不直接建树？
因为直接建树，很难维护一个区间（\(1\)$i-1$）中小于指定元素（$i$）的元素数目（因为缺少信息，我们无法查询$1$\(i-1\)区间中小于指定元素（\(i\)）的元素数目，能查询的只是整个区间中的数目）。
但是动态更新就不同了，因为当前树中只有\(1\)~\(i-1\)的元素，问题就顺利解决了。
三元组就是在二元组的基础上，再建一棵线段树（更多元也可以依次类推），第二棵线段树与前一棵不同就在于它维护的是每一个位置上的二元组数量。
最后，AC代码如下：
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int max_n = 3e4;
const long long max_a = 1LL << 63LL - 1LL;
long long arr[max_n + 1], sorted_arr[max_n + 1], n, ans;
int tree1[max_n * 4], tree2[max_n * 4];
map<long long, int>value2idx;
int query(int idx, int l, int r, int L, int R, int tree[]) {
if (L <= l && r <= R) return tree[idx];
int m = l + r >> 1;
int sum = 0;
if (L <= m) sum += query(idx << 1, l, m, L, R, tree);
if (m + 1 <= R) sum += query((idx << 1) + 1, m + 1, r, L, R, tree);
return sum;
}
void update(int idx, int l, int r, int x, int val, int tree[]) {
if (l == r) {
tree[idx] += val;
return;
}
int m = l + r >> 1;
if (x <= m) update(idx << 1, l, m, x, val, tree);
if (x >= m + 1) update((idx << 1) + 1, m + 1, r, x, val, tree);
tree[idx] = tree[idx << 1] + tree[(idx << 1) + 1];
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
sorted_arr[i] = arr[i];
}
//离散化
sort(sorted_arr + 1, sorted_arr + n + 1, [](long long x1, long long x2) {
return x1 < x2;
});
int new_id = 2;
value2idx[sorted_arr[1]] = 1;
for (int i = 2; i <= n; i++)
if (sorted_arr[i] != sorted_arr[i - 1]) value2idx[sorted_arr[i]] = new_id++;
new_id--;
//动态维护
long long ans = 0, ret = 0;
for (int i = 1; i <= n; i++) {
int idx = value2idx[arr[i]];
if (idx != 1) ans += query(1, 1, new_id, 1, idx - 1, tree2);
update(1, 1, new_id, idx, 1, tree1);
if (idx != 1) {
ret = query(1, 1, new_id, 1, idx - 1, tree1);
update(1, 1, new_id, idx, ret, tree2);
}
}
cout << ans << endl;
return 0;
}
[Daimayuan] T3 漂亮数（C++，字符串）
有一个长度为 \(n\) 的数字 \(X\)，由 \(n\) 位数字组成，即 \(a_1,a_2,...a_n\)，它们按从左到右的顺序组成一个十进制的数。
并且，你将得到一个数 \(k\)，需要你构造出一个最小的数 \(Y\)，对于每一位 \(i\)(\(1≤i≤m−k\))， 满足 \(b_i=b_{i+k}\)，并且\(X≤Y\)。
输入描述
第一行给出两个数 \(n,k\) 其中 (\(2≤n≤200000,1≤k<n\))。
第二行给出 \(X:a_1,a_2,...a_n\)。
输出描述
第一行给出\(Y\)的长度 \(m\)。
输出最小的满足条件的数 \(Y:b_1,b_2,...b_m\)。
输入样例
3 2
353
输出样例
3
353
解题思路
根据题意，我们需要找出一个长度为\(k\)的子串，使得用它循环形成的字符串\(Y>X\)。
采用模拟来理解思路：
（1）首先取\(X\)的前\(k\)个数字形成子串；
for (int i = 0; i < k; i++) {
arr[i] = X[i];
}
（2）将子串在\(X\)上滑动比较，如果小于，将子串的最低位自增\(1\)。
bool flag = true;
for (int i = k; flag && i < n; i += k) {//滑动窗口（窗口长度k）
for (int j = 0; flag && j < k && i + j < n; j++) {//比较
if (arr[j] < X[i + j]) {//小于，自增1
arr[k - 1]++;
int idx = k - 1;
while (arr[idx] > 9) {
arr[idx--] = 0;
arr[idx]++;
}
flag = false;
}
else if (arr[j] > X[i + j]) {//特判
flag = false;
break;
}
}
}
需要注意的是，当高位已经大于，我们就不需要继续匹配低位了，所以需要增加特判操作。
最后，AC代码如下：
#include <iostream>
using namespace std;
const int max_len = 200000;
const int max_k = max_len - 1;
int X[max_len], arr[max_k];
int main() {
int n, k;
string str;
cin >> n >> k;
cin >> str;
for (int i = 0; i < n; i++) {
X[i] = str[i] - '0';
if (i < k) arr[i] = X[i];
}
bool flag = true;
for (int i = k; flag && i < n; i += k) {//滑动窗口（窗口长度k）
for (int j = 0; flag && j < k && i + j < n; j++) {//比较
if (arr[j] < X[i + j]) {//小于，自增1
arr[k - 1]++;
int idx = k - 1;
while (arr[idx] > 9) {
arr[idx--] = 0;
arr[idx]++;
}
flag = false;
}
else if (arr[j] > X[i + j]) {
flag = false;
break;
}
}
}
printf("%d\n", n);
for (int i = 0; i < n; i += k) {
for (int j = 0; j < k && i + j < n; j++) {
printf("%d", arr[j]);
}
}
return 0;
}
[Daimayuan] T4 真假字符串（C++，逻辑推理）
给定两个长度相等的字符串 \(S_1,S_2\), 问能否找出一个字符串 \(S\), 使得 \(S\) 只删除一个字符可以得到 \(S_1\), 并且 \(S\) 只删除一个字符也可以得到 \(S_2\) (可以是不同位置的字符)。
输入格式
输入第一行给出字符串 \(S_1\), 第二行给出字符串 \(S_2\), 两个字符串的长度 \(1≤len≤300000\)。
输出格式
如果能找到满足条件的字符串 \(S\), 输出 \(1\), 否则输出 \(0\)。
样例输入
abacaa
aacaba
样例输出
1
样例解释
\(abacaba\) 删除第二个字符 \(b\) 可以得到字符串 \(S_1\), 并且删除第一个字符 \(b\) 可以得到字符串 \(S_2\)。
解题思路
共有两种输出\(1\)的情况：
（1）\(S_1,S_2\)完全相同（视为删除字符位置一致）；
（2）\(S_1,S_2\)各自删除一个字符之后完全相同。
其余情况均输出\(0\)。
接下来进行代码实现：
当且仅当同时到达末尾的时候，输出\(1\)。字符匹配一共有三种情况：
（1）匹配两个字符，如果相同，则继续匹配；
（2）如果不同，先尝试删除\(S_1\)中的字符；如果再次遇到不同，尝试删除\(S_2\)中字符；若两个字符串仍不匹配，进行（3）；
（3）如果不同，先尝试删除\(S_2\)中的字符；如果再次遇到不同，尝试删除\(S_1\)中字符；若两个字符串仍不匹配，输出\(0\)。
最后，AC代码如下：
#include <iostream>
using namespace std;
string s1, s2;
bool judge(int i, int j) {//判断是否能够相等
int len = s1.size();
bool flag = true;//尝试删除的机会
while (i < len && j < len) {
if (s1[i] != s2[j]) {
if (flag) {
if (i < j) i++;
else j++;
flag = false;
}
else return false;
}
i++, j++;
}
if (i != j && !flag) return false;
return true;
}
int main() {
cin >> s1 >> s2;
int len = s1.size(), ans = -1;
for (int i = 0; i < len; i++) {//找出第一个不匹配
if (s1[i] != s2[i]) {
ans = i;
break;
}
}
if (ans == -1) cout << 1 << endl;//两个字符串相等
else {//分情况讨论
if (judge(ans, ans + 1) || judge(ans + 1, ans)) cout << 1 << endl;
else cout << 0 << endl;
}
return 0;
}
[Daimayuan] T5 走不出的迷宫（C++，图论，DP）
有一个 \(H\) 行 \(W\) 列的迷宫（行号从上到下是 \(1−H\)，列号从左到右是 \(1−W\)），现在有一个由 . 和 # 组成的 H 行 W 列的矩阵表示这个迷宫的构造，. 代表可以通过的空地，# 代表不能通过的墙。
现在有个人从 起点 \((1,1)\) 开始走，他每一步只能往右走一格或者往下走一格，并且他不能跨越迷宫的边界。他会一直走，直到没有可以走的路时停下来。
请问这个人最多可以经过多少个格子？
输入格式
第一行两个整数 \(H\)，\(W\)，表示迷宫有 \(H\) 行 \(W\) 列。
接下来一个 \(H\) 行 \(W\) 列的由 . 和 # 组成的矩阵，表示迷宫的构造。
注意：保证 \((1,1)\) 的位置一定是 .。
输出格式
一个整数，表示最多步数。
样例输入1
3 4
.#..
..#.
..##
样例输出1
4
样例输入2
1 1
.
样例输出2
1
样例输入3
5 5
.....
.....
.....
.....
.....
样例输出3
9
数据规模
对于全部数据保证 \(1≤H,W≤100\)
解题思路
主体思路为动态规划，时间复杂度为\(O(H*W)\)。
由题意可知，我们到达一个格子的方式只有从左边和上边到达两种情况，那么我们就继承这两种情况中步数更多的一种\(+1\)来更新：
sum[i][j] = max(sum[i - 1][j], sum[i][j - 1]) + 1;
采用二重循环遍历整张图，由循环顺序，显而易见：在我们到达(i, j)之前，已经到达了(i - 1, j)和(i, j - 1)。
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
sum[i][j] = max(sum[i - 1][j], sum[i][j - 1]) + 1;
}
}
但是需要注意两点：
（1）注意障碍物的存在，以下代码采用的方式是掩码把墙的sum置为\(0\)；
（2）注意寻找最大步数时还需要进行一次\(BFS\)，因为我们可能到达不了某些格子，从而导致我们得到的答案并不是sum数组中的最大值。
AC代码如下：
#include <iostream>
#include <queue>
using namespace std;
const int max_h = 100;
const int max_w = 100;
bool map[max_h + 1][max_w + 1], book[max_h][max_w];
long long sum[max_h + 1][max_w + 1];
long long h, w, ans = 1;
struct node { int x, y; };
queue<node>q;
inline void read() {
string str;
cin >> h >> w;
for (int i = 1; i <= h; i++) {
cin >> str;
for (int j = 1; j <= w; j++) {
if (str[j - 1] == '.') map[i][j] = true;
else map[i][j] = false;
}
}
}
void bfs() {
q.push(node{ 1,1 });
book[1][1] = true;
int step[2][2] = { {1,0}, {0,1} }, temp_x, temp_y;
while (!q.empty()) {
node temp = q.front(); q.pop();
for (int i = 0; i < 2; i++) {
temp_x = step[i][0] + temp.x;
temp_y = step[i][1] + temp.y;
if (temp_x > h || temp_y > w) continue;
if (!map[temp_x][temp_y]) continue;
if (book[temp_x][temp_y]) continue;
q.push(node{ temp_x,temp_y });
book[temp_x][temp_y] = true;
ans = max(ans, sum[temp_x][temp_y]);
}
}
}
inline void solve() {
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= h; j++) {
sum[i][j] = max(sum[i - 1][j] * map[i - 1][j],
sum[i][j - 1] * map[i][j - 1]) + 1;
}
}
bfs();
cout << ans << endl;
}
int main() {
read();
solve();
return 0;
}
[Daimayuan] T6 最长同余子数组（C++，gcd，线段树）
给定一个 \(N\) 长数组 \(\{A\}\), 元素之间 两两不同.
现在要求你找出最长的 连续子序列, 使得这些元素 \(mod\ M\) 意义下同余, 其中 \(M≥2\).
形式化的说, 在数组中找到最长的 \(A[L..R],∃M≥2\), 使得:
\(A_L≡A_{L+1}≡A_{L+2}≡⋯≡A_R(mod\ M)\)
其中, a≡b(mod M) 即是说 a%M=b%M
输出此长度即可.
数据规模
- \(1≤n≤2×10^3\)
- \(1≤a_i≤10^{18}\)
输入格式
第一行一个数字 \(N\)。
接下来一行 \(N\) 个整数 \(A_1,A_2,…,A_N\)。
输出格式
一个数，表示最长连续同余子序列的长度。
样例输入
4
8 2 10 5
样例输出
3
注意到 \(8,2,10\) 均为偶数.
进阶：
bonus 1: consider what if \(N\) is greater (even \(1≤N≤2×10^5\))?
bonus 2: consider how to solve the 'subsequence' version.
解题思路
首先来理解一下同余：同余即是元素之间的差值可以被同一个数整除（类似于等差数列）。
整个过程分为三步：
（1）我们把输入处理成两个相邻元素之间的差值：
cin >> buffer1;
for (int i = 1; i < n; i++) {
cin >> buffer2;
arr[i] = abs(buffer2 - buffer1);
buffer1 = buffer2;
}
（2）然后建一棵维护区间\(gcd\)的线段树：
void build_tree(int idx, int l, int r) {
if (l == r) {
tree[idx] = arr[l];
return;
}
int m = l + r >> 1;
build_tree(idx << 1, l, m);
build_tree((idx << 1) + 1, m + 1, r);
tree[idx] = gcd(tree[idx << 1], tree[(idx << 1) + 1]);
}
（3）最后跑一个滑动窗口，求得最大长度：
long long ans = 0, l = 1, r = 1;
while (r <= n - 1) {
if (query(1, 1, n - 1, l, r) != 1) {
ans = max(ans, r - l + 1);
r++;
}
else l++;
while (r - l + 1 <= ans) r++;//小于ans的尝试没有意义
}
cout << ans + 1 << endl;
需要注意的就是当相邻两个数相等时的处理：
题意要求模数\(M\ge2\)，所以我们应该当query返回值大于\(1\)的时候增加窗口长度。
根据gcd的算法，当其中一个输入数据为\(0\)时，会返回另外一个数，所以\(0\)对于最大公约数的计算没有影响。
但是当查询范围内的所有差值均为\(0\)的时候，query会返回\(0\)，需要注意这时是可以增加窗口长度的。
所以更改判断条件为query != 1而不是query > 1。
最后，AC代码如下：
#include <iostream>
using namespace std;
const int max_n = 2e3;
long long tree[max_n * 4], arr[max_n + 1];
long long gcd(long long x, long long y) {
long long t;
while (y != 0) {
t = x % y;
x = y;
y = t;
}
return x;
}
void build_tree(int idx, int l, int r) {
if (l == r) {
tree[idx] = arr[l];
return;
}
int m = l + r >> 1;
build_tree(idx << 1, l, m);
build_tree((idx << 1) + 1, m + 1, r);
tree[idx] = gcd(tree[idx << 1], tree[(idx << 1) + 1]);
}
long long query(int idx, int l, int r, int L, int R) {
if (L <= l && r <= R) return tree[idx];
int m = l + r >> 1;
if (R <= m) return query(idx << 1, l, m, L, R);
else if (L >= m + 1) return query((idx << 1) + 1, m + 1, r, L, R);
else return gcd(query(idx << 1, l, m, L, R), query((idx << 1) + 1, m + 1, r, L, R));
}
int main() {
long long n, buffer1, buffer2;
cin >> n;
cin >> buffer1;
for (int i = 1; i < n; i++) {
cin >> buffer2;
arr[i] = abs(buffer2 - buffer1);
buffer1 = buffer2;
}
build_tree(1, 1, n - 1);
long long ans = 0, l = 1, r = 1;
while (r <= n - 1) {
if (query(1, 1, n - 1, l, r) != 1) {
ans = max(ans, r - l + 1);
r++;
}
else l++;
while (r - l + 1 <= ans) r++;
}
cout << ans + 1 << endl;
return 0;
}
[Daimayuan] T7 互质（C++，数学）
题目描述
给你一个包含n个正整数的序列 \(A=(A1,A2,...,An)\),找到 \([1,m]\)中每一个满足下列条件的 \(k\)：
\(gcd(A_i,k)=1\), \(1≤i≤n\)
输入描述
第一行输入两个整数 \(n\), \(m\) 第二行输入\(n\)个整数代表序列\(A\)
输出描述
第一行输出一个整数代表满足条件的k的数量 接下里每一行输出一个整数，代表一个满足条件的\(k\)
样例输入
3 12
6 1 5
样例输出
3
1
7
11
数据范围
\(1≤n,m≤100000\)
\(1≤a_i≤100000\)
解题思路
本来这道题是想用欧拉筛做的（只考虑部分数情况下的“质数”），但是并不是质数就符合条件，因为互质要求是最大公约数为\(1\)，而质数只是不能分解而已。
对于互质的数\(a,b\)，\(gcd(a,b)=1\)，也就是说互质的数不能有公因数。
我们将这个问题优化一下，互质的数不能有公共质因数（因为任何合数都可以分解为质数的乘积）。
那么现在我们的思路就是将所有输入分解为质因数，然后利用分解得到的质因数筛选符合条件的\(k\)。
接下来是代码实现部分：
首先，我们需要知道如何将输入分解为质因数
int num;
for (int i = 0; i < n; i++) {
cin >> num;
while (num != 1) {
fliter[maxPrime[num]] = true;
num /= maxPrime[num];
}
}
其实，就是将\(num\)不断除以其最大质因数。
那么问题出现了，如何求任意数的最大质因数？这里采用埃氏筛的算法（简而言之就是用质数的倍数筛去非质数）的变形：
memset(isPrime + 1, true, sizeof(bool) * max_n);//初始化，默认所有数均为质数
maxPrime[1] = 1;//对1进行特殊处理
isPrime[1] = false;
for (int i = 2; i <= max_n; i++) {
if (!isPrime[i]) continue;//非质数
maxPrime[i] = i;
for (int j = 2 * i; j <= max_n; j += i) {
isPrime[j] = false;
maxPrime[j] = i;
}
}
筛子做好了，接下来就是筛选\(1\)~\(M\)的所有数了：
vector<int>v;
v.push_back(1);//对1进行特殊处理
for (int i = 2; i <= m; i++) {
bool flag = true;
int temp = i;
while (temp != 1) {
if (fliter[maxPrime[temp]]) {
flag = false;
break;
}
temp /= maxPrime[temp];
}
if (flag) v.push_back(i);
}
在题目之初提到的问题就是筛选一个\(k\)，既需要考虑\(k\)能否分解为小于\(k\)的数，又要考虑\(k\)之后的数是否为\(k\)的倍数。
但是现在我们将序列\(A\)中的元素分解了，就没有这个问题了，只需要考虑\(k\)能否分解即可。
最后，AC代码如下：
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
const int max_n = 100000;
bool isPrime[max_n + 1], fliter[max_n + 1]; //质数数组, 筛子
int maxPrime[max_n + 1]; //最大质因数
int main() {
//prepare
memset(isPrime + 1, true, sizeof(bool) * max_n);//初始化，默认所有数均为质数
maxPrime[1] = 1;//对1进行特殊处理
isPrime[1] = false;
for (int i = 2; i <= max_n; i++) {
if (!isPrime[i]) continue;//非质数
maxPrime[i] = i;
for (int j = 2 * i; j <= max_n; j += i) {
isPrime[j] = false;
maxPrime[j] = i;
}
}
//input
int n, m, num;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> num;
while (num != 1) {
fliter[maxPrime[num]] = true;
num /= maxPrime[num];
}
}
//fliter
vector<int>v;
v.push_back(1);//对1进行特殊处理
for (int i = 2; i <= m; i++) {
bool flag = true;
int temp = i;
while (temp != 1) {
if (fliter[maxPrime[temp]]) {
flag = false;
break;
}
temp /= maxPrime[temp];
}
if (flag) v.push_back(i);
}
//output
cout << v.size() << endl;
for (auto iter : v) {
cout << iter << endl;
}
return 0;
}
[Daimayuan] T9 最短路计数（C++，DP）
题目描述
给出一个 \(N\) 个顶点 \(M\) 条边的无向无权图。
问从顶点 \(1\) 开始，到其他每个点的最短路有几条。
输入格式
第 \(1\) 行包含两个正整数 \(N\)，\(M\)。
接下来 \(M\) 行，每行两个正整数 \(x,y\)表示存在一条由顶点 \(x\) 到顶点 \(y\) 的边。（可能存在重边和自环）
输出格式
输出 \(N\) 行，每行一个非负整数。
第 \(i\) 行输出从顶点 \(1\) 到顶点 \(i\) 的不同最短路个数。
由于数据可能很大，你只需要输出 \(ans\ mod\ 100003\) 的结果。
若顶点 \(1\) 不能到达顶点 \(i\)，请输出 \(0\)。
样例输入
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
样例输出
1
1
1
2
4
数据范围
\(1≤N≤10^6\)，\(1≤M≤2×10^6\)
提示
由于数据量较大，请使用较为快速的输入/输出方式。
解题思路
根据数据范围，我们估计算法的复杂度至多是\(O(N)\)，因此想到了动态规划：
对于节点\(i\)，有若干个节点与之相连，在与之相连的节点当中从\(1\)到\(k_1,k_2,...,k_n\)节点的路径长度相同且最短，那么我们计算得出，从\(1\)到节点\(i\)的最短路径数为\(num[k_1]+num[k_2]+...+num[k_n]\)。
以上是思路的主体部分，接下来实现代码：
数据量庞大，同时也是因为存在重边，故不能采用二维数组存图，因此采用链式前向星。
对于代码主体部分，维护一个队列与一个路径长度的数组。
初始化将\(1\)节点加入队列，然后不断尝试到达新的节点。
void solve() {
q.push(1);
while (!q.empty()) {
int node = q.front(); q.pop();
for (int i = head[node]; i != -1; i = edges[i].next) {
int v = edges[i].v;
q.push(v);
}
}
}
利用队列元素先进先出的特点，我们可以保证，队首的节点永远是距离\(1\)最近的节点。
进而我们可以保证，用队首去更新路径长度，得到的一定是最短路径长度。
void solve() {
q.push(1);
path[1] = 0;
while (!q.empty()) {
int node = q.front(); q.pop();
int path_len = path[node] + 1;
for (int i = head[node]; i != -1; i = edges[i].next) {
int v = edges[i].v;
if (path_len > path[v]) continue;
if (path[v] == NaN) {//NaN代表无穷大，即为未到达的节点
path[v] = path_len;
q.push(v);
}
}
}
}
以此为基础，很容易实现最初的思想：
void solve() {
q.push(1);
path[1] = 0;
sum[1] = 1LL;
while (!q.empty()) {
int node = q.front(); q.pop();
int path_len = path[node] + 1;
for (int i = head[node]; i != -1; i = edges[i].next) {
int v = edges[i].v;
if (path_len > path[v]) continue;
sum[v] = (sum[v] + sum[node]) % mod_num;
if (path[v] == NaN) {
path[v] = path_len;
q.push(v);
}
}
}
}
最后，AC代码如下：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <string.h>
using namespace std;
const int max_n = 1e6;
const int max_m = 2e6;
const int NaN = 0x3F3F3F3F;
const long long mod_num = 100003;
struct edge { int v, next; }edges[2 * max_m];
int tot = -1, head[max_n + 1], path[max_n + 1];
queue<int>q;
long long sum[max_n + 1];
void add_edge(int u, int v) {
edges[++tot] = { v, head[u] }; head[u] = tot;
edges[++tot] = { u, head[v] }; head[v] = tot;
}
void solve() {
q.push(1);
path[1] = 0;
sum[1] = 1LL;
while (!q.empty()) {
int node = q.front(); q.pop();
int path_len = path[node] + 1;
for (int i = head[node]; i != -1; i = edges[i].next) {
int v = edges[i].v;
if (path_len > path[v]) continue;
sum[v] = (sum[v] + sum[node]) % mod_num;
if (path[v] == NaN) {
path[v] = path_len;
q.push(v);
}
}
}
}
int main() {
memset(head, -1, sizeof(int) * (max_n + 1));
memset(path, 0x3F, sizeof(int) * (max_n + 1));
int n, m;
scanf("%d%d", &n, &m);
//cin >> n >> m;
int u, v;
for (int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
//cin >> u >> v;
add_edge(u, v);
}
solve();
for (int i = 1; i <= n; i++) {
printf("%lld\n", sum[i]);
}
return 0;
}
[Daimayuan] T10 最后的舞会（C++，DFS）
老师为即将毕业的同学们准备了一场舞会，有\(2N\)个同学会参加这场舞会，他们会被分成\(N\)对跳舞，每个人有一个编号，如果编号为\(i\)的同学和编号为\(j\)的同学配对，那么这一对的满意度是\(A_{i,j}(i<j)\)，我们规定这个舞会的满意度为每一队的满意度的异或和，也就是说，当同学们分成\(N\)组后，第\(i\)对同学的满意度为\(A_i\)，那么舞会的满意度为\(A1⊕A2⊕...AN\)
请你求出本场舞会满意度的最大值
输入描述
第一行给出一个数\(N\)，有\(2N\)个人参加舞会
接下来给出一个矩阵表示\(i\)和\(j\)配对时的满意度
\(A_{1,2},A_{1,3},...A_{1,2N}\)
\(A_{2,3},...A_{2,2N}\)
.. .. ..
\(A_{2N−1,2N}\)
其中\(1≤N≤8,0≤A_{i,j}≤2^{30}\)
输出描述
输出本场舞会满意度的最大值
样例输入
2
4 0 1
5 3
2
样例输出
6
样例解释
如果\(\{1,2\},\{3,4\},ans=A_{1,2}⊕A_{3,4}=4⊕2=6\)
如果\(\{1,3\},\{2,4\},ans=A_{1,3}⊕A_{2,4}=0⊕3=3\)
如果\(\{1,4\},\{2,3\},ans=A_{1,4}⊕A_{2,3}=1⊕5=4\)
最后答案为\(max(6,3,4)=6\)
解题思路
因为数据\(N\le8\)，所以直接\(DFS+\)剪枝就可以。
问题可能在于如何\(DFS\)：
写一个\(DFS\)需要定义四个部分（并不一定都需要）：状态部分（函数声明），停止条件，主体部分，返回后操作。
我们从简单到复杂逐个定义。
（1）结束条件：配对数到达\(n\)；
（2）返回后操作：将已配对的两个人取消标记；
（3）状态部分：状态部分为已配对数、舞会满意度；
（4）主体部分：首先利用一个循环找出第一个未配对的人，然后再用一个循环去为他搭配所有可能。
void dfs(int couple, int confid) {//状态
if (couple == n + 1) {//结束条件
ans = max(ans, confid);
return;
}
//函数主体
int i, j;
for (i = 1; i <= 2 * n; i++) {
if (!vis[i]) {
for (j = i + 1; j <= 2 * n; j++) {
if (!vis[j]) {
vis[i] = vis[j] = true;
dfs(couple + 1, confid ^ relation[i][j]);
vis[i] = vis[j] = false;//返回后操作
}
}
}
}
}
如何降低时间复杂度：
（1）依靠遍历顺序：\(1,2\)和\(2,1\)算一种情况，所以只考虑前者（递增序），依靠遍历查找的顺序来实现；
（2）依靠\(DFS\)序：我们在第一层配对\(1\)和\(3\)，在第二层配对\(2\)和\(4\)这种情况与我们在第一层配对\(2\)和\(4\)和在第二层配对\(1\)和\(3\)二者是相同的。
优化之后的算法如下：
void dfs(int couple, int confid) {
if (couple == n + 1) {
ans = max(ans, confid);
return;
}
int i, j;
for (i = 1; i <= 2 * n; i++) {
if (!vis[i]) break;//DFS序剪枝
}
for (j = i + 1; j <= 2 * n; j++) {//遍历顺序剪枝
if (!vis[j]) {
vis[i] = vis[j] = true;
dfs(couple + 1, confid ^ relation[i][j]);
vis[i] = vis[j] = false;
}
}
}
AC代码如下：
#include <iostream>
using namespace std;
const int max_n = 16;
int relation[max_n + 1][max_n + 1], n, ans;
bool vis[max_n + 1];
void dfs(int couple, int confid) {
if (couple == n + 1) {
ans = max(ans, confid);
return;
}
int i, j;
for (i = 1; i <= 2 * n; i++) {
if (!vis[i]) break;
}
for (j = i + 1; j <= 2 * n; j++) {
if (!vis[j]) {
vis[i] = vis[j] = true;
dfs(couple + 1, confid ^ relation[i][j]);
vis[i] = vis[j] = false;
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= 2 * n; i++) {
for (int j = i + 1; j <= 2 * n; j++) {
cin >> relation[i][j];
}
}
dfs(1, 0);
cout << ans << endl;
return 0;
}
（并没有什么奇妙的算法呢\(qwq\)）