阿里笔试0427
编程题总体难度还好，成功AK，下面是大概思路和代码（代码细节可能有错，也可进一步优化，仅供参考）
T1
- 构造题。当大小为2的连通图能够刚好填满a行或者b列的时候才有答案，否则一定会出现一个大小至少为3的连通块。优先构造大小为2的连通图。
/*
** Created by Wangjy.
*/
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
if(k % m != 0 && k % n != 0) {
cout << -1 << '\n';
return 0;
}
vector<vector<int>> res(n, vector<int>(m));
// 大小为2的连通图填满每一行的前2 * a列
if(k % n == 0) {
int a = k / n;
for(int i = 0;i < n;i++) {
// 第一个for循环填大小为2的连通块
for(int j = 0;j < a;j++) {
// 需要找规律，连续的两个位置都填一样的数字
if(i % 2 == j % 2) {
res[i] = 1;
res[i][j + 1] = 1;
}
}
// 填剩下的大小为1的连通块，只需要和前一个不一样即可
for(int j = a * 2;j < m;j++) {
if(j - 1 >= 0) {
res[i][j] = 1 - res[i][j - 1];
}
else {
res[i][j] = 1;
}
}
}
}
// 大小为2的连通图填满每一列的前2 * a行, 思路和上面的情况一样
else {
int a = k / m;
for(int j = 0;j < m;j++) {
for(int i = 0;i < a;i++) {
if(i % 2 == j % 2) {
res[2 * i][j] = 1;
res[2 * i + 1][j] = 1;
}
}
for(int i = 2 * a;i < n;i++) {
if(i - 1 >= 0) {
res[i][j] = 1 - res[i - 1][j];
}
else {
res[i][j] = 1;
}
}
}
}
// 输出答案
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) {
cout << res[i][j];
}
cout << '\n';
}
return 0;
}
T2
- 贡献法，统计连续的最长的“长城”的长度并设为len，如果len >= 2，那么这个序列中的每个长度大于等于2的连续子数组都是“长城”，累加到答案中即可。
/*
** Created by Wangjy.
*/
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for(int i = 0;i < n;i++) {
cin >> a[i];
}
// 注意使用int可能会溢出
// 长度为1的也算长城
long long res = n;
if(n >= 2 && a[i] != a[i - 1]) {
res++;
}
// 当前长城的长度
int len = 2;
for(int i = 2;i < n;i++) {
// 特判长度为2的序列是不是长城
if(a[i] != a[i - 1]) {
res++;
}
if(a[i] != a[i - 1] && a[i] == a[i - 2]) {
len++;
}
else {
if(len > 2) {
res += (long long) (len - 2) * (len - 1) / 2;
len = 2;
}
}
}
// 遍历结束后需要特判，不然可能会漏掉最后一个符合条件的序列
if(len > 2) {
res += (long long) (len - 2) * (len - 1) / 2;
len = 2;
}
cout << res << '\b';
return 0;
}
T3
- 并查集 + 克鲁斯卡尔算法求最小生成树。尽量去掉权值大的边等价于尽量留下权值较小的边，直接转化为求最小生成树的问题。另外题目中还有限制删除的边的数量不能超过k，所以还需要判断除了生成树中的边之外，是否还有其他的边不能够被删除。
/*
** Created by Wangjy.
*/
#include<bits/stdc++.h>
using namespace std;
// 并查集模板
struct DSU {
vector<int> p, r;
DSU(int n) : p(n), r(n, 0) {iota(p.begin(), p.end(), 0);}
int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if(r[x] < r[y]) {
p[x] = p[y];
}
else {
p[y] = p[x];
}
if(x != y && r[x] == r[y]) {
r[x]++;
}
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> g(m, vector<int>(3));
// 总的边的权值
long long s = 0;
for(int i = 0;i < m;i++) {
cin >> g[i][0] >> g[i][1] >> g[i][2];
s += g[i][2];
}
DSU dsu(n + 1);
sort(g.begin(), g.end(), [&](vector<int>& a, vector<int>& b) {return a[2] < b[2];});
// 标记哪条边被加入到最小生成树中
vector<bool> fs(m + 1, false);
for(int i = 0;i < m;i++) {
int u = g[i][0], v = g[i][1], w = g[i][2];
if(dsu.find(u) != dsu.find(v)) {
dsu.merge(u, v);
// 如果这条边被加到最小生成树中，就减去这条边的权值
s -= w;
fs[i] = true;
}
}
// 剩余多少条边不在最小生成树中
int c = m - n + 1;
for(int i = 0;i < m;i++) {
// 如果还需要添加边到最小生成树中并且当前边不在最小生成树中，就把这条边的权值也减去
if(c > k && !fs[i]) {
s -= g[i][2];
c--;
}
}
cout << s << '\n';
return 0;
}
查看10道真题和解析
投递联想等公司10个岗位 >