原题解链接：https://ac.nowcoder.com/discuss/151166 动态规划: 当s[i]=′1′s[i]='1's[i]=′1′时可以选择休息和工作，当s[i]=′0′s[i]='0's[i]=′0′时只能休息 理解一、 我们用dp[i][j][k]dp[i][j][k]dp[i][j][k]表示考虑到第iii天，当前已经一共工作了jjj天，且现在连续工作的天数为kkk的时候剩余体力的最大值，那么我们就可以根据当前位是000还是111写出状态转移方程 当s[i]==′0′s[i]=='0's[i]==′0′时 dp[i][j][0]=max(dp[i][j][0],dp...

原题解链接：https://ac.nowcoder.com/discuss/151166 可以用字符串最小表示法解决 #include <cstdio> #include <bits/stdc++.h> #include <map> #include <cstring> #include <algorithm> using namespace std; #define mst(a,b) memset((a),(b),sizeof(a)) #define rush() int T;scanf("%d",&T);while(T--...

原题解链接：https://ac.nowcoder.com/discuss/150263 强连通分量+并查集 时间复杂度O(M)O(M)O(M) 由于情况非常的复杂，考虑一次性判断完所有情况，可能会写的非常的累。 于是我们可以分成三次检查，每次检查只检查一部分不合法的情况。 第一次强连通算法的检查: 强连通算法跑出来之后,如果存在一个强连通分量中有一些成员拥有照片和一些成员没有即为不合法，如果超过一个强连通分量里有人拥有照片也是不合法。 第二次并查集检查: 对于每一条两个端点都是拥有照片的人的边。我们合并这条边的两个端点。 然后依此合并完，如果所有拥有照片的人无法合并到一个集合中，那么我们认为...

原题解链接：https://ac.nowcoder.com/discuss/150263 后级数组: 时间复杂度O(SUM(M)∗log(SUM(M))+SUM(M)+N)O(SUM(M)*log(SUM(M))+ SUM(M)+N)O(SUM(M)∗log(SUM(M))+SUM(M)+N) 我们把歌曲当成字符串。 我们将所有的字符串，加上分割字符之后，跑后缀数组,然后forforfor一遍sasasa数组,通过heightheightheight数组，来维护一个distdistdist数组，用来代表当前后缀所在的字符串和所有其他字符串的“满足SASASA小于当前SA的最近一个后缀"的LCP...

原题解链接：https://ac.nowcoder.com/discuss/150263 解法很多，比如DP,贪心，二分。 题解里提供二分的解法。 时间复杂度O(T∗log(1e18)∗2)O(T*log(1e18)*2)O(T∗log(1e18)∗2) 我们发现，最后交出来的答案的区间在小进制下一定连续的。 所以我们考虑，所以我们二分出答案区间在小进制下的左右端点，然后做差就是答案。 注意，特判两段区间没交集的时候请输出0而不是负数或者其他的结果。 #include<bits/stdc++.h> using namespace std; long long change_m_10...

原题解链接：https://ac.nowcoder.com/discuss/150263 时间复杂度预处理O(233∗233∗233)O(233*233*233)O(233∗233∗233) 单次查询O(1)O(1)O(1) 弗洛伊德处理233∗232233*232233∗232对之间的转换最短路。 先特判AAA与BBB是否相等，相等就是000,如果AAA和BBB不相等并且BBB大于等于233233233的话,就是无解。 如果AAA小于233233233，BBB小于233233233,直接查询弗洛伊德表。 如果AAA大于等于233233233的话我们要先使用F(X)F(X)F(X)和G(X)G...

原题解链接：https://ac.nowcoder.com/discuss/150263 入门动态规划: 时间复杂度O(N+(A+B))O(N+(A+B))O(N+(A+B)) dp[5000][2][50]dp[5000] [2] [50]dp[5000][2][50] 第一个维度表示当前处理到第几个位置也就是DP的阶段,第二个维度表示重复的是元音还是辅音，第三个维度表示重复的次数。 对于每一个阶段。考虑4种转移。 上一个是元音当前状态也是元音的转移。 上一个是辅音当前状态是元音的转移。 上一个是元音当前状态是辅音的转移。 上一个是辅音当前状态也是辅音的转移。 转移方程: dp[i][0][...

原题解链接：https://ac.nowcoder.com/discuss/150263 时间复杂度O(1)O(1)O(1) 签到题:要考虑题中定义二进制整数必须是222的kkk次方(k>0)(k>0)(k>0) 因此二进制整数不可能是奇数,所以二进制半整数也不可能是奇数，而且最小应该是444。 然后二进制整数也可能是二进制半整数。 综合下来就是满足，大于等于444，并且不是奇数，并且二进制位里有111个或者222个111。 #include<bits/stdc++.h> using namespace std; long long bit_count(long ...

原题解链接：https://ac.nowcoder.com/discuss/150249 题解:通过暴力程序可以找到规律，答案等于A∗n！A*n！A∗n！,A AA为最高项的系数。1e9!1e9!1e9!可以用分块打表实现。 暴力打表，存下1e7,2e7,3e7....1e9−1e7,1e91e7,2e7,3e7....1e9-1e7,1e91e7,2e7,3e7....1e9−1e7,1e9。总共100100100个数。然后比如要求(2e7−1)!(2e7-1)!(2e7−1)!,那就从表中2e72e72e7开始往下接着算。时间复杂度为O(1e7) O(1e7)O(1e7)。 证明:多项式数...

原题解链接：https://ac.nowcoder.com/discuss/150249 hashhashhash练习题。 预处理所有262626种变化的hashhashhash表，用hashhashhash表来判断子串是否相等。 假设xxx的第iii种变化与yyy相等，ans=min(i,26−i)ans=min(i,26-i)ans=min(i,26−i)。 都不相等就−1-1−1。 #include <bits/stdc++.h> using namespace std; typedef unsigned long long ULL; const int maxn = 2e5...

原题解链接：https://ac.nowcoder.com/discuss/150249 先树状数组求逆序数，然后有个结论。 结论: 111到nnn的排列，任意交换两个数，逆序数奇偶性发生改变。 ansansans=(操作前的序列的逆序数+需要交换多少次才能变成操作后的序列(不需要求最小操作次数))%222。  #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+100; struct BIT{ int val[maxn]; int lowbit(int x){ return x & -x; ...

原题解链接：https://ac.nowcoder.com/discuss/150249 首先一个结论:若后三位能被8整除，那么这个数就能被8整除。 那么做法就是贪心，前面的数尽量大，后三位的每位都尽量小，而且排列后能被888整除。 实现方式比较多(? ), 这里仅说一下stdstdstd做法。 特判掉只有111位和222位，这里注意不能直接判能不能被888整除，比如23−>3223->3223−>32。 预处理后333位能被888整除的所有情况，每种情况按字典序降序后，再总体按字典序升序。 比如: 104−>410104->410104−>410， 112...

原题解链接：https://ac.nowcoder.com/discuss/150249 ans=r/x−(I−1)/xans=r/x-(I-1)/xans=r/x−(I−1)/x // // Created by calabash_boy on 18-10-18. // #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #ifdef __LOCAL_DEBUG__ # define _debug(fmt, ...) fprintf(stderr, "\033[91m[%s %3d]: " f...

原题解链接：https://ac.nowcoder.com/discuss/150249 数数xi的个数，用埃筛的方式计数。然后forforfor一遍找到最大值，再forforfor一遍统计最大值数量即可。 时间复杂度O(nlogn)O(nlogn)O(nlogn)。 // // Created by calabash_boy on 18-10-18. // #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #ifdef __LOCAL_DEBUG__ # define _debug(fmt,...