题意：1：将的值改为。2：令，求t能被多少个不同的素数整除。 题解： 本题有两种解法，带修莫队和线段树，带修莫队的话需要开个O3提提速，不然会T一个点。 1.带修莫队题目不是5e4的范围吗，带修莫队会卡时间？因为莫队移动的操作时间复杂度为O(1)，但是这个移动的时间复杂度却不是O(1)，应该是一个10左右的常数的大小，再加上vector本身就有点慢，所以会有点卡时间。 带修莫队的话，其实就可以当场是一个比较模板的题目了，只不过一个位置上的数字变成了好几个而已。 代码： #pragma GCC optimize(3) //#pragma GCC optimize(3,"Ofast...

题意： 给你一棵树，问树上所有两点路径上的（最大值最小值乘积）之和。 题解： 很明显的一个点分治问题，然后就是个二维偏序问题了（虽然我也不知道啥是二维偏序）。点分治不难，重点是点分治内cal函数如何去写。 假设当前计算的这个树是以root为根节点，我们对于每一次分治的过程，每个结点储存两个值，一个是从根节点到当前结点路径上的最大值，另一个是最小值记为。对于任意两点，是由这两个点到root的边上的最大值最小值决定的，也就是他们两个点的乘积实际上是 得到的。 那么我们考虑如何快速的计算出来经过root点的任意两点的所有答案。 考虑把所有点的最大值和最小值存到一个数组里面，然后按照最小值从小到大...

题意：题解：因为这个题目是弱化以后的，正常的范围是5e4 . 看了官方题解去学习了一波可持久化01trie然后回来把这个题补完。 可持久数据结构其实就是我们的数据结构的内容会不断发生变化，而我们还要查询以前的历史版本，比如某个区间的情况。 听名字可以听出来，可持久化01trie跟可持久化线段树差不多的效果，对于01字典树来说，可以指定查询 范围内的数组成的字典树。 但是针对于这个题目我们直接使用可持久化01trie进行维护，时间还是不能被允许的，所以说， 我们还需要去继续优化。 如何优化呢？ 分块！ 我们用数组预处理出来 块x到块y之间的区间任意两数的最大异或值。 时间复杂度呢？ ...

