[HAOI2016]字符合并 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld  题目描述  有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。 输入描述: 第一行两个整数n，k。 接下来一行长度为n的01串，表示初始串。 接下来2k行，每行一个字符ci和一个整数wi，ci 表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符,wi表示对应的第i种方案对...

[SDOI2008]SUE的小球   文章目录    题目描述 题解： 代码：    时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld  题目描述  Sue和Sandy最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且充满刺激的大海上，Sue有一支轻便小巧的小船。然而，Sue的目标并不是当一个海盗，而是要收集空中漂浮的彩蛋，Sue有一个秘密武器，只要她将小船划到一个彩蛋的正下方，然后使用秘密武器便可以在瞬间收集到这个彩蛋。然而，彩蛋有一个魅力值，这个魅力值会随着彩蛋在空中降落的时间而降低，Su...

[SCOI2003]字符串折叠 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld  题目描述  折叠的定义如下： 一个字符串可以看成它自身的折叠。记作S = S X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。 如果A = A’, B = B’，则AB = A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B) = AAACBB，而2(3(A)C)2(B) = AAACAAACBB 给一个字符串，求它的最短折叠。例如A...

来源：牛客网： 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 131072K，其他语言262144K 64bit IO Format: %lld  题目描述 给你一棵树，最开始点权为0，每次将与一个点x树上距离<=1的所有点点权+1，之后询问这些点修改后的点权和. 输入描述: 第一行两个数n和m 第二行n-1个数，第i个数fa[i + 1]表示i + 1点的父亲编号，保证fa[i + 1]<i + 1 第三行m个数，每个数x依次表示这次操作的点是x 输出描述: 输出一个数，即这m次操作的答案的hash值 如果是第i次操作，这次操作结果为ans,则这个hash值加上...

2020 年百度之星·程序设计大赛 - 初赛一 [toc] 6743 Drink 题解： 每一种饮料求一个卡路里，取最小值 第一看以为是背包，其实出题人在第二层 代码： #include<iostream> #include<cstdio> #include<string> #include<cstring> using namespace std; int dp[10005]; inline int read() {  char ch = getchar(); int x = 0, f = 1; while(ch < '0' || ch ...

2020牛客暑期多校训练营（第四场） 这场属实有点难受   文章目录    A Ancient Distance B Basic Gcd Problem   题目 代码：  C Count New String D Dividing Strings E Eliminate++ F Finding the Order   题意： 题解： 代码：  G Geometry Challenge H Harder Gcd Problem I Investigating Legions J Jumping on the Graph    A Ancient Distance B Basic Gcd Pro...

牛客算法周周练15   文章目录    A 数列下标 B 可持久化动态图上树状数组维护01背包 C 璀璨光滑 D 树上求和 E 算式子    A 数列下标 题意很明确，再看看数据，所以我们直接两重循环，用数组b来记录右边第一个大的数的下标 代码： #include<bits/stdc++.h> typedef long long ll; using namespace std; ll a[10004]; ll b[10004]; int main() {  int n; cin>>n; int cnt=0; for(int i=1;i<=n;i++) {  cin...

【每日一题】7月17日题目精讲—BOWL 碗的叠放 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld  题目描述  小H有n个碗需要放进橱柜，她希望将他们叠起来放置。你知道每个碗都是规则的圆柱体，并且都是上宽下窄，你已经测量出了每个碗的两个半径及高，请你帮小H找出一种叠放顺序，使得叠放出来的碗堆的高度尽量小，比如：  100%数据满足n < = 9。所有输入的数绝对值不超过1000。  输入描述:  第一行一个整数n，表示碗的数目。 以下n行，每行三个整数h，r1，r2。分别表示碗高及两个半...

来源：牛客网：   文章目录    题目描述 题解： 代码：    时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld  题目描述  有n个木块排成一行，从左到右依次编号为1~n。 你有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块。 所有油漆刚好足够涂满所有木块，即c1+c2+…+ck=n。 相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。  输入描述:  第一行为一个正整数k，第二行包含k个整数c1, c2, … , ck。  输出描述:  输出一个整数，...

Fake Maxpooling（2020多校第二场F）   文章目录    题意： 题解： 代码：    题意： 一个n * m的矩阵，第i行第j列的值是lcm（i，j），然后给定一个 k * k的子矩阵（k<=min(n,m)），然后求出大矩阵中每个子矩阵的最大值的和 看样例： 3 4 2  38  给的矩阵是： 1 2 3 4 2 2 6 4 3 6 3 12 所有2 * 2的子矩阵的最大值分别是 ： 2,6，6,6，6,12，总和是38 题解： 暴力求法是O（n m log n），先考虑O（n m）的做法 for(int i=1;i<=n;i++) {  for(int j=...

Cover the Tree   文章目录    题意： 题解： 代码    题意： 一个无向树，选择最少数量的链子，能将树上所有边覆盖，答案不唯一 (1≤n≤2×105） 链子就是两点之间的边 看看样例 输入 5 1 2 1 3 2 4 2 5  输出 2 2 3 4 5  一种情况如图所示： 所有边被覆盖的链子有： 链子2->3:覆盖了边1-2,1-3 链子4->5:覆盖了边4-2,2-5  题解：  上述文字看不懂也没关系，我也不大懂，我结合题解谈谈我的认识 所用知识： dfs序讲解 题目要求我们找链，链有两个端点，其实说白了就是在树上两两找点，让他们匹配，要覆盖所有边 如果...

来源：牛客网： 区间权值 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 1048576K，其他语言2097152K 64bit IO Format: %lld  题目描述  输入描述: 第一行一个正整数 n 第二行 n 个正整数 a1…an 第三行 n 个正整数 w1…wn 输出描述: 输出答案对 109+7 取模后的值 示例1 输入 复制 3 1 1 1 1 1 1  输出 复制 10  备注:  1≤ n≤ 3x 105 1≤ ai≤ 107 1≤ wi≤ 107  题解： 吐槽一下，官方题解有点小错误，应该是打错了。。。  题目是求公式，我们将式子化简： for(l =...

2020牛客暑期多校训练营（第六场） 额，睡了一下午，直接错过了比赛。。。   文章目录    A African Sort   题意： 题解： 代码：  B Binary Vector C Combination of Physics and Maths   题意： 题解： 代码：  D Data structure E Easy Construction   题意： 题解： 代码：  F Fibonacci Partition G Grid Coloring H Harmony Pairs I Interesting Stiriling J Josephus Transform K K-B...

比赛链接 菜鸡的我，第四名。。 A 矛盾激化 题意 给定地图，这个地图有两个出口，现在我们需要求出从所有点到任意一个出口的距离中的最短路径的最大值 本题为输出答案题，给定你一种情况，然后输出它的答案 题解 如果实在不会，可以手查（滑稽） 如果直接从每个点开始搜一遍最短距离不现实 因为只有两个出口，所以我们可以从出口出发然后跑两边BFS，每个点都维护一个距离的最小值 有几个坑点： 1.从出口往里面跳的时候只能跳一个格子 2.从别的格子跳往其他格子时只能跳两个格子 3.跳两格的时候还要判断中间隔过去的一格是不是空格 4.输入的格子有些恶心人 代码 #include <iostream>...