原题解链接：https://ac.nowcoder.com/discuss/150260 本来一开始是想找规律的,然后也确实有点规律,只要数字不进位,最后求出来的这个加权数根就是2−92-92−9循环的,但是每次进位都会跳一小段。 首先计算最大数字的加权数根，发现计算一次之后的结果小于16001600 1600,所以预处理111到160016001600的加权数根。( 当然多算几次压到101010以内也可以)并且把第一次计算数根的结果作为状态存入dpdpdp数组。 然后分别求222到999即可。( 111不用求，只有111的加权数根才等于111 ,后面不可能出现111) #include &l...

原题解链接：https://ac.nowcoder.com/discuss/150260 先把所有数字按从小到大排序,然后第一个数字必须是111 ,如果不是111的话首先111就凑不出来。 然后下一个面值可以是111也可以是222 ,但是不可能为333,因为如果是333或者比333还大的话,那么222就凑不出来了。 所以得到一个递推的规律: 将数字从小到大排序后,如果下一张纸币的面值≤sum+1\leq sum+1≤sum+1( sumsumsum为当前纸币的面值 和).那么这张纸币就能放进来更新sumsumsum ,否则就会断掉导致sum+1sum+1sum+1无法被构造出来。 最后再判断一...

原题解链接：https://ac.nowcoder.com/discuss/150260 可以线段树,但是没必要。因为是先给出线段最后在做询问,所以可以用差分区间修改,最后来一遍前缀和还原。 然后记录数组中被线段仅仅覆盖1次的位置,将这些位置的权值标为1 ,做一遍前缀和。 然后答案就是sum[r]−sum[l−1]sum[r]-sum[l-1]sum[r]−sum[l−1]这样,注意再加上一开始就没有被线段覆盖的点就好了。 #include<bits/stdc++.h> using namespace std; int n,m; const int N = 1e5+5; int a...

原题解链接：https://ac.nowcoder.com/discuss/150260 签到题,假设存在一个数字xx x,改变这个数字的符号后和为000。那么x=sum/2x=sum/2x=sum/2 , sumsumsum 为所有数字的和。然后注意如果一开始所有数字的和是一个奇数的话,那么不可能存在这个xxx。 #include<bits/stdc++.h> using namespace std; int a[100005]; int main() { int n;scanf("%d",&n); int sum=0; for(int i=1;i<=n;++i) ...

原题解链接：https://ac.nowcoder.com/discuss/150260 签到题,两元一瓶汽水,两个汽水瓶可以换一瓶汽水。 也就是说一个汽水瓶的价值是1元钱。 最后可以借一个空瓶,所以最后手里不会剩下空瓶。那么一开始能花掉多少钱,最后就能够喝到多少汽水。 所以奇数会剩下一块钱花不出去,偶数最后不会有剩余。答案为奇数−1-1−1 ,偶数直接输出。 C++可以使用string类。 #include<bits/stdc++.h> using namespace std; int T; string a; int main() { cin>>T; while(T...

原题解链接：https://ac.nowcoder.com/discuss/150246 设f[i]f[i]f[i]表示长度为nnn的不合法序列的数量 如果存在一个位置iii不合法,那么此时1−i1 -i1−i的数恰好构成了一个1−i1 -i1−i的排列 考虑直接递推计算，为了避免重复计算答案，我们去枚举最大的不满足条件的iii 比如序列{123456123456123456}在i=2i = 2i=2或333时都不满足条件,我们只在333处计算贡献 一种的统计方法是,如果是最大的不满足条件的位置，那么i十1 ni十1 ~ ni十1 n位置的数构成的序列一定是合法的，方案数是...

原题解链接：https://ac.nowcoder.com/discuss/150246 O(nm)O(nm)O(nm)是可以跑过的。考虑暴力一点的做法。 对每个位置存一个链表。 每次区间赋值就在区间中每个位置的链表末尾加入一个0/10/10/1。 查询就看区间中每个位置的链表末尾是000还是111。 撤销操作,就是链表的删除，对某个位置的删除是O(1)O(1)O(1)的。 所以时间复杂度为O(nm)O(nm)O(nm),但是空间也是O(nm)O(nm)O(nm)的。 注意到不同位置互不影响，对每个位置依次计算,空间就是O(m)O(m)O(m)的了。 stdstdstd 撤销操作容易想到线段树...

