- 博客(1393)
- 收藏
- 关注
RSS订阅原创 最大上升子序列和 （数据结构优化DP、离散化）
3662. 最大上升子序列和给定一个长度为 n 的整数序列 a1,a2,…,an。请你选出一个该序列的严格上升子序列，要求所选子序列的各元素之和尽可能大。请问这个最大值是多少？输入格式第一行包含整数 n。第二行包含 n 个整数 a1,a2,…,an。输出格式输出最大的上升子序列和。数据范围对于前三个测试点，1≤n≤4。对于全部测试点，1≤n≤105,1≤ai≤109。输入样例1：2100 40输出样例1：100输入样例2：41 9 7 10输出样例2：20样例解释
2021-06-13 10:13:30
716
原创 状压DP dd爱探险（最短Hamilton路径升级版本）
dd爱探险链接：https://ac.nowcoder.com/acm/contest/11211/B来源：牛客网时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld题目描述星际中有nn个空间站，任意两个空间站间可以相互跳跃，由空间站x跳跃到空间站y所需要的代价为 P[x][y],注意不保证 p[x][y]= p[y][x]，dddd可以任意选择出发的空间站，并通过恰好n−1次跳跃把所有空间站跳完，并且d
2021-05-30 16:40:47
387
原创 状压DP 最短Hamilton路径
最短Hamilton路径给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。输入格式第一行输入整数 n。接下来 n 行每行 n 个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为 a[i,j]）。对于任意的 x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]。输出格式输
2021-05-30 16:05:55
410
原创 状压DP Leetcode 5756. 两个数组最小的异或值之和
给你两个整数数组 nums1 和 nums2 ，它们长度都为 n 。两个数组的 异或值之和 为 (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + … + (nums1[n - 1] XOR nums2[n - 1]) （下标从 0 开始）。比方说，[1,2,3] 和 [3,2,1] 的 异或值之和 等于 (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4 。请你将 nums2 中的元素重新排列，使得
2021-05-30 13:19:39
188
原创 牛客小白月赛34
dd爱科学1.0链接：https://ac.nowcoder.com/acm/contest/11211/A来源：牛客网题目描述大科学家dddd最近在研究转基因白菜，白菜的基因序列由一串大写英文字母构成，dddd经过严谨的推理证明发现，只有当白菜的基因序列呈按位非递减形式时，这株白菜的高附加值将达到最高，于是优秀的dddd开始着手修改白菜的基因序列，dddd每次修改基因序列的任意位需要的代价是11，dddd想知道，修改白菜的基因序列使其高附加值达到最高，所需要的最小代价的是多少。输入描述:第一行
2021-05-28 23:40:36
652
1
原创 CF527B AcWing 3580. 整数配对 (
输入样例1：65 10 2 3 14 5输出样例1：5输入样例2：21 100输出样例2：99题解结论：排序后，相邻配对必为答案n = 4的情形易证假设存在a<b<c<d只会存在两种配对情况b和c配对，a和d配对，则ans1 = c - b + d - aa和b配对，c和d配对，则ans2 = b - a + d - cans1 - ans2 = 2*(c - b) > 0所以配对情况2优于配对情况1，可扩展到n个数上#include<.
2021-05-27 23:57:32
161
原创 2021-01-20
实验7-2-5 判断上三角矩阵 (15分)上三角矩阵指主对角线以下的元素都为0的矩阵；主对角线为从矩阵的左上角至右下角的连线。本题要求编写程序，判断一个给定的方阵是否上三角矩阵。输入格式：输入第一行给出一个正整数T，为待测矩阵的个数。接下来给出T个矩阵的信息：每个矩阵信息的第一行给出一个不超过10的正整数n。随后n行，每行给出n个整数，其间以空格分隔。输出格式：每个矩阵的判断结果占一行。如果输入的矩阵是上三角矩阵，输出“YES”，否则输出“NO”。输入样例：231 2 30 4 50
2021-01-20 16:08:11
286
原创 随笔记忆
位运算基础知识& 与| 或~ 非^ 异或>> 右移 ：a>>k相当于a/2ka>>k 相当于a/2^ka>>k相当于a/2k<< 左移 : a<<k相当于a∗2ka<<k相当于a*2^ka<<k相当于a∗2k常用操作x & 1 可以用来判断x的奇偶性，等于1就是奇数，等于0是偶数。x = x & (x -1) 可以清掉x最低位的1求x的第k位数字
2021-01-17 20:29:39
162
原创 牛客2020跨年场题解
B 牛牛想起飞题解DP问题，dp[i][j]表示前i个数中是否有%m为j的数，有为1，否则为0。#include<bits/stdc++.h>using namespace std;typedef long long LL;const LL N = 500010, M = 100;int dp[N][M],a[N],b[N];int main(){ LL n, m, res = 0,sum1 = 0; scanf("%lld%lld", &n, &a
2021-01-01 13:45:04
277
1
原创 P1903 [国家集训队]数颜色 / 维护队列 （带莫队算法模板：求区间不同数的个数+单点修改）
题目描述墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？输入输出格式输入格式：第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做...
2020-12-24 14:48:30
488
原创 10.机器学习——Tips for Training DNN
本文会顺带解决CNN部分的两个问题：1、max pooling架构中用到的max无法微分，那在gradient descent的时候该如何处理？2、L1 的Regression到底是什么东西本文的主要思路：针对training set和testing set上的performance分别提出针对性的解决方法1、在training set上准确率不高：- new activation function：ReLU、Maxout- adaptive learning rate：Adagrad、RM.
2020-12-14 22:06:19
455
原创 9.机器学习——Backpropagation
Backpropagation(反向传播)，就是告诉我们用gradient descent来train一个neural network的时候该怎么做，它只是求微分的一种方法，而不是一种新的算法Gradient Descentgradient descent的使用方法，跟linear Regression或者是Logistic Regression是一模一样的，唯一的区别就在于当它用在neural network的时候，network parametersθ=w1,w2,…,b1,b2,…\theta.
2020-12-03 15:30:37
340
原创 8.机器学习——Deep Learning
深度学习的三个步骤Step1：神经网络（Neural network）Step2：模型评估（Goodness of function）Step3：选择最优函数（Pick best function）Step1：神经网络神经网络有很多不同的连接方式，产生不同的结构（structure）。Fully Connect Feedforward Network(全连接前馈网络)全链接和前馈的理解输入层（Input Layer）：1层隐藏层（Hidden Layer）：N层输出层（Output
2020-12-03 10:36:20
320
原创 《剑指Offer》第34-44题
AcWing 46. 二叉搜索树的后序遍历序列输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。样例输入：[4, 8, 6, 12, 16, 14, 10]输出：true题解：中序（二叉搜索树的中序是从小到大的结果）+后序建树后序遍历最后一个数为根，二叉搜索树的性质，我们直接从头开始找到比根小的值，这便是左子树；右边部分便是右子树，如果不符合便是错误。class Solution {pu
2020-12-02 14:59:01
187
原创 DP回顾——背包问题
背包问题N 件物品放入容量为 V 的背包，求最大的价值。常见的背包问题分为：01背包问题，完全背包问题其中核心的问题还是 01背包问题，其余的背包问题都是基于01背包的变形。AcWing 2. 01背包问题有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。输入格式第一行两个整数N，V，用空格隔开，分别表示物品数量和背包容积。接下来有 N 行，每
2020-12-02 14:58:14
1560
原创 牛客编程巅峰赛S2第5场
A 牛牛算数链接：https://ac.nowcoder.com/acm/contest/9556/A来源：牛客网题目描述给你一个含有n个元素的数组arr[i]，请你告诉牛牛这个数组的中位数大还是平均数大，如果中位数更大输出1，如果平均数更大输出-1，如果中位数和平均数相等输出0示例1输入复制[1,3,4]返回值复制1说明中位数3，平均数约等于2.67，所以输出1示例2输入复制[7,4,8,11]返回值复制0说明中位数7.5，平均数7.5，所以输出0示例3输入
2020-12-01 21:26:29
255
1
原创 牛客编程巅峰赛S2第4场
又没中奖 =_=A 牛牛掷硬币链接：https://ac.nowcoder.com/acm/contest/9475/A来源：牛客网题目描述牛牛最近很喜欢掷硬币，由于他今天很无聊，所以他在家掷了n次硬币，如果这n次硬币全部朝上或者全部朝下牛牛就很开心，请问牛牛开心的概率是多少。（每次掷硬币朝上的概率与朝下的概率相同）示例1输入复制1返回值复制“1.00”说明概率为1，四舍五入保留两位小数的字符串为"1.00"示例2输入复制5返回值复制“0.06”说明概率为0.0
2020-12-01 12:49:47
174
原创 7.机器学习——Logistic Regression
上一章的分类可以推导了P(C1∣x)=σ(z)=11+e−zP(C_1|x)=\sigma(z)=\frac{1}{1+e^{-z}}P(C1∣x)=σ(z)=1+e−z1，并且在Gaussian的distribution下考虑class 1和class 2共用Σ\SigmaΣ，可以得到一个线性的z(其实很多其他的Probability model经过化简以后也都可以得到同样的结果)Pw,b(C1∣x)=σ(z)=11+e−z P_{w,b}(C_1|x)=\sigma(z)=\frac{1}{1+
2020-11-23 20:58:07
229
原创 6.机器学习——分类
Classification分类要找一个 function 函数，输入对象 x 特征， 输出是该对象属于n个类别中是属于哪一个。How to classification预测回归模型 vs 概率模型分类当作回归硬解。 举一个二分类的例子，假设输入神奇宝贝的特征 x，判断属于类别1或者类别2，把当作回归问题。类别1：相当于target是 1。类别2：相当于target是 −1。输入数值化要想把一个东西当做function的input，就需要把它数值化...
2020-11-17 12:44:02
307
原创 解谜游戏（思维)
小明正在玩一款解谜游戏。谜题由 24 根塑料棒组成，其中黄色塑料棒 4 根，红色 8 根，绿色 12 根 (后面用 Y 表示黄色、R 表示红色、G 表示绿色)。初始时这些塑料棒排成三圈，如上图所示，外圈 12 根，中圈 8 根，内圈 4 根。小明可以进行三种操作：将三圈塑料棒都顺时针旋转一个单位。例如当前外圈从 0 点位置开始顺时针依次是 YRYGRYGRGGGG，中圈是 RGRGGRRY，内圈是 GGGR。那么顺时针旋转一次之后，外圈、中圈、内圈依次变为：GYRYGRYGRGGG、YRGRGG
2020-11-13 20:57:56
770
原创 字符串A-＞字符串B例题 :最短编辑距离、最优包含 （线性DP）
AcWing 902. 最短编辑距离给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有：删除–将字符串A中的某个字符删除。插入–在字符串A的某个位置插入某个字符。替换–将字符串A中的某个字符替换为另一个字符。现在请你求出，将A变为B至少需要进行多少次操作。输入格式第一行包含整数n，表示字符串A的长度。第二行包含一个长度为n的字符串A。第三行包含整数m，表示字符串B的长度。第四行包含一个长度为m的字符串B。字符串中均只包含大写字母。输出格式输出一个整数，表示最少操
2020-11-13 20:33:40
1315
原创 1583. PAT 计数 （状态机DP）
字符串 APPAPT 中共包含两个 PAT 作为子串。第一个子串由第二，第四和第六个字符组成，第二个子串由第三，第四和第六个字符组成。现在给定一个字符串，请你求出字符串中包含的 PAT 的数量。输入格式共一行，包含一个由大写字母 P,A,T 构成的字符串。输出格式输出字符串中包含的 PAT 的数量。由于结果可能很大，请你输出对 1000000007 取模后的结果。数据范围给定字符串的长度不超过 105。输入样例：APPAPT输出样例：2题解状态机模型S[] = “APPAPT
2020-11-12 10:35:39
183
原创 2548. 大胖子走迷宫 (时间bfs）
小明是个大胖子，或者说是个大大胖子，如果说正常人占用 1×1 的面积，小明要占用 5×5 的面积。由于小明太胖了，所以他行动起来很不方便。当玩一些游戏时，小明相比小伙伴就吃亏很多。小明的朋友们制定了一个计划，帮助小明减肥。计划的主要内容是带小明玩一些游戏，让小明在游戏中运动消耗脂肪。走迷宫是计划中的重要环节。朋友们设计了一个迷宫，迷宫可以看成是一个由 n×n 个方阵组成的方阵，正常人每次占用方阵中 1×1 的区域，而小明要占用 5×5 的区域。小明的位置定义为小明最正中的一个方格。迷宫四周都
2020-11-11 21:08:19
576
2
原创 作业一：预测PM2.5（李宏毅机器学习2020HW1——线性回归）
作业描述采集了台湾环境监测所的数据。要求：根据前9小时的数据，用线性回归来预测第10个小时的PM2.5的数值。任务要求输入：9个小时的数据，共18项特征（AMB_TEMP, CH4, CO, NHMC, NO, NO2, NOx, O3, PM10, PM2.5, RAINFALL, RH, SO2, THC, WD_HR, WIND_DIREC, WIND_SPEED, WS_HR）输出：第10小时的PM2.5数值模型：线性回归模型搭建Load 'train.csv’本次作业使用了某
2020-11-11 20:06:48
3566
1
原创 AtCoder Beginner Contest 182 题解
比赛地址A - twiblr直接输出2A+100-B即可，时间复杂度O(1)。a, b = map(int, input().split())print(2 * a + 100 - b)Problem B - Almost GCD暴力穷举即可。IA = lambda: map(int, input().split()) N = 1005cnt = [0 for i in range(N)]n = int(input())a = list(IA())maxx = -1res =
2020-11-10 12:42:28
427
4
原创 5.机器学习——回归代码演示
目的在假设有10个x_data和y_data，x和y之间的关系是y_data=b+w*x_data。b，w都是参数，是需要学习出来的。现在我们来练习用梯度下降找到b和w。库准备import numpy as npimport matplotlib.pyplot as pltfrom pylab import mpl# matplotlib没有中文字体，动态解决plt.rcParams['font.sans-serif'] = ['Simhei'] # 显示中文mpl.rcParams['
2020-11-09 09:54:30
288
原创 3.机器学习——Error的来源
这些 Error 的主要有两个来源，分别是 bias 和 variance 。●准: bias描述的是根据样本拟合出的模型的输出预测结果的期望与样本真实结果的差距，简单讲，就是在样本上拟合的好不好。要想在bias上表现好，low bias,就得复杂化模型，增加模型的参数，但这样容易过拟合(overfitting), 过拟合对应上图是high variance，点很分散。low bias对应就是点都打在靶心附近，所以瞄的是准的，但手不一定稳。●确:varience描述的是样本上训练出来的模型在测试集上的表
2020-11-06 11:06:49
508
原创 《剑指Offer》第23-33题
AcWing 35. 反转链表定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。思考题：请同时实现迭代版本和递归版本。样例输入:1->2->3->4->5->NULL输出:5->4->3->2->1->NULL递推# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self
2020-11-05 13:12:18
707
原创 lt 5600. 第 K 条最小指令 （组合数+思维）
第 K 条最小指令思路优先确定高位 + 组合计数首先，此题可以转化为排列h个H和v个V组成字符串集合中，第k小的字符串是哪一个？考虑最高位是放 H 还是 V。由于后者的字典序较大，因此如果最高位放 V，那么所有最高位为H 的字符串的字典序都比它小，这样的字符串共有n = c[h + v - 1][h - 1]个。即就是确定了最高位为 H，剩余 h+v-1个位置中选择 h-1 个放入 H，其余位置自动放入 V 的方案数。因此：如果 k大于这个组合数 n，那么最高位一定是 V。我们将 v 减少 1
2020-11-01 22:01:10
210
原创 2020中南大学研究生招生夏令营机试题
title: 2020中南大学研究生招生夏令营机试题date: 2020-05-07 17:34:23categories: 算法tags: [C++, 思维]mathjax: true题目编号标题来源/分类正确提交Y1252缺失的彩虹2020中南大学研究生招生夏令营机试题136334Y1253最小价值和2020中南大学研究生招生夏令营机试题201645Y1254PIPI上学路2020中南大学研究生招生夏令营机试题12158.
2020-10-30 21:00:11
740
原创 2019中南大学研究生招生夏令营机试题
title: 2019中南大学研究生招生夏令营机试题date: 2020-04-17 17:34:23categories: 算法tags: [C++, 马拉车, 最短路, dfs]mathjax: true2019中南大学研究生招生夏令营机试题题目编号标题来源/分类正确提交Y1110地砖问题2019中南大学研究生招生夏令营机试题306932Y1111最小花费2019中南大学研究生招生夏令营机试题105454Y1112回文串2.
2020-10-30 20:57:56
397
原创 1225. 正则问题(递归)
1225. 正则问题考虑一种简单的正则表达式：只由 x ( ) | 组成的正则表达式。小明想求出这个正则表达式能接受的最长字符串的长度。例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。输入格式一个由x()|组成的正则表达式。输出格式输出所给正则表达式能接受的最长字符串的长度。数据范围输入长度不超过100，保证合法。输入样例：((xx|xxx)x|(x|xx))xx输出样例：6题解X 表示字符| 表示左右两边都可以，选择一个递
2020-10-30 15:40:17
179
原创 扩展欧几里得算法算法例题——1299. 五指山、1301. C 循环
大圣在佛祖的手掌中。我们假设佛祖的手掌是一个圆圈，圆圈的长为 n，逆时针记为：0,1,2,…,n−1，而大圣每次飞的距离为 d。现在大圣所在的位置记为 x，而大圣想去的地方在 y。要你告诉大圣至少要飞多少次才能到达目的地。注意：孙悟空的筋斗云只沿着逆时针方向翻。输入格式有多组测试数据。第一行是一个正整数 T，表示测试数据的组数；每组测试数据包括一行，四个非负整数，分别为如来手掌圆圈的长度 n，筋斗所能飞的距离 d，大圣的初始位置 x 和大圣想去的地方 y。输出格式对于每组测试数据，输出一
2020-10-29 20:41:48
852
原创 经典问题——重复覆盖问题
糖果店的老板一共有 M 种口味的糖果出售。为了方便描述，我们将 M 种口味编号 1∼M。小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是 K 颗一包整包出售。幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。输入格式第一行包含三个整数 N,M,K。接下来 N 行每行 K 这整数 T1,T2,⋅⋅⋅,TK，代表一包糖果的口味。输出格式一个整数表示答案。如果小明无法
2020-10-29 19:54:04
1524
原创 位运算与常用库函数 (c++)
位运算& 与| 或~ 非^ 异或>> 右移<< 左移常用操作：求x的二进制右数第k位数字 :x >> k & 1将x在二进制右数第k位赋1 : x | (1<<k)将x在二进制右数第k位赋0 : x &(~ (1<<k))将x在二进制右数第k位取反 : x ^(1<<k)lowbit(x) = x & -x，返回x的最后一位1b >>= 1 // b/=2i
2020-10-29 15:30:27
435
原创 算术基本定理例题—— X的因子链、聪明的燕姿
1295. X的因子链输入正整数 X，求 X 的大于 1 的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度，以及满足最大长度的序列的个数。输入格式输入包含多组数据，每组数据占一行，包含一个正整数表示 X。输出格式对于每组数据，输出序列的最大长度以及满足最大长度的序列的个数。每个结果占一行。数据范围1≤X≤220输入样例：23410100输出样例：1 11 12 12 24 6题解：由算术基本定理得：所有正整数都可以分解成质因子乘积的形式，N=P
2020-10-29 10:46:47
404
原创 公约数例题——等差数列、最大比例
1246. 等差数列数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？输入格式输入的第一行包含一个整数 N。第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。(注意 A1∼AN 并不一定是按等差数列中的顺序给出)输出格式输出一个整数表示答案。数据范围2≤N≤100000,0≤Ai≤109输入样例：52 6 4 10 20输出样例：10样例解释包含
2020-10-28 15:33:28
468
原创 《剑指Offer》第12-22题
AcWing 24. 机器人的运动范围地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。但是不能进入行坐标和列坐标的数位之和大于 k 的格子。请问该机器人能够达到多少个格子？样例1输入：k=7, m=4, n=5输出：20样例2输入：k=18, m=40, n=40输出：1484解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它
2020-10-27 19:06:42
666
原创 2.机器学习——Regression
回归定义Regression 就是找到一个函数 function ，通过输入特征 x，输出一个数值 Scalar。模型步骤step1：模型假设，选择模型框架（线性模型）step2：模型评估，如何判断众多模型的好坏（损失函数）step3：模型优化，如何筛选最优的模型（梯度下降）Step 1：模型假设 - 线性模型一元线性模型（单个特征）以一个特征 xcpx_{cp}xcp 为例，线性模型假设 y=b+w⋅xcpy = b + w·x_{cp}y=b+w⋅xcp 。多元线性模型（多个特
2020-10-25 23:38:55
444
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人