- 博客(148)
- 收藏
- 关注
RSS订阅原创 Recovering Non-Rigid 3D Shape from Image Streams
论文下载通道Abstract提出本论文主要解决的问题是：recovering 3D non-rigid shape models from image sequences\text{recovering 3D non-rigid shape models from image sequences}recovering 3D non-rigid shape models from&nbs
2021-10-27 16:24:02
265
原创 过拟合和正则化
这里写自定义目录标题欠拟合解决方法过拟合过拟合的原因防止过拟合的方法L1/L2正则化L1正则化L2正则化在深度学习领域，训练模型时，我们不仅要求模型对训练数据集有很好的拟合（较低的训练误差），同时也希望它可以对未知数据集（测试集）有很好的拟合结果（泛化能力），所产生的测试误差被称为泛化误差。其中就会产生欠拟合和过拟合的问题。度量泛化能力的好坏，最直观的表现就是模型的过拟合（overfitting）和欠拟合（underfitting）。模型开始训练时，处于欠拟合阶段，随着训练的进行，训练误差和测试误差开
2021-08-13 17:33:29
492
原创 机器学习中常用激活函数
激活函数的作用激活函数的引入是为了增加神经网络模型的非线性，没有激活函数每层就相当于矩阵相乘。每一层输出都是上层的输入的线性函数，无论神经网络多少层，输出都是输入的线性组合，就是最原始的感知机。Softmax函数又称为归一化指数函数，用于多分类过程中，将多个神经元的输出映射到 [0,1][0,1][0,1] 区间中。假如有 nnn 个输出，分别为 V1∼nV_{1\sim n}V1∼n ，则第 iii 个输出的概率为:Si=ei∑ejS_i=\frac{e^i}{\sum{e^j}}Si=
2021-07-31 16:42:34
490
原创 GDCPC广东省大学生程序设计竞赛（正式赛）A.An Easy Problem【贪心+堆】
题意给出 n,m,kn,m,kn,m,k，定义 F(i,j)=i×jF(i,j)=i\times jF(i,j)=i×j，求出第 kkk 的 F(i,j)F(i,j)F(i,j)，其中 1≤i≤n,1≤j≤m1\leq i \leq n,1\leq j \leq m1≤i≤n,1≤j≤m，数据范围：1≤n,m,k≤1061\leq n,m,k \leq 10^61≤n,m,k≤106 且 k≤n×mk\leq n\times mk≤n×m。分析大致画出 F(i,j)F(i,j)F(i,j) 的分布，可
2021-07-03 17:50:55
639
原创 ARC116 C - Multiple Sequences【组合数学/DP】
Link题目给出一个 nnn 和 mmm，求出满足下列要求的序列的个数：1≤Ai≤M(i=1,2,⋯ ,N)1\leq A_i \leq M(i=1,2,\cdots,N)1≤Ai≤M(i=1,2,⋯,N)Ai+1A_{i+1}Ai+1 是 AiA_iAi 的倍数(i=1,2,⋯ ,N−1)(i=1,2,\cdots,N-1)(i=1,2,⋯,N−1)结果取模 998244353998244353998244353，1≤N,M≤2×1051\leq N,M \leq 2\times 10
2021-04-23 16:17:18
243
原创 CF1514-D. Cut and Stick【莫队/主席树/线段树/随机数】
题意给出一个序列 aaa，长度为 n(1≤n≤3⋅105)n(1\leq n \leq 3· 10^5)n(1≤n≤3⋅105)。给出 q(1≤n≤3⋅105)q(1\leq n \leq 3· 10^5)q(1≤n≤3⋅105) 个询问，每次选择一个区间 [l,r][l,r][l,r] ，问最少要将该区间拆分为几个子序列，使得每个序列中出现次数最多的数出现的次数不大于⌈len2⌉\lceil \frac{len}{2}\rceil⌈2len⌉，其中 lenlenlen 为序列长度。分析假设序列长度
2021-04-21 21:52:49
161
原创 CF1514-C.Product 1 Modulo N
题意给出一个 nnn (2≤n≤1052\leq n \leq 10^52≤n≤105)，在 [1,n−1][1,n-1][1,n−1] 内求出一个最长的子序列，使得该序列的乘积模 nnn 等于 111。求出序列的最长长度以及序列的各个数是多少。分析首先有如下等式成立：∏gcd(x,n)=1,x<nx=±1mod n\prod_{gcd(x,n)=1,x<n}{x}=\pm1 \mod ngcd(x,n)=1,x<n∏x=±1modn根据该等式，如果乘积 ppp 取模 n
2021-04-21 10:47:41
112
原创 ARC117 C - Tricolor Pyramid
题意给出一个长为 nnn 的数组，每个元素为 W，B 或 R，表示每个块的颜色。通过这个块，可以输出一个三角形。生成规则：如果相邻两个块的颜色相同，则得到一个同色的块；如果两个块的颜色不同，则得到没有出现过的颜色。如下图所示：求最上面的块的颜色。数据范围：2≤N≤4×1052\leq N \leq 4 \times10^52≤N≤4×105分析主要在如何分析转化颜色之间的转换关系，可以令三种颜色分别为：0，1，2，通过加法生成新的块的颜色。具体见下图：其中，did_idi 表示该方块颜色代
2021-04-19 18:09:16
163
原创 ARC116 B - Products of Min-Max
题意给出一个长度为 NNN 的序列 A，对于它的每个非空子序列 B，求出所有 max(B)×min(B)\max(B)\times \min(B)max(B)×min(B) 的和，结果模 998244353998244353998244353。数据范围：1≤N≤2×105,0≤Ai≤9982443521\leq N \leq 2\times 10^5,0\leq A_i \leq 9982443521≤N≤2×105,0≤Ai≤998244352分析显然不能直接计算，考虑如何算贡献。代码
2021-04-11 22:19:43
87
原创 Difference between Triplets POJ - 3244
题意对于每一个三元组：Ta=(Ia,Ja,Ka),Tb=(Ib,Jb,Kb)T_a=(I_a,J_a,K_a),T_b=(I_b,J_b,K_b)Ta=(Ia,Ja,Ka),Tb=(Ib,Jb,Kb)定义：D(Ta,Tb)=max{Ia−Ib,Ja−Jb,Ka−Kb}−min{Ia−Ib,Ja−Jb,Ka−Kb}D(T_a,T_b)=\max\{I_a-I_b,J_a-J_b,K_a-K_b\}-\min\{I_a-I_b,J_a-J_b,K_a-K_b \}D(Ta,Tb)
2021-04-11 19:27:34
102
原创 牛客练习赛80 C-不降数
题意数据范围：1≤n≤1081\leq n\leq 10^81≤n≤108分析可以先写出前面几项，按照末尾数字枚举：987654321n=1111111111n=2987654321n=3453628211510831在枚举的过程中，可以发现明显的递推关系：a(i,j)=∑k=1ja(i−1,k)a_{(i,j)}=\sum_{k=1}^{j}{a_{(i-1,k)}}a(i,j)=
2021-04-10 21:11:32
126
原创 牛客挑战赛48C 铬合金之声【Prufer序列+思维转化】
题目链接题意分析向 nnn 个点中加入 mmm 条边，形成 n−mn-mn−m 个联通块，那么每个联通块必然为一棵树。利用反证法可以证明：如果一个大小为 xxx 的联通块含有大于 x−1x-1x−1 条边，那么最后形成的联通块的数量显然小于n−mn-mn−m 个，因为有一些边并没有使得联通块的数量减少 111。又因为，对于一棵无根树而言，计算其大小的贡献，相当于选择其根的方案数。此时，再建立一个虚点 000 并固定其度为 n−mn-mn−m ，就将 n−mn-mn−m 棵树的森林转化为 n+1n+1
2021-03-31 21:09:14
90
原创 平面分割
直线切割平面nnn 条直线，最多可以把平面分为多少个区域。推导令 fnf_nfn 表示 nnn 条直线将平面分割的最大区域数，如果当前平面中已有 n−1n-1n−1 条直线，要加入第 和nnn 条直线，要使分割出来的区域数量最多，那么第 nnn 条直线就要和之前的每条直线产生一个交点，就产生了 n−2n-2n−2 条线段和 222 条射线。那么，增加的平面数为 nnn，一条线段产生一个，一条射线产生一个。所以，有：fn=fn−1+nf_n=f_{n-1}+nfn=fn−1+n。可得：fn=f
2021-03-31 17:26:49
930
原创 CCA的区间【状压+子集和DP】
题目链接题意给定一个长度为 nnn 的序列，序列中的每个元素都是 222 的幂次 。现在你需要找出一个各元素之和最大的，内部没有相同元素的子区间，输出这个元素和的最大值 。你可以最多翻转一个子区间 。(n≤105,1≤序列中的元素≤223)(n \leq 10^5,1 \leq 序列中的元素 \leq 2^{23})(n≤105,1≤序列中的元素≤223)分析关键在于翻转子区间的作用，翻转子区间，相当于可以把两段不相邻的区间合并。又因为每个数都是 222 的幂次，并且最多 242424 位，因此可以
2021-03-31 12:43:59
122
原创 CF1506 D. Epic Transformation【模拟+思维】
题意给出长度为 nnn 的数组，每次可以选择两个不同的数从数组中去掉，问数组中最后最少可以剩余多少个数。(1≤n≤2⋅105,1≤ai≤109)(1\leq n \leq 2·10^5,1\leq a_i \leq 10^9)(1≤n≤2⋅105,1≤ai≤109)分析每次选择出现次数最多的两个数去掉，一直重复，直到不能消除。用优先队列模拟即可。代码#include <bits/stdc++.h>using namespace std;typedef pair<int,i
2021-03-29 19:54:04
172
原创 2020CCPC绵阳L. Lottery
题目链接题意有 nnn 个筐，每个筐里有 xix_ixi 个球，每个球上有一个标签 aia_iai，表示 2ai2^{a_i}2ai，同一个筐中的球的标签相同，不同筐中球的标签一定不同。从筐中取任意个球，问和的个数有多少个。(1≤xi≤109,0≤ai≤109,1≤n≤105)(1\leq x_i \leq 10^9,0\leq a_i \leq 10^9,1\leq n \leq 10^5)(1≤xi≤109,0≤ai≤109,1≤n≤105)分析将二进制位分成一些段，分别计算每段的种类
2021-03-27 16:38:28
204
原创 CF1484 D. Playlist【模拟】
题目链接题意一个序列有 nnn 个数，分别为：aia_iai。从位置1开始循环遍历序列，如果位置 i和它后面的数（循环）互质，那么就把i后面的数删除，同时跳到原来i后面的第二个位置处，求出删除数的顺序。(1≤n≤105)(1\leq n \leq 10^5)(1≤n≤105)分析直接模拟，用nxt[i]数组来存 i的下一个位置。一开始先遍历一遍数组，求出满足要求的数对，保存起来。当每次删除数时，更新 nxt数组，并判断是否会产生新的数对。同时，开一个标记数组，防止对已删除的数再次处理。代码#i
2021-03-23 21:52:23
386
原创 CF1484 C. Basic Diplomacy【贪心/网络流】
题目链接题意某人有 nnn 个朋友，在 mmm 天中，每天会有 kkk 个朋友有空，问是否存在一种方案收到每个朋友出现的次数不大于 ⌈m2⌉\lceil\frac{m}{2}\rceil⌈2m⌉，存在则输出YES和每天选择的朋友编号，否则输出 NO。(1≤n,m≤105)(1≤n,m≤10^5)(1≤n,m≤105)分析题目的目的是让每个人出现的天数尽可能少，那么可以先处理掉那些只有一个人的时间，然后，按照贪心，每次选择出现次数最少的人。代码#include <bits/stdc++.h
2021-03-23 20:58:02
157
1
原创 Is-A? Has-A? Who Knowz-A?【传递闭包】
题目：Two familiar concepts in object oriented programming are the is-a and has-a relationships. Given two classes A and B, we say that A is-a B if A is a subclass of B; we say A has-a B if one of the f...
2020-03-01 11:22:19
184
原创 0 or 1 HDU - 4370【最短路+起点的最小环】
分析：把所给矩阵当作邻接矩阵，由三个限制，可以得到：1.节点 111 的出度为 111，但入度不确定；2.节点 nnn 的入度为 111，但出度不确定；3.其余节点的入度 === 出度； 当节点 111 的入度 =0=0=0，节点 nnn 的出度 =0=0=0，最小值就等于从 1→n1\to n1→n的最短距离； 如果节点 111的入度 =1=1=1，节点 nnn 的出度 =1=1...
2020-02-27 21:37:30
168
原创 Codeforce 1311F - Moving Points【树状数组或pbds】
题意： 给出 xxx 坐标轴上的 nnn 个点，各点坐标为：xix_ixi（保证所有的 xix_ixi 不相等），同时每个点有一个速度 viv_ivi，因此 ttt 时刻，点 xix_ixi 的位置可以表示为 xi+t∗vix_i+t*v_ixi+t∗vi。d(i,j)d(i,j)d(i,j) 表示点 iii 和点 jjj 在运动过程中的相距距离的最小值。求 ∑1≤i<j≤...
2020-02-25 16:52:50
178
原创 Codeforce 1311D - Three Integers【枚举】
题意：给出三个数 ：a,b,c,(a≤b≤c)a,b,c,(a\leq b \leq c)a,b,c,(a≤b≤c) ，可以对任意一个数进行任意次 +1+1+1 或 −1-1−1 的操作。要求操作之后得到的数 A,B,CA,B,CA,B,C，满足：均为正数， A≤B≤CA\leq B\leq CA≤B≤C，AAA可以整除 BBB，BBB可以整除 CCC。思路：枚举。先确定 AAA 的范围，...
2020-02-25 15:15:32
148
原创 Codeforces 1313C2 - Skyscrapers【思维】
题意：要求在一条直线上建 nnn 栋楼，并且要满足下列要求：1.每栋楼的层数不能超过其楼层限制 m[i]m[i]m[i]；2.对于第 i,j,ki,j,ki,j,k 栋，如果满足： i<j<ki<j<ki<j<k，那么其层数要满足：aj>ai<aka_j>a_i<a_kaj>ai<ak，其中 j,kj ,kj,k ...
2020-02-24 11:28:46
236
原创 Codeforces 1307D - Cow and Fields【最短路+思维转换】
题目： 给出一个 nnn 个点，mmm 条边的无向连通图，其中有 kkk 个特殊的点。选择连接这 kkk 个点中的两个，使得从 111 号点到 nnn 号的最短距离最大化，并求出该最短距离。思路： 先考虑暴力的做法，用两次 bfsbfsbfs 求出 111 号点和 nnn 号点到各个点的距离，分别用 x[i]x[i]x[i] 和 y[i]y[i]y[i] 表示。然后暴力枚举这 kkk 个...
2020-02-23 22:33:09
120
原创 Codeforces1307C - Cow and Message【思维】
题目：给出一个字符串 sss ,要求求出其下标为等差数列的出现次数最多的子序列的出现次数。(1≤∣s∣≤105)(1≤|s|≤10^5)(1≤∣s∣≤105)思路：因为要求下标是等差数列，所以只需要考虑长度为 111 或 222 的子序列即可。对于长度为1 的子序列，用一个一维计数即可。对于长度为2的子序列，用一个二维数组计数。复杂度：O(26∗∣S∣)O(26*|S|)O(26∗∣...
2020-02-23 16:24:27
144
原创 KPI HDU - 5249【权值线段树】
Problem Description： 你工作以后, KPI 就是你的全部了. 我开发了一个服务，取得了很大的知名度。数十亿的请求被推到一个大管道后同时服务从管头拉取请求。让我们来定义每个请求都有一个重要值。我的KPI是由当前管道内请求的重要值的中间值来计算。现在给你服务记录，有时我想知道当前管道内请求的重要值得中间值。Input：有大约100组数据。每组数据第一行有一个n(1≤n≤1...
2020-02-23 10:18:49
142
原创 DNA Sequence POJ - 2778【AC自动机+矩阵快速幂】
题意： 给出 mmm 个只由 A,T,C,GA,T,C,GA,T,C,G 组成的字符串（每个的长度不大于 101010），求一个长度为 nnn 且也只由 A,T,C,GA,T,C,GA,T,C,G 组成但不包含之前所给的 mmm个字符串的序列的种类数。思路： 借助离散数学中可达矩阵的概念。先把m个字符串建立成AC自动机中的字典树，同时对于字符串的结尾节点，进行标记。一个节点要想一步到达另...
2020-02-22 20:12:30
92
原创 Petya and Array CodeForces - 1042D【逆序对变形】
题意： 给出一个 nnn 个数的数组和一个 ttt，要求出满足∑i=lrai<t\sum_{i=l}^{r}{a_i}<t∑i=lrai<t 的 lll和 rrr 的对数。数据范围：1≤n≤200,000,∣t∣≤2⋅1014,∣ai∣≤1091≤n≤200,000,|t|≤2⋅10^{14},|a_i|≤10^91≤n≤200,000,∣t∣≤2⋅1014,∣ai∣...
2020-02-21 17:08:48
104
原创 Path HDU - 6582【求最短路所有边+最小割】
题意： 给一个有向图，删除每一条边的代价是边的长度，要求花费最小的代价，使得 1→n1\to n1→n最短路变长,求该最小花费。思路： 要使得最短路变长，那么删除的边一定要破坏原来的最短路。即要先把所有最短路的所有边找出来，通过删除某几条边，使得所有的最短路无效。 如何把最短路的所有边全部找出呢？以 dis1[i]dis1[i]dis1[i] 表示原图中，111 号节点到其余节点的最...
2020-02-20 20:47:48
133
原创 P4240 毒瘤之神的考验【莫比乌斯反演+各种数学技巧】
毒瘤题题意：TTT 次询问，每次给定 n,mn,mn,m ，求：(∑i=1n∑j=1mφ(ij)) mod 998244353(\sum_{i=1}^{n}{\sum_{j=1}^{m}{\varphi(ij)}})\;mod\;998244353(∑i=1n∑j=1mφ(ij))mod998244353 的值。数据范围：1≤T≤104,1≤n,m≤1051\leq T \leq 1...
2020-02-19 23:30:49
107
原创 莫比乌斯反演
莫比乌斯函数μ(d)：（积性函数）d=1时：μ(d)=1;d=p1p2…*pk时（两两为互质的质数），μ(d)=(-1)^k其他情况，μ(d)=0;线性筛莫比乌斯函数（基于欧拉筛）：#include <bits/stdc++.h>using namespace std;const int N=1e5+5;vector<int>prime;int mob[N...
2020-02-19 10:15:41
186
原创 AC自动机
定义： Aho–CorasickAho–CorasickAho–Corasick 算法是由 AlfredV.AhoAlfred V. AhoAlfredV.Aho 和 MargaretJ.CorasickMargaret J.CorasickMargaretJ.Corasick 发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字...
2020-02-17 23:10:54
77
原创 CodeForce 1304E 1-Trees and Queries【LCA】
题意： 首先给一棵 nnn 个点的树，然后有 qqq 次的询问，每次询问会向树上点 xxx 和 yyy 之间增加一条边（保证增加的边之前不存在），然后问点 aaa 和 bbb 之间是否存在一条路径长度为 kkk 的路径。每次询问相互独立，即每次增加的边在下一次的询问中不存在。数据范围：3≤n≤105,1≤q≤105,1≤x,y,a,b≤n,x≠y,1≤k≤1093≤ n ≤10^5,1≤q...
2020-02-16 14:54:01
143
原创 2020牛客寒假算法基础集训营6
题解A.配对：#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e5+5;const double eps=1e-6;priority_queue<int,vector<int>,greater<int> >que;int a[...
2020-02-15 20:53:26
148
1
原创 三分应用
1.hdu 3400题意： 在二维平面中有两个线带，有两个段 ABABAB 和 CDCDCD，lxhgwlxhgwlxhgw在 ABABAB 上的速度是 ppp，CDCDCD 上是qqq，他可以以速度 rrr 在平面上的其他区域移动。从 AAA 到 DDD 需要多长时间？思路： 如果不考虑速度，两点之间肯定是直线最短。但是由于速度的大小影响，所以不一定走直线。那么必然在直线 ABABA...
2020-02-14 23:19:11
92
原创 2020牛客寒假算法基础集训营5
B.牛牛战队的比赛地：要求最大距离的最小值，三分。三分用于单峰函数求最值，又因为是对浮点数进行三分，可以通过限定三分的次数来达到一定的精度要求。#include <bits/stdc++.h>using namespace std;const int N=1e5+5;typedef long long ll;ll x[N],y[N];int n;double che...
2020-02-14 18:11:19
168
原创 CodeForce1299A-Anu Has a Function【位运算+前后缀】
定义函数：f(x,y)=(x∣y)−yf(x,y)=(x|y)-yf(x,y)=(x∣y)−y 给出数组 aaa，要求求出使得 f(f(…f(f(a1,a2),a3),…an−1),an)f(f(…f(f(a_1,a_2),a_3),…a_{n−1}),a_n)f(f(…f(f(a1,a2),a3),…an−1),an)的值最大d的数组 aaa 的排列。 仔细观察函数定义，可以发...
2020-02-13 12:32:52
180
原创 Tunnel Warfare HDU - 1540【线段树-区间合并最大连续区间】
操作:D：单点修改；Q：查询该点所在的最大连续区间长度；R：把最近一次删除的点还原； 我一开始的思路是：对于最长连续区间长度的查询，用的是set来存储之前被删除的点（目的是让点排好序），用数组模拟一下栈按删除顺序存点，对于当前要查找的点，利用二分查找找到set中第一个大于等于该位置的点，和前一个点作差，直接求出。#include <bits/stdc++.h>using ...
2020-02-12 15:30:12
124
原创 2020牛客寒假算法基础集训营4
题解G.音乐鉴赏【概率】：还没有做过概率题，感觉都被以前的概率题吓怕了。主要是推公式：设期末分数占比为：xxx，期末分数为：yyy，平时分数：scorescorescore那么最终的分数为优秀：score∗(1−x)+y∗x≥90score*(1-x)+y*x\geq 90score∗(1−x)+y∗x≥90化简得：y≥90−score∗(1−x)xy\geq\frac{90-sc...
2020-02-11 22:42:55
64
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人