原题解链接：https://ac.nowcoder.com/discuss/150246 转化后的题意为:给出一张图，有多少条边一定在最小生成树上 考虑这样的做法: 按照Kruskal算法的思想，对边按照权值排序，然后依次加入，同时用并查集维护两点之间的连通性 本题最难处理的也就是权值相同的边，我们可以放在一起考虑 如果一条边连接的两个点已经联通了，那么不需要考虑这条边 否则，把该边加入到新图中, tarjan一遍求出所有的桥即可，可以证明这些边一定在最小生成树上 时间复杂度:O(mlogm) O(mlogm)O(mlogm) /* void make_data(int test) { int...

原题解链接：https://ac.nowcoder.com/discuss/150246 令f[i][j]f[i][j]f[i][j]表示次取球后盒子里有jjj个白球的概率,则f[0][1]=1f[0][1] = 1f[0][1]=1。 对于每次取球,j jj个白球只能由jjj或j−1j - 1j−1个白球得到。所以有 f[i][j]=i+1−ji+1f[i−1][j]+j−1i+1f[i−1][j−1]f[i][j]=\frac{i+1-j}{i+1} f[i-1][j]+\frac{j-1}{i+1} f[i-1][j-1]f[i][j]=i+1i+1−j​f[i−1][j]+i+1j−1...

原题解链接：https://ac.nowcoder.com/discuss/150246 对每个点，考虑它被多少条路径经过。在枚举子树的时候用sizesizesize算一下就可以了。 #include <cstdio> #include <cctype> #include <algorithm> #define gc() getchar() typedef long long LL; const int N=1e6+5; int n,Ans,Enum,H[N],nxt[N<<1],to[N<<1],A[N],sz[N]; inline...

原题解链接：https://ac.nowcoder.com/discuss/150246 显然，当k≥vk\ge vk≥v时，最优的构造方法为kkk个111 当k<vk < vk<v时,最优的构造方法为长度为vvv的序列，两端各有一个111,从中间位置开始向左向右各有k−22\frac{k-2}{2}2k−2​个1,也就是10000...1111...0000110000...1111... 0000110000...1111...00001 直接构造输出解的复杂度: O(k)O(k)O(k)或O(klogk)O(klogk)O(klogk) 当然还有更优的做法:即把中间的一...

原题解链接：https://ac.nowcoder.com/discuss/150009 一个简单的期望dpdpdp。用std::vector与std::map暴力存下状态，O(n)O(n)O(n) 转移。转移时枚举 选到了哪个数，根据后继状态更新当前状态。注意当前状态的后继有可能还是自己，那么只要移 一下项就可以计算了。 fst=p1fnxt1+p2fnxt2+…+pkfstf_{s t}=p_{1} f_{n x t_{1}}+p_{2} f_{n x t_{2}}+\ldots+p_{k} f_{s t}fst​=p1​fnxt1​​+p2​fnxt2​​+…+pk​fst​ 转移的式子...

原题解链接：https://ac.nowcoder.com/discuss/150007 块状树套上平衡树 将整块树分成好几部分，分块之后，将整棵树变成了一颗很小的树（一号树），每一个结点都是一个块，定义为二号树。 000查询 查询的是一棵子树，首先，我们找到查询的结点uuu，接着，对uuu所属的那个块中的属于uuu子树的结点都查询一遍，判断其权值是不是严格大于xxx。其次，在222号树对111号树中的子节点所属的块进行查询。 #include<iostream> #include<cstdio> #include<algorithm> #include&l...

原题解链接：https://ac.nowcoder.com/discuss/150007 暴力 #define _CRT_SECURE_NO_DEPRECATE /************************ *创建时间：2018 09 14 *文件类型：源代码文件 *题目来源：原创题 *当前状态：已通过 *备忘录：最小点覆盖 标程 *作者：HtBest ************************/ #include <stdio.h> #include <iostream> #include <string> #include <stdli...