首页 algorithm 算法OJ “钉耙编程”

# 1001 数列计数

1001 数列计数

首先我们来重新理解一遍题目：

对于特定的 i ，它要求找到一个数 b[i]

  • 使得 b[i] < L[i]
  • a[i]a[i] 的每一位都大于 b[i]b[i]

为什么呢？

首先，(aibi)≡1(mod2)\binom{a_i}{b_i}\equiv 1\pmod 2，因为 mod 2 的余数只有 1 和 0 ，要求相乘是 1 ，所以所有的都是 1

根据 lucas 定理

设 pp 是一个素数，nn 和 kk 是非负整数。将 nn 和 kk 表示为 pp 进制数：

n=n0+n1p+n2p2+⋯+nmpmn = n_0 + n_1 p + n_2 p^2 + \dots + n_m p^m

k=k0+k1p+k2p2+⋯+kmpmk = k_0 + k_1 p + k_2 p^2 + \dots + k_m p^m

其中(0≤ni,ki<p)(0 \leq n_i, k_i < p)。那么，组合数 (nk)\binom{n}{k} 模 pp 的值可以通过以下公式计算：

(nk)≡∏i=0m(niki)(modp)\binom{n}{k} \equiv \prod_{i=0}^m \binom{n_i}{k_i} \pmod{p}

如果某个 ki>nik_i > n_i，则 (niki)=0\binom{n_i}{k_i} = 0，因此 (nk)≡0(modp)\binom{n}{k} \equiv 0 \pmod{p}。

那么对于 (ab)≡1(mod2)\binom{a}{b}\equiv 1\pmod 2， mod 2 就相当于把数写成二进制，要求二进制的每一个位数 ai>bia_i > b_i，这样才能使 (ab)≡1(mod2)\binom{a}{b}\equiv 1\pmod 2

接下来就想怎么实现题目的要求呢？

我们可以从高位到低位遍历，为了满足b[i]<L[i]b[i] < L[i] 的条件

  1. 如果前面的所有位数都和 L[i] 是一样的
    • 那么这一位如果 L[i] 是 1，那么就根据 a[i] 判断这一位填 0 还是 0 1 都可以
    • 这一位如果 L[i] 是 0，那么就只能填 0
  2. 如果前面有一位 L[i] 是 1，但是我们填了 0 ，后面就不受 L 的控制了，只需要管 a[i] 的约束即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int vis[32][2], dp[32][2];
int cal(int pos, int strict, int a, int l)
{
	if(pos < 0) return 1;
	
	if(vis[pos][strict]) return dp[pos][strict];
	vis[pos][strict] = 1;
	int& res = dp[pos][strict];
	res = 0;
	
	bool ba = (a >> pos) & 1;
	bool bl = (l >> pos) & 1;
	if(strict)
	{
		if(bl == 1)
		{
			if(ba == 1)
			{
				res += cal(pos - 1, 0, a, l);
				res += cal(pos - 1, 1, a, l);
			}
			else
				res += cal(pos - 1, 0, a, l);
		}
		else
		{
			res += cal(pos - 1, 1, a, l);	
		}
	}
	else
	{
		if(ba == 1)
		{
			res += cal(pos - 1, 0, a, l);
			res += cal(pos - 1, 0, a, l);
		}
		else
		{
			res += cal(pos - 1, 0, a, l);
		}
	}
	return res;
}
void solve()
{
	int n;
	cin >> n;
	vector<int> a(n + 1), l(n + 1);
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) cin >> l[i];
	int ans = 1;
	for(int i = 1; i <= n; i++)
	{
		if(l[i] >= a[i]) 
		{
			int num1 = 0; 
			while(a[i])
			{
				num1 += a[i] % 2;
				a[i] /= 2;
			}
			ans = ans * (1 << num1) % mod;
		}
		else
		{
			memset(vis, 0, sizeof vis);
			int res = cal(31, 1, a[i], l[i]);
			ans = ans * res % mod;
		}
	}
	cout << ans;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1; cin >> t;
	while(t--) solve();
	return 0;
}

# 1003 拼尽全力

1003 拼尽全力

贪心

