varinic 的博客

#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;typedef long long ll;const int MAXN=1000;const ll INF=1e9;

题意：给你一个有向图，问这个有向图中任何一对结点间，至少有一个结点到另一个结点是可达的。实际上就是判断一个图是否单侧连通。做法很简单，先强连通分解，然后在新建的图中找一条最长的链，如果这条链包含所有点，那原图就是单侧联通的，否则就不是。那如何找最长链呢，很简单因为新建的图是DAG，所以最长链的长度=最长路。而对DAG求最短路最长路都是可以用dp高效求解的。时间复杂度o（n+m）

题目大意：  给你n个字符，这n个字符是由字母表前k个字符组成的。问两个区间，这两个区间所含字符种类不同，输出两个区间最大乘积。令b[ sta ]为sta所能取的最大值，dp[ sta ]为sta及其子集所能取的最大值，转移方程 dp[ sta]=max（b[sta],dp[ sta最大真子集 ]）。那么sta^(1#include#include#incl

题目大意：给你一棵树，每个点都有权值，每条边也有权值，从一个点出发，获得点值，走过一条边付出边值，点值只能获得一次，边值走一次付出一次。问从每个点出发，可以获得的最大价值。每个点记录从这个点出发又回来的最大值re[x]，以及从这个点出发最终往一个方向走的最大值ans[x][0]。第一次dfs还要记录下最优值ans[x][0]、次优值ans[x][1]，以及最优值是往那条边走的f[x][0]。第