第41次CCF计算机软件能力认证(CSP)＜题解＞
smqyOJ Judge((10/10) + (22/22) + (23/23) + (13/25) + (24/50))
仓库地址
Q1 平衡数
Q1 算法思路
- 模拟即可，
solve(x)统计 x 的二进制表示中0和1的个数，判断是否相等 - 该题解可以通过 smqyOJ (10/10)的测试点
Q1 代码实现
#include <bits/stdc++.h>
using namespace std;
int n, ans;
bool solve(int x)
{
int n0 = 0, n1 = 0;
while (x)
{
if (x & 1) n1 ++;
else n0 ++;
x >>= 1;
}
if (n0 == n1) return true;
else return false;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++)
{
int x;
cin >> x;
bool flag = solve(x);
if (flag) ans ++;
}
cout << ans << endl;
return 0;
}
Q2 机器人项目管理
Q2 算法思路(demo1, WA)
- 贪心处理，
cost统计每个任务的单位咖啡的减时效果，降序处理后，优先处理单位咖啡减时效果大的任务 - 处理任务时，考虑两种情况：灵活型任务和普通型任务
- 该题解可以通过 smqyOJ (18/22)的测试点，得分 82 分
Q2 代码实现(demo1, WA)
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
typedef pair<int, int> PII;
double n, m;
struct Task
{
int o;
double t, a, b;
}task[N];
struct Cost
{
int idx;
double c;
bool operator < (const struct Cost e)
{
return c > e.c;
}
}cost[N];
bool st[N]; // st[i] 标记 是否是灵活性任务
int main()
{
cin >> n >> m;
double time = 0;
for (int i = 0; i < n; i ++)
{
cin >> task[i].o >> task[i].t >> task[i].a >> task[i].b;
time += task[i].t;
cost[i].idx = i;
cost[i].c = task[i].b / task[i].a;
if (task[i].o == 0) st[i] = true;
else st[i] = false;
}
sort(cost, cost + (int)n);
for (int i = 0; i < n; i ++)
{
if (m <= 0) break;
int index = cost[i].idx;
if (st[index]) // 灵活型
{
double v = min(m, task[index].a);
m -= v;
time -= v * cost[i].c;
}
else // 普通型
{
if (m >= task[index].a)
{
m -= task[index].a;
time -= task[index].b;
}
}
}
printf("%.6lf\n", time);
return 0;
}
Q2 算法思路(demo2, AC)
- 灵活型任务是允许分割的任务，对应经典的部分背包问题，采用贪心解法（按性价比降序排列优先选择）即可
- 普通型任务是不可分割的任务，对应经典的0-1背包问题，采用动态规划解法
- 该题解可以通过 smqyOJ (22/22)的测试点，得分 100 分
前述的 demo1 代码中，贪心处理了所有任务，导致部分测试点无法通过。反例如下所示：
假设你现在的咖啡预算是
m
=
10
m = 10
m=10。
有 3 个普通型任务：
任务 A：耗咖啡
a
=
6
a = 6
a=6，减时
b
=
12
b = 12
b=12。性价比：
12
/
6
=
2.0
12 / 6 = 2.0
12/6=2.0
任务 B：耗咖啡
a
=
5
a = 5
a=5，减时
b
=
9
b = 9
b=9。性价比：
9
/
5
=
1.8
9 / 5 = 1.8
9/5=1.8
任务 C：耗咖啡
a
=
5
a = 5
a=5，减时
b
=
9
b = 9
b=9。性价比：
9
/
5
=
1.8
9 / 5 = 1.8
9/5=1.8
按照贪心逻辑：优先把性价比最高的任务 A 拿走，消耗 6 杯咖啡，减时 12。剩余咖啡
10
−
6
=
4
10 - 6 = 4
10−6=4 杯。剩下的 4 杯咖啡不够执行任务 B 或 C（因为是普通型，必须
≥
5
\ge 5
≥5 杯才能起效）。贪心最终结果：总减时 = 12。
而实际上的最优解：放弃任务 A，直接选择任务 B 和任务 C。消耗
5
+
5
=
10
5 + 5 = 10
5+5=10 杯咖啡，刚好用完。最优解结果：总减时 =
9
+
9
=
18
9 + 9 = 18
9+9=18。
Q2 代码实现(demo2, AC)
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int n, m;
struct Task
{
double t, a, b;
};
struct Task task0[N];
struct Task task1[N];
struct Cost
{
int idx;
double c;
bool operator < (const struct Cost &e)
{
return c > e.c;
}
}cost[N];
int dp[1010];
int main()
{
cin >> n >> m;
double time = 0, ans = 0;
int num0 = 0, num1 = 0;
for (int i = 0; i < n; i ++) // 按照任务种类分别存储任务信息
{
int o;
double t, a, b;
cin >> o >> t >> a >> b;
time += t;
if (o == 0)
{
task0[num0] = {t, a, b};
cost[num0] = {num0, b / a};
num0 ++;
}
else task1[num1 ++] = {t, a, b};
}
ans = time;
sort(cost, cost + num0); // 灵活型任务按照性价比降序排序
for (int i = 0; i < num1; i ++) // 普通型任务采用 0-1 背包的动态规划解法，dp[j] 表示分配 j 杯咖啡能获得的最大减时效果
{
for (int j = m; j >= task1[i].a; j --)
dp[j] = max(dp[j], dp[j - (int)task1[i].a] + (int)task1[i].b);
}
for (int i = 0; i <= m; i ++) // 普通型任务分配 i 杯咖啡
{
double task1_save = dp[i];
double task0_save = 0;
int k = m - i;
for (int j = 0; j < num0; j ++) // 灵活型任务分配剩余的 m - i 杯咖啡
{
if (k <= 0) break;
int v = min(k, (int)task0[cost[j].idx].a);
k -= v;
task0_save += v * cost[j].c;
}
ans = min(ans, time - task0_save - task1_save);
}
printf("%.6lf\n", ans);
return 0;
}
Q3 进程通信
Q3 算法思路(demo1, subtask-40%)
- 针对前 40% 不存在 delete 操作的测试点，模拟即可
- 使用
freePos维护当前的空闲段，标记是否占用和是否存储对象的数组e和ele似乎没有必要，可以直接通过freePos来维护空闲段信息 - 使用
pro[p].chain维护进程 p 的链表信息 op_new是 first fit 分配方式，而不是题目所要求的 best fit 分配方式，因为不存在 delete 操作，所以 first fit 和 best fit 的结果是一样的- 该题解可以通过 smqyOJ (8/23)的测试点，得分 40 分
Q3 代码实现(demo1, subtask-40%)
#include <bits/stdc++.h>
using namespace std;
const int N = 8e+5 + 10;
typedef pair<int, int> PII;
#define x first
#define y second
int n, q;
bool e[N]; // 是否占用
bool ele[N]; // 是否存储对象
vector<PII> freePos;
int numFreePos;
struct Node
{
int l, r, pos = -1; // pos 为当前已经存储的位置
};
struct Process
{
int numNode = 0;
vector<Node> chain;
}pro[110];
void op_new(int p, int l)
{
for (int i = 0; i < numFreePos; i ++) // 寻找空闲段
{
int start = freePos[i].x, end = freePos[i].y;
if (end - start + 1 >= l)
{
// 维护进程接口
Node temp = {start, start + l - 1, -1};
pro[p].chain.push_back(temp);
pro[p].numNode ++;
// 维护空闲段
if (end - start + 1 > l)
freePos[i] = {start + l, end};
else
freePos.erase(freePos.begin() + i);
printf("%d\n", start);
break;
}
}
}
void op_send(int p)
{
int ans = 0;
for (int i = 0; i < pro[p].numNode; i ++)
{
auto &t = pro[p].chain[i];
int insertPos = t.pos;
if (insertPos == -1 || insertPos == t.r) t.pos = t.l;
else t.pos = insertPos + 1;
ans += t.pos;
}
printf("%d\n", ans);
}
void op_delete(int p, int k)
{
}
int main()
{
cin >> n >> q;
freePos.push_back({0, 0x3f3f3f3f});
numFreePos = 1;
for (int i = 0; i < q; i ++)
{
string op;
cin >> op;
int p, l;
if (op == "new")
{
cin >> p >> l;
op_new(p, l);
}
else if (op == "delete")
{
cin >> p >> l;
op_delete(p, l);
}
else
{
cin >> p;
op_send(p);
}
}
return 0;
}
Q3 算法思路(demo2, subtask-80%)
- 添加 delete 操作的处理，维护空闲段时需要考虑合并相邻的空闲段，合理利用
vector insert/erase库函数 op_new需要按照 best fit 的方式分配内存段，遍历freePos寻找最适合的空闲段- 该题解可以通过 smqyOJ (21/23)的测试点，得分 80 分
Q3 代码实现(demo2, subtask-80%)
#include <bits/stdc++.h>
using namespace std;
const int N = 8e+5 + 10;
typedef pair<int, int> PII;
#define x first
#define y second
int n, q;
bool e[N]; // 是否占用
bool ele[N]; // 是否存储对象
vector<PII> freePos;
int numFreePos;
struct Node
{
int l, r, pos = -1; // pos 为当前已经存储的位置
};
struct Process
{
int numNode = 0;
vector<Node> chain;
}pro[110];
void op_new(int p, int l)
{
int flag = -1, min_len = 0;
for (int i = 0; i < numFreePos; i ++) // 寻找最佳空闲段
{
int start = freePos[i].x, end = freePos[i].y;
int length = end - start + 1;
if (flag == -1 && length >= l)
flag = i, min_len = length;
if (length >= l && length < min_len)
flag = i, min_len = length;
}
int start = freePos[flag].x, end = freePos[flag].y;
Node temp = {start, start + l - 1, -1};
pro[p].chain.push_back(temp);
pro[p].numNode ++;
if (end - start + 1 > l)
freePos[flag] = {start + l, end};
else
freePos.erase(freePos.begin() + flag), numFreePos --;
printf("%d\n", start);
}
void op_send(int p)
{
int ans = 0;
for (int i = 0; i < pro[p].numNode; i ++)
{
auto &t = pro[p].chain[i];
int insertPos = t.pos;
if (insertPos == -1 || insertPos == t.r) t.pos = t.l;
else t.pos = insertPos + 1;
ans += t.pos;
}
printf("%d\n", ans);
}
void op_delete(int p, int k)
{
auto &t = pro[p].chain[k - 1];
int start = t.l, end = t.r;
// 删除进程接口
pro[p].chain.erase(pro[p].chain.begin() + k - 1);
pro[p].numNode --;
// 维护空闲段
// 找到插入位置
int loc = 0;
while (loc < numFreePos && freePos[loc].x < start) loc ++;
// 插入新段
freePos.insert(freePos.begin() + loc, {start, end});
numFreePos ++;
// 合并左边
if (loc > 0)
{
auto &prev = freePos[loc - 1];
auto &curr = freePos[loc];
if (prev.y == curr.x - 1)
{
prev.y = curr.y;
freePos.erase(freePos.begin() + loc);
loc --; // 合并后位置左移
numFreePos --;
}
}
// 合并右边
if (loc <= numFreePos - 2)
{
auto &curr = freePos[loc];
auto &next = freePos[loc + 1];
if (curr.y == next.x - 1)
{
curr.y = next.y;
freePos.erase(freePos.begin() + loc + 1);
numFreePos --;
}
}
}
int main()
{
cin >> n >> q;
freePos.push_back({0, 0x3f3f3f3f});
numFreePos = 1;
for (int i = 0; i < q; i ++)
{
string op;
cin >> op;
int p, l;
if (op == "new")
{
cin >> p >> l;
op_new(p, l);
}
else if (op == "delete")
{
cin >> p >> l;
op_delete(p, l);
}
else
{
cin >> p;
op_send(p);
}
}
return 0;
}
Q3 算法思路(demo3, AC)
-
最大操作数 q ⩽ 8000 q \leqslant 8000 q⩽8000，每次最大申请长度 L m ⩽ 5 × 10 5 L_m \leqslant 5 \times 10^5 Lm⩽5×105，最极端情况下，全部都是new 操作，总共需要消耗内存单元数约 8000 × 5 × 10 5 = 4 × 10 9 8000 \times 5 \times 10^5 = 4 \times 10^9 8000×5×105=4×109。
-
使用
long long来存储内存地址 -
该题解可以通过 smqyOJ (23/23)的测试点，得分 100 分
-
int的范围是 [ − 2 31 , 2 31 − 1 ] [-2^{31}, 2^{31} - 1] [−231,231−1]，约为 [ − 2.15 × 10 9 , 2.15 × 10 9 ] [-2.15 \times 10^9, 2.15 \times 10^9] [−2.15×109,2.15×109]，不足以存储 4 × 10 9 4 \times 10^9 4×109 的内存地址，可能会发生溢出。 -
long long的范围是 [ − 2 63 , 2 63 − 1 ] [-2^{63}, 2^{63} - 1] [−263,263−1]，约为 [ − 9.22 × 10 18 , 9.22 × 10 18 ] [-9.22 \times 10^{18}, 9.22 \times 10^{18}] [−9.22×1018,9.22×1018]，远大于 4 × 10 9 4 \times 10^9 4×109，因此使用long long来存储内存地址是安全的，不会发生溢出。
Q3 代码实现(demo3, AC)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PII;
#define x first
#define y second
LL n, q;
vector<PII> freePos;
int numFreePos;
struct Node
{
LL l, r, pos = -1; // pos 为当前已经存储的位置
};
struct Process
{
int numNode = 0;
vector<Node> chain;
}pro[110];
void op_new(int p, int l)
{
int flag = -1, min_len = 0;
for (int i = 0; i < numFreePos; i ++) // 寻找最佳空闲段
{
LL start = freePos[i].x, end = freePos[i].y;
LL length = end - start + 1;
if (flag == -1 && length >= l)
flag = i, min_len = length;
if (length >= l && length < min_len)
flag = i, min_len = length;
}
LL start = freePos[flag].x, end = freePos[flag].y;
Node temp = {start, start + l - 1, -1};
pro[p].chain.push_back(temp);
pro[p].numNode ++;
if (end - start + 1 > l)
freePos[flag] = {start + l, end};
else
freePos.erase(freePos.begin() + flag), numFreePos --;
printf("%lld\n", start);
}
void op_send(int p)
{
LL ans = 0;
for (int i = 0; i < pro[p].numNode; i ++)
{
auto &t = pro[p].chain[i];
LL insertPos = t.pos;
if (insertPos == -1 || insertPos == t.r) t.pos = t.l;
else t.pos = insertPos + 1;
ans += t.pos;
}
printf("%lld\n", ans);
}
void op_delete(int p, int k)
{
auto &t = pro[p].chain[k - 1];
LL start = t.l, end = t.r;
// 删除进程接口
pro[p].chain.erase(pro[p].chain.begin() + k - 1);
pro[p].numNode --;
// 维护空闲段
// 找到插入位置
int loc = 0;
while (loc < numFreePos && freePos[loc].x < start) loc ++;
// 插入新段
freePos.insert(freePos.begin() + loc, {start, end});
numFreePos ++;
// 合并左边
if (loc > 0)
{
auto &prev = freePos[loc - 1];
auto &curr = freePos[loc];
if (prev.y == curr.x - 1)
{
prev.y = curr.y;
freePos.erase(freePos.begin() + loc);
loc --; // 合并后位置左移
numFreePos --;
}
}
// 合并右边
if (loc <= numFreePos - 2)
{
auto &curr = freePos[loc];
auto &next = freePos[loc + 1];
if (curr.y == next.x - 1)
{
curr.y = next.y;
freePos.erase(freePos.begin() + loc + 1);
numFreePos --;
}
}
}
int main()
{
cin >> n >> q;
freePos.push_back({0, 2e18});
numFreePos = 1;
for (int i = 0; i < q; i ++)
{
string op;
cin >> op;
int p, l;
if (op == "new")
{
cin >> p >> l;
op_new(p, l);
}
else if (op == "delete")
{
cin >> p >> l;
op_delete(p, l);
}
else
{
cin >> p;
op_send(p);
}
}
return 0;
}
Q4 异或
Q4 算法思路(demo1, TLE)
- 模拟处理，
work(u, v)计算u和v的k进制表示对应位的和mod k的结果 deal1(l, r, v)对区间[l, r]的每个数执行work(a[i], v)的操作deal2(l, r)计算区间[l, r]的每个数的阶乘的异或结果，阶乘的计算也需要使用work函数来处理- 该题解可以通过 smqyOJ (1/25)的测试点，得分 0 分
Q4 代码实现(demo1, TLE)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e+5 + 10;
int n, m, k;
LL a[N];
LL work(LL u, LL v)
{
LL res = 0;
LL power = 1;
while (u || v)
{
LL du = u % k, dv = v % k;
LL sumBit = (du + dv) % k;
res += sumBit * power;
power = power * k;
u /= k, v /= k;
}
return res;
}
void deal1(int l, int r, LL v)
{
for (int i = l; i <= r; i ++)
a[i] = work(a[i], v);
}
LL deal2(int l, int r)
{
LL res = 0;
for (int i = l; i <= r; i ++)
{
LL fai = 0;
for (int j = 1; j <= a[i]; j ++)
fai = work(fai, j);
res = work(res, fai);
}
return res;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
for (int i = 0; i < m; i ++)
{
int op;
scanf("%d", &op);
if (op == 1)
{
int l, r;
LL v;
scanf("%d%d%lld", &l, &r, &v);
deal1(l, r, v);
}
else
{
int l, r;
scanf("%d%d", &l, &r);
LL res = deal2(l, r);
printf("%lld\n", res);
}
}
}
Q4 算法思路(demo2, subtask1&2)
- f ( n ) = 0 ⊕ k 1 ⊕ k 2 ⊕ k ⋯ ⊕ k n f(n) = 0 \oplus_k 1 \oplus_k 2 \oplus_k \dots \oplus_k n f(n)=0⊕k1⊕k2⊕k⋯⊕kn
- 优化
f(n)函数的求解(把 O ( n ) O(n) O(n) 的循环优化成 O ( log k n ) O(\log_k n) O(logkn))，优化思路借鉴 k k k 进制列加法的模拟过程 - 假设在
k
=
3
k = 3
k=3 的情况下，列竖式计算
f(n)的过程如下所示：
| value | pos 0 | pos 1 | pos 2 | pos 3 | … |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | … |
| 1 | 1 | 0 | 0 | 0 | … |
| 2 | 2 | 0 | 0 | 0 | … |
| 3 | 0 | 1 | 0 | 0 | … |
| 4 | 1 | 1 | 0 | 0 | … |
| 5 | 2 | 1 | 0 | 0 | … |
| 6 | 0 | 2 | 0 | 0 | … |
| 7 | 1 | 2 | 0 | 0 | … |
| 8 | 2 | 2 | 0 | 0 | … |
| 9 | 0 | 0 | 1 | 0 | … |
| 10 | 1 | 0 | 1 | 0 | … |
| 11 | 2 | 0 | 1 | 0 | … |
| 12 | 0 | 1 | 1 | 0 | … |
| 13 | 1 | 1 | 1 | 0 | … |
| 14 | 2 | 1 | 1 | 0 | … |
| 15 | 0 | 2 | 1 | 0 | … |
- 若计算
f(15)，则进行如上的列式，从pos 0开始，纵向求和得到sumBit，并将sumBit % k作为f(15)在pos 0的值，依此类推，计算其他位的值 - 可以发现，从上至下，
pos 0的值的变化周期为 k k k，从0到k-1循环往复 pos j的值的变动期限(该期限内位值不变)为 k j k^j kj，例如，3进制下，pos 1的值在 [ 0 , 2 ] [0, 2] [0,2] 内为0，在 [ 3 , 5 ] [3, 5] [3,5] 内为1，在 [ 6 , 8 ] [6, 8] [6,8] 内为2，在 [ 9 , 11 ] [9, 11] [9,11] 内为0，在 [ 12 , 14 ] [12, 14] [12,14] 内为1，在 [ 15 , 17 ] [15, 17] [15,17] 内为2，以此类推- 假定 n n n 的 k k k 进制表示为 d m d m − 1 … d 1 d 0 d_m d_{m-1} \dots d_1 d_0 dmdm−1…d1d0
- 考虑
pos 0处和值的计算：-
0
+
1
+
2
+
⋯
+
(
k
−
1
)
=
(
k
−
1
)
k
2
0 + 1 + 2 + \dots + (k-1) = \frac{(k-1)k}{2}
0+1+2+⋯+(k−1)=2(k−1)k，题目中
k
k
k 为奇数，所以
(
k
−
1
)
k
2
\frac{(k-1)k}{2}
2(k−1)k 是
k
k
k 的倍数，该完整往复区间的和值
m
o
d
k
\mod k
modk 的结果为
0 - 当 n n n 不在完整往复区间的末尾时，剩余部分的和值 m o d k \mod k modk 的结果为 ( 0 + 1 + 2 + ⋯ + d 0 ) m o d k = d 0 ⋅ ( d 0 + 1 ) 2 m o d k (0 + 1 + 2 + \dots + d_0) \mod k = \frac{d_0 \cdot (d_0 + 1)}{2} \mod k (0+1+2+⋯+d0)modk=2d0⋅(d0+1)modk
-
0
+
1
+
2
+
⋯
+
(
k
−
1
)
=
(
k
−
1
)
k
2
0 + 1 + 2 + \dots + (k-1) = \frac{(k-1)k}{2}
0+1+2+⋯+(k−1)=2(k−1)k，题目中
k
k
k 为奇数，所以
(
k
−
1
)
k
2
\frac{(k-1)k}{2}
2(k−1)k 是
k
k
k 的倍数，该完整往复区间的和值
m
o
d
k
\mod k
modk 的结果为
- 考虑
pos j处和值的计算：- 每
k
j
k^j
kj 个数为一个值的变动期限，这
k
j
k^j
kj 个数的和值一定是
k
k
k 的倍数，所以每个值的变动期限内的和值
m
o
d
k
\mod k
modk 的结果为
0 - 当
n
n
n 不在完整往复区间的末尾时，剩余部分的和值
m
o
d
k
\mod k
modk 的结果为
d
j
⋅
(
n
m
o
d
k
j
+
1
)
m
o
d
k
d_j \cdot (n \mod k^j + 1) \mod k
dj⋅(nmodkj+1)modk，其中
d
j
d_j
dj 是
n
n
n 在
pos j处的值， ( n m o d k j + 1 ) (n \mod k^j + 1) (nmodkj+1) 在模 k k k 的意义下等效为 d 0 + 1 d_0 + 1 d0+1，其中 d 0 d_0 d0 是 n n n 在pos 0处的值
- 每
k
j
k^j
kj 个数为一个值的变动期限，这
k
j
k^j
kj 个数的和值一定是
k
k
k 的倍数，所以每个值的变动期限内的和值
m
o
d
k
\mod k
modk 的结果为
- 该题解可以通过 smqyOJ (13/25)的测试点，得分 50 分
Q4 代码实现(demo2, subtask1&2)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e+5 + 10;
int n, m, k;
LL a[N];
LL work(LL u, LL v)
{
LL res = 0;
LL power = 1;
while (u || v)
{
LL du = u % k, dv = v % k;
LL sumBit = (du + dv) % k;
res += sumBit * power;
power = power * k;
u /= k, v /= k;
}
return res;
}
void deal1(int l, int r, LL v)
{
for (int i = l; i <= r; i ++)
a[i] = work(a[i], v);
}
LL f(LL x)
{
LL res = 0;
LL power = 1;
// pos 0
LL lowBit = x % k;
LL d0 = lowBit;
res += (lowBit + 1) * lowBit / 2 % k * power;
x /= k;
power *= k;
// pos j
while (x)
{
lowBit = x % k;
res += lowBit * (d0 + 1) % k * power;
x /= k;
power *= k;
}
return res;
}
LL deal2(int l, int r)
{
LL res = 0;
for (int i = l; i <= r; i ++)
{
LL fai = f(a[i]);
res = work(res, fai);
}
return res;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
for (int i = 0; i < m; i ++)
{
int op;
scanf("%d", &op);
if (op == 1)
{
int l, r;
LL v;
scanf("%d%d%lld", &l, &r, &v);
deal1(l, r, v);
}
else
{
int l, r;
scanf("%d%d", &l, &r);
LL res = deal2(l, r);
printf("%lld\n", res);
}
}
}
Q5 旅游计划
Q5 算法思路(demo1, subtask1&2)
- 由于题面中节点和边数的设定，该图便是树。
- 构建好邻接表之后，利用
dfs构建以节点1为根的树，同时维护每一个节点x的深度值dpt[x]和其对应的父节点p[x]。 - 对于旅行计划的可行性判定过程中，从计划的起始点和终点同时在构建的树上向上移动，直到移动至两节点的公共祖先节点为止。
- 在移动的过程中，利用道路的翻修情况
is_renovated[]和是否是维修站点st[x]来判定可行性。这里的备胎情况可以视作是个人资金pay，起始资金为 1，每经过未翻修的道路，便会扣除资金值 1 个单位，若资金值出现了负值(直接宣布个人破产，计划失败)，若遇到维修站，你的个人资金便会自动充值到 1。 - LCA 缝合点的特判:
- 我们先穷举一下在 LCA 汇合时的 3 种情况：
pay1 = 1, pay2 = 1：左段未遇到烂路，右半段也未遇到烂路。资金总消耗为 0，安全。pay1 = 1, pay2 = 0(或相反)：其中半段遇到了一条烂路，另半段未遇到烂路。资金总消耗 1，安全。pay1 = 0, pay2 = 0：左段遇到一条烂路(无资金可用)，右段也遇到一条烂路(无资金可用)。危险！- 为什么要缝合(特判)？
- 因为在构建代码逻辑时，为了方便向上查找 LCA，采用的策略是"假装有两辆车"：第一辆车从起点 s 出发，带着 1 单位的资金，向上行进，第二辆车从终点 t 出发，带着 1 单位的资金，向上行进。如果两辆车都在半路用掉了自己的资金(
pay1=0, pay2=0)，它们确实都能活着开到 LCA。但是！现实中只有一辆车、一个单位的资金！如果左半边需要 1 个单位的资金，右半边也需要 1 个单位的资金，加起来这条完整的路径就需要 2 个单位的资金，完全无中生有！所以这条路是死路。
- 所以，唯一需要特判的情况就是
pay1 == 0 && pay2 == 0或pay1 + pay2 < 1 - 该题解可以通过 smqyOJ (24/50)的测试点，得分 30 分
Q5 代码实现(demo1, subtask1&2)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1e+5 + 10;
int n, X, lastans, k, m, q;
bool st[N]; // 表示该城市是否有维修站
PII tour[N]; // 旅行计划
int h[N], e[N * 2], ne[N * 2], idx;
int dpt[N], p[N]; // dpt[x] 标记节点所在树的深度，p[x] 标记节点所在树的父节点
bool is_renovated[N]; // is_renovated[x] 标记节点 x 与其父节点 p[x] 之间的道路是否翻修过
void add(int u, int v)
{
e[idx] = v, ne[idx] = h[u], h[u] = idx ++;
}
void deal1(int u, int v)
{
int du = dpt[u], dv = dpt[v];
if (du > dv)
is_renovated[u] = true;
else
is_renovated[v] = true;
}
int setPay(int pay, int p) // 判定 node-p[node] 道路是否翻修，返回 pay 值
{
if (is_renovated[p]) return pay;
else
{
pay -= 1;
return pay;
}
}
bool check(int id)
{
int p1 = tour[id].x, p2 = tour[id].y;
if (dpt[p1] > dpt[p2]) swap(p1, p2); // 调节 p2 节点至更深
int pay1 = 1, pay2 = 1;
while (dpt[p1] != dpt[p2]) // 上移 p2
{
pay2 = setPay(pay2, p2);
if (pay2 < 0) return false; // 先判定是否死在半路，再行动 (Hack point)
p2 = p[p2];
if (st[p2]) pay2 = 1; // 维修点
}
if (p1 == p2) return true;
else
{
while (p1 != p2)
{
pay1 = setPay(pay1, p1);
if (pay1 < 0) return false; // 先判定是否死在半路，再行动 (Hack point)
p1 = p[p1];
if (st[p1]) pay1 = 1; // 维修点
pay2 = setPay(pay2, p2);
if (pay2 < 0) return false; // 先判定是否死在半路，再行动 (Hack point)
p2 = p[p2];
if (st[p2]) pay2 = 1; // 维修点
}
// LCA 缝合点的特判
if (pay1 + pay2 < 1) return false; // (Bug point)
}
return true;
}
void deal2()
{
int cnt = 0;
for (int i = 0; i < m; i ++)
{
bool flag = check(i); // 判定第 i 份旅行计划
if (flag) cnt ++;
}
lastans = cnt;
printf("%d\n", cnt);
}
void dfs(int start, int father) // 构建树的结构，并同时维护 dpt[] 与 p[]
{
dpt[start] = dpt[father] + 1, p[start] = father;
for (int i = h[start]; ~i; i = ne[i])
{
int j = e[i];
if (j == father) continue;
dfs(j, start);
}
}
int main()
{
scanf("%d%d", &n, &X);
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++) // 读入道路信息
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
dfs(1, 0);
scanf("%d", &k);
for (int i = 0; i < k; i ++) // 读入维护站信息
{
int node;
scanf("%d", &node);
st[node] = true;
}
scanf("%d", &m);
for (int i = 0; i < m; i ++) // 读入旅行计划信息
{
int s, t;
scanf("%d%d", &s, &t);
tour[i] = {s, t};
}
scanf("%d", &q);
for (int i = 0; i < q; i ++) // 读入询问操作信息
{
int op;
scanf("%d", &op);
if (op == 1)
{
int u, v;
scanf("%d%d", &u, &v);
u = u ^ (X * lastans), v = v ^ (X * lastans);
deal1(u, v);
}
else
{
deal2();
}
}
return 0;
}
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
10
0- 0
已为社区贡献3条内容
所有评论(0)