#pragma GCC optimize(2) #include <iostream> #include <map> #include <ctime> #include <vector> #include <climits> #include <algorithm> #include <random> #include <cstring> #include <cstdio> #include <map> #include <set> #include <bi...

A.神秘钥匙 答案明显是(从n人找i人，并且i人都可以当队长)，但是，这个时间限制只能O(1)求值，因此，考虑怎么求和。推导过程： 我们令j=i-1,则：  #include <iostream> #include <map> #include <ctime> #include <vector> #include <climits> #include <algorithm> #include <random> #include <cstring> #include <cstdio> #i...

这道题算是一道分层图的最短路：按照天数对图进行分层，并且，在day-1层和day层，每个相连的节点(u,v)都有一条权值为w[day]的边，表示从day-1天在u到day天到v需要w[day]的路费。这样考虑的话，我们可以把每个节点拆成k个，然后每个节点u的第day-1个连到v节点的第day个，边权为w[day]，构建一个图然后跑最短路。但是，蒟蒻不会拆点(划掉)。由于每次连点都是从u的day-1转移到v的day，因此，考虑在松弛操作上做手脚，达到类似分层的效果：把松弛操作改为 if(dis[v][day+1]>dis[u][day]+e[i].w+a[day+1]) dis[v][da...

回文串大家都很熟悉，但我们平常使用的方法是枚举中心点向外扩展求，复杂度是.但这道题，需要枚举n种字符串，每个最长为5e3，若找最大长度会炸，所以，需要马拉车算法优化，复杂度为。具体算法内容网上有很多。具体看代码注释吧。 #include <iostream> #include <map> #include <ctime> #include <vector> #include <climits> #include <algorithm> #include <random> #include <cstring...

首先，题目有个条件：n个节点，n-1条路径，所以，这是一棵树。之后，会再在u,v之间加入一条边权为0的边，让我们求图上任意两点的最短路。若我们忽略新加入的uv边，那直接求lca求距离就行了。但是，现在加入了uv边，但是，我们可以想到，如果真正的最短路径不经过uv边，那么答案依旧还是lca求得的结果，因此，我们可以分两种情况：经过uv边和不经过uv边。不经过uv边上面已经说过了，若经过uv边，肯定经过u，v中的某一个节点，则，我们可以把这个节点（u和v任选一个）作为中转节点（这里假设选了u），那么，很显然，在经过u的情况下的最短路径对dis[x]+disy，因此，我们可以以u点为原点跑一次单源点...

打开博客发现上次咕咕咕了写一半。。想想还是补完，顺便复习下。 A、胖胖的牛牛 好像bfs也行。我这里用的是dfs，后来用了最短路解。这里主要说最短路。将每个点分成上下左右四个点，用点，其中i、j是点坐标，k为其方向：0为左，1为上，2为右，3为下，(因为当i=n,j=n时，，所以是)然后用0点作为超级起点,作为超级终点，套下最短路就行了。DFS: #include <iostream> #include <map> #include <ctime> #include <vector> #include <climits> #inclu...

这道题需要了解素数筛的原理，而不是只是套模板。需要明白一点，我们在欧拉筛中筛掉合数用的是这个合数的最小值因子。还记得那一步if(i%primes[j]==0) break;吗？这一步就保证我们用的是最小值因子筛掉所有的合数。我们可以这么理解，当i%primes[j]的时候，i=k*primes[j],这时候，我们如果不break，继续下一个，则i*primes[j+1]=k*priems[j]*primes[j+1]=(i*primes[j+1])*primes，说明现在的i*primes[j+1]的最小质因子其实是primes[j],只要后面i增大了，i*primes[j+1]自然会被筛掉。...

默认的dp原问题是问最后回到1点的可能方法。子问题是已知上一部传到各点的方法数，求这一步传到某一点的方法数。设状态dp[i][j]为在第j步的时候，求传到i的方法数状态转移方程为dp[i][j]=dp[left][j-1]+dp[right]j+1.这里给出两种写法。 #include <iostream> #include <map> #include <ctime> #include <vector> #include <climits> #include <algorithm> #include <random...

思路很简单，就是枚举最高点，然后两边分别lis再求len1+len2+1的最大值，主要是lis的nlogn写法。 #include <iostream> #include <map> #include <ctime> #include <vector> #include <climits> #include <algorithm> #include <random> #include <cstring> #include <cstdio> #include <map> #in...

A.论如何出一道水题签到题，注意下特殊情况 n=input() n=int(n) if n==1: print(2) else: print(2*n-1) B.暴力出奇迹感觉好难想。。这道题的方法是：按位把ai分解，然后，按照二进制位，纵向的看各个ai，若在一段中ai在某一位上都是1，那么，这一点"与运算"出来的结果也会是1，那么，我们就可以尝试下这个值是不是最大值(说简单点，就是一整段&之后去和ans取一个max),最后出来的结果就是最大值。直接写完会有个疑虑:会不会存在一种情况，中间有个0，但是选出来的AND*SUM更大呢？这个得看其他位上的情况。若其他位上的这个位置都为0，那么很...

这道题的解法非常妙。一开始，我的想法是：在bfs是搜索过程中带着状态变量con(表示是否遇到过墨菲斯托或莉莉丝，两个都遇到了这个路线就不成立，可以pop掉。)但是发现这样vis数组会其冲突，压缩起来会比较麻烦。参考大佬的解法：分两次bfs第一次，将墨菲斯托的位置全部设为无法进入，莉莉丝设为空房间，bfs一次，得出最短路。这一步的目的是：求出不经过墨菲斯托所在位置能不能得到书，能的话，返回最短距离，不能则返回-1。第二次反过来，墨菲斯托设为空房间，莉莉丝设为无法进入，再进行一次bfs。同样的，这一步的求出不经过莉莉丝能不能得到书。然后，综合两次结果得出结论：若两个结果都是-1，说明不管怎么走，都...

A.小A买彩票 一开始想到排列组合，但是发现太菜不会写orz。看到数据范围小，想直接暴力，TLE，然后，联想到记忆化搜素减少搜索，所以应该是dp。但是菜鸡并不会设计状态（划掉），所以，只能写dfs+记忆化搜索。 #include <iostream> #include <map> #include <ctime> #include <vector> #include <climits> #include <algorithm> #include <random> #include <cstring>...

本来不想打的，结果看着看着自己就打进去了（笑哭） A.第k小数 记得上课讲过。这道题卡排序（但听说有人排序过了？？） #include <iostream> #include <map> #include <ctime> #include <vector> #include <climits> #include <algorithm> #include <random> #include <cstring> #include <cstdio> #include <map> #...

A拯救咕咕咕之史莱姆 签到题。从1到6天，依次扣除3,6,9,12,18,27,求个和就是75，也就是说只要hp<=75，他就会乖乖求饶，否则，死磕到底。 #include <iostream> #include <map> #include <ctime> #include <vector> #include <climits> #include <algorithm> #include <random> #include <cstring> #include <cstdio> ...