原题解链接：https://ac.nowcoder.com/discuss/181037 首先树形dpdpdp一下,用f[i]f[i]f[i]表示以iii为根的子树最大收益是多少。 询问的简单路径中，有些边是必须跑的，所以j把这些边从dpdpdp里面单独拿出来。然后再强制加回去就行了。 /* * @Author: wxyww * @Date: 2019-01-24 17:27:42 * @Last Modified time: 2019-01-25 17:25:41 */ #include<cstdio> #include<iostream> #include&lt...

原题解链接：https://ac.nowcoder.com/discuss/181037 此题为送温暖题目。。 把所有的数字转换为三进制，对于每个卡片都是形如000001000000000100000000010000的形式 所以SSS为222222222222222222的形式，共有nnn位 然后考虑当第iii位上为111的时候，表示这一位上需要选111个3i3^i3i 的卡片，同样，为222时需要222个，为000时只需一个。 当需要111个时，有两种选择，其他的都只有一种选择。 又因为SSS的形式是222222222222222222 我们从111枚举到SSS，只需考虑哪些位置上面是22...

原题解链接：https://ac.nowcoder.com/discuss/181037 首先换个姿势看这个问题 求有多少个xxx满足L≤x<x+2k≤RL \le x < x + 2k \le RL≤x<x+2k≤R，并且gcd(x,x+2k)=1gcd(x,x+2k)=1gcd(x,x+2k)=1 众所周知，gcd(x,x+2k)=1gcd(x,x + 2k)=1gcd(x,x+2k)=1与gcd(x,2k)=1gcd(x,2k)=1gcd(x,2k)=1等价。 所以问题转化为求区间[L,R−2k][L,R - 2k][L,R−2k]内有多少xxx满足gcd(x,2k)=...

原题解链接：https://ac.nowcoder.com/discuss/181037 画出图来，可以发现具有单调性，只要计算出有多少个位置回到了源点就行了。 /* * @Author: wxyww * @Date: 2019-01-21 09:11:22 * @Last Modified time: 2019-01-25 18:05:44 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #inclu...

原题解链接：https://ac.nowcoder.com/discuss/181037 对于每种颜色，只要找到出现的最靠右的位置和最靠左的位置输出即可。如果找不到，那就藏在下一种颜色下面。 其实可以做到O(n)O(n)O(n)数据范围受限于SPJSPJSPJ /* * @Author: wxyww * @Date: 2019-04-18 14:30:15 * @Last Modified time: 2019-04-18 14:34:18 */ #include<cstdio> #include<iostream> #include<cstdlib> ...

原题解链接：https://ac.nowcoder.com/discuss/173818 简单的数学题。 首先，你需要注意到题面种“若存在j∣i j \mid ij∣i，则会使的你的血量减少 111”这句话的含义，是“如果存在，那么血量减111”，因此无论有多少个jjj 满足j∣i j \mid ij∣i ，你的血量都只会减少1 11 考虑k=0k=0k=0时，你开局就死了，因此答案一定为QAQQAQQAQ 考虑k=1k=1k=1，即你不能选择任何会触发反击魔咒的武器，即你能够选择的数，不是[2,m][2,m][2,m]中任何一个数的倍数。当 m=1m = 1m=1 时，注意到我们不需要考...

原题解链接：https://ac.nowcoder.com/discuss/173818 简单的网络流题。 抛开要求时间的限制，我们直接考虑如何判断这些废水是否可以被处理。我们把每户人家看做一个点，发现限制主要是在点而不是在边，我们就可以很自然地将每个点v vv 拆成两个点v1 v_1v1​ ​ 和v2 v_2v2​ ，建立源点S SS 和汇点T TT，对于每一个v vv，我们建立源点到 v1v_1v1​ ​ 的弧，容量为该点一开始拥有废水的数量vi v_ivi​ ，v2v_2v2​ ​ 连向 TTT一条容量为废水处理数量wi w_iwi​ ​ 的弧。对于原图的每一条边 (a,b)(a,b)(...

