链接：@[toc]小A的柱状图 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形，但是小A的柱状图却不是一个规范的柱状图，它的每个矩形下端的宽度可以是不相同的一些整数，分别为a[i]a[i],每个矩形的高度是h[i]h[i],现在小A只想知道，在这个图形里面包含的最大矩形面积是多少。 输入描述:  一行一个整数N，表示长方形的个数 接下来一行N个整数表示每个长方形的宽度 接下来一行N个整数表示每个长方形的高度  输出描述:一行一个整...

来源：牛客网： 乌龟棋 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K，其他语言262144K 64bit IO Format: %lld @[toc] 题目描述 小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。 乌龟棋的棋盘是一行N 个格子，每个格子上一个分数（非负整数）。棋盘第1 格是唯一的起点，第N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。 ![在这里插入图片描述](https://uploadfiles.nowcoder.com/files/20200802/543071257_1596297793971_202008012344359...

来源：牛客网：@[toc] wpy的请求 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K Special Judge, 64bit IO Format: %lld 题目描述   “题目名称只是吸引你来做题的啦，其实和题目没什么卵关系：o(￣▽￣)o” —— 历史——殿堂 wpy移情别恋啦，他不喜欢spfa了，现在他喜欢使用dij，但是他又发现了一个新的问题，dij无法跑有负权边的图，于是wpy找到了她的男朋友也就是你来帮忙，为了你晚上的幸福生活，你必须在1秒内帮她解决这个问题，然后蹿到床上。。。balabala（捂脸）。。。。(/ω＼)简...

2020牛客暑期多校训练营（第六场）额，睡了一下午，直接错过了比赛。。。@[toc] A African Sort 题意： 题解： 代码： B Binary Vector C Combination of Physics and Maths 题意： 一个矩阵的底面积定义为最后一行的数的和，重量定义为矩阵内所有数的和（含最后一行），给一个正整数矩阵，找一个压强（压强等于重量/面积）最大的可非连续子矩阵 题解： 其实单列矩阵就是最大情况如果一个子矩阵有多列，那么可以拆成两个行数不变的更小子矩阵，且其中一个一定不比原情况差证明：所以我们只需要求出每一列矩阵的压强值，从上到下选入所以元素 代码： #i...

来源：牛客网： 区间权值 时间限制：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 10^5^ 1≤ ai≤ 10^7^ 1≤ wi≤ 10^7^  题解： 吐槽一下，官方题解有点小错误，应该是打错了。。。题目是求公式，我们将式子化简：for(l = 1--&gt...

Cover the Tree@[toc] 题意： 一个无向树，选择最少数量的链子，能将树上所有边覆盖，答案不唯一(1≤n≤2×10^5^）链子就是两点之间的边看看样例输入 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序讲解题目要求我们找链，链有两个端点，其实说白了就是在树上两两找点，让他们匹配，要覆盖所有边如果有x个叶子节点，那我们最少的子链也要是（x/2）向上取整（不然...

Boundary（2020多校第二场B）@[toc] 题意： 坐标平面有n个点（不与原点（0,0）重复）,现考虑一个圆，（0,0）点在圆的边界，问这个圆的边界上最多能有多少其他的点（不含原点）？我们看一下样例： 4 1 1 0 2 2 0 2 2 如图所示，我们选（0,2）为P,线段op对应的角中，∠PA2O=∠OA3P，说明A2，A3也在圆上，再加上p点，一共是三个，答案就是三 题解： 我一开始是暴力求解，直接枚举两个点，再枚举其他点看在不在边界上，复杂度是O(n^3^),但显然不行 思路1： 原点肯定在边界，我们可以先枚举一个点p，原点O与p组成线段op，op是圆上的一个弦，再枚举其他点A...

Duration（2020多校第二场D）@[toc]首先，非常感谢出题人出这个题，避免了我全wa的尴尬 题意 求两个时间相差多少秒，两个时间为同一天 题解 全部转化成秒，然后求差 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; int h1,m1,s1; int h2,m2,s2; int main() { scanf("%d:%d:%d",&h1,&m1,&s1); scanf("%d:%d:%d",&h2,&m2,&s2); ll sum1...

2020牛客暑期多校训练营（第二场）最烦英语题@[toc] A All with Pairs B Boundary 题解 C Cover the Tree 题解 D Duration 题解 E Exclusive OR F Fake Maxpooling 题解 G Greater and Greater H Happy Triangle I Interval J Just Shuffle K Keyboard Free

Fake Maxpooling（2020多校第二场F）@[toc] 题意： 一个n * m的矩阵，第i行第j列的值是lcm（i，j），然后给定一个 k * k的子矩阵（k<=min(n,m)），然后求出大矩阵中每个子矩阵的最大值的和看样例： 3 4 2 38 给的矩阵是：1 2 3 42 2 6 43 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=1;j<=m;j++) { if(!Gcd[i][...

来源：牛客网：@[toc] 时间限制：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。  输出描述:  输出一个整数，即方案总数模1,000,000,007...

@[toc]2020牛客暑期多校训练营（第一场） A B-Suffix Array B Infinite Tree C Domino D Quadratic Form E Counting Spanning Trees F Infinite String Comparision 题意： 两个字符串A和B，对AAAA....和BBBB...(字符串A和B无限重复）进行比较，输出 > = <  题解： 方法一：字符串a和b从第一位开始比较，当比到其中最后一位时再跳转到第一位继续。那什么时候算等于呢，我一开始想的是a和b的最小公倍数，这样会超时，我们其实只需比较较长字符串的两倍即可。因为...