邬澄瑶的gcd 如果用 表示第 个质数，那么任何一个整数 都对应唯一一个形如 的式子 。 而 。 即如果我们要求一堆数的最大公约数，我们只要对每一个质数求出在这些数的最大次数中的最小值，最后把这些幂次累乘起来，就是这些数的最大公约数。 吴楚月的表达式 一个非空表达式前缀可以表示成 的形式。 如果后面接了一个 ，则变成 ； 如果后面接了一个 ，则变成 ； 如果后面接了一个 ，则变成 ； 如果后面接了一个 ，则变成 。 最后还是可以表示成 的形式。 因此只需要遍历整棵树维护每个节点对应的 即可。 温澈滢的狗狗 一旦确定亲密值 以后就只需要 扫一遍即可。 考虑二分亲密值 ，问题转化为对于给定的 ，如...

#1024#AC自动机fail树上dfs序建可持久化线段树cslnb!

https://nanti.jisuanke.com/t/41395 题意：给你两个串a，b，让你找出字典序严格大于b的a的子序列的最大长度。 思路：这道题一看就是模拟嘛，枚举子序列从哪一位后开始字典序严格大于b，找到那一位在a中满足的最左的坐标，然后把后面的也全算上加上前面枚举到的长度就是当前解，对于每个解取个max即可。 那么我们首先开个s数组来预处理一下i位置后26种字母出现的最小下标，0的话则表示不存在这种字母在后面了 for(int i=n-1;i>=0;i--){ for(int j=0;j<26;j++){ if(j==a[i+1]-'a'){ s[i][j]=i+1...

**这道题首先可以二分答案，也就是满足条件的下标个数，我们可以换种方式来理解他：数列中出现的断层数量，下图表示的就是样例中的情况，假使数列为直接的1-n序列，那答案显然是n-1，而如果其中每出现一个断层，则答案减一，而每个断层开始自然是1最优，因此我们需要确定的就是最少的断层数**   **那么为什么具有二分性呢，很显然，一个有x个断层的序列，那对于x+1个断层，我只要在原序列中随意一个断层中再断一次就能严格减小花费，因此二分是合理的**  **然后我们的check函数中要做的就是确定构成该数目断层需要的最少数字之和，那么这里又是很容易就能想到，最长的断层和最短的断层长度差值不会超过1，为什么...

A kotori和糖果   将一个堆二分，递归求该堆合并的最小代价，用map判重。       B kotori和气球   dp递推，在第i个位置放颜色为x的球的方案数为在i-1处放除x以外的球的方案数之和 状态转移方程：s[i][x]=sum{s[i-1][y]，y!=x}    C kotori和出道   先递推求出每一轮报数是奇数位还是偶数位出局直到只剩一个人，然后将该过程逆推即可求得获胜者编号      D kotori和迷宫   直接BFS求解即可         E kotori和素因子   打表筛出每个数的质因子，然后深搜求解最小值     F kotori和n皇后   用map...

A kotori和糖果 B kotori和气球 C kotori和出道 D kotori和迷宫 E kotori和素因子 F kotori和n皇后 G kotori和抽卡（二） H andy和购物 I andy种树 J andy的树被砍了

链接：https://ac.nowcoder.com/acm/contest/940/J 来源：牛客网 题目描述 andy又开始种树了，他觉得老用魔法不太好，这次他决定老老实实地每天种一棵树，第i天种一颗高度为hi的树，按理说老老实实种树就完事了，哪有那么多问题呢？但是他们学校有个叫kotori的人，非常爱砍树，每天都会把所有andy已经种下的树砍掉ci，如果第i天的时候某棵树的高度已经小于等于ci了，那么这棵树就会死亡，以后再也不会被砍了。并且如果到了第n天，有一些树还没被砍，那么kotori就会在第n + 1天把这些树全部砍死。 输入描述: 第一行输入一个整数n，表示andy会种n天的树。...

链接：https://ac.nowcoder.com/acm/contest/940/I 来源：牛客网 题目描述 andy在他的庄园里种了n棵树，排列成一排，标号为1到n。最开始的时候n棵树的高度都是0，也就是种子刚刚被埋下，树还没有长出来。 andy会一种魔法，他每使用一次魔法，就可以让树标号落在连续区间[l, r]里的树的高度增加1。他可以使用q次这种魔法，然后他很好奇，在使用了q次魔法之后，他的所有树的高度分别是多少呢？ 输入描述: 第一行输入两个整数n，q。(1<= n, q <= 1e5) 接下来q行，每行输入两个整数l, r(l <= r)，表示andy让标号落在...

链接：https://ac.nowcoder.com/acm/contest/940/H 来源：牛客网 题目描述 andy要去市场买n件货物，每件货物的价格为ai。商家为了吸引顾客，给每个买N件货物的顾客一个折扣清单，清单上有N个小于1的小数bj表示折扣。对于每个折扣bj，由用户自行决定用它使哪个货物的价格变成bj * ai，并且只能用一次。 andy想让你帮他算一下他最少的花费。 输入描述: 先输入一个正整数t，代表样例的组数。（1≤t≤10） 对于每个样例： 第一行，输入一个正整数n（1≤n≤1000）。 第二行包含n个整数，第i个整数a[i]代表第i个商品的原价。（1≤a[i]≤1e9）...

链接：https://ac.nowcoder.com/acm/contest/940/G 来源：牛客网 题目描述 kotori最近喜欢上了lovelive这个游戏，因为她发现自己居然也是里面的一个人物。 lovelive有个抽卡系统。共有R、SR、SSR、UR四个稀有度，每次单抽对应稀有度的概率分别是80%，15%，4%，1%。 然而，kotori抽了很多次卡还没出一张UR，反而出了一大堆R，气得她想删游戏了。她想知道n次单抽正好出m张R卡的概率是多少？ 输入描述: 两个正整数n和m（1<=m<=n<=50） 输出描述: n次单抽正好出m张R的概率。保留四位小数。 动态规划，...

链接：https://ac.nowcoder.com/acm/contest/940/F 来源：牛客网 题目描述 kotori最近在研究n皇后的问题。 所谓n皇后问题是这样的：一个n*n的地图，上面一共放n个皇后，保证任意两个皇后都不能互相攻击（每个皇后可以攻击同一行、同一列以及同一45度角斜线和135度角斜线上的所有其他皇后）。 kotori思考了很久都无法得出答案，整个人都变成琴梨了。她于是拿了一堆皇后在一个无穷大的棋盘上模拟，按照次序一共放了k个皇后。 但是，皇后的站位太复杂了，kotori甚至不知道是否存在两个皇后会互相攻击。于是她想问问聪明的你，在第i个皇后放置在棋盘上之后，是否存在...

链接：https://ac.nowcoder.com/acm/contest/940/E 来源：牛客网 题目描述 kotori拿到了一些正整数。她决定从每个正整数取出一个素因子。但是，kotori有强迫症，她不允许两个不同的正整数取出相同的素因子。 她想知道，最终所有取出的数的和的最小值是多少？ 注：若a%k==0，则称k是a的因子。若一个数有且仅有两个因子，则称其是素数。显然1只有一个因子，不是素数。 打表筛出每个数的质因子，然后深搜求解最小值 #include<bits/stdc++.h> using namespace std; #define PB push_back #d...