题目大意：数轴上有n个点，在总代价不超过m的情况下，至多可以将多少个点移到一起？（代价：每个点移动的距离） 数据范围500万，递增输入，不需要排序，显然需要用O(n)做法才能满分，而且读入还可能被卡。 能走到一起的，必然是连续的若干个点：如果一个区间中有个点没有移动过去，那么终点要么在他左边，要么在他右边；如果在左边，他右边的点移动过去的代价比他大，没必要；另外的方向同理。 区间平移：至少1各点，区间至少为2才判断；从区间[i=1, j=2]开始，如果能移到一起，那么j加1，尝试让更多的点移到一起；如果不能移到一起，那么左端点无论如何都无法跟j以及j右边的点移到一起了，i加1；边界：i跟j相等...

题目大意：n个点n-1条边的一棵树，有m个点是超市；现在每个点到超市的最短距离都不超过D，至多删除多少条边，还能够保证每个点到超市的最短距离都不超过D？ 预处理：超市点的数量是x，非超市点是y，x+y = n。 1、对于不是超市的点，都需要1条边来连向超市，所以至少需要y条边，至多删除n-1 - y条边。 2、要想删边后每个点到超市的距离不超过D，可以用y条边就够了。超市不需要用边；非超市点，必有一条路连向超市，选距离最短的。不需要管怎么找到这条路，因为我们只需要知道是否可行就够。 #include <bits/stdc++.h> #define N 1000005 using n...

题目大意：n个任务，给你t的时间，最多做多少个？ 选出来的任务时间之后不超过t即可。 假设答案是k个任务，如果其他任务的时间更小，换一个时间更短的任务进来，不影响答案，且花时间只会更少、更好！ 因此，我们可以选最短时间的k个任务。 排序，贪心选择即可。 注意：累加可能爆long long，用减法代替加法可避免此问题。 #include <bits/stdc++.h> using namespace std; long long n, m, i, j, k, a[1000005]; int main(){ scanf("%lld%lld", &m, &n); ...

题目大意：已知n个数的平均值m以及前n-1个数，请问第n个数是多少？ #include <stdio.h> int n, m, i, j, k, s; int main(){ scanf("%d", &n); for(i=1; i<n; i++){ scanf("%d", &k); s += k; } scanf("%d", &m); printf("%lld\n", (long long)m*n-s); return 0; }

题目大意：从第三项开始，每一项等于前两项之和，已知第x项和第y项的值，输出第1项和第2项。 类似于斐波拉契数列，第一项是a，第二项是b，那么之后每一项都与a和b有关： 从第1项开始，a的数量是：1 0 1 1 2 3 5 8 13……从第1项开始，b的数量是：0 1 1 2 3 5 8 13 21…… 首先算出第x项有xa个a、xb个b，第y项有ya个a，yb个b。（需要用矩阵快速幂） xa * a + xb * b = sx（第x项的值）ya * a + yb * b = sy（第y项的值） 第一个式子乘以ya，第二个式子乘以xa，就可以消去a，算出b了！b = (sy - sx) / (b...

题目大意：输入前一个时间和经过的分数数，输出当前时间。 s数组解释：将下列字符串转成一行，反斜杠转义，每行长度42，那么0就是0-2、42-45、84-86，其他字符以此类推。 ._....._.._....._.._.._.._.._......__..... |.|..|._|._||_||_.|_...||_||_|./\.|__||\/| |_|..||_.._|..|._||_|..||_|._|/--\|...|..| 1、预处理数字将每个数字的字符放到一个字符串里面，便于以后比较，b[i]存储第i个数据的字符串。（当然，直接跟s串比也行，不太舒服而已） 2、打印数字输出时，每个数...

题目大意：一棵树，相邻两点不能同色，现有红黄蓝以及各点涂各种颜色的价值，请问涂色后最大价值是多少？ f[i][j]表示结点i涂颜色j子树的最大价值。如果i点图j色，那么儿子结点只能图另外2中颜色，取最大值即可。 最终答案是f[1][0]、f[1][1]、f[1][2]里面找。 #include <bits/stdc++.h> #define LL long long #define N 100005 using namespace std; LL n, m, i, j, k, a, b, ans; LL h[N], v[N][3], f[N][3], u[N]; struct AB...

题目大意：一个从1开始编号的数组的不完美度为，现在可以将数组分成两个从1开始编号的数组，请问分成的两个数组的不完美度之和最小是多少？ 将一个数组分成两半，左半边的不完美度的没有任何变化的。 右半部分，假设是从i开始，区间是[i, n]：第i个元素由a[i]i变成了a[i]*1，第i+1个元素由a[i+1](i+1)变成了a[i+1]2，第j个元素由a[j]*j变成了a[j](j-i+1)……即这个区间多有元素都少加了i-1次！ 枚举端口位置i，右边区间之和乘以i-1即可以减去的不完美度。 注意，整个区间加起来，极端情况下是1e51e51e9/2，约5e18，好像没爆long long。 #in...

题目大意：根据指定规则生成序列a，在所有长度不小于L的区间中，平均值最大是多少？ 1、递推计算序列：根据题目公式计算即可。 2、预处理前缀和：区间平均值，用到区间和，区间和可以通过前缀和O(1)算出来。 3、平均值即斜率：区间i+1到j的平均值是(s[j]-s[i]) / (j-i)，可以使用斜率优化！ 平均值最大的区间，必有一个开头和结尾，即用对应的i和j的斜率。 枚举区间右端点，选择最好的左端点：右端点从长度c开始，选择左端点前，把最先的左端点i-c压入单调队列。 如何维护单调队列？ 1、相邻3个起点x、y、z，斜率应递增，即xy的斜率应小于yz的斜率。 如果xy斜率大于yz的斜率，那么y...

题目大意：n个点，m条边，每条边有颜色，生成一棵树，要求边的颜色数最少，输出最小值。 边多、点少，稠密图，但不能直接去重边，因为颜色是很重要的。因为颜色数量不超过12，那就用二进制存储颜色，输出的结果也是1到12之间！ 用邻接矩阵存储边，暴力枚举每种颜色是否选，时间复杂度，接着搜索判断是否连通。因为只需要知道能不能到达，不需要找最短路，搜过不需要再搜，时间复杂度跟Flood Fill是一样的，因为用邻接矩阵，所以是O(n*n)。总时间复杂度是可以接受。 #include <bits/stdc++.h> using namespace std; int t, n, m, s, i, ...

题目大意：判断2到m有多少个数字是合法的。 对于给定的n个数，是合法的；其他数字若是合法，那么必须存在2到n-1的约数，且这些约数都是合法的。 暴力求解：从小到大枚举2到m，如果约数都合法，标记该数字合法；如果遇到一个不合法的约数，则不标记合法。 需要从小到大确定是否合法，保证用到的约数都是更小的、已确定是否合法。时间复杂度： #include <stdio.h> #include <string.h> #define N 300005 int t, n, m, i, j, k, ans, f[N]; int main(){ scanf("%d", &t...

题目大意：给定一个多项式各校的系数和次幂，输出化简后的非零项数目。 排序，将次幂相同的排在一起；合并同类型，次幂相同累加系数，非零则统计。 （次幂非常大，不能用桶排序；需要哈希或者使用map；排序去重统计更方便。） #include <bits/stdc++.h> using namespace std; int n, m, t, i, j, k, ans; struct AB{ int a, b; bool operator < (const AB &A) const{ return a < A.a; } } d[100...