咦，竟然之前做过 题解：是一道很经典的树差分模板题， 点差分我们需要让cnt[s]++,让cnt[t]++，而让他们的cnt[lca]--，cnt[faher(lca)]--;边差分cnt[s]++ ， cnt[t]++ ，cnt[LCA]-=2 边差分：边差分的话要把边的权值存在他连着的儿子节点上，然后儿子节点的权值就是这条边的边权了，u至v路径上所有边的边权+1，那么c[u]++,c[v]++,c[lca]-=2,可以在多次更新树链之后，得到某边权值。 首先我们可以的看到这个题目是在操作了好多边以后最后询问一个答案，这不就是经典树上边差分模板题目吗。树剖LCA+树差分 代码： /*Keep...

题解：简单的dp。也许dp我只会做这种小白型的了（剩下的交给队友奥里给）首先我们先看一下，不优化空间的dp怎么写的。 我们发现他最多会演唱50首歌曲，最大音调为1000。开一个代表演唱到第i个物品的时候，能不能演唱出来音调为j的歌曲。初始状态全是false，只有转移方程： 代码： #include <bits/stdc++.h> #define int long long #define endl '\n' const int maxn=1010; using namespace std; const int mod=1e9+7; bool dp[55][maxn]; in...

题解：这种题之前做过一个类似的题目，也是关于选择区间然后给区间进行排序。这种题用线段树把排序转换成区间修改区间求和即可。类似的题目：https://vjudge.net/problem/HDU-5649 首先我们看到这个题是针对于字母进行排序的，区间操作很像线段树，那么如何把他转换成线段树呢？我们考虑他只有26个字母，那么我们是否可以转换成维护这26个字母呢？对于每一段区间，我们查询每个字母出现的个数。然后按照题目要求（升序还是降序）然后从l到r依次填从小到大填入字母即可。转换为了区间修改和区间查询操作。 #include <bits/stdc++.h> //#define in...

首先先说一下基本概念： 1.重儿子：一个结点的所有儿子中，大小最大的那个（最重的，所以说只有一个，如果有多个儿子的大小相等那就随便取一个）。 2.轻儿子：一个结点的儿子除了重儿子以外的所有儿子都是轻儿子。（根节点为轻儿子） 3.重链：从一个轻儿子开始，一路往重儿子走，连出来的链叫重链。 4.轻链：除了重链全是轻链。 如下图： 重链即为标染色点连出的边。 dfs序即为即为图中红色标号。那么我们如何处理出这个dfs序呢？ 通过两个dfs. 第一个dfs需要： 1.标记结点的父亲 2.标记结点的重儿子 3.标记结点的深度 4.结点的大小 第二个dfs需要： 为什么要第二遍才可以（因为需要第一遍跑...

题解： 对于叶子节点，我们直接购买要求购买的个数即可然后树上维护几个变量，sz表示该节点的子树已经挂在了多少个礼物了，如果挂载的礼物总数小于要求的总数，那么当前结点是要必须再购买一些礼物的，但是并不一定买在当前结点上，我们可以买在他已经他子树上，找一个最便宜的结点来购买礼物，从而保证价格最低！这个我们就需要维护另一个变量imin，表示当前结点包含的所有子树价格最低的是多少。 代码： //#pragma GCC optimize(3 , "Ofast" , "inline") #include<bits/stdc++.h> #define l...

题解： 线段树，不过这里线段树区间维护要换一种方法。我们发现这个等差数列的等差为1。对于修改一段区间如果我们知道首项值，那么我们便可以在的时间复杂度计算出这段区间的大小。又可以知道，对于线段树每一个结点，代表一段区间，那么我们我们用lazy数组保存这一段区间的首项，那么我们便可以在O（1）的时间复杂度内算出这一段区间的值。 代码： #pragma GCC optimize(3 , "Ofast" , "inline") #include<bits/stdc++.h> //#define ll long long using namespac...

题解：二分+bfs，二分最长距离，这个题在bfs时使用堆来处理会变得比较简单，优先去走油量较多的那个点（某个点当前能量最大一定“有利于”接下来点的转移），每当遇到特殊点的时候，把油量加满即可。走到终点即返回true。没走到返回false即可。 代码： /*Keep on going Never give up*/ //#pragma GCC optimize(2) #include<bits/stdc++.h> //#include<iostream> //#include<string> //#include<cmath> //#include...

B.牛牛抓牛妹 题解：感情这个题目很妙。分层图+瞎几把搜索。 我们可以发现题目中最多就只有7个锁，，那我们可以建128层图，读题可知牛妹每回合都会寻找当前位置到终点的最短路线移动，如果最短路线不唯一，她总是会选择移动到节点编号较小的节点，我们不会每次都要跑一次最短路吧。。？？想了想是不必要得，我们可以提前把每种状态他走的下一个点提前预处理出来，就可以O(1)知道牛妹得下一个点去哪了。如何预处理？对于每一种状态来说，我们可以从终点开始进行bfs，遍历每个点，每个点得next即为他的父节点。 我们最终得目的就是把牛妹骗到陷阱当中，那么我们从七点开始bfs搜索，走到走不出来得地方即可break输出。...

A.串 题解：dp三维dp可能更好理解一些。 代表长度为的字符串，当j=1时代表已经含有u了的字符串的个数，k=1时代表已经含有us的字符串的个数。最后输出即可。 /*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> #define int long long #define endl '\n' using namespace std; const int maxn=500+10; const int mod=1e9+7; int ans; i...

题解：分成两种情况来讨论：1.石头单独放到一边，这样就是看看石头能凑出哪些数即可。2.另一边也可以放石头，那么那个重物就是，全为石头一边的重量-另一边石头的重量。分好这两种情况之后就可以进行dp了。 /*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> #define endl '\n' //#define int long long using namespace std; const int maxn=1e5+10; int a[maxn...

题解：暴力枚举+并查集维护联通由于本题点的范围不大，并且边的范围在5000以内。这样的话我们可以采用复杂度的算法。类似于贪心的方法，把边权从小到大排序。因为这个题目只取决于最大最小值，两者比值越小越好。我们把边权挨着枚举一遍即可。从边权最小开始枚举，用并查集维护，每次加入一条边，并且检查s与t是否连接起来，如果连接起来，那么直接与当前最小比较一下然后break。break后，再从次小边开始枚举......再从第三小......直到枚举完所有边即可。所有的情况都枚举过，所以可以确保一定包含最接近题目要求的值 /*Keep on going Never give up*/ #pragma GCC ...