原题解链接：https://ac.nowcoder.com/discuss/163610 题目大意 给定一个序列，求一个子串，使得数字的异或和加上所有的数字最大 题目分析 根据异或的定义，可以得到：b⊕c≥b−cb \oplus c \ge b-cb⊕c≥b−c，原因是： {1⊕1=01−1=01⊕0=11−0=10⊕1=10−1=−10⊕0=00−0=0\begin{cases} 1 \oplus 1=0 & 1-1=0 \\\\ 1 \oplus 0=1 & 1-0=1 \\\\ 0 \oplus 1=1 & 0-1=-1 \\\\ 0 \oplus 0=0 &am...

原题解链接：https://ac.nowcoder.com/discuss/163610 显然，我们要求的答案是(LCP(A[l,r],B[l,r])+1)×(LCS(A[l,r],B[l,r])+1)−1(\texttt{LCP}(A[l,r],B[l,r]) +1) \times ( \texttt{LCS}(A[l,r],B[l,r]) +1)-1(LCP(A[l,r],B[l,r])+1)×(LCS(A[l,r],B[l,r])+1)−1。 那么成为答案的那个区间一定是连续的一段A,BA,BA,B两串相等的子串。否则，若我们选择的不是连续的A,BA,BA,B相等的子串，那么我们可以让选...

原题解链接：https://ac.nowcoder.com/discuss/157310 由题面可知 t=f(x)\ t=f(x) t=f(x)没有平方根，加上xxx的最大质因子为717171，说明它的质因子种数只有202020种。 那么 t=f(x)\ t=f(x) t=f(x)可映射成一个202020位的二进制数。 即 t=p0∗b0+p1∗b1+...+pk∗bkt=p_{0}*b_{0}+p_{1}*b_{1}+...+p_{k}*b_{k}t=p0​∗b0​+p1​∗b1​+...+pk​∗bk​ 其中  pi\ p_{i}&nbsp...

原题解链接：https://ac.nowcoder.com/discuss/157310 设两个球 A\ A A和 B \ B B的体积分别为 Va\ V_{a} Va​ 和 Vb\ V_{b} Vb​ ，半径分别为  ra\ r_{a}  ra​ 和 rb\ r_{b} rb​ ，两球球心距离为 d\ d d。 分三种情况讨论： 两球/相离/外切，那么答案是  Va+Vb\ V_{a}+V_{b}  Va​+Vb​ ； 两球内含/内切...

原题解链接：https://ac.nowcoder.com/discuss/157310 此题可以用FWTFWTFWT通过，但是出题时的想法是一道BFSBFSBFS就可过的题。 MMM最大只有202020，如果把每个二进制串看成一个状态，最多只有220=10485762^{20}=1 048 576220=1048576个状态。 我们把开始给定的所有二进制串看成起始点，每一步搜索对二进制串进行一个二进制位的翻转对全部状态进行BFSBFSBFS，设搜到的步数最大的状态步数为XXX，则答案就是M−XM-XM−X 复杂度O(N2M)O(N 2^M)O(N2M) #include<bits/s...

原题解链接：https://ac.nowcoder.com/discuss/157310 把每个地点看作一个点，那么每个点一定有且仅有一条有向出边。 每个点出度只有111，如果某些点组成了一个有向环，这个环上所有点不会有额外的出边，即这个环一定是一个简单环。 也易证每个点最终都会走向一个环。 结论:单独看待每个联通块，每个连通块一定有且只有一个环，只要在这个环上任何一个点建立哨卡，就能抓到这个联通块中的所有。可以使用把边都看成无向，使用并查集等找出所有连通块并求每个连通块上所有点的数量之和，从大到小排序，取前mmm大即可。 复杂度O(nlogn)O(nlogn)O(nlogn) #includ...

原题解链接：https://ac.nowcoder.com/discuss/157310 简单的计数dpdpdp。 dp[i][j]dp[i][j]dp[i][j]代表第iii个回合后分数为j的方案数 则:dp[i][j]=dp[i−1][j−ai]dp[i−1][−j]dp[i][j]=dp[i-1][j-ai] dp[i-1][-j]dp[i][j]=dp[i−1][j−ai]dp[i−1][−j] 因为开二维内存不够，需要使用滚动数组 特判屏蔽所有来自j=666j=666j=666的状态转移 复杂度O(n∗n∗1333)O(n*n*1333)O(n∗n∗1333) #include &l...