重点是对于优先队列的使用

  1. 我们记录对于每家公司，有多少维度是当前达不到的；如果所有的都可以达到，那么就可以加入选择队列
  2. 对每一个维度，我们用优先队列记录当前最低的要求，每次选择公司之后更新每个维度的能力，然后和这个维度的加入优先队列的要求做比较。如果能力大于要求，就可以剔除该要求，并相应减少这届公司的不达标记录
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> a(m + 1);
	for(int i = 1; i <= m; i++) cin >> a[i];
	vector<vector<int>> c(n + 1, vector<int>(m + 1)), w(n + 1, vector<int>(m + 1));
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++) cin >> c[i][j];
		for(int j = 1; j <= m; j++) cin >> w[i][j];
	}
	
	vector<int> err(n + 1);//记录每家公司还有多少指标没有达成
	vector<priority_queue<PII, vector<PII>, greater<PII>>> qf(m + 1);//小根堆，待完成的指标
	queue<int> qt;//全部指标达标的公司
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(c[i][j] > a[j]) err[i]++;
			qf[j].push({c[i][j], i});	
		}
		if(err[i] == 0) qt.push(i);	
	}
	int cnt = 0;
	while(qt.size())
	{
		cnt++;
		int i = qt.front();
		qt.pop();
		for(int j = 1; j <= m; j++)
		{
			a[j] += w[i][j];
			while(qf[j].size() && a[j] >= qf[j].top().first)
			{
				int t = qf[j].top().second;
				err[t]--;
				if(err[t] == 0) qt.push(t);
				qf[j].pop(); 
			}
		}
	}
	cout << (cnt == n ? "YES" : "NO")<< '\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1; cin >> t;
	while(t--) solve();
	return 0;
}

# 1004 弯曲的筷子

1004 弯曲筷子

显然我们需要对筷子的弯曲程度进行排序

那么对于必选的筷子我们的选择可以分两种情况

  1. 选择相邻的两根筷子
  2. 如果两个必选的筷子恰好间隔一个，那么我们也可以选择直接选这两根必选的筷子

那如果两根必选的筷子之间间隔两个，我们能否也直接取这两根筷子呢？

答案是 不能！

因为对于 a<b<c<da < b <c < d，我们可以证明 (d−a)2>(d−c)2+(b−a)2(d - a)^2>(d-c)^2+(b-a)^2

而对于只间隔一个，因为中间的一个不能被重复选，所以需要考虑是否要跳过中间那个

那么接着考虑，dpdp 状态转移方程是什么呢？

  1. 如果 i−1i - 1 必选，那么对于第 ii 根筷子

    1
    2
    dp[i][0] = dp[i - 1][1];
    dp[i][1] = dp[i - 1][0] + pw(a[i].x- a[i - 1].x);

  2. 如果第 i−1i - 1 可选可不选，那么对于第 ii 根筷子，它可以从 i−1i - 1 转移，也可以从 i−2i - 2 转移

    1
    2
    dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]);
    dp[i][1] = min(dp[i - 1][0] + pw(a[i].x - a[i - 1].x), dp[i - 2][0] + pw(a[i].x - a[i - 2].x));

注意：如果 vector<array<int, 2>> dp(n + 1, {INF, INF}) 开大了会 TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 3e5 + 10, INF = 1e18;
struct info
{
	int x;
	int st = 0;
};
int pw(int x)
{
	return x * x;
}
void solve()
{
	int n, m;
	cin >> n >> m;
	vector<info> a(n + 1);
	vector<array<int, 2>> dp(n + 1, {INF, INF});
	for(int i = 1; i <= n; i++) cin >> a[i].x;
	for(int i = 1; i <= m; i++) 
	{
		int x; cin >> x;
		a[x].st = 1;
	}
	sort(a.begin() + 1, a.end(), [&](info u, info v){
		return u.x < v.x;
	});
	dp[1][0] = 0;
	if(!a[1].st) dp[2][0] = 0;
	dp[2][1] = dp[1][0] + pw(a[2].x - a[1].x);
	for(int i = 3; i <= n; i++)
	{
		if(a[i - 1].st)//i - 1必选 
		{
			dp[i][0] = dp[i - 1][1];
			dp[i][1] = dp[i - 1][0] + pw(a[i].x- a[i - 1].x);
		}
		else
		{
			dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]);
			dp[i][1] = min(dp[i - 1][0] + pw(a[i].x - a[i - 1].x), dp[i - 2][0] + pw(a[i].x - a[i - 2].x));
		}
	}
	int ans = dp[n][1];
	if(!a[n].st) ans = min(ans, dp[n][0]);
	cout << ans <<'\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1; cin >> t;
	while(t--) solve();
	return 0;
}

# 1005 修复公路

1005 修复公路

