将边权->点权，只需要在dfs的时候求出两个点的深度，把边权下方到深度更深的节点上即可。但是转化完之后，最后query_path的时候要注意，是求的son[u]和v之间的信息（因为点u保存的是u点到他的father节点之间的那条边，不应该算在u->v内）Housewife Windtips：边权转化为点权，然后单点修改线段树，线段树维护区间和信息。一点需要注意：如果query_path最后的u == v，就要直接break而不能算了。因为边权转化为点权后算son[u]和v的信息会出错。 #include<iostream> #include<cstdio> ...

线段树维护区间信息的题单dalao的博客最长区间带修改的严格最长上升子序列长度。【练习线段树做法】要深入理解线段树的l, r是指的数组下标这句话emm.一个节点保存：左边的LIS长度， 右边的LIS长度， 区间总体的LIS长度， 区间的元素个数（其实可以算出来）。关键在于pushup函数：先更新区间的llis,rlis,tlis.然后如果左边最右的值<右边最左的值（这个可以用线段树中节点在数组的下标实现，因为l,r指的是下标）：那左右两个区间就可以构成lis,所以可以继续更新：如果左边的llis==左边的size，代表左边整个是一个最长上升子序列，那llis就可以更新；同理rlis也可以...

不降数这个题很有意思哇 有很多的解法emm记录一下做题过程qwq如果n的范围小一点，可以直接用数位dp过掉，但是n太大会mle.于是写了一个线性dp递推+滚动数组，复杂度是1e10的emmmdp[i, j]表示第i位以j结尾的数的个数。可以留着对拍： #include<bits/stdc++.h> #define ll long long using namespace std; const int mod = 100019; ll dp[2][15], n; int main(){ for(int i = 1; i <= 9; ++ i) dp[1][i...

D. Omkar and Circle 【前缀和，区间DP思想】题意： 在一个圆上排布着奇数个点，连续的3个点，可以合并为1个点，这个点的值由左右2个点的和决定【例如1 2 3可以合并成4,2的两侧1 + 3】，只要有3个以上的点，就可以不断进行合并，最后，圆上只会剩下一个点，要求这个点的值最大。思路：明显的拆环成链区间DP。定义dp[i, j]为从i到j能得到的最大数值，注意区间长度为偶数的时候是无法合并成一个点的，所以dp的值为0.计算l->r的时候，选k为分界，i->k-1是一段，k+1->j是一段，合并这两段即可。【可以用来对拍qwq】 #include<bit...

B. GCD Compression【思维】题意： 给出一个2n数组a，从a数组选出2（n-1），每次取两个数，其和加入b数组，使b数组构成一个n-1长且gcd(b1,b2,...,bn)>1，输出n-1对数在a数组的下标。思路： 奇数两两配对， 偶数两两配对， gcd至少是2. void solve(){ cin >> n; vector<int> odd, even; for(int i = 1; i <= 2 * n; ++ i){ cin >> mp[i]; if(mp[i] &am...

C - A Cookie for You【贪心】题意： if the guest of the first type: if v>c the guest selects a vanilla cookie. Otherwise, the guest selects a chocolate cookie.if the guest of the second type: if v>c the guest selects a chocolate cookie. Otherwise, the guest selects a vanilla cookie.思路： 可以发现，第一种类型的人只要有...

cf补题 652B - AccurateLee 题意：如果一个字符串有连续10，可以去掉1或者去掉0,问最短的字典序最小的串。思路：前面的0和后面的1一定去不掉。中间的10无论怎么排列，都可以消成一个0，所以前后找一遍即可。注意特判00001111这种一个都消不掉的。 void solve(){ cin >> n >> s + 1; int idx1 = 1, idx2 = 0; for(idx1 = 1; idx1 <= n; ++ idx1) if(s[idx1] == '1') break; ...

城市规划 【贪心】 #include<bits/stdc++.h> #define ll long long using namespace std; const int N = 1000010, M = 10000010; #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++) char buf[(1 << 22)], *p1 = buf, *p2 = buf; inline int ...

G. Maximize the Remaining StringCF 1506G 【2000 贪心 单调栈】题意： 给一个字符串， 每个字符只能保留一个， 要求字典序最大。自己写的时候写假了emm 因为每次判断的时候并不知道后面的字母是不是已经被选过了qwq辣鸡wa2代码： void solve(){ scanf(" %s", s + 1); memset(a, 0, sizeof a); n = strlen(s + 1); vector<int> v[30]; for(int i = 1; s[i]; ++ i){ ...

白兔的字符串 【字符串hash】思路：根据题目描述，可以把T串扩展成2倍，然后每lenT段求一个字符串hash值，这样就可以求得所有同构串的hash值了。然后对于新串，每隔长度为lenT段求一个hash，看这个hash值是否出现即可。tips:这题听说map会T, 可以手写一个二分查找，起到一样的效果。 #include<bits/stdc++.h> #define ll unsigned long long using namespace std; const int N = 2000010, P = 131; int n,m,len; ll h[N],p[N]; char...

诡异数字https://ac.nowcoder.com/acm/problem/20669思路：dp[pos, pre, cnt]表示当前位置是pos,上一位出现的数是pre, 这个数出现cnt次的数量。 #include<bits/stdc++.h> #define ll long long using namespace std; const int N = 25, mod = 20020219; ll t ,l, r, n, numlim[N], num[N], dp[N][10][1010]; ll dfs(int pos, bool limit, bool le...