首页 algorithm 算法竞赛 蓝桥杯

# 填空题

# 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
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define int long long
signed main()
{
	int res = 0;
	for(int i = 1; i <= 100000000; i++)
	{
	  int t = i, s = 0;
	  vector<int> a(20);
	  while(t)
	  {
		a[s++] = t % 10;
		t /= 10;
	  }
	  int ans1 = 0, ans2 = 0;
	  if(s % 2 == 0)
	  {
	  	for(int j = 0; j < s / 2; j++) ans1 += a[j];
	  	for(int j = s / 2; j < s; j++) ans2 += a[j];
	  	if(ans1 == ans2) res++;	
	  }
	}
	cout << res;//4430091
	return 0;
}

# 2 有奖问答

暴力 dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define int long long
using namespace std;
int ans = 0;
void dfs(int i, int s)//题数和分数 
{
    //注意是先判断分数，再判断是否结束
	if(s == 70) ans++;
	if(i == 30 || s == 100) return;
	
	dfs(i + 1, s + 10);
	dfs(i + 1, 0);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	dfs(0, 0);
	cout << ans;//8335366
	return 0;
}

Dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[35][150];//前i道题 分数为j 的方案数 
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	dp[0][0] = 1;//初始化答0题得0分的方案数是1
	for(int i = 1; i <= 30; i++)
	{
		for(int j = 0; j <= 100; j += 10)
		{
			if(j < 100) dp[i][0] += dp[i - 1][j];//第i道题答错，上一道题的分数不能是100 
			if(j > 0) dp[i][j] += dp[i - 1][j - 10];//第i道题答对，答完后不能是0分 
		}
	}
	int res = 0;
	for(int i = 0; i <= 30; i++) res += dp[i][70];
	cout << res;
	return 0;
}

# 程序题

# 3 平方差

高精度模版题

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
#define int long long
using namespace std;
class bigint
{
private:
	string value;
public:
	int cmp(const bigint& other) const
	{
		if(value.length() != other.value.length()) return value.length() < other.value.length() ? -1 : 1;
		return value.compare(other.value);
	}
	bigint(const string& s = "0")
	{
		value = s;
	}
	//加法 
	bigint operator+(const bigint& other) const
	{
		string result;
		int carry = 0;
		int i = value.size() - 1, j = other.value.size() - 1;
		while(i >= 0 || j >= 0 || carry > 0)
		{
			int sum = carry;
			if(i >= 0) sum += value[i--] - '0';
			if(j >= 0) sum += other.value[j--] - '0';
			carry = sum / 10;
			result.push_back(sum % 10 + '0');
		}
		reverse(result.begin(), result.end());
		return bigint(result);
	}
	//减法
	bigint operator-(const bigint& other) const
	{
		string result;
		int borrow = 0;
		int i = value.length() - 1, j = other.value.length() - 1;
		while(i >= 0 || j >= 0)
		{
			int diff = borrow;
			if(i >= 0) diff += value[i--] - '0';
			if(j >= 0) diff -= other.value[j--] - '0';
			if(diff < 0)
			{
				diff += 10;
				borrow = -1; 
			}
			else borrow = 0;
			result.push_back(diff + '0');
 		}
 		reverse(result.begin(), result.end());
 		result.erase(0, result.find_first_not_of('0'));
 		if(result.empty()) result = "0";
 		return bigint(result);
	}
	//乘法
	bigint operator*(const bigint& other) const
	{
		string result(value.length() + other.value.length(), '0');
		for(int i = value.length() - 1; i >= 0; i--)
		{
			int carry = 0;
			for(int j = other.value.length() - 1; j >= 0; j--)
			{
				int temp = (value[i] - '0') * (other.value[j] - '0') + carry + (result[i + j + 1] - '0');
				carry = temp / 10;
				result[i + j + 1] = temp % 10 + '0';//得到的数从1开始 
			}
			result[i] += carry;//进位 
		}
		result.erase(0, result.find_first_not_of('0'));
		if(result.empty()) result = "0";
		return bigint(result);
	} 
	//除法
	bigint operator/(const bigint& other)const
	{
		if(other.value == "0")  throw runtime_error("Division by zero");
		if(cmp(other) < 0) return bigint("0");
		string result;
		bigint temp("0");
		for(char digit: value)
		{
			temp = temp * bigint("10") + bigint(string(1, digit));
			int count = 0;
			while(temp.cmp(other) > 0)
			{
				temp = temp - other;
				count++;
			}
			result.push_back(count + '0');
		}
		result.erase(0, result.find_first_not_of('0'));
		if(result.empty()) result = "0";
		return bigint(result);
 	} 
 	friend ostream& operator<<(ostream& os, const bigint& num)
 	{
 		os << num.value;
 		return os;
	 }
};
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	string a, b;
	cin >> a >> b;
    if(a[0] == '-') a.erase(a.begin());
    if(b[0] == '-') b.erase(b.begin());
	bigint x(a), y(b);
	if(a.length() > b.length() || (a.length() == b.length() && a.compare(b) > 0))
		cout << x * x - y * y << '\n';
	else 
		cout << '-' << y * y - x * x << '\n';
	return 0;
}

