传送门 思路 若，则可以通过化简取取对数，得到。所以本题同理，这样化简后，就转成了，以结尾的子序列个数有多少，所以可以枚举起点和终点。时间复杂度： Tags DP 数学 参考代码 //#include <bits/stdc++.h> #include <bitset> #include <iomanip> #include <iostream> #include <list> #include <set> #include <sstream> #include <stack> #include ...

传送门 分析 本题的要点在于i到j有通路必须所有我们可以根据给出的建图。那么第一个问题就是求从1出发，最多可以经过多少个点，这个问题用BFS/DFS统计下点的个数即可。主要问题在于第二个问题，因为题目说不考虑时间胶囊的消耗，而且可以连续食用，所以最后走出来的形状一定是树的样子。但是由于路线方向是根据的高度所决定的，只能从高处到低处，所以并不是最小生成树。但是本题可以理解为一个最小生成树的变型问题，在本题中若从点u到点v，必须满足如下的要求： u和v都和起点连通 那我们可以根据算法的思想，定义以下的排序原则： 若，则按照来排序 否则按照高度排序 这样相当于我们在一层一层扩展，先把最高层...

传送门 题意 有个人，分成2个队伍，每个人都有一个战力值第秒，第个人会消灭前面不属于同一个队伍，且战力值小于他的所有人。与此同时，有m次机会，第每次前个人的战力都会增加1，问你第秒存活的人数与此同时，有m次机会，每次前个人的战力都会增加1，问你第n秒存活的人数。 分析 从后向前遍历，若当前为第个人，那只有前个人会受到影响。对于次的发功，可以维护一个后缀和，然后每个人的实际战斗力为。如此只需要维护两个队伍的最大值，如果第个人的战斗力比另外一个队伍的最大值小，第个人就会消灭掉。 时间复杂度： 参考代码 #include <bits/stdc++.h> using namespace s...

传送门 题意 更定n段长度为的木棍，问若把他们分成k个相同长度的，最大长度是多少 tags 二分分析 可以对长度进行二分。二分下届为1，上界为max(a[i])。用贪心的方法经行检查。每个对于答案的贡献是。所以若说明mid的取值大了可以减少，否则需要增大。check函数复杂度：，总复杂度：参考代码 #include <bits/stdc++.h> using namespace std; #define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) typedef long long ll; type...

传送门 题意 给定一棵n个点的树，问其中有多少条长度为偶数的路径。 tags dfs/bfs 思维 分析 以节点开始，记录每个点的深度。设奇偶深度的点个数分别为：和，则ans=。具体证明过程如下图： 参考代码 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100000 + 10; int head[maxn], cnt; int dep[maxn]; struct node { int v, next; } e[maxn << 1...

分析 动态处理中位数，对顶堆的模板题。 本质是维护了两个堆，设当前元素个数为： 大根堆 ：序列中从小到大的数字 小根堆 ：序列中从小到大的数字 两个堆始终保证着元数个数相差不超过1的性质。如果在某一个时刻，打破了这一个性质，那么就讲元素多的堆顶元素插入到另外一个堆中。这样一来中位数就是小根堆的对顶元素。 当每次插入一个新的数字的时候，如果，则插到大根堆，否则插入到小根堆中。时间复杂度 参考代码 #include <bits/stdc++.h> using namespace std; #define FAST_IO ios::sync_with_stdio(false),cin...

传送门 A - Maximize The Beautiful Value tags: 贪心、前缀和、推公式 分析 题目说明了是不降的序列，所以低于答案的贡献必定是越大的数字在后面越好，我们可以考虑如果枚举数字，让他们都往前移动位，取最大的值。 本题难点在于如何移动进行计算，如果暴力计算的话复杂度为。我们设原答案为，选择的是第个数字，观察数列变化，返现对于答案的贡献是不变的，的结果每一项都加上了。所以可以维护前缀和，取得这一部分的区间和。 时间复杂度 AC代码 #include <bits/stdc++.h> using namespace std; typedef long l...

POJ - 1860 最短路 判正环 题意 一开始，在点有个金币，而点的过程会产生的变化，问是否有一条路线可以使得最终的。 分析 要是最找的增加，有两种可能性： 原本路径中就纯在这样的边权 有正环的存在，因为而双向的通路，而若纯在一个正环，在环中走一些，不断的松弛操作后，最终会变成一个无穷大的数字，这样无论环中是否存在点都可以通过回路达到 所以本题能够利用的思想去解题。 因此初始化而源点到其他点的距离（权值）初始化为无穷小（0），当到其他某点的距离能不断变大时，说明存在最大路径；如果可以一直变大（也就是松弛次数超过次），说明存在正环。 本题因为数据范围不大，使用都可以。我此题采用的是。复杂...

POJ - 1797 最短路变形 题意 给定一张n点m条边的无向图，求出1-n路径中边权最小值最大的边。 分析 这道题，刚开始的时候，没有什么思路。最简单暴力的方法就是的搜索，暴力比较。但是这题在最短路的专题里，那必定和最短路有关。 在最短路算法中，通过复杂度，可以排除，剩下的。而最短边权最大，其实就是选出边权最大的一条路，然后更新到终点v的最小值即可。原本的松弛操作变成了。 另外，因为选出最大边权，最小。所以可以贪心的用最大生成树，来实现。 证明：若1->n中，经过x点，最大生成树贪心连边，保证1->x连通的最大，则不存在比更大的边。从而构建出一颗最大路径树取其中最小值即可。...

​ 寒假开始，最近一段时间开始了寒假训练。这段时间如果没有别的事情，争取每天多刷题。每天都抽点空写写题解，写写刷题收获。 POJ - 2387 Dijkstra 题意 ​ 一个无向图，起点为1，终点为N的最短路，保证有解。 ​ 一个最短路的裸题。。。直接上熟悉的Dijkstra代码，堆优化复杂度。 AC代码 //#include <bits/stdc++.h> #include <iostream> #include <iomanip> #include <bitset> #include <st...

原题链接 题目描述 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例 给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5. note 给定的 n 保证是有效的。 思路 遍历两次列表。第一遍历用于求出链表的长度，然后第二次遍历节点指针到处，把第的节点的next连接到第节点。复杂度 **** 。注意编写接口时的边界处理，一开始在NULL处疯狂WA。 AC代码 /** * Definition for singly-linked list. * struct...

#1024#当我已经写完A题的时候，他们已经AK了?@ACM圈

A-乘积最大 题目链接 题意 给定一个数字字符串，把字符串分成`K+1`个数，使这些数乘积最大。分析 本题最佳解法应该是区间dp但本蒟蒻不会dp。只能暴力dfs了。在串中插入*其性质和排列类似。可以参考蓝书P15递归实现排列型枚举。对于在第i个位置插入*分成i之前的为一段，及i和i之后一段。 需要注意在数字相连时的边界情况。 AC代码 #include <bits/stdc++.h> using namespace std; #define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) typedef lo...

比赛总结 暑期第一次打牛客团队赛，居然运气不错的就中奖了。不过这次的题总体都不难，差1题就可以AK了呢。还是来总结下吧，先附上算法大纲。 easy：B(模拟)、C(高精度)、G(排序)、H(BF)、I(规律题)、J(简单DP)、L(打表BF) mid：K(floyd传递闭包)、D(复杂模拟)、F(最短路+二分) hard：E(二分+并查集)、A(树形DP求最小支配集合) 其中蒟蒻的我写了BCGHIF(果然我只配写简单题) B-iCow 题目传送门 题意   有N(1 <= N <= 1,000)首歌曲，按照1-N编号。 第i首曲子有一个初始权值R_i(1 <= R_i ...