魔法使いの秘密基地

[toc] 序列模型例子音乐、语言、文本、视频、股价…… 统计方法方案A：马尔科夫假设假设当前当前数据只跟 $\tau$ 个过去数据点相关 p\left(x_{t} \mid x_{1}, \ldots x_{t-1}\right)=p\left(x_{t} \mid x_{t-\tau}, \ldots x_{t-1}\right)=p\left(x_{t} \mid f\left(x_{t-\tau}, \ldots x_{t-1}\right)\right)方案B：潜变量模型 引人潜变量 $h_{t}$ 来表示过去信息 $h_{t}=f\left(x_{1}, \ldots x_{t-1}\right)$ 这样 $x_{t}=p\left(x_{t} \mid h_{t}\right)$ 文本预处理 序列数据往往存在多种形式，文本是其中常见的形式之一，例如一篇文章可以被简单地看作是一串单词序列，甚至是一串字符序列 将文本当做时序序列，将文本中的字或者字符、词当成样本，样本之间是存在时序信息的，因此文本是一个很长的时序序列 文本预处理的核心思想是如何将文本中的词转化成能够训练的 ...

线段树与树状数组的区别线段树和树状数组的基本功能都是在某一满足结合律的操作(比如加法，乘法，最大值，最小值)下，O(log⁡n)的时间复杂度内修改单个元素并且维护区间信息。 不同的是，树状数组只能维护前缀“操作和”(前缀和，前缀积，前缀最大最小)，而线段树可以维护区间操作和。但是某些操作是存在逆元的（即：可以用一个操作抵消部分影响，减之于加，除之于乘），这样就给人一种树状数组可以维护区间信息的错觉:维护区间和，模质数意义下的区间乘积，区间 xor 和。能这样做的本质是取右端点的前缀结果，然后对左端点左边的前缀结果的逆元做一次操作，所以树状数组的区间询问其实是在两次前缀和询问。 一个简单的整数问题(树状数组+差分)题意给定长度为 N 的数列 A，然后输入 M 行操作指令。 第一类指令形如 C l r d，表示把数列中第 l∼r 个数都加 d。 第二类指令形如 Q x，表示询问数列中第 x 个数的值。 对于每个询问，输出一个整数表示答案。 思考一般的树状数组：单点加，求区间和 这道题反过来了，用差分数组就行了。 123456789101112131415161718192021222324 ...

超快速排序题意通过交换相邻两个数，来给序列排序。求交换次数。 思考就是求逆序对的个数，用归并排序求。 123456789101112131415161718192021222324252627282930313233343536373839404142#include <cstdio>typedef long long LL;const int N = 500010;int n;LL q[N], w[N];LL merge_sort(int l, int r){ if (l == r) return 0; int mid = l + r >> 1; LL res = merge_sort(l, mid) + merge_sort(mid + 1, r); int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) if (q[i] <= q[j]) w[k ++ ] = q[i ++ ]; else ...

64位整数乘法（龟速乘）题意求a*b mod p的值。 1≤a,b,p≤10e18 思考龟速乘用加法来模拟乘法，时间复杂度log(n)，好处是不用写高精度。 1234567891011121314151617181920#include <iostream>using namespace std;typedef long long LL;LL a,b,p;LL gcheng(LL a,LL b,LL p){ LL res=0; while(b){ if(b&1) res=(res+a)%p; a = (a+a)%p; b>>=1; } return res;}int main(){ cin>>a>>b>>p; cout<<gcheng(a,b,p); return 0;} 费解的开关(递推)题意5*5的矩形，0表示灭，1表示开。每次改变十字形的灯的状态。 给定一个初 ...

K : King of Gamers题意给定一个期望达到的胜率a/b，n次比赛，每次的输赢有当前的胜率和期望达到的胜率决定。 问n次比赛后能赢多少次。 思考显然答案是[a*n/b]和[a*n/b]+1中的一个，具体是哪一个。通过打表（或者分析前一步的情况）可以得到，为1 +(n - 1) * a / bz 1234567891011121314151617181920212223242526#include<bits/stdc++.h> using namespace std;long long t,n,a,b;int main(){ scanf("%lld",&t); while(t--){ scanf("%lld%lld%lld",&n,&a,&b); double t = 1.0*a/b; t *= n; long long tpp = t; if(n!=1){ ...

