简易题解


一个月没更新,欠的有点多,更不过来了
????????????????
偷懒更一个统一题解吧
????????????????
????????????????
????????????????

3065:替罪羊树,每个节点上维护一棵权值线段树存储该子树的权值信息,查询时将需要的权值线段树拿出来统一查询.注意空间.

1025:注意到操作是一种置换,等价于一堆环套在一起,则周期就是这些环长度的lcm,问题转化成求若干个和为n的数的lcm有多少种.设dp[x][i]表示和为x的数,其中出现的最大质因子为第i个质数的lcm种数就能做了.

1037:dp[i][j][k][l]表示前i个人中有j个男孩,从队尾往前数,男孩数-女孩数最大为k,女孩数-男孩数最大为l的方案数.

3551:用到了一个叫kruskal重构树的东西,原图中显然只有最小生成树上面的边是有意义的,那么在建立最小生成树的过程中,每增加一条边,就新建一个节点作为两个节点原来祖先的祖先,边权为这条边的边权.容易证明点x走不超过len的边能到达的点,在这棵树上就是x一直往上走,直到下一个边权超过len为止,子树中的所有叶子结点.那么用倍增找出这这个点,然后用主席树维护dfs序.

1135:一个显然可行的策略是从脚最小的人开始每个人都穿尽量小的鞋,那么考虑溜冰鞋不够的情况,显然是某个区间(x,y)内人的数量超过了(x,y+k)内鞋的数量也就是d(y-x+1+k),画一下柿子发现就是维护最大连续子段和.

3774:经典最小割模型,黑白染色翻转源汇.

4819:分数规划,费用流

1778:在i城市爆炸的概率等于期望经过i城市的次数/期望走的步数,高斯消元解一下.

3576:n堆石子每堆是一个子游戏,那么求出所有石子数的sg函数异或起来看是不是0.有一个性质就是把n颗石子分成m堆只有根号种本质不同的方案,由此可以求sg函数.

1228:依然要求每组石子的sg函数,打表发现一组的sg函数跟两堆石子数量对2^k取模的结果有关,暴力枚举k就行.

2453:带修改莫队,跟普通莫队差不多,普通莫队只有l和r,再加一维时间就可以了.

3560:利用公式考虑乘积中每个质因子的贡献,然后再统计到每个数字里面去,最后考虑这个质因子选不选.

2460:贪心,按权值从大到小加入n线性基,最后线性基中的权值和就是答案.

3105:贪心从大到小加入线性基,然后求和.

3569:求一棵原图的生成树,那么切断k条边后图不连通当且仅当有一条树边被切断了,并且所有覆盖他的非树边也被切断了.可以给非树边一个随机权值,树边的权值是所有覆盖它的非树边的权值异或和,然后每次用线性基判断k条边的权值是否线性无关就能得到图是否联通.

4004:从小往大贪心,用高斯消元判断.

2115:对图中所有简单环求线性基,然后随便找一条1到n的简单路径,求这条路径权值在线性基中能异或出来的最大值.

4027:贪心,发现一个性质:如果父节点和子节点是不可同时删除的,那么一定是删除子节点更划算,所以自底向上贪心,每层从小到大删儿子.

2337:拆位,再将每个点拆成0和1两个点,高斯消元计算点(n,1)的期望经过次数(一个小于等于1的数).

4568:倍增+线性基合并

4184:用一棵线段树维护时间轴,对每棵葱打标记,最后dfs线段树.要用vector优化空间.

3028:把生成函数乘起来,然后用广义二项式定理求n-1次项系数,答案就是.

4259:给每个字母一个特征值,通配符的特征值为0,用FFT求一个和为0的位置就能匹配上.

3790:就是用一堆回文串覆盖整个串,manacher+线段覆盖.

3160:答案就是满足1的减去只满足1不满足2的,第一个用FFT,第二个用manacher

1084:无脑DP

2565:manacher求一下极长回文串长度,用单调队列求每个分隔符前面的最长回文和后面的最长回文,然后加起来.数据貌似很水.

2901:前缀和

5020:函数用泰勒展开+二项式定理转成多项式,用LCT维护.

4827:把柿子展开发现是x^2的和加上y^2的和,减去一个卷积再加上一个只跟c有关的二次函数.求一下二次函数最小值即可.

发表评论

电子邮件地址不会被公开。 必填项已用*标注