原题解链接：https://ac.nowcoder.com/discuss/173818 简单的贪心题。最后一个测试点专门卡了一下n=0n=0n=0可能让部分dalao的体验极差……出题人在此谢罪qwq 题目的含义其实是可以从{a},{b}\{a\}, \{b\}{a},{b}中选出若干个数，选择一个数代价为111，你的利益为你{a}\{a\}{a}和{b}\{b\}{b}利益中的最小值。最大化你的利益。 我们记A=∑i=1naici,B=∑i=1nbidi,K=∑i=1nci+∑i=1ndiA=\sum^n_{i=1} a_ic_i, B=\sum^n_{i=1} b_id_i, K=\su...

原题解链接： https://ac.nowcoder.com/discuss/173818 简单的图论题。 首先，我们考虑最简单的情况，即k=0k=0k=0。然后，为了判定答案是否合法，我们考虑求出学完所有知识点的最小用时。考虑到一个知识点yyy只能被下列两种途径学会： 单独学习这一个知识点，耗时TyT_yTy​ ​ 从某个已经学会的知识点xxx中学习得来，耗时HxyH_{xy}Hxy​ ​ 如果我们新建一个“虚拟知识点”GGG，并假设它刚开始便已经学会。那么，我们可以将第一种方案转化为第二种方案，即HGyH_{Gy}HGy​ 。而学会所有知识点，本质上就是将所有知识点联通，即求出原图的最小生...

原题解链接：https://ac.nowcoder.com/discuss/173818 简单的模拟题。 题目等价于求分数 ab\frac{a}{b} ba​ 的小数点后K1 K_1K1​ 到K2 K_2K2​ 位的所有数字。 直接暴力模拟除法过程是肯定会 TT T的，但是我们发现我们不用从头开始模拟，只需要从K1 K_1K1​ ​ 位开始模拟就可以了。 直接通过快速幂+取模算出第 K1K_1K1​ ​ 位的数字。然后我们发现K2−K1≤105 K_2-K_1 \leq 10^5K2​−K1​≤105 ，所以暴力枚举除法过程就可以。 时间复杂度 O(n)O(n)O(n)。 #include ...

原题解链接：https://ac.nowcoder.com/discuss/173818 简单的枚举题。 直接 O(n2)O(n^2)O(n2) 枚举每对人判断是否成立即可。 注意到输出的字符串为 YE5 和 N0 即可通过此题。 #include <bits/stdc++.h> using namespace std; int n; long long p[101],d[101]; int main(int argc, char *argv[]){ cin>>n; for(int i = 1;i <= n;i++) cin>>p[i]&gt...

原题解链接：https://ac.nowcoder.com/discuss/163610 题目大意 给定一棵树和树上的一些点集，多次询问一个点到某个点集的距离的最小值。 题目分析 我们不妨对每个点集建立虚树，那就相当于从虚树上找到离询问点最近的那个点，再加上虚树上这个点到询问点集中的点的距离的最小值。 那么现在的问题就是如何找到虚树里询问点最近的那个点。 首先，如果询问点不在虚树根的这个子树里，那么虚树的根就是我们要找的那个点，否则肯定就是这种情况： 假设A,BA,BA,B两点是虚树上的相邻的点，C是我们的询问点。 那么我们要找的点肯定是A,BA,BA,B中的一个点。 考虑我们怎么找AAA点...

原题解链接：https://ac.nowcoder.com/discuss/163610 题目大意 给定一棵树，点有权值，有 qqq次询问，每次给定 l,rl,rl,r，求所有点权在[l,r] [l,r][l,r]之内的点所构成的斯坦纳树的大小（即构成的最小连通块中点的个数） 其中 1≤n≤4×105,1≤q≤3×106,1≤ai≤109,1≤l≤r≤1091 \leq n \leq 4 \times 10 ^ { 5 } , 1 \leq q \leq 3 \times 10 ^ { 6 } , 1 \leq a _ { i } \leq 10 ^ { 9 } , 1 \leq l \leq...

原题解链接：https://ac.nowcoder.com/discuss/163610 题目大意 请你求出一个111 ~ NNN的排列，使得它正好有K KK个逆序对。 由于存在很多种这样的排列，所以要求出字典序最大的排列。 因为排列可能很长，所以你只用输出类似于将这个排列放到N+1 N+1N+1 进制下的值，即 ∑i=1Np[i]∗(N+1)imod   109+7\sum \limits _{i=1}^{N} p[i]*(N+1)^i \mod \ 10^9+7 i=1∑N​p[i]∗(N+1)imod 109+7，其中 ppp 是你求出的排列。 题目分析 观察字典序最...