算法竞赛笔记

CF-Div1037

B题说要dp其实没有dp，对于休息的那天直接贪心算
C题是一个模拟，排序后合起来考虑时刻，高度（不要拆开模拟）
D题的提示是数据结构，题解使用了pair<int,pair<int,int>>

前几题的思路都是贪心算，我做的时候方法很不灵活，相关基础也没掌握好，笨笨的。需要大量练习。

E.G-C-D，Unlucky!

gcd有一个性质：
gcd(a,b)=1等价于gcd(a,kb)=1

▶

证明

Tutorial里边有打段的解释，其实还是围绕这个性质来的。
关键要知道s_n和p_n有公因子g （通过将g消去可以联系两个等式）
S_i = s_i / g
P_i = p_i / g
对于中间一个a_i来说，S_i 整除 a_i / g ， P_i 整除 a_i / g
(由上述的性质)
所以 a_i / g 既要和 p_i-1 / p_i 互质，又要和 s_i+1 / s_i 互质
令x = p_i-1 / p_i
y = s_i+1 / s_i
所以 a_i / g = k * x * y
令k=1即可得出 a_i = g * x * y 这里就可以算出每一个可行的解

这个可行解能存在的条件可以是gcd(x,S_i)=1且gcd(y,P_i)=1
即
gcd(p[i-1],lcm(s[i],p[i]))=p[i]
gcd(s[i+1],lcm(s[i],p[i]))=s[i]

#include <bits/stdc++.h>
using namespace std;
main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		long long a[n + 1];
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		long long b[n + 1];
		for (int i = 1; i <= n; i++) {
			cin >> b[i];
		}
		long long ans[n + 1];
		for (int i = n; i >= 1; i--) {
			ans[i] = lcm(a[i], b[i]);
		}
		bool ch = 1;
		if(ans[1] != a[1]) ch = 0;
		if(ans[n] != b[n]) ch = 0;
		for (int i = 2; i <= n; i++) {
			if (__gcd(a[i - 1], ans[i]) != a[i]) {
				ch = 0;
			}
		}
		for (int i = n - 1; i >= 1; i--) {
			if (__gcd(b[i + 1], ans[i]) != b[i]) {
				ch = 0;
			}
		}
		if (ch) {
			cout << "YES" << "\n";
		} else {
			cout << "NO" << "\n";
		}
	}
}

---

get_count - 区间模运算计数

#include<bits/stdc++.h>
using namespace std;
int N, L, R;
const int MOD = 1e9 + 7;
int dp[2][3];
int countt[3];
int prefix_sum[3];
int get_count(long long x, int r) {
	if (x < r) 
		return 0;
	return (x - r) / 3 + 1;
}

int main() {
	scanf("%d%d%d", &N, &L, &R);
	dp[0][0] = 1;
	dp[0][1] = 0;
	dp[0][2] = 0;
	

	for (int r = 0; r < 3; r++) {
		countt[r] = get_count(R, r) - get_count(L-1, r);
	}
	
	int current = 0;
	int next = 1;
	
	for (int i = 1; i <= N; i++) {
		dp[next][0] = dp[next][1] = dp[next][2] = 0;
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				int new_mod = (j + k) % 3;
				dp[next][new_mod] = (dp[next][new_mod] + (long long)dp[current][j] * countt[k]) % MOD;
			}
		}
		current = next;
		next = 1 - next;
	}
	
	printf("%d\n", dp[current][0]);
	return 0;
}

求一个区间内模N的各个数字的个数，最快的办法怎么做？
——用公式计算。
当然可以！让我们来详细分析一下 get_count 函数的作用。

函数定义

int get_count(long long x, int r) {
    if (x < r) 
        return 0;
    return (x - r) / 3 + 1;
}

函数的作用

get_count 函数的作用是计算在范围 ([r, x]) 内，有多少个数除以3的余数等于 (r)。

参数解释

• x：范围的上限。
• r：目标余数，即我们想要计算的数除以3的余数。

返回值

函数返回在范围 ([r, x]) 内，有多少个数除以3的余数等于 (r)。

详细分析

1. 边界条件：

   • 如果 x < r，那么在范围 ([r, x]) 内没有数可以满足条件，因此返回0。

2. 计算公式：

   • 对于范围 ([r, x])，我们需要找出所有满足 (n \mod 3 = r) 的数 (n)。
   • 这些数可以表示为 (n = 3k + r)，其中 (k) 是非负整数。
   • 最小的 (n) 是 (r)，最大的 (n) 是 (x)。
   • 因此，我们需要找出所有满足 (r \leq 3k + r \leq x) 的 (k)。

3. 推导公式：

   • 从 (r \leq 3k + r)，我们得到 (k \geq 0)。
   • 从 (3k + r \leq x)，我们得到 (k \leq \frac{x - r}{3})。
   • 因此，(k) 的取值范围是从0到 (\left\lfloor \frac{x - r}{3} \right\rfloor)。

4. 计算数量：

   • 满足条件的 (k) 的数量是 (\left\lfloor \frac{x - r}{3} \right\rfloor + 1)。

示例

假设 (x = 10)，(r = 1)，我们来计算在范围 ([1, 10]) 内，有多少个数除以3的余数等于1。

• 最小的数是 (1)（即 (3 \times 0 + 1)）。
• 最大的数是 (7)（即 (3 \times 2 + 1)）。
• 满足条件的数是 (1, 4, 7)，共有3个。

使用公式：
[
\left\lfloor \frac{10 - 1}{3} \right\rfloor + 1 = \left\lfloor \frac{9}{3} \right\rfloor + 1 = 3 + 1 = 3
]

代码中的应用

在代码中，get_count 函数用于计算每个模3的结果对应的成色值数量。具体来说：

• countt[r] = get_count(R, r) - get_count(L-1, r);
  • get_count(R, r) 计算在范围 ([0, R]) 内，有多少个数除以3的余数等于 (r)。
  • get_count(L-1, r) 计算在范围 ([0, L-1]) 内，有多少个数除以3的余数等于 (r)。
  • 两者的差值就是范围 ([L, R]) 内，有多少个数除以3的余数等于 (r)。

总结

get_count 函数通过简单的数学推导，快速计算在某个范围内，有多少个数除以3的余数等于某个特定值。这在动态规划的状态转移中非常有用，可以显著减少计算量。