原题解链接：https://ac.nowcoder.com/discuss/157310 因为mmm是一个偶数,不妨分类讨论: 1.一回合可以直接翻转所有硬币(n=m)(n=m)(n=m) 很显然，答案YesYesYes 2.一回合不能直接翻转所有硬币，因为mmm是偶数，所以只需要讨论nnn的奇偶性。 （1）nnn是奇数 某回合结束后所有硬币反面朝上可以等价于所有硬币都被翻转了奇数次。假设可以达成，那么该回合后所有回合总翻转次数一定要为奇数(因为奇数个奇数相加是奇数)然而m是偶数，即使在不使坏的情况下，无论翻转多少个回合，总翻转次数也一定是偶数，所以在这种情况下是不可能赢得游戏的。答案是No ...

原题解链接：https://ac.nowcoder.com/discuss/154293 先将w,v0,v1 w,v_0,v_1w,v0​,v1​ 求和，然后将选择/不选择视为在此基础上付出代价，问题就转化为了求最小代价。 对于每个约束，考虑如下的一个图，s,ts, ts,t表示源点和汇点，x,y x, yx,y表示跟这个约束相关的两把剑，a,b,c,d,e,f a,b,c,d,e,fa,b,c,d,e,f表示权值 将割掉s ss到某一把剑x xx的边视为不选择x xx ，割掉x xx到t tt的边视为选择xx x。 要使s,t s,ts,t不连通，割有四种a,c，b,d，a,e,d，c,f,...

原题解链接：https://ac.nowcoder.com/discuss/154293 默认n≤m n \leq mn≤m ∏i=1n∏j=1mg(gcd⁡(i,j))\prod_{i=1}^{n} \prod_{j=1}^{m} g(\operatorname{gcd}(i, j))∏i=1n​∏j=1m​g(gcd(i,j)) 更换枚举顺序，先枚举gcd(i,j)​ \text{gcd}(i,j)​gcd(i,j)​ ，原式化为 ∏d=1ng(d)∑i=1n∑j=1m[gcd⁡(i,j)=d]\prod_{d=1}^{n} g(d)^{\sum_{i=1}^{n} \sum_{j=1}^...

原题解链接：https://ac.nowcoder.com/discuss/154293 令Ax=∑i=1xai×i,Bx=∑i=1xaiA_{x}=\sum_{i=1}^{x} a_{i} \times i, B_{x}=\sum_{i=1}^{x} a_{i}Ax​=∑i=1x​ai​×i,Bx​=∑i=1x​ai​ fif_ifi​ ​ 表示以i ii为右端点的 “最大子段和”，假设左端点为j+1 j+1j+1 则 fi=∑k=j+1iak×(k−j)f_{i}=\sum_{k=j+1}^{i} a_{k} \times(k-j)fi​=∑k=j+1i​ak​×(k−j) =Ai−Aj−...

原题解链接：https://ac.nowcoder.com/discuss/154293 先考虑回路的情况。由于是一棵树，任两点间路径只有一条，从一条边走到深度更大的点，一定还会从同一条边返回以回到起点或者遍历其他子树，所以每条边需要复制一次，此时答案是边权和的两倍。 不是回路的情况可以减掉从终点回到起点的路径，要让这条路径尽量长，所以长度一定是直径的长度。 答案就是边权和的两倍减去直径长度。 求直径可以树形DPDPDP或者BFS/DFSBFS/DFSBFS/DFS两次 复杂度 O(n)O(n)O(n) #include <bits/stdc++.h> using namespa...

原题解链接：https://ac.nowcoder.com/discuss/154293 以完成时间为关键字从小到大排序(可以交换两个完成时间不同的任务来证明这样的正确性)，按这个顺序来做任务，同时维护一个关于zi z_izi​ 的大根堆，如果规定时间内完不成任务，就从堆里取出zi z_izi​ 最大的任务来花费金币，维护每个任务的剩余时间，如果花费金币后剩余时间不为 000 则重新pushpushpush入堆 复杂度 O(nlogn)O(nlogn)O(nlogn) #include <bits/stdc++.h> using namespace std; typedef pa...

原题解链接：https://ac.nowcoder.com/discuss/154293 令 dpi,j,kdp_{i,j,k}dpi,j,k​表示目前序列放入到第i ii位，最后两个数字为j,k j,kj,k时的方案数，提前将不合法的子段标记 转移方程为 dpi,k,l=∑j=149can⁡j,k,l×dpi−1,j,kd p_{i, k, l}=\sum_{j=1}^{49} \operatorname{can}_{j, k, l} \times d p_{i-1, j, k}dpi,k,l​=∑j=149​canj,k,l​×dpi−1,j,k​ cancancan为000表示不合法，1...