链接：https://www.nowcoder.com/acm/contest/204/A 来源：牛客网 题目描述 小 A 最近在研究深度学习，他自己搭建了一个很牛逼的神经网络，现在他手头一共有 n 组训练数据，一开始他会给自己的神经网络设置一个 batch size，假设为 B (1≤ B≤ n) ，每次训练他都会从手头的 n 组训练数据中抽取不同的 B 组数据，然后扔到神经网络去训练。 然而小 A 的服务器并不是特别支持并行，所以运行时间和 B 成正比，每一次训练都会花费 B 秒的时间。 现在小 A 发现这样每次随机选数据的话，从概率上讲要训练好多次才能使得每组训练数据都被选中过。小 A ...

链接：https://www.nowcoder.com/acm/contest/204/D 来源：牛客网 题目描述 小 A 有一张 n 个点的带权无向图，这张无向图非常特别，首先第 i 个点有一个点权 ai，之后这张无向图是一张完全图，且边 (u,v) 的权值为 au+av 现在小 A 想找一个这张图的边权之和最小的生成树，需要你来帮帮他 输入描述: 第一行一个正整数 n 第二行 n 个整数 a1,a2…an 输出描述: 输出边权和最小的生成树的边权之和 示例1 输入 复制 3 1 2 3 输出 复制 7 备注: 1≤ n≤ 105 0≤ ai≤ 109  假的最小生成树… 因为是完全图，也就...

链接：https://www.nowcoder.com/acm/contest/204/J 来源：牛客网 题目描述 某个 QQ 群里一共有 n 个人，他们的编号是 1…n，其中有一些人本质上是复读机。 小 A 发现，如果一个人的本质是复读机，那么他每次发的消息一定跟群里的上一条消息一样，特别地第一个发消息的人一定不是复读机。 现在小 A 搞到了一份聊天记录，他想请你找出所有可能是复读机的群友 输入描述: 第一行两个正整数 n,m，表示群里的人数和聊天记录的总条数 接下来 m 行按时间顺序给出聊天记录，每行有一个正整数 x 和一个小写字母字符串 S，表示群友 x 发了消息 S 输出描述: 输出一...

链接：https://www.nowcoder.com/acm/contest/204/I 来源：牛客网 题目描述 小 A 有一棵长的很奇怪的树，他由 n 条链和 1 个点作为根构成，第 i 条链有 ai 个点，每一条链的一端都与根结点相连。 现在小 A 想知道，这棵长得奇怪的树有多少非空的连通子树，你只需要输出答案对 998244353 取模的值即可 输入描述: 第一行一个正整数 n 第二行 n 个正整数 a1…an 输出描述: 输出答案对 998244353 取模后的值 示例1 输入 复制 2 1 1 输出 复制 6 备注: 1≤ n≤ 105 1≤ ai≤ 107  卡了很久 一开始从组...

链接：https://www.nowcoder.com/acm/contest/204/G 来源：牛客网 题目描述 小 Bo 有 n 个正整数 a1…an，以及一个权值序列 w1…wn，现在他定义  现在他想知道 的值，需要你来帮帮他 你只需要输出答案对 109+7 取模后的值 输入描述: 第一行一个正整数 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  感觉很经典的题 双重的前...

链接：https://www.nowcoder.com/acm/contest/205/L 来源：牛客网 题目描述 终于活成了自己讨厌的样子。 这是她们都还没长大的时候发生的故事。那个时候，栗子米也不需要为了所谓的爱情苦恼。 她们可以在夏日的午后，花大把的时间去研究生活中一些琐碎而有趣的事情，比如数论。 有一天西柚柚问了栗子米一个题，她想知道中有多少不同的数，这些不同的数字里面第k大的是多少。 输入描述: 第一行一个整数T(T≤ 105)，表示数据组数。 每组数据第一行两个整数，表示n,k(1≤ n≤ 1018)，保证k不会超过不同的数字个数。 输出描述: 对于每组数据输出，输出两个整数，表示...

链接：https://www.nowcoder.com/acm/contest/206/C 来源：牛客网 题目描述 现在我们要把这n个数字首尾连接组成一个环，使得相邻元素互质的对数尽可能多。请输出最大对数。 输入描述: 一行一个整数n(1≤ n≤ 1000)。 输出描述: 一行一个整数表示答案。 示例1 输入 复制 4 输出 复制 4 说明 样例的一种构造方法为1 4 3 2。  签到题 差点想复杂去搜索了，我突然提出这么多人过应该就是输入和输出吧，然后和队友突然就发现i和i+1肯定互质，然后1和n肯定也互质，那只要1到n连成一串就可以了 代码： #include <cstdio>...

