Description 华华看书了解到，一起玩养成类的游戏有助于两人培养感情。所以他决定和月月一起种一棵树。因为华华现在也是信息学高手了，所以他们种的树是信息学意义下的。华华和月月一起维护了一棵动态有根树，每个点有一个权值。刚开存档的时候，树上只有 0 号节点，权值为 0 。接下来有两种操作：操作 1：输入格式1 i，表示月月氪金使节点 i 长出了一个新的儿子节点，权值为0，编号为当前最大编号 +1（也可以理解为，当前是第几个操作 1，新节点的编号就是多少）。操作 2：输入格式 2 i a表示华华上线做任务使节点 i 的子树中所有节点（即它和它的所有子孙节点）权值加 a 。但是月月有时会检查华...

Description 有 n 件货物， 第 i 件重 吨，另有 x 个集装箱，每个集装箱可以装重量不超过 W 吨的货物。货物不能分拆，请判断这 x 个集装箱能否装下所有货物。 Solution , 考虑搜索，由于货物不能拆分，于是我们所需要的集装箱最多需要 个，那么我们可以预处理出 个容量为 的桶，然后每次搜索能否放到该桶里面，最后回溯。注意这道题还需要一些剪枝技巧，详情看代码。 Code #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 23 + 5; int...

Description 牛妹现在正在1号点（自己家里），他决定前往n号点（牛妹想去的地方），中途可以多次经过1~n号点。现在，已知每个点都有个权值 ，如果 & ≠0，则i号点和j号点之间连有一条双向边，权值为。他想要最小化自己的行走距离，但是他计算不出来qaq。相信全牛客最聪明的你一定会吧！ Solution 朴素做法是暴力连所有边，但是边集规模过大，考虑二进制优化，对32个二进制位建立32个虚点，对于每个，如果该二进制位j为1，那么连边权值为 1 << j。（注意虚点到该点的距离为0）最后跑一个Dijkstra即可，注意 ，不能开 int Code #include...

Description 他手里有一个长度为n的序列a，保证它是一个01序列，并执行以下两种操作：1.单点修改：将位置x上的数翻转（0变1,1变0）；2.前缀修改：将位置1~x上的数翻转（每个数都0变1,1变0）。他现在想要最小化翻转次数，使得数列上的所有数都变为0。 Solution 贪心贪不动，考虑dp，主要在于如何表示状态,设： 表示到了第i个位置，把前面的都变成0的最小操作数 表示到了第i个位置，把前面的都变成1的最小操作数 那么很容易就能表示出状态转移方程，最后输出 即可。 Code #include<bits/stdc++.h> using namespace std; ...

Description Solution 打表，得到的表如下（0代表Frame，1代表Alan）：n ans1 12 13 04 1（可以转化为3 必败态给对手）5 1（可以转化为3 必败态给对手）6 07 1（可以转化为6 必败态给对手）8 1（可以转化为6 必败态给对手）9 0 看出规律，3的倍数时为必败态。 Code #include<bits/stdc++.h> using namespace std; typedef long long ll; int m...

Description 他刚刚理解&的用法(and)，准备趁热打铁，做做下面这题：给定一个长度为n的序列a，你需要从中挑出任意多个（可以0个）数，使得他们&起来值最大。看起来挺简单的，可是牛牛就是不会做。比如说选出五个数1,3,5,7,9，他们&起来的值就是1&3&5&7&9=1 Solution 找最大值，多个数字相互做按位与，结果 <= 原来的数字。 Code #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int a[N]; i...

Description 牛牛得到了一个字符串（可能含有空格），他希望在这些字符串中提取出数字。例如：a1b23c456d007890中可以提取出1, 23, 456, 7890共4个数字。 现在，他得到了一个长度高达1000的字符串，请你帮他提取出所有的数字。 Solution 注意两个细节1：输出的时候格式是字符串，因为数字过长整型变量存不下。2：无前导0 Code #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { string s; while(getl...