# 4 更小的数

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int main()
{
  string s;
  cin >> s;
  int ans = 0;
  for(int i = 0; i < s.size(); i++)
  {
      for(int j = i + 1; j < s.size(); j++)
      {
        int l = i, r = j;
        while(l < r && s[l] == s[r])
        {
            l++, r--;
        }
        if(l >= r || s[l] - '0' < s[r] - '0') continue;
        else ans++;
      }
  }
  cout << ans;
  return 0;
}

# 5 颜色平衡树

数据结构：

1
2
3
4
5
6
struct Node 
{
    int color; //该节点的颜色
    vector<int> child; //该节点的孩子节点
    unordered_map<int, int> color_cnt;//每种颜色的个数 
};

启发式合并：每次将小的树合并到大的树上

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200010;

struct Node 
{
    int color; 
    vector<int> child; 
    unordered_map<int, int> color_cnt; 
};

Node node[N];
int ans = 0;

// 启发式合并函数
void merge(unordered_map<int, int>& a, unordered_map<int, int>& b) 
{
    if (a.size() < b.size()) swap(a, b); 
    for (auto& [color, cnt] : b) 
    {
        a[color] += cnt; 
    }
    b.clear();
}

// DFS 遍历树
void dfs(int u) 
{
    for (int v : node[u].child) 
    {
        dfs(v); 
        merge(node[u].color_cnt, node[v].color_cnt); 
    }
    node[u].color_cnt[node[u].color]++; 

    bool flag = true;
    int cnt = -1;
    for (auto& [color, num] : node[u].color_cnt) 
    {
        if (cnt == -1) cnt = num; 
        else if (cnt != num) 
        { 
            flag = false;
            break;
        }
    }
    if (flag) ans++; 
}

signed main() 
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) 
    {
        int color, parent;
        cin >> color >> parent; 
        node[i].color = color;
        if (parent != 0) node[parent].child.push_back(i); 
    }

    dfs(1);
    cout << ans << endl;
    return 0;
}

# 6 卖瓜

预处理：将瓜的重量 *2

贪心：从最大的开始取

dfs 会 TLE，注意剪枝：

  1. 当前枚举情况大于曾经的最好的值，退出
  2. 如果取的值大于需要的 m 或者 即使取出后面的所有仍然小于 m，退出
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
vector<int> a(50), last(50);
int ans = 50;
void dfs(int sum, int i, int cnt)
{
	if(cnt >= ans) return;
    if(sum == m) ans = min(ans, cnt);
    if(i > n || sum >= m || sum + last[i] < m) return;

    dfs(sum + a[i], i + 1, cnt);//取一整个
    dfs(sum + a[i] / 2, i + 1, cnt + 1);//取一半
    dfs(sum, i + 1, cnt);//不取
}
signed main()
{
  cin >> n >> m;
  m <<= 1;//为了消除小数点的影响
  for(int i = 1; i <= n; i++) cin >> a[i], a[i] <<= 1;
  sort(a.begin() + 1, a.begin() + n + 1, greater<int>());
  for(int i = n; i >= 1; i--)
      last[i] = last[i + 1] + a[i];

  dfs(0, 1, 0);
  if(ans == 50) cout << -1;
  else cout << ans;
  return 0;
}

# 7 网络稳定性

Kruskal：找到最大生成树，因为要求找到稳定性最大的那条，而所有的两个节点一定可以通过这个最大生成树连接，且一定是最大的

LCA：找到两个节点到最近公共祖先的 “稳定性”，分别为 a,b ，则两个节点的稳定性为 min(a, b)

利用树上倍增：维护 cost 数组，找到两个节点之间的最小权重边， cost[u][i] = min(cost[u][i - 1], cost[dp[u][i - 1]][i - 1])

