原题：度度熊的午饭时光 原题大意01背包，但是要输出路径，按照序号和最小，字典序最小输出。 程序代码可以用vis[i][j]，来记录路径。 #include <cstdio> #include <cstring> #include <iostream> #define clr(a, b) memset(a, b, sizeof(a)) using namespace std; typedef long long ll; const int MAXN = 111; const int MAXB = 1111; struct meal { int score, cost; } m[MAXN]; int B, N; int dp[MAXB]; bool tmp[MAXN]; bool vis[MAXN][MAXB]; int main() { int T, ce = 1; scanf("%d", &T); while (T--) { scanf("% ...

原题：Kanade’s sum 原题大意1~n的数组成了序列A，f(l,r,k)为[l, r]里第k大的数，如果r-l+1 < k,那么f(l,r,k)就为0.现在求 t = 0 for l in 1 : n for r in 1 : n t+=f(l,r,k) 即求t，注意k < min(n, 80) 算法分析考虑每个数被几个有效区间包含，每个数向左右各找最多k个比它大的数，然后按左边i个，右边k-i-1个这样讨论。这里可以用链表优化，先维护一个1~n的链表，记录每个数的位置，我们贪心的从1开始选，一直选到n，计算完之后就把它删除，这样就能保证每次选的数都是最小的。 程序代码#include <bits/stdc++.h> using namespace std; const int maxn = 5e5+5; typedef long long ll; int pos[maxn], v[maxn], n, k, T; int pre[maxn], nxt[maxn]; ll a[maxn], b[maxn]; ll solve(int ...

Tarjan离线求LCA的博客 http://www.cnblogs.com/JVxie/p/4854719.html 例题1 http://hihocoder.com/problemset/problem/1067 给出n行父-子的名字，q个询问，输出最近公共祖先 程序代码#include <bits/stdc++.h> #define pb push_back using namespace std; const int maxn = 100050; vector<int> g[maxn]; vector<int> q[maxn]; vector<int> num[maxn]; int ans[maxn]; int n, Q; map<string,int> dict; vector<string> v; int fa[maxn], r[maxn], ind[maxn]; bool vis[maxn]; int find(int x){return fa[x] == x ? x : fa[x] = fin ...

原题：Same Occurrence 原题大意给一个长度为n的序列，和q个询问，每个询问有两个数x，y。问在所有的子序列中x，y出现次数相同的序列个数有多少？ 算法分析首先观察数据范围可以得出一下结论： n的长度最多有8000，可以用离散化缩小单个数据范围 询问最多有500000，如果n小一点的话，肯定会有重复询问，可以有数组记录询问结果 然后考虑具体的询问 如果两个数相同或者都不在序列中，那么答案是n*(n+1)/2 如果只有一个数 x存在于序列 a, b, c, x, e, f, x, g, h, i, x中，我们可以将序列分割成如下形式[a,b,c],[e,f],[g,h,i]，然后按上一种情况处理每个区间。 如果两个数都存在于序列中，设前i个数里含x的有c个，含y的有d个，在前j（j < i）处，含x的有a个，含y的有b个，若使得（i，j]可以被选中，那么c-a == d-b，变型一下就是c-d == a-b。那么现在维护前缀就好了。因为序列中存在大量的非x，y的数，我们可以用vector记录x,y出现的位置，然后vector里的后一个减去前一个，就得到了中间的值， ...

原题：相交的铁路线 算法分析考虑朴素的算法t1 = lca(x1,y1), S1 = x1->t1 ∪ t1->y1;同理可得t2和S2。判断S1∩S2是否为空 假设有交点t且假设经过y1,y2，所以x1->t1->t->y1,x2->t2->t->y2,因为t只有一个父亲，所以t1,t2一定是祖先关系，那么t1或t2一定是交点，假设t1是交点，即t2是t1的祖先，则需要两个判定条件： lca(t1,t2) = t2 lca(t1,y2) = t1 或 lca(t1,x2) = t1 程序代码#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int maxn = 100050; struct nod{ int to, cost; nod(int a=0,int b=0){to = a; cost = b;} }; in ...