Description 小明现在要追讨一笔债务，已知有n座城市，每个城市都有编号，城市与城市之间存在道路相连（每条道路都是双向的），经过任意一条道路需要支付费用。小明一开始位于编号为1的城市，欠债人位于编号为n的城市。小明每次从一个城市到达另一个城市需要耗时1天，而欠债人每天都会挥霍一定的钱，等到第k天后（即第k+1天）他就会离开城n并再也找不到了。小明必须要在他离开前抓到他（最开始为第0天），同时希望自己的行程花费和欠债人挥霍的钱的总和最小，你能帮他计算一下最小总和吗？ Solution 显然是最短路问题，求1到n的最短路，由于多出了个欠债人的影响，考虑分层图最短路，用 代表第 天到达 ...

字体 \textbf 粗体\textit 斜体\songti 宋体\heiti 黑体\fangsong 仿宋\kaishu 楷书加^号 输入\hat 或 \widehat加横线 输入 \overline加波浪线 输入 \widetilde关于作用域 {\textbf } 特殊字符 \quad 1em\qquad 2em 插图 \usepackage{graphicx}\includegraphics [<选项>][<文件名>]\graphicspath{{figure/}, {pics/} % 图片在当前目录下的 figure 目录

A.牛牛的分配 Solution 签到题，从大到小排序，多出来的统计，少的看能不能补上，不能补的话就跳出 Code class Solution { public: /** * 返回重新分配后，满足牛牛要求的水量的瓶子最多的数量 * @param n int整型 瓶子的数量 * @param x int整型 牛牛的对瓶中的水量要求 * @param a int整型vector 每个瓶子中的含水量 * @return int整型 */ int solve(int n, int x, vector<int>&a...

1. 训练拟合 import tensorflow as tf import numpy as np x_data = np.random.rand(100).astype(np.float32) y_data = x_data * 0.1 + 0.3 Weights = tf.Variable(tf.random_uniform([1], -1.0, 1.0)) biases = tf.Variable(tf.zeros([1])) y = Weights * x_data + biases loss = tf.reduce_mean(tf.square(y - y_data)) ...

Desciption 小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。 乌龟棋的棋盘是一行N 个格子，每个格子上一个分数（非负整数）。棋盘第1 格是唯一的起点，第N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。 乌龟棋中M 张爬行卡片，分成4 种不同的类型（M 张卡片中不一定包含所有4 种类型的卡片见样例），每种类型的卡片上分别标有1、2、3、4 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。游戏中，乌龟棋子自动获得起点格子...

Description 有一只可爱的兔子被困在了密室了，密室里有两个数字，还有一行字：只有解开密码，才能够出去。可爱的兔子摸索了好久，发现密室里的两个数字是表示的是一个区间[L,R]而密码是这个区间中任意选择两个(可以相同的)整数后异或的最大值。比如给了区间[2,5] 那么就有2 3 4 5这些数，其中 2 xor 5=7最大 所以密码就是7。兔子立马解开了密室的门，发现门外还是一个门，而且数字越来越大，兔子没有办法了，所以来求助你。 Solution 注意到如果给定两个数字，他们的二进制为11111101那么显然对于前两位，在这个区间上都是1，那么我们最终构造的必不可能在这两位中取得贡献。注...

高等代数 1. 什么是正定矩阵？ 正定矩阵 （1）广义定义：设M是n阶方阵，如果对任何非零向量z，都有> 0，其中 表示z的转置，就称M为正定矩阵。例如：B为n阶矩阵，E为单位矩阵，a为正实数。在a充分大时，aE+B为正定矩阵。（B必须为对称阵）（2）狭义定义：一个n阶的实对称矩阵M是正定的的条件是当且仅当对于所有的非零实系数向量z，都有 > 0。其中表示z的转置。 对称正定矩阵 Hermite正定矩阵 判定定理 对于n阶实对称矩阵A，下列条件是等价的：（1）A是正定矩阵；（2）A的一切顺序主子式均为正；（3）A的一切主子式均为正；（4）A的特征值均为正；（5）存在实可逆...