链接：https://www.nowcoder.com/acm/contest/206/H 来源：牛客网 题目描述 平面上有n座山，每座山都有左右两面，第i座山的高度为ai，现在弱弱在第一座山的左边山脚下（高度为0），他想要依此爬过这些山，到达第n座山的右边山脚下。 除了简单的爬上爬下，还有一种特殊操作。 如果弱弱目前在第i座山右面的海拔x的位置，且第j ( i < j )座山的海拔大于等于x，且第座山中没有一座山的海拔高于x，那么他可以使用绳索滑到第j座山左面海拔x的位置。 弱弱想找到一种方式，使得他在行程中海拔变化的幅度最小。请输出最小幅度。 输入描述: 第一行一个整数n（1≤ n≤...

链接：https://www.nowcoder.com/acm/contest/206/B 来源：牛客网 题目描述 恬恬有一个nx n的数组。她在用这个数组玩游戏： 开始时，数组中每一个元素都是0。 恬恬会做某些操作。在一次操作中，她可以将某一行的所有元素同时加上一个值，也可以将某一列的所有元素同时加上一个值。 在几次操作后，一个元素被隐藏了。你能帮助她回忆隐藏的数是几吗？ 输入描述: 第一行一个整数n（1≤ n≤ 1000）。 接下来n行每行n个整数表示数组a。 第(i+1)行的第j个元素表示aij（aij=-1或0≤ aij ≤ 10000）。-1表示隐藏的元素。 输出描述: 仅一个整数表...

链接：https://www.nowcoder.com/acm/contest/206/A 来源：牛客网 题目描述 恬恬的生日临近了。宇扬给她准备了一个蛋糕。 正如往常一样，宇扬在蛋糕上插了n支蜡烛，并把蛋糕分为m个区域。因为某种原因，他必须把第i根蜡烛插在第ai个区域或第bi个区域。区域之间是不相交的。宇扬在一个区域内同时摆放x支蜡烛就要花费x2的时间。宇扬布置蛋糕所用的总时间是他在每个区域花的时间的和。 宇扬想快些见到恬恬，你能告诉他布置蛋糕最少需要多少时间吗？ 输入描述: 第一行包含两个整数n，m（1 ≤ n ≤ 50， 2≤ m≤ 50）。 接下来n行，每行两个整数ai,bi（1 ≤ ...

链接：https://www.nowcoder.com/acm/contest/206/E 来源：牛客网 题目描述 弱弱有两个属性a和b，这两个属性初始的时候均为0，每一天他可以通过努力，让a涨1点或b涨1点。 为了激励弱弱努力学习，我们共有n种奖励，第i种奖励有xi，yi，zi三种属性，若a≥ xi且b≥ yi，则弱弱在接下来的每一天都可以得到zi的分数。 问m天以后弱弱最多能得到多少分数。 输入描述: 第一行一个两个整数n和m（1≤ n≤ 1000，1≤ m≤ 2000000000）。 接下来n行，每行三个整数xi，yi，zi（1≤ xi,yi≤ 1000000000，1≤ zi ≤ 10...

给你一个mn的格子的棋盘，每个格子里面有一个非负数。 从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取数所在的2个格子不能相邻，并且取出的数的和最大。 Input 包括多个测试实例，每个测试实例包括2整数m,n和mn个非负数(m<=50,n<=50) Output 对于每个测试实例，输出可能取得的最大的和 Sample Input 3 3 75 15 21 75 15 28 34 70 5 Sample Output 188  第一次做根本没想到是网络流，这次搜网络流的题目找到了这道题，从一个矩阵中找出若干个不相邻的数使得权值和最大 咋一看是dp啥的，但其实这是一...

题目省略  前半个小时想了个假思路，后面找到正确思路，然而想错了int的范围，而且没考虑到for循环的i变量如果是int的话可能会直接爆，卡题到结束 题意是给n个点m条边，然后这个图保证没有自环和重边，然后求最大和最小可能的孤立点个数，最小的其实就是一条边尽量消耗两个点，就是n-2m，最大就是找到k个点的完全图，然后m条边先减去这k阶完全图的边数k(k-1)/2，剩下的边又另一个点连向这个k阶完全图 代码： #include <cstdio> #include <algorithm> using namespace std; long long n,m; const i...

题目省略  思路不清晰，后面想复杂了，然后就tle了 题意是给一个数列，代表每个建筑的高度，然后水平一刀切下去，每次拿走的不能超过k个，然后要切多少次才能切平 首先读取每一个高度的时候记录下最大和最小的，最小的其实就是切平的位置，所以以下的都不用管了，然后先记录每一个高度出现的次数，然后用前缀和就可以记录每一层的块的个数了，比如高度为4的有2个，那么第四层的块的个数就等于2，而第三层的块的个数就等于高度为3的个数加上第四层块的个数，因为能到第四层肯定能到第三层 然后就On遍历这个前缀和数组，记录临时和，如果小于k就继续加，直到大于k就切一刀，然后临时和变成这一层的块的个数 代码： #inclu...