分析 这是要维护一个k叉哈夫曼树。有几个值得注意的地方：补零 合并 合并：每次合并k个节点，其实每多k-1个节点,那么就要和原本的节点产生一个新节点，如果这是个满k叉树，那么最后的的总 节点个数就是(c+1)*(k-1)+1(c为一个常数),将其设为n,那么判定他为一棵满k叉树就是判断(n-1)%(k-1)是否为0。每次合 并挑最小的k个合并,为什么？我不知道这个贪心是否正确，以二叉树为例，假设当前有a,b,c(a>b>c),如果把a,b合并为d， c与d合并，代价是w1=hc+d(c+1),如果把b,c合并为e，a与e合并，代价是w2=ha+(h+1)e，两者相减，w2&...

前言 有时候题解不仅仅是题解 关于莫队 现在只说普通莫队 离线处理区间问题,可以发现某些题的条件是必须由上一个答案转移过来，就是因为出题人害怕被莫队暴虐(fake,反正我都要被虐) 他有许多神奇操作:询问的分块排序，以及区间的伸缩 莫队的分块排序 这是精髓 为什么不考虑普通排序呢？好问题。聪明的你应该懂了。如果优先按照左端点排序。这种排序的方式，保证左端点只会向右挪，但是右端点每次最坏还是可以从最前面挪到最后面，从最后面挪到最前面，这样的复杂度还是 O(nm)，是不行的，就像[1,n],[2,3],[3,n],[4,5]...来来回回，何来AC？ 那么这样不行，就要换种方式...

C - 小睿睿的兄弟 题目大意（划重点） 有一棵树,肯定要跑一遍啊 求x的第k代兄弟,说明他肯定要有这个祖先而且兄弟得有这么多 还要求k小值（giao）,怎么这么麻烦 分析问题（现在没有探讨珂学） 首先得有一个全局思想(我要求什么,怎么求) 我们要求一个k祖先,所以记录一个数组f[i][j],表示点j的(1<<i)代祖先 解决这个问题的关键一步,是想出怎么求出x的兄弟,因为他们虽然可能在同一层,但是有可能没有共同的k代祖先但是可以发现,如果我们以深度为第一关键字,遍历顺序为第二关键字,开一个vector存储每一个深度对应的节点,就可以保证这些节点的有序,所以还...

分析 这道题数据范围较小,看题目问题,可确定是一个dfs,每次要么走'-',要么走'+',时间复杂度大概为O( ),可以小剪枝一下,如果当前加上所有的数如果都小于最后一个数,就不用搜了,或者是减去后面所有数都大于最后的数,也不用再搜下去了 代码 //#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops") //#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt") /* (写点什么吧......

分析 其实题目说得很清楚了，就是每一个不同的字符串是否都对应一个天敌(map搞定一切),锅主要是在题目中的字符串,相信很多人第一次看就只输入了字符 代码 //#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops") //#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt") #include<bits/stdc++.h> #define R register #define ...

前言      这道题怎么可以没you题解呢 思路分析        即使每个人都有朋友,但是一定会有一个人的前面没有站着朋友,那么我们就把这些朋友放在一个连通块里,那么如果里面有一个点(i==f[i])说明他必须要站在最前面,，题目要求字典序最小,那么我么就尽量把编号较大的点合并到最小的点里，然后把每队朋友关系连边,把能到达的点存入一个优先队列里(小根堆),这样每次记录答案是得到的就是最小的 代码 //#pragma GCC optimize(3,"inline",...

Analysis 因为有环,所以可以先tarjan算法求出e-DCC(边双连通分量),这个时候就要去染色, 这时候我们就要思考对于每一个分量我们需要多少种颜色,其实不难看出,如果存在奇环 (就像1->2->3->4->1,我们发现如果仅用两种颜色，是没办法使每条边两端的端点的颜 色不同),于是对于每一个连通分量跑一次dfs,如果存在奇环,说明要用三种颜色才能满足。代码实现 #include using namespace std; const int N=1e4+10; int n,cnt,tot,scc,ans=2,m; int h[N],nex[N],dfn...