直接利用并查集即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10;
int f[N];
int find(int x)
{
	if(x != f[x]) f[x] = find(f[x]);
	return f[x];
}
void merge(int x, int y)
{
	int fx = find(x), fy = find(y);
	if(fx != fy) f[fy] = fx;
}
void solve()
{
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for(int i = 1; i <= n; i++) f[i] = i;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		if(i + a[i] <= n) merge(i, i + a[i]);
		if(i - a[i] >= 1) merge(i, i - a[i]);
	}
	int ans = 0;
	for(int i = 1; i <= n; i++)
	{
		if(f[i] == i) ans++;
	}
	cout << ans - 1 << '\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1; cin >> t;
	while(t--) solve();
	return 0;
}

# 1007 宝石商店

1007 宝石商店

首先我们将式子 (ai∨x)⊕(ai∧x)(a_i\vee x) \oplus(a_i\wedge x) 化简，其实要求的就是 ai⊕xa_i\oplus x 的最大值

那么显然对于异或最大值，利用 TrieTrie 树求解就好

具体可看 143. 最大异或对 - AcWing 题库

那么这个题就多要求了需要异或的节点在 [l,r][l,r] 之间

要怎么实现呢？

我们可以给每个节点标记它来源于哪个数，再判断这个数是否在 [l,r][l,r] 中

因为一个节点可能来自多个数（树上的一个节点可能被多个节点走过），所以需要利用数组存储

然后用二分查找，是否存在一个数在 [l,r][l,r] ，并且那一位是 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10, M = N * 30;
int son[M][2], idx;
vector<vector<int>> indices(M); // 存储每个节点对应的数字索引

void insert(int x, int id) 
{
    int p = 0;
    indices[p].push_back(id);
    for(int i = 29; i >= 0; i--) 
	{
        int u = (x >> i) & 1;
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
        indices[p].push_back(id);
    }
}

bool has_index_in_range(int p, int l, int r) 
{
    auto& vec = indices[p];
    auto it = lower_bound(vec.begin(), vec.end(), l);
    return it != vec.end() && *it <= r;
}

int query(int l, int r, int x) 
{
    int p = 0, res = 0;
    for(int i = 29; i >= 0; i--) 
	{
        int u = (x >> i) & 1;
        
        // 优先选择相反的位
        if(son[p][!u] && has_index_in_range(son[p][!u], l, r)) 
		{
            p = son[p][!u];
            res = res * 2 + 1;
        } 
        else if(son[p][u] && has_index_in_range(son[p][u], l, r)) 
		{
            p = son[p][u];
            res = res * 2;
        } 
        else 
		{
            return -1; // 没有满足条件的数字
        }
    }
    return res;
}

void solve() 
{
    // 重置全局变量
    memset(son, 0, sizeof son);
    for(auto& v : indices) v.clear();
    idx = 0;
    
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i < n; i++) 
	{
        cin >> a[i];
        insert(a[i], i + 1); 
    }
    
    // 预处理排序所有indices以便二分查找
    for(auto& v : indices) 
	{
        sort(v.begin(), v.end());
    }
    
    while(q--) 
	{
        int l, r, x;
        cin >> l >> r >> x;
        cout << query(l, r, x) << '\n';
    }
}

signed main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

# 1009 部落冲突

1009 部落冲突

哦～真是让人迷糊的小题目

我迟早要被这些部落和野蛮人绕晕😣

首先我们需要分清，这个题目中有两个元素，一个是部落，另一个是人

其中有个非常特别的操作 33，他需要交换两个部落，显然我们不能实际交换部落，只能交换部落的编号

我们将实际交换之后的部落叫 “真部落”，只是编号交换的部落叫 “假部落”

那么题目询问中出现的都是 “真部落”

那么我们就需要以下几个数组：

  1. id[x] ：真部落 →\rightarrow 假部落的映射，即如果交换部落 a 和 b ，交换 id[a] 和 id[b] 即可
  2. uid[x] ：假部落 →\rightarrow 真部落的映射，即如果要求当前部落实际在哪个部落里，那么就用 uid ；在交换部落之后 uid 的对应关系也会改变，所以也需要交换。因为题目中给的是真部落，所以我们先用 id[a] 变成假部落，再 swap(uid[id[a]], uid[id[b]])
  3. f[x] ：表示每个部落的父部落，用于部落的合并
  4. g[x] ：表示每个野蛮人所在的部落，用于野蛮人修改部落