家谱树题意拓扑排序模板题 思考12345678910111213141516171819202122232425262728293031#include<bits/stdc++.h>using namespace std;int n;vector<int> mp[110];queue<int> qu;int d[110];int main(){ cin>>n; for(int i=1;i<=n;i++){ int s; while(cin>>s,s){ mp[i].push_back(s); d[s]++; } } for(int i=1;i<=n;i++){ if(d[i]==0) qu.push(i); } while(!qu.empty()){ int tp=qu.front(); ...

智乃买瓜题意智乃来到水果摊前买瓜, 水果摊上贩卖着 $N$ 个不同的西瓜, 第 $i$ 个西瓜的重量为 $w_{i}$ 。智乃对于每个瓜都可以选择买一个整瓜或者把瓜憵开买半个瓜, 半个瓜的重量为 $\frac{w_{i}}{2}$ 。 也就是说对于每个西瓜, 智乃都有三种不同的决策: 购买一整个重量为 $w_{i}$ 的西瓜 把瓜憵开, 购买半个重量为 $\frac{w_{i}}{2}$ 的西瓜 不进行购买操作为了简化题目, 我们保证所有瓜的重量都是一个正偶数。现在智乃想要知道, 如果他想要购买西瓜的重量和分别为 $k=1,2,3 \ldots M$ 时, 有多少种购买西瓜的方案, 因为这些数字可能会很大, 请输出方案数对 $10^{9}+7$ 取余数后的结果。 思考分组背包 1234567891011121314151617181920212223242526#include<bits/stdc++.h>using namespace std;const int MAXN=1005;int n,m,x;const long long mod=1e9+7;long lo ...

蒙德里安的梦想题意思考题目分析摆放方块的时候，先放横着的，再放竖着的。总方案数等于只放横着的小方块的合法方案数。 如何判断，当前方案数是否合法？ 所有剩余位置能否填充满竖着的小方块。可以按列来看，每一列内部所有连续的空着的小方块需要是偶数个。 状态表示f[i][j] 表示已经将前 i -1 列摆好，且从第 i−1列，伸出到第 i 列的状态是 j 的所有方案。其中j是一个二进制数，用来表示哪一行的小方块是横着放的，其位数和棋盘的行数一致。 状态转移既然第 i 列固定了，我们需要看 第 i-2 列是怎么转移到到第 i-1列的（看最后转移过来的状态）。假设此时对应的状态是k（第i-2列到第i-1列伸出来的二进制数，比如00100），k也是一个二进制数，1表示哪几行小方块是横着伸出来的，0表示哪几行不是横着伸出来的。 它对应的方案数是 f[i−1,k]，即前i-2列都已摆完，且从第i-2列伸到第i-1列的状态为 k 的所有方案数。 这个k需要满足什么条件呢? 首先==k不能和 j在同一行==（如下图）：因为从i-1列到第i列是横着摆放的12的方块，那么i-2列到i-1列就不能是横着摆放的，否则 ...

休息时间题意一天由 N个小时构成，我们称 0 点到 1 点为第 1 个小时 在第 i 个小时睡觉能够恢复 Ui 点体力。 在这个星球上住着一头牛，它每天要休息 B 个小时。 它休息的这 B 个小时不一定连续，可以分成若干段，但是在每段的第一个小时，它需要从清醒逐渐入睡，不能恢复体力，从下一个小时开始才能睡着。 另外，因为时间是连续的，即每一天的第 N 个小时和下一天的第 1 个小时是相连的（N 点等于 0 点），这头牛只需要在每 N 个小时内休息够 B 个小时就可以了。 请你帮忙给这头牛安排一个睡觉计划，使它每天恢复的体力最多。 思考破题口在于如何找到状态表示，首先观察题目，发现制约因素仅仅知识在休息的一段时间里面，第一个小时不算，所以我们可能利用线性dp的思路，找到相邻两项的关系，这里我们用f[i][j][0&1]表示当前在第i个小时，当前以及睡了j个小时，且当前这个小时有没有睡（0 & 1），然后找到相邻两项的递推关系，容易得到: 1234567891011121314151617181920212223242526272829303132333435363738 ...

石子合并题意模板题 123456789101112131415161718192021#include<bits/stdc++.h>using namespace std;const int N=310,INF=0x3f3f3f3f;int s[N],a[N],n,f[N][N];int main(){ cin>>n; memset(f,0x3f,sizeof f); for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i],f[i][i]=0; for(int len=2;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r=l+len-1; for(int k=l;k<r;k++){ f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1] ...