[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\)),现在有一个由 .# 组成的 HW 列的矩阵表示这个迷宫的构造,. 代表可以通过的空地,# 代表不能通过的墙。

现在有个人从 起点 \((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\)

原文链接:https://www.cnblogs.com/witheredsakura/p/17351071.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:[Week 18] 每日一题(C++,动态规划,线段树,数学) - Python技术站

(0)
上一篇 2023年4月25日
下一篇 2023年4月25日

相关文章

  • 【ACM算法竞赛日常训练】DAY5题解与分析【储物点的距离】【糖糖别胡说,我真的不是签到题目】| 前缀和 | 思维

    DAY5共2题: 储物点的距离(前缀和) 糖糖别胡说,我真的不是签到题目(multiset,思维) ? 作者:Eriktse? 简介:19岁,211计算机在读,现役ACM银牌选手?力争以通俗易懂的方式讲解算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持续更新中……)?? 原文链接(阅读原文获得更好阅读体验):https://www.eri…

    算法与数据结构 2023年4月18日
    00
  • el-tree的实现叶子节点单选的示例代码

    下面我将详细讲解“el-tree的实现叶子节点单选的示例代码”的完整攻略。 示例代码实现 el-tree 的实现叶子节点单选,需要在 el-tree 上绑定 @check-change 事件,并通过 check-strictly 属性来配置选择模式。代码示例如下: <template> <el-tree :data="data&q…

    数据结构 2023年5月17日
    00
  • python实现可逆简单的加密算法

    下面是关于“Python实现可逆简单的加密算法”的完整攻略。 1. 可逆简单的加密算法简介 可逆简单的加密算法是一种基密码学的法,它可以将明文转换为密文,从而保证数据的安全性。与其他加密算法不同的是可逆简单加密算法可以通过相同的算法逆向解密,将密文还原为明文。这种算法通常用对敏感数据进行加密,如密码、银行卡号等。 2. Python实现可逆简单的加密算法 2…

    python 2023年5月13日
    00
  • 利用PyTorch实现爬山算法

    利用PyTorch实现爬山算法 爬山算法(Hill Climbing)是一种基于局部搜索的优化算法,它的主要思想是从当前解的邻域中选择一个更优的解作为下一次搜索的起点,直到找到最优解或达到最大迭代次数。本文将详细讲解如何使用PyTorch实现爬山算法,并提供两个示例说明。 爬山算法原理 爬山算法的基本思想是从当前解的邻域中选择一个更优的解作为下一次搜索的起点…

    python 2023年5月14日
    00
  • Go 语言数据结构之双链表学习教程

    Go 语言数据结构之双链表学习教程 一、前言 双链表是常见的数据结构,Go语言作为一种静态类型的语言,自带指针类型支持,因此在实现双链表时相对比较容易。本文中,我们将介绍双链表的基础理论和实践应用,并结合代码实现来详细讲解。 二、实现双链表的基本操作 1. 创建双链表 创建双链表需要定义链表中存储的元素类型,以及定义一个结构体来表示双链表中的一个节点。 ty…

    数据结构 2023年5月17日
    00
  • python快速查找算法应用实例

    下面是详细讲解“Python快速查找算法应用实例”的完整攻略。 快速查找算法 快速查找算法(Binary Search)是一种高效的查找算法,它的基本思想是将查找区间不断缩小,直到找到目标元素或者确定目标元素不存在。快速查找算法的时间复杂度为O(log n),比线性查找算法的时间复杂度O(n)更加高效。 Python实现快速查找算法 下面是一个Python实…

    python 2023年5月14日
    00
  • 实现用python算法计算圆周率的小诀窍

    实现用Python算法计算圆周率的小诀窍 计算圆周率是计算机科学中的一个经典问题。本文将介绍使用Python实现计圆周率的小诀窍,包括算法原理、实现步骤和示例。 算法原理 计算圆周率的经典法是蒙特卡罗方法。该方法基于随机采样的思想,通过在一个正方形内随机生成大量的点,并统计落在圆内的点的数量,从而估算圆的面和圆周率。 具体来说,假设有一个半径为r的圆,面积为…

    python 2023年5月14日
    00
  • 详解Java数据结构之平衡二叉树

    详解Java数据结构之平衡二叉树 什么是平衡二叉树? 平衡二叉树(Balanced Binary Tree)是一种特殊的二叉搜索树,它的左子树和右子树的高度差不超过1,这样可以保证在最坏情况下,查找、插入、删除等操作的时间复杂度都是O(log n)。 平衡二叉树的基本性质 左子树和右子树的高度差不超过1。 平衡二叉树的左右子树也是平衡二叉树。 如何实现? 平…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部