题目描述 你需要走n天，这n天你都要从1走到m城市。并且给出城市之间的边关系以及长度（就是花费的时间）。但是有一个不同寻常的地方有些城市会在 [ a , b ] 的天数内无法进入。所以这些天中你不能走进这些城市之中去。并且当你选定路线之后，每做一次路线更换都要额外花费 k 的时间。现在询问你这n天从1去m的最短时间是多少？  Solution 跳出一般的图论思维，看到这n天都要去，是不是可以分解出子问题，第1天去最短花费，第二天去最短花费……可以看出这个求解是可以通过动态规划解决。紧接着，我们如何求道第一天的最短花费呢？这个过程就需要用的图论的最短路了。我们只需要把第一天不能走的点给他打上一个...

题目描述 你有n个节点的一棵树，n的量级是1e6。后面存在n-1行，第i行代表第i个节点的父节点是谁，并且给出第i个节点的权值，父节点是0的节点就是根。现在需要你找出一种方案，把两条连接的边切断，把这棵树分成三颗树，并且三棵树的权值之和相等。是否存在这种切法。如果不存在的话，需要输出-1。 Solution 第一步比较容易的特判就是节点权值之和如果不是3的倍数，那就不存在分法可以分成三等分，直接-1。第二步的情况，我们把权值之和除以三，遍历这颗树，把子树权值累加，当加到一个节点的权值等于 sum / 3的时候，把这个节点分隔开，也就是把这个节点的权值改成0，不连接在父节点之下了。最后只要特判是...

题目描述 第一行输入数轴长度n，以及操作次数m，都是1e5的量级。后面存在m行，第一列是操作数，第二列是 l ，第三列是 r 。op==1,把数轴 [ l , r ] 中间的点全部+1op==2，把操作编号是 [ l , r ] 的操作重新执行一遍。 Solution 不看操作2，只看操作1，会发现是个很容易解决的一个差分数组。如果只看操作2，不看操作1，你也会发现这也是一个差分数组。现在我们想要交叉的处理两个有关联的差分数组？如何处理？后缀差分！  ans[i] 数组这个表示最后 i 点的点权值。 sum[i] 数组表示第 i 次操作被执行了几次。 很明显之前每次的操作都是被执行了一次的，所...

A、奖券数目 有些人很迷信数字，比如带“4”的数字，认为和“死”谐音，就觉得不吉利。虽然这些说法纯属无稽之谈，但有时还要迎合大众的需求。某抽奖活动的奖券号码是5位数（10000-99999），要求其中不要出现带“4”的号码，主办单位请你计算一下，如果任何两张奖券不重号，最多可发出奖券多少张。  #include <cstdio> int check(int x) { while (x) { if (x % 10 == 4) return 0; x /= 10; } return 1; } int main() { int cnt = 0; for (int i = 10000; i...

题目描述 在一根数轴上，你需要处理n个目标物，你只有k个炸弹，每个炸弹可以你随意放置在x的地方，它的爆炸范围是这个区间，你需要求解k个炸弹的情况下最小的r是多少？ Solution 滑动窗口，二分求解。目标物的下标不一定有序，我们直接对目标物的下标进行排序。紧接着二分这个答案r，使用一个类似与滑动窗口的办法去处理炸弹数目，最后判断是否大于k个炸弹数即可。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #...

A、跑步训练 小明要做一个跑步训练。初始时，小明充满体力，体力值计为 10000。如果小明跑步，每分钟损耗600 的体力。如果小明休息，每分钟增加 300 的体力。体力的损耗和增加都是均匀变化的。小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循环。如果某个时刻小明的体力到达 0，他就停止锻炼。请问小明在多久后停止锻炼。为了使答案为整数，请以秒为单位输出答案。答案中只填写数，不填写单位。  #include <cstdio> int main() { int n = 10000, ans = 0, op = 1; while (1) { if (op) { for (...

A、小y的考试 结构体变量统计长度以及下标，对长度排序，在一个个判断就行了，符合那个情况就输出下标字母，最后输出C  #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__vv__).begin(), (__vv__).end() #define endl "\n" #define pai pair<int, int> #define ms(__x__,__val...

A、12.5MB 【问题描述】在计算机存储中，12.5MB是多少字节？【答案提交】这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。  #include <cstdio> using namespace std; int main() { long long ans = 12.5 * 1024 * 1024;// MB KB B printf("%lld\n", ans); // 13107200 return 0; } B、最多边数 【问题描述】一个包含有2019个结点的有向图，最多包...

A、15.125GB 【问题描述】在计算机存储中，15.125GB是多少MB？【答案提交】这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。  #include <cstdio> #include <algorithm> using namespace std; const int N = 1e5 + 7; int a[N], n, m; int main() { printf("%f\n", 15.125 * 1024); //15488 return 0; } B、约数个...

A、组队  作为篮球队教练，你需要从以下名单中选出 1 号位至 5 号位各一名球员，组成球队的首发阵容。每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1号位至 5 号位的评分之和最大可能是多少？   #include <cstdio> #include <iostream> #include <queue> #include <vector> #include <algorithm> using namespace std; const int N = 1e6 + 7; int num[25][8]; boo...

A、牛牛和牛可乐的赌约 正面不容易直接得到答案，那就 1 - 反面的答案。如果我们求得不是他输的概率而是赢的概率的话，那就十分好求答案就是，我们直接拿1减掉，再通过费马小定理，逆元运算求得MOD下的值即可。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h> using namespace std; #define js ios::sync_wit...

A、第几天 2000年的1月1日，是那一年的第1天。那么，2000年的5月4日，是那一年的第几天？ 注意：需要提交的是一个整数，不要填写任何多余内容。 #include <cstdio> #include <iostream> #include <queue> #include <vector> #include <algorithm> using namespace std; const int N = 1e6 + 7; int main() { int ans = 31 + 29 + 31 + 30 + 4; printf(&qu...

题目描述 第一行输入共有N个同学，带了N个笔记本，N < 2e5 + 1，需要坚持 K 分钟。第二行给出N个整数，每个整数代表笔记本初始电量，a[i] < 1e12 + 1第三行给出N个整数，每个整数代表笔记本每分钟消好电量，b[i] < 1e7 + 1现在你可以买一个充电器，再每分钟给某个笔记本充电 x 的电量，这个 x 最小是多少？如果永远无法满足那就输出 -1  Solution 稍微思考，可以发现这个答案 x 满足二分的性质，如果当前x可以，我是不是能买小一点的充电器呢？如果不行的就只能吧 x 变大了，所以可以二分这个答案去验证是否可以实现。那么问题来到如何验证当前 ...

题目意思 给你个01地图大小n * m，你只能走最大T个1的地方。问你能最远走多远？起点随便选终点距离最远即可。地图规模最大30 * 30 解题思路 地图规模比较小，可以随便写复杂度，那么我们直接使用最暴力的算法，枚举每一个位置成为起点，对每一个位置算一次DFS，把去到每一个点的最短1的数量算出来，当然稍微减枝一下，如果超过了T个1直接保持无穷大不需要递归，还一个就是最优性减枝，第二次来到这个地方花费比之前还多，那也没必要走下去了。这样算出每一个地方需要踩过的1的数量，在枚举全部的终点去判断起点终点距离求MAX即可。  #pragma GCC target("avx,sse2,sse3,sse...