WORIA

https://ac.nowcoder.com/acm/contest/11190 C - k-palindrome   题意：定义字符串 sss 为 k−palindromek-palindromek−palindrome 当且仅当：是回文串，且若 k>1k>1k>1，则 s[1⋯⌊n2⌋]s[1\cdots \lfloor\frac{n}{2}\rfloor]s[1⋯⌊2n​⌋] 和 s[n−⌊n2⌋+1⋯n−1]s[n-\lfloor\frac{n}{2}\rfloor+1\cdots n-1]s[n−⌊2n​⌋+1⋯n−1] 都是 (k−1)−palindrome(k-1)-palindrome(k−1)−palindrome。给定字符串 sss，问对于 k=1,⋯ ,mk=1,\cdots,mk=1,⋯,m ，sss 的本质不同的非空子串中 k−palindromek-palindromek−palindrome 的个数。 Manacher+字符串哈希 k−palindromek-palindromek−palindrome 一定是 (k−1)−palind ...

https://ac.nowcoder.com/acm/contest/10743 D - Lots of Edges   题意：给定 nnn 个点，有点权 aia_iai​，若 ai&aj=0a_i\&a_j=0ai​&aj​=0，则点 i,ji,ji,j 连一条边权为 111 的边，给定起点 SSS，问从 SSS 到每个点的最短路。 枚举子集+bfs 重新建图，把原图上点权相同的点缩成一个点，则每一条边的两个端点都有二进制下的子集关系，则总边数是 O(3k)O(3^k)O(3k)。再bfs求最短路。 要注意点权和起点相同的点要在最后特殊处理。以及枚举子集时不要忘了0. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << (x) ...

https://ac.nowcoder.com/acm/contest/9510 B - 最小的指数   题意：T,1≤T≤100000T,1\le T\le100000T,1≤T≤100000 次询问，每次给定数 n,1≤n≤1018n,1\le n\le 10^{18}n,1≤n≤1018，令 n=p1a1p2a2⋯pkak,a1,a2,⋯ ,ak>0n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},a_1,a_2,\cdots,a_k>0n=p1a1​​p2a2​​⋯pkak​​,a1​,a2​,⋯,ak​>0，问 min⁡{a1,a2,⋯ ,ak}\min\{a_1,a_2,\cdots,a_k\}min{a1​,a2​,⋯,ak​}。 因数分解 对于这种 nnn 很大的题目，如果要分解质因数，首先就应该考虑能否只枚举一个小范围内的质因子。 枚举 [2,5000][2,5000][2,5000] 的质数，暴力分解，最终 nnn 只包含 >5000>5000>5000 的质因子。 如果 ans=4ans=4ans=4，说 ...

https://ac.nowcoder.com/acm/contest/8051 C - 有用的 LCM   题意：定义前缀 lcm 为 Ln=lcm(1,2,3,...,n)L_n= lcm(1,2,3,...,n)Ln​=lcm(1,2,3,...,n) ，且一个数 x 对其前缀 lcm 有贡献当且仅当 Lx−1≠LxL_{x-1}\not= L_xLx−1​=Lx​ 。特别的， 1 不视为对其前缀 lcm 有贡献。现在你需要求出 1~ n 内所有对其前缀 lcm 有贡献的数的个数。 min25筛 显然答案是 p 的幂次的个数。 只有小于等于 n\sqrt{n}n​ 的质数有大于 1 的幂次，对于这些质数欧拉筛出来，同时统计幂次的个数。 还需要得到小于等于 nnn 的质数的个数，min25筛模板题。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include <bits/stdc++.h>#define debug( ...

https://ac.nowcoder.com/acm/contest/1087 C - 斐波那契数列卷积   题意：给定 nnn，求 an=∑k=0nFn−k×Fka_n=\sum_{k=0}^n F_{n-k}\times F_kan​=∑k=0n​Fn−k​×Fk​，q≤n≤1018q\le n\le 10^{18}q≤n≤1018，其中 FFF 是斐波那契数列，F0=0,F1=1F_0=0,F_1=1F0​=0,F1​=1。 先拆开来看看 an=F0Fn+F1Fn−1+⋯+FnF0an−1=F0Fn−1+F1Fn−2+⋯+Fn−1F0an−2=F0Fn−2+F1Fn−3+⋯+Fn−2F0\begin{align} a_n &= F_0F_n+F_1F_{n-1}+\cdots+F_nF_0\\ a_{n-1}&=F_0F_{n-1}+F_1F_{n-2}+\cdots+F_{n-1}F_0\\ a_{n-2}&=F_0F_{n-2}+F_1F_{n-3}+\cdots+F_{n-2}F_0\\ \end{align} an​an−1​an−2​​=F0​ ...