接下来对几个操作进行理解：

  1. 合并两个部落：
    • 首先我们需要将真部落变成假部落，利用 id[x]
    • 然后将假部落的 f[x] 进行修改
  2. 修改野蛮人部落：
    • 首先找到题目给的真部落对应的假部落
    • 修改野蛮人所在部落 g[x]
  3. 交换两个部落：
    • 交换两个真部落的假部落
    • 交换两个假部落的真部落编号
  4. 查找某个野蛮人所在部落：
    • 利用 g[x] 找到当前野蛮人所在部落
    • 利用 find(g[x]) 找到当前部落的父部落（假部落）
    • 找到父部落对应的真部落
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int f[N], id[N], uid[N], g[N];
int n, q;
int find(int x)
{
	if(x != f[x]) f[x] = find(f[x]);
	return f[x];
}
void merge(int x, int y)
{
	int fx = find(x), fy = find(y);
	if(fx != fy) f[fy] = fx;
}
void solve()
{
	cin >> n >> q;
	for(int i = 1; i <= n; i++) f[i] = id[i] = uid[i] = g[i] = i;
	while(q--)
	{
		int op; cin >> op;
		int a, b;
		if(op == 1)
		{
			cin >> a >> b;
			int fa = id[a], fb = id[b];
			merge(fa, fb);
		}
		else if(op == 2)
		{
			cin >> a >> b;
			int fb = id[b];
			g[a] = fb;
		}
		else if(op == 3)
		{
			cin >> a >> b;
			swap(id[a], id[b]);
			swap(uid[id[a]], uid[id[b]]);
		}
		else
		{
			cin >> a;
			int fa = find(g[a]);
			cout << uid[fa] << '\n'; 
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1; cin >> t;
	while(t--) solve();
	return 0;
}

# 1010 选择配送

1010 选择配送

对于曼哈顿距离，最常见的方法就是转换成切比雪夫距离

曼哈顿距离与切比雪夫距离的互化 - SGCollin - 博客园

对于曼哈顿距离的计算公式

d=∣x1−x2∣+∣y1−y2∣⇒d=max(x1−x2+y1−y2,x1−x2+y2−y1,x2−x1+y1−y2,x2−x1+y2−y1)d = |x_1-x_2|+|y_1-y_2|\\ \Rightarrow d =max(x_1-x_2+y_1-y_2,x_1-x_2+y_2-y_1,x_2-x_1+y_1-y_2,x_2-x_1+y_2-y_1)\\

假设我们令X=x+y,Y=x−yX = x+y,Y=x-y

那么曼哈顿距离可以转换成

d=max(X1−X2,Y1−Y2,Y2−Y1,X2−X1)⇒d=max(∣X1−X2∣,∣Y1−Y2∣)d=max(X_1-X_2,Y_1-Y_2,Y_2-Y_1,X_2-X_1)\\ \Rightarrow d= max(|X_1-X_2|,|Y_1-Y_2|)

我们将A(x1,y1),B(x2,y2)A(x_1,y_1),B(x_2,y_2) 转换成A′(x1+y1,x1−y1),B′(x2+y2,x2−y2)A'(x_1+y_1,x_1-y_1),B'(x_2+y_2,x_2-y_2)

那么求 AA 和 BB 的曼哈顿距离可以转换成 max(XA′−XB′,YA′−YB′)max(X_{A'}-X_{B'},Y_{A'}-Y_{B'})

我们可以列出客户的最小和最大的Xmin,Xmax,Ymin,YmaxX_{min},X_{max},Y_{min},Y_{max}，那么我们只需枚举每个配送站的X′,Y′X',Y'，最远的距离就是 max(X′−Xmin,Y′−Ymin,Xmax−X′,Ymax−Y′)max(X'-X_{min},Y'-Y_{min},X_{max}-X',Y_{max}-Y')

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;

void solve() 
{
    int n, m;
    cin >> n >> m;

    int ming_X = LLONG_MAX, maxg_X = LLONG_MIN;
    int ming_Y = LLONG_MAX, maxg_Y = LLONG_MIN;

    for (int i = 1; i <= n; i++) 
	{
        int x, y;
        cin >> x >> y;
        ming_X = min(ming_X, x + y);
        maxg_X = max(maxg_X, x + y);
        ming_Y = min(ming_Y, x - y);
        maxg_Y = max(maxg_Y, x - y);
    }
	int ans = 2e9 +10;
    for (int i = 1; i <= m; i++) 
	{
        int x, y;
        cin >> x >> y;
        ans = min(ans, max({x + y - ming_X, maxg_X - x - y, x - y - ming_Y, maxg_Y - x + y}));
    }
    cout << ans << '\n';
}

signed main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}