3 GoLakerswxy

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 5w+

生成正态分布(高斯分布)的随机数

double generateGaussianNoise(double mu, double sigma){ const double epsilon = std::numeric_limits<double>::min(); const double two_pi = 2.0*3.14159265358979323846; static double z0, z1; static bool generate; generate = !generat.

2020-06-24 10:07:59

背包问题

背包问题是NP-hard问题。背包容量可以理解是一个值的位数。背包问题复杂度实际上是为多项式的。不会就得多读书,不能和老板杠。标记一下《algorithmdesign》一书,好像有点贵。。。

2020-06-08 18:20:34

一维正态分布的最大似然估计

正态分布密度函数是:  若随机变量X服从一个数学期望为μ、方差为σ2的正态分布,记为N(μ,σ2)。当μ=0,σ2=1是,称为标准正态分布。不需要记住这个复杂的公式,知道它的意义即可,在使用时可以随时查阅。  在研究正态分布时,我们认为每个样本都是等权的,因此μ是随机变量的均值,控制了曲线的位置,σ2控制了曲线的陡峭程度:  σ2越小,样本越靠近μ:  在上图中,当σ=0.2时,曲线更陡峭,倒钟更窄,样本更向μ处集中。最大似然估计量  随机变量X服从正态分布:  

2020-06-02 18:56:52

统计合法序列数目

今晚hu老师发了我一道题目,好久没碰过了,没想到写了一下还ok。题意是时间限制:1.0秒空间限制:256MB输入m,n,x,y表示,序列长度是2*n,序列中最大数是m,合法序列定义:前n个数不下降,后n个数不上升,x和y位置的数相等。求和法序列的数目ans%998244353后的值。(其中 1≤x<y≤2n 1≤n,m≤10^5)样例1输入3213样例1输...

2020-04-25 21:38:14

shell多线程 跑C语言随机数代码

获取秒级,毫秒级和纳秒级的当前时间的代码:/// 获取秒级,毫秒级和纳秒级的当前时间#include<stdio.h>#include<sys/time.h>#include<iostream>using namespace std;int main(){ struct timeval time_now = {0}; unsigne...

2020-03-18 11:44:47

Codeforces Round #571 (Div. 2)C. Vus the Cossack and Strings

字符串a和字符串b(|a|>=|b|),在a中取与b长度相等的所有子串,比较子串与b串中对应位置字符不同的数量,问有多少子串产生偶数数量。假设b长度为3(a1^b1)(a2^b2)(a3^b3)为不同的字符的数量,(a1^b1)^(a2^b2)^(a3^b3)表示的便是奇偶进行下一步:(a2^b1)^(a3^b2)^(a4^b3)==(a1^b1)^(a2^b2)^(a3^b...

2019-07-03 10:41:56

计蒜客 南昌网络赛 C. Angry FFF Party(java大数快速幂)

好久没写博客了,周六晚上破实验课好无聊,把下午做的题贴一下。思路很简单,预处理到30就足足够了,10以内是有最优选择的,大数的时候因为两个数字之间的差值是特别大的,所以直接贪心一下就可以了。没学过Java,之前就写过一个java大数的A+B;这次网络赛现学现卖,一A真的是刺激!///package D;import java.util.Scanner;import java...

2019-04-20 18:46:52

退役总结

       距离打完退役战西安ec-final已经一个月了,当了一个月的咸鱼,才想到要写一个退役总结。       进集训队打了两个赛季比赛,最后终要退役了。       我从高中开始学的编程,但是只拿了两年省二无奈我是一个失败的oier,或者根本称不上是oier吧!有一点编程基础,到了大学开始寻找打比赛的团队,不想再留遗憾了。印象最深刻的一件事是16年大连区域赛后三位14级学长在睿思楼...

2019-01-16 21:02:13

HDU - 5000 Clone (dp)

题目:克隆人有n个属性,给出每个属性的最大值T[i];属性值可以是0-T[i];如果A的所有属性都不比B低,那么B就不能存活,问最多存活多少人。思路:经过分析可以得到,让他们的属性和达到(T[1] + T[2].....+ T[n] )/2 也就相当于每个属性都取到平均值,无疑可以有更多人;  那么dp[i][j]就代表前i种属性,和达到j的有多少种。dp[i][j]  += dp[i-1...

2018-09-17 22:16:38

计蒜客 焦作网络赛 String and Times(后缀数组)

题目:给一个字符串问重复出现的次数在[A,B] 区间的子串有多少种。思路:后缀数组,对于一个height[i],求height[i-1]---height[i]区间有多少个h满足存在大于等于h的连续的最长长度>=A并且<=B的一个序列(h的数量比较少可以单个枚举。。),这里用rmq来实现。然后另外算一下A==1的情况,也就是只出现了一次的子串有多少个(比赛时就是这里写错了,唉,我t...

2018-09-15 20:09:34

HDU 5469 Antonidas(搜索剪枝)

题目:n个节点的一颗树,每个节点有个字母,给出目标字符串,问求是否存在点对u,v使得u到v的路径上的字母正好组成这个字符串。思路:dfs搜索,感觉复杂度过不了,但是却过了。到达一个点时候判断还剩下没匹配的长度是不是小于这个点往外连接的最大长度。#include<bits/stdc++.h>using namespace std;typedef long long ll;...

2018-09-14 16:11:21

HDU - 5468 Puzzled Elena (dfs序+容斥原理/莫比乌斯反演)

题目:给出一棵树,每个点上有权值.然后求每棵子树中与根节点互质 即gcd(a,b)=1 的节点个数.思路:该题涉及到一个典型问题.问x与S中有多少个数不互素。解决办法是将S中所有元素依次进行两个步骤:①将元素进行质因数分解。②将质因数可能产生的乘积的出现次数加1。记录一下遍历子树之前的cnt值和遍历子树之后的cnt值,作差就是这棵子树的cnt值。将x进行质因数分解,利用容斥原理求解。#i...

2018-09-14 15:05:54

hihocoder 1388 Periodic Signal (FFT)

题目:两个序列,求一个差值平方和最小 min{(a1-b1)²+...+(an-bn)²,(a1-b2)²+...+(an-b1)²,...,(a1-bn)²+...+(an-b1)²}思路:原式变形后就是sigma(a[i]^2)+sigma(b[i]^2)-2*sigma(a[i]*b[(i+k)%n])的最大值,也就是sigma(a[i]*b[(i+k)%n])的最小值。这个可以用F...

2018-09-13 16:30:58

HihoCoder - 1387 求树上相同颜色的直径

题目: 给你一棵n个节点的树,每个节点的颜色可能不同,现在要给你两种颜色,问你两种颜色的最大距离。如果有一种颜色不存在那么直接输出-1 即可。#include<bits/stdc++.h>using namespace std;const int inf=99999999;const int maxn=1e5+10;int n,m,a[maxn];struct no...

2018-09-13 14:44:08

hdu 6212 Zuma(区间dp)

题目:一共有两种颜色的祖玛游戏,每三个连在一起(或者大于三个)的球球就会被消除掉,问将这个字符串消除干净的最小吐球个数。思路:区间dp,考虑几种情况,**** *****直接是两个组合,1***1中间挖掉一部分后两边合在一起,1***1***1中间挖掉两部分。#include<bits/stdc++.h>using namespace std;const int inf=...

2018-09-13 12:54:16

计蒜客 2018南京网络赛 I Skr(回文树)

题目:给一串由0..9组成的数字字符串,求所有不同回文串的权值和。比如说“1121”这个串中有“1”,“2”,“11”,“121”三种回文串,他们的权值分别是1,2,11,121。最终输出ans=135。思路:之前写了马拉车的算法,网上看到的这个题是回文树的模板题。。。#include<bits/stdc++.h>using namespace std;typedef l...

2018-09-11 11:25:06

回文树(模板)

引用:Palindromic Tree——回文树【处理一类回文串问题的强力工具】回文树练习题集首先,回文树有何功能?假设我们有一个串S,S下标从0开始,则回文树能做到如下几点:1.求串S前缀0~i内本质不同回文串的个数(两个串长度不同或者长度相同且至少有一个字符不同便是本质不同)2.求串S内每一个本质不同回文串出现的次数3.求串S内回文串的个数(其实就是1和2结合起来)4.求以下标i结...

2018-09-09 21:48:35

计蒜客 徐州网络赛 A.Hard to prepare (递推)

题目:n个人坐成一圈,每个人可以选0....2^k-1里面选一个数,问最后相邻的人的数字的xnor大于0的方案数有多少。思路:对于一个确定的k位的数,与它nxor值为0的数字只有一个,就是他的补码。然后对于一条直线来说再加一个满足条件的数的数量就是n-1了。现在这个题目是个圈。加一个数,需要考虑所加数与第1个数是否冲突,与第n-1个数是否冲突。如果第1个数与第n-1个数一样,那么第n-2...

2018-09-09 19:53:24

计蒜客 徐州网络赛J.Maze Designer(最小生成树)

题目:给一个n*m的方格,每个格子中间有个权值表示加上一堵墙的代价,然后需要构成一个图是的任意两点直接有且只有一条路,给出q组询问,每次查询两点之间的最短距离。思路:最大生成树,求lca。很裸的一道题目,唉。但是比赛时没读懂题意,以为每次查询都对应着一个图。。。。#include <bits/stdc++.h>using namespace std;typedef lon...

2018-09-09 19:29:23

POJ-2888 Magic Bracelet (polya定理+dp矩阵快速幂)

题目:用m种颜色给长度为n的项链染色,其中k对颜色不能相邻,旋转相同看作同一种方案,问方案数,结果模9973 。思路:对于一段上的方案数是,dp[i][j]=sigma(dp[i-1][k]) (j与k可以相邻);长度非常大的时候这是做不了的,看到这个形式就可以考虑一下矩阵快速幂了。然后应用polya计数。#include<cstdio>#include<cstrin...

2018-09-07 19:12:52

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 阅读者勋章Lv1
    阅读者勋章Lv1
    授予在CSDN APP累计阅读博文达到3天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。