可能有多个连通块，dfs 需要从多个根节点开始；kruskal 不能以找到 n - 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
93
94
95
96
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 3e5 + 10;
int n, m, q;
struct Edge
{
    int w;
    int to, pre;
}edge[N];
bool cmp(Edge& x, Edge& y)
{
	return x.w > y.w;
}
vector<PII> tree[N];
int fa[N];
int find(int x)
{
	if(x != fa[x]) fa[x] = find(fa[x]);
	return fa[x];
}
void kruskal()
{
	for(int i = 1; i <= m; i++)
	{
		int fx = find(edge[i].pre), fy = find(edge[i].to);
		if(fx != fy)
		{
			fa[fx] = fy;
			tree[edge[i].pre].push_back({edge[i].to, edge[i].w});
			tree[edge[i].to].push_back({edge[i].pre, edge[i].w});
		}
	}
}
int dep[N], dp[N][20], cost[N][20], vis[N];
void dfs(int u, int p)
{
	vis[u] = 1;
	dep[u] = dep[p] + 1;
	dp[u][0] = p;
	for(int i = 1; i < 20; i++) 
	{
		dp[u][i] = dp[dp[u][i - 1]][i - 1];
		cost[u][i] = min(cost[u][i - 1], cost[dp[u][i - 1]][i - 1]);	
	}
	for(auto t: tree[u])
	{
		int child = t.first, c = t.second;
		if(child != p)
		{
			cost[child][0] = c;
			dfs(child, u);
		}
	}
}
int lca(int x, int y)
{
	int ans = 1e18;
	if(dep[x] < dep[y]) swap(x, y);
	int d = dep[x] - dep[y];
	for(int i = 0; i < 20; i++) 
		if((1 << i) & d) 
		{
			ans = min(ans, cost[x][i]);
			x = dp[x][i];
		}
	if(x == y) return ans;
	for(int i = 20 - 1; i >= 0; i--)
	{
		if(dp[x][i] != dp[y][i])
		{
			ans = min(ans, min(cost[x][i], cost[y][i]));
			x = dp[x][i], y = dp[y][i];
		}
	}
	ans = min(ans, min(cost[x][0], cost[y][0]));
	return ans;
}
int main()
{
	cin >> n >> m >> q;
	for(int i = 1; i <= m; i++) cin >> edge[i].pre >> edge[i].to >> edge[i].w;
	sort(edge + 1, edge + 1 + m, cmp);
	for(int i = 1; i <= n; i++) fa[i] = i;
	kruskal();
	for(int i = 1; i <= n; i++) if(!vis[i]) dfs(i, 0);//可能有多个连通块	
	while(q--)
	{
		int x, y;
		cin >> x >> y;
		int fx = find(x), fy = find(y);
		if(fx != fy) cout << -1 << '\n';
		else cout << lca(x, y) << '\n';
	}
    return 0;
}

# 8 异或和之和

首先利用异或前缀和，将最后的结果用 ans += a[j] ^ a[i - 1] 得到，这样可以过 8 / 10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i], a[i] = a[i] ^ a[i - 1];
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = i; j <= n; j++)
        {
            ans += a[j] ^ a[i - 1];
        }
    }
    cout << ans;
    return 0;
}

因为只需要两个值的异或即 a[j], a[i - 1] ，那么就可以利用二进制，计算每一位 0 和 1 的个数。

对于第 i 位， cnt[i][0] 和 cnt[i][1] 分别表示 0 和 1 的个数，那么最后的结果这一位为 1 的情况有 cnt[i][0] * cnt[i][1] 个，而这一位对结果的贡献是 1 << i ，所以最后的总贡献为 cnt[i][0] * cnt[i][1] * (1 << i)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define int long long
using namespace std;
int cnt[25][2];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	vector<int> a(n + 1);
	memset(cnt, 0, sizeof(cnt));
	for(int i = 1; i <= n; i++) cin >> a[i], a[i] ^= a[i - 1];
	int ans = 0;
	for(int i = 0; i < 25; i++)//位数
        for(int j = 0; j <= n; j++)
            cnt[i][(a[j] >> i) & 1]++;
    for(int i = 0; i < 25; i++)
        ans += cnt[i][0] * cnt[i][1] * (1 << i);
	cout << ans;
	return 0;
}

# 9 像素放置

dfs 暴力即可

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 15;
int n, m;
char g[N][N];
int ans[N][N], st[N][N];
bool check(int x, int y)
{
	if(g[x][y] == '_') return true;
	int cnt = 0;
	for(int i = x - 1; i <= x + 1; i++)
		for(int j = y - 1; j <= y + 1; j++)
			cnt += ans[i][j];
	if(cnt == g[x][y] - '0') return true;
	else return false;
}
void dfs(int x, int y)
{
	ans[x][y] = 0;
	int ok = 1;
	if(x > 1 && y > 1) ok &= check(x - 1, y - 1);
	if(x > 1 && y == m) ok &= check(x - 1, y);
	if(x  == n && y > 1) ok &= check(x, y - 1);
	if(x == n && y == m) ok &= check(x, y);
	if(ok)
	{
		if(x == n && y == m)
		{
			for(int i = 1; i <= n; i++)
			{
				for(int j = 1; j <= m; j++)
					cout << ans[i][j];
				cout << endl;
			}
			exit(0);
		}
		if(y == m) dfs(x + 1, 1);
		else dfs(x, y + 1);
	}
	ans[x][y] = 1;
	ok = 1;
	if(x > 1 && y > 1) ok &= check(x - 1, y - 1);
	if(x > 1 && y == m) ok &= check(x - 1, y);
	if(x  == n && y > 1) ok &= check(x, y - 1);
	if(x == n && y == m) ok &= check(x, y);
	if(ok)
	{
		if(x == n && y == m)
		{
			for(int i = 1; i <= n; i++)
			{
				for(int j = 1; j <= m; j++)
					cout << ans[i][j];
				cout << endl;
			}
			exit(0);
		}
		if(y == m) dfs(x + 1, 1);
		else dfs(x, y + 1);
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> g[i][j];
	dfs(1, 1);
	return 0;
}