https://ac.nowcoder.com/acm/contest/375 B - 小A的排列   题意：给定 n,seedn,seedn,seed 以及 nnn 的排列 p[]p[]p[]，问 2×∑l=1n∑r=lnseed(l−1)∗n+rmidl,r2\times\sum\limits_{l=1}^n\sum\limits_{r=l}^nseed^{(l-1)*n+r}mid_{l,r}2×l=1∑n​r=l∑n​seed(l−1)∗n+rmidl,r​，其中 midl,rmid_{l,r}midl,r​ 为 区间 [l,r][l,r][l,r] 中数字的中位数。n≤104n\le 10^4n≤104 思维+链表 首先肯定是想着枚举区间，然后set或者线段树或者主席树之类的维护以下。但是这复杂度显然多了个 log⁡\loglog。 但区间还是要枚举的，在挪动到下一个区间时，需要 O(1)O(1)O(1) 更新中位数，所以需要一个维护权值的链表。 链表中 nxt 维护的是在当前区间中，比 xxx 大的数中最小的那个数字（即当前区间排序后 xxx 后一个数）。pre 维护的是， ...

https://ac.nowcoder.com/acm/contest/11175 D - 数学家的迷题   题意：给定一个数组 aaa，两种操作：将 a[id]a[id]a[id] 改为 xxx；查询 ∏i=lra[i]\prod_{i=l}^ra[i]∏i=lr​a[i] 的素因子个数。n,q≤5∗104,a[i],x≤105n,q\le 5*10^4,a[i],x\le 10^5n,q≤5∗104,a[i],x≤105. 线段树+bitset 10510^5105 内大约有 10410^4104 个质数。用 10410^4104 位的bitset代表。 线段树每个节点维护该节点上的bitset，向上合并时取或。 起初想分块，但是 n\sqrt{n}n​ 的复杂度还是不够，必须 log⁡\loglog。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475 ...

https://ac.nowcoder.com/acm/contest/11174 D - 牛客推荐系统开发之动态特征获取   题意：每个特征有有时间戳，且保质期都为 yyy，在时间戳+ yyy 秒后会失效，每个特征都有优先级，越近使用的特征的优先级越高，内存中只能存放优先级最高的 mmm 个特征，问 nnn 次交互中各次是否需要重新取特征。 双端队列 在内存中需要两个条件：未过期，且优先级在前 mmm 个。 因此维护两个双端队列：时间戳队列，队列中的特征都未过期；优先级队列，队列中的特征的优先级都在前 mmm。 可以直接把按照时间排序后的交互队列作为，优先级队列，只需要记录门槛，保证门槛右侧的都是前 mmm。记录每个特征最近被使用的时间，只要判断这个时间是否位于门槛右侧就能判断优先级是否满足条件。 在维护时间戳队列时需要记录每个特征在队列中的次数，因为一个特征可能先由于优先级不够而离开内存，但由于没有过期，所以在时间戳队列中仍然存在，当再次交互时需要重新取，因此又放进了时间戳队列中，导致在时间戳队列中有两个这个特征。 因此仅当一个特征在时间戳队列中出现次数为 0 时才能视为过期。 1 ...

https://ac.nowcoder.com/acm/contest/7199/A 题意：初始一个 0 节点，三种操作：节点 i 长出一个新的子节点；节点 i 的子树中所有节点权值加 a；询问节点 i 的权值。 离线+线段树 刚开始想树刨，但是如果一条链的话复杂度退化。 关键点在于子树的 dfs序 是连续的，所以子树中所有节点+a 可以变成一个连续区间+a，那么就自然要想到线段树，但是如果动态加边的话肯定不行，因为dfs序会变。 所以需要离线下来，先把整棵树建完。再遍历操作，对于操作2，把它子树对应dfs序的区间加，对于操作3，直接查询，但是在一个节点没有产生时也可能有操作，所以对每点设置一个附加值，在操作 1 第一次产生某个节点时查询此时它的权值，并令附加值为权值的负值。真正的查询结果为查询值+附加值。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475 ...

https://ac.nowcoder.com/acm/contest/7189/A 题意：有 nnn 件货物， 第 iii 件重 wiw_iwi​ 吨，另有 xxx 个集装箱，每个集装箱可以装重量不超过 WWW 吨的货物。 货物不能分拆，判断这 xxx 个集装箱能否装下所有货物。 状压dp f[s]f[s]f[s] 表示已装车的货物情况为 s 时最小需要的集装箱数量。 g[s]g[s]g[s] 表示已装车的货物情况为 s 时最后一个集装箱最大剩余空间。 则对于 s ，遍历每一个为 1 的位，判断如果能状态 t 最后一个集装箱装下这个货物，则箱数等于 t 的，否则等于 t 的+1，取最小值得到 s 的 f 值。最后再遍历所有取到最小值的情况，更新 g。 关键的一点在于遍历所有取到最小值的情况更新 g，如果某一情况的箱子数大于最小值，则即使它剩余的空间很大，也不行，因为最小值可以再开一个空箱子。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include ...