Fighting_Peter的博客

C. Code a Trie 大佬题解，代码基本就是抄的 对于每一个值计算所有串的LCA，也就是最长公共前缀，将该节点（Trie树的节点）标记，对于这些字符串在LCA下面的点一定不存在（如果存在他们不会返回相同的值） 每个Trie树中的节点只能被标记一次，并且从跟到LCA路径上的变必须存在 dfs贪心计算每个子树中最少的节点 插入时统计cnt[]表示它的子树中被标记为LCA的点的数量 如果cnt[u]>1，这个点必选，如果说该节点没被标记为LCA，那么它可以替代它一个儿子称为那个值的LCA，如果被标

I. Space Station #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=100010,mod=1e9+7; int a[N],n; ll fact[N]; bool st[N]; ll res; void dfs(int u,ll now) { if(u==n) { res=(res+1)%mod;

F. Paper Grading 大佬题解 一般关于前缀的问题基本都是Trie树。 首先将所给字符串建立一棵Trie树，Trie能够解决一个字符串在一个字符串集合中出现的次数，而查询前缀次数只需要找到Trie树中所给字符末尾的位置，那么其子树中打标记的次数即前缀次数。 由于子树dfs序[L,R]连续，于是把字典树按照dfs序标记，即变成区间查询问题[l,r]中[L,R]之间数的个数，二位偏序问题。 树套树（树状数组套下标线段树）即可解决，要动态开点！ #include<iostream> usi

A. Golden Spirit 签到题，首先把所有老人带到对岸，然后在对休息讨论一下即可。 #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<random

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstrin

codeforces原题链接 大佬题解 B - Binary Tree #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #in.

就做了两个签到题，然后一直调E调不过 E - Equidistant 队友想的方法：先以1为根节点跑一边dfs，记录每个节点的深度，然后把m个关键点中，深度最大的点mx和深度最小的点mn拿出来，找到这两个点路径上的中点s（depmx−deps=deps−deplca+depmn−deplcadep_{mx}-deps=dep_s-dep_{lca}+dep_{mn}-dep_{lca}depmx​−deps=deps​−deplca​+depmn​−deplca​），找到该点后，以该点为根节点重建树，那么m

E. Exam Results 感觉想的没问题，为啥wa2啊？求高手指点 对于所有学生的最高成绩只可能是ai(1≤i≤n)a_i(1\leq i\leq n)ai​(1≤i≤n)或者最大的bib_ibi​，对于后面一种情况直接特殊考虑一下即可，下面主要分析最高成绩是ai(1≤i≤n)a_i(1\leq i\leq n)ai​(1≤i≤n)的情况。 首先将所有学生按照aaa从大到小排序，然后依次枚举每一个学生的aia_iai​作为最高成绩，假设当前这位是aia_iai​，那么对于i→ni\to ni→n这些学