- 博客(176)
- 资源 (7)
- 收藏
- 关注
RSS订阅原创 【读书笔记】《认知语义学》序言
【读书笔记】《认知语义学》序言认知语义学研究就是对概念内容及其语言组织形式的研究，即研究概念内容的本质以及普遍组织形式。一.与语言内容相关的研究大体可以分为三个范式:形式研究范式、心理学研究范式和概念研究范式。形式研究范式的一个主流方法是生成语法，但是生成语法没有研究语言的普遍概念结构，生成语法只是将心理学的认知结构和加工过程用于形式语义学的范畴划分和语义运算上。心理学范式是以相对...
2018-07-11 23:41:13
1176
原创 数学建模美赛写作LaTeX简易教程
数学建模美赛写作LaTeX简易教程为什么要用LATEX" role="presentation" style="position: relative;">LATEXLATEX\LaTeX，因为好看啊！接下来我们就来学习如何使用LATEX" role="presentation" style="position: relativ
2018-01-14 19:44:07
26992
20
原创 NCPC 2016 A Artwork(并查集)
Artwork - 题目大意 给你一个n*m的格子，依次向其中放入q个线段，让你输出每放一个线段之后图中的连通分量有多少个分析 逆向思维 先将所有线段放上去之后从最后一个依次取，每取一个用并查集维护连通分量的个数代码#include<cstdio>#include<iostream>#include<cmath>#include<cstring>#include<cstdlib
2017-10-03 19:42:43
930
原创 17年ICPC新疆网络赛F Islands(强连通 缩点)
题目大意 给你一个有向无环图（DAG），问你最少加入几条边可以将这个图变成强连通分析 裸的一道强连通题，缩点后统计入度为0和出度为0的个数，输出这两者间的最大值即可代码#include<cstdio>#include<iostream>#include<cmath>#include<cstring>#include<cstdlib>#include<queue>#include
2017-09-09 19:48:08
586
原创 17年ICPC新疆网络赛G Query on a string(线段树 KMP)
题目大意给一个字符串S(长度最大100000)和T(最长10) 给出n次操作，一共有两种操作:Q i j :计算S中区间[i,j]中有多少个子区间能和T匹配C x ch :将S[x]变成字符ch分析 我们用A数组记录下S中以每个下标为开头的字符串是否匹配，1表示匹配，0表示不匹配 这样就可以通过线段树来查询一个区间中有多少匹配的子区间了(维护一个区间最大值) 然后就是更新的操作了，因为T
2017-09-09 19:38:24
756
原创 CF 828C String Reconstruction(暴力)
题目大意 给你一个字符串中的一些信息:某些字串和这些字串的位置，同一个字串可以出现很多次，输出原字符串分析 我的做法是用f[i]f[i]记录以ii开头的最长的子串,这样只需要线性扫一遍就行了代码#include<cstdio>#include<iostream>#include<cmath>#include<cstring>#include<cstdlib>#include<qu
2017-09-04 16:05:34
1877
原创 CF 817D(线段树 计数 pre数组)
题目大意 给你一个序列，这个序列中任意一个区间的最大值减去最小值得到一个数，让你求所有的区间的这个数加起来的和是多少。分析 这道题可以用线性扫描pre数组的方法差不多O(n)O(n)的复杂度做出来 我做的时候是分治的思想，用线段树来维护，O(nlogn)O(nlogn)的复杂度 找到最大的那个元素，设下标为loc，就将问题分成了三部分: ⎧⎩⎨包含这个最大元素的区间这个最大元素左边的区间
2017-09-04 12:47:13
445
原创 POJ 3342 Party at Hali-Bula(树的最大独立集)
题目大意 求树的最大独立集节点个数并判断最大独立集是否唯一 ps:树的最大独立集是指选出尽量多的点使得两两点之间没有边相连分析如果不判断是否唯一这道题可以用贪心来做 但加了这个条件之后贪心就不好判断了 考虑动态规划的做法,用dp[i][0]dp[i][0]和dp[i][1]dp[i][1]分别表示以ii节点为根的子树ii节点不选和选两种情况下的最大独立集节点数，转移方程就不用多说了。
2017-09-01 10:34:25
359
原创 【专题】树的最小支配集 最小点覆盖 最大独立集
最小支配集 最小点覆盖 最大独立集图G=(V,E)定义：最小支配集：从V中取尽量少的点组成一个集合使得V中剩下的点都与取出来的点有边相连最小点覆盖：从V中取尽量少的点组成一个集合使得E中所有的边都与取出来的点相连最大独立集：从V中取尽量少的点组成一个集合使得这些点之间没有边相连对于图中的最下支配集、最小点覆最大独立集问题是一个NP的问题，但在树中可以通过贪心或动态规划的方法很快求得。贪心这三个问题得
2017-08-31 16:38:40
833
原创 【专题】树链剖分
树链剖分定义: size[u]size[u]表示以节点u为根的子树的节点个数 我们将一个节点到它的儿子中sizesize值最大的那个节点的边定义为重边，其他边定义为轻边 我们称某条路径为重路径(或重链)当且仅当它全部由重边组成性质: 我们可以证明对于每个点到根的路径上都不超过O(logn)O(logn)条轻边和O(logn)O(logn)条重路径组成.这种将树上的边(路径)分为重边(重路径)
2017-08-30 21:46:33
355
原创 HDU 6180 Schedule(任务调度 贪心策略 17多校第十场)
题目大意 有n个任务，每个任务有一个起始时间和终止时间，一台机器一个时间最多处理一个任务，一台机器的运行时间定义为这台机器处理的任务中第一个任务开始的时间到最后一个任务结束的时间。 问你最少需要多少台机器，在最少机器数量的情况下所有机器总的时间花费是多少.分析 这种区间任务调度问题通常可行的一种实现方式是将左右端点看成独立的点来处理(用01来表示是左端点还是右端点)，排一次序依次处理。 符
2017-08-25 14:43:10
622
原创 HDU 6178 Monkeys(树上DP 17多校第十场)
题目大意 给你一颗树，让你选出k个节点和尽量少的边使得这k个节点的每个点都至少通过选出的边与一个节点相邻，文这个最少的边数是多少分析 比较明显的DP问题 通过观察不难发现我们应该尽量将点分成能够两两配对的点对 所以我们希望知道以某个节点为根节点的子树中最大能匹配的点数 为了方便状态的转移，我的做法是设 dp[i][0]dp[i][0]表示以i为根的子树中能够两两配对的最大点数，不包含
2017-08-25 12:24:14
341
原创 HDU 6162 Ch’s gift(LCA 暴力 17多校第九场)
题目大意 给你一颗n个节点的树，每个节点有一个权值，给出m组询问，每次询问对于给定的一个点对(a,b)(a,b)，问你a,b两个点的最短路径上点权值在[L,R][L,R]内的和是多少 1≤n,m≤1051\le n,m\le 10^5分析这道题数据范围比较小(数据比较弱)，直接暴力从两个点出发一步一步往上走直到相遇统计路径上满足条件的点权和即可 官方题解给出了树链剖分的思路，有空再补吧
2017-08-24 10:48:03
441
原创 HDU 6165 FFF at Valentine(强连通 缩点 17多校第九场)
HDU 6155 FFF at Valentine(强连通 缩点)题目大意 给定一个又向图，让你判断是否是对于给定的任意两个点都能从u到v或v到u分析缩点成DAG之后，从度小的点开始删，如果某个时刻出现两个或以上入度为0的点则不满足 算法的实现采用的是Tarjan算法求强连通分量缩点代码#include<cstdio>#include<iostream>#include<cmath>
2017-08-24 10:35:36
285
原创 CodeForces - 816B(贪心+前缀和)
题目大意 数轴上覆盖了n个线段，现在给出q组询问，每组询问一个区间[l,r][l,r]中覆盖超过k的点数的个数分析 线性扫一遍就行了，用一个变量x维护当前点上覆盖的线段数目，从左往右扫，遇到左端点x++,右端点x– 在左端点和右端点上的点特殊处理以下就行，最后在求个前缀和。代码#include<cstdio>#include<iostream>#include<cmath>#inc
2017-08-22 10:35:02
407
原创 HDU 6143 Killer Names(组合数学 递推 17多校第八场)
题目大意 有m种字母，每种字母可以随便用，让你用这m种字母组成两个长为n的字符串，满足这两个字符串中不含有相同字母的方案数有多少种。分析先分类：组成第一个字符串的数目为ii,对ii进行分类 不难得出， ans=∑i=1min(n,m−1)Cim⋅f(n,i)⋅g(n,m−i)f(n,i)表示从由i种字母组成长为n的方案数,i种都要用到g(n,i)表示从由i种字母组成长为n的方案数,i种不一定
2017-08-20 11:42:13
339
原创 HDU 6156 Palindrome Function(数位 回文串 17CCPC网络赛)
题目大意 定义：f(n,k)={k1如果n在k进制下是一个回文数否则 定义： f(n,k)= \begin{cases} k & 如果n在k进制下是一个回文数\\ 1 & 否则 \end{cases} 让你求 ∑i=LR∑j=lrf(i,j) \sum_{i=L}^{R}\sum_{j=l}^{r}f(i,j) 分析这道题可以将问题简化成求：
2017-08-20 11:19:11
441
原创 HDU 6140 Hybrid Crystals(简单题 17多校第八场)
题目大意 给出一串正数aia_i，每个数有一个属性：N、L或D N表示这个数的符号可正可负；L表示这个数的符号是正；D表示符号为负 这些数满足: >a1=1,b1=N>ai≤∑j=1i−1aj[bj=N]+∑j=1i−1aj[bi=L∩bj=L]+∑j=1i−1aj[bi=D∩bj=D](2≤i≤n).> >a_1=1,b_1=N\\ >a_i \le \sum_{j
2017-08-18 10:05:14
327
原创 HDU 6121 Build a tree(树 递归 17多校第七场)
题目大意 有一棵nn个点的有根树，标号为00到n−1n-1，ii号点的父亲是⌊i−1k⌋\lfloor\frac{i-1}{k}\rfloor号点，求所有子树大小的异或和。 1≤n,k≤10181\le n,k\le 10^{18}。分析题目中⌊i−1k⌋\lfloor\frac{i-1}{k}\rfloor这个的意思就是说这是一颗完全k叉树 我们容易发现以根节点的儿子为根的子树中，
2017-08-16 09:28:31
302
原创 HDU 6127 Hard challenge(几何 多校第七场)
POJ 2728 Desert King(最优比率生成树)题目大意 有n个村庄，村庄在不同坐标和海拔，现在要对所有村庄供水，只要两个村庄之间有一条路即可，建造水管距离为坐标之间的欧几里德距离，费用为海拔之差，现在要求方案使得费用与距离的比值最小，很显然，这个题目是要求一棵最优比率生成树。分析 以下内容摘录自网上(其他博客排版太丑重排了一下) 概念 有带权图G, 对于图中每条边e
2017-08-15 18:35:52
644
原创 HDU 6107 Typesetting(倍增法 17多校第六场)
题目大意 在一个页面上有n个单词组成的一段话和一个图片,页面宽度、图片宽度、图片两边边距是确定的。告诉了你这段话中每个单词的长度，这些单词在页面中要满足: 图片上不能放单词 一行中的连续区间中的两个单词之间要有一个空格 现在给出Q组询问，每次询问给出一个x和h，x表示图片的起始行数，h表示图片长度 问这些单词加图片一共覆盖了多少行分析采用倍增的做法 整个页面可以分
2017-08-14 16:29:17
590
原创 POJ 2728 Desert King(最优比率生成树)
POJ 2728 Desert King(最优比率生成树)题目大意 有n个村庄，村庄在不同坐标和海拔，现在要对所有村庄供水，只要两个村庄之间有一条路即可，建造水管距离为坐标之间的欧几里德距离，费用为海拔之差，现在要求方案使得费用与距离的比值最小，很显然，这个题目是要求一棵最优比率生成树。分析 以下内容摘录自网上(其他博客排版太丑重排了一下) 概念 有带权图G, 对于图中每条边e[i
2017-08-13 09:45:46
361
原创 HDU 6092 Rikka with Subset(动态规划 17多校第五场)
题目大意 有A1A_1到AnA_n的n个数构成一个集合，这个集合有2n2^n个子集，每个子集的所有数相加得到一个和,有一个BB数组,BiB_i表示和为i(1≤i≤m)i(1\le i\le m)的集合有多少个. 现在输入nn和mm和B0...BmB_0...B_m，让你输出AA数组(1≤n≤50,1≤m≤104,0≤Bi≤2n)(1\le n\le 50,1\le m\le 10^4,0\
2017-08-12 09:08:21
263
原创 HDU 6105 Gameia(树上博弈 17多校第六场)
题目大意 给定一个树，A可以选一个未染色结点染成白色 B有k次机会可以在任何时候切断一条连边，B可以选一个未染色结点染成黑色，同时和这个结点连接的点也会变成黑色（无论是白色还是未染色），本题是个无向图。最后还有白色的结点那么A赢否则B赢。 分析如果Bob能把这棵树分成若干两个一组的点对，那么Bob取得胜利，否则Alice获胜代码#include<bits/stdc++.h>using na
2017-08-11 17:45:47
370
原创 HDU 6103 Kirinriki (字符串翻转 尺取法 17多校第六场)
POJ 6103 Kirinriki (字符串翻转 尺取法)题目大意 给定m和一个字符串，定义两个字符串的dis两者对应字符字典序之差，对应方式为一个从前到后，一个从后到前。然后给定一个m，先要求出最长的给定字符串的两个子串满足它们之间的dis小于等于m的长度。分析将字符串翻转后和自己配对然后不断错位配对 注意有两个方向的错位配对 然后用尺取法取一个最长的不超过m的区间的长度即为答
2017-08-11 15:35:44
420
原创 CF 833B(动态规划优化DP)
题目大意 一个长度为n的序列a[i]a[i]，让你把它分成k份，将每份中不同的数的个数求和，问这个最大的和是多少. 1≤n≤35000,1≤k≤501\le n\le 35000,1\le k \le 50分析看见这道题我们很容易想到从动态规划的角度思考。 这道题类似于n个乘号,题目中说分成k份，那么我们可以通过k-1份的状态来得到份数是k的时候的状态. 设d[k][i]d[k][i]
2017-08-11 15:12:25
1205
原创 HDU 6070 Dirt Ratio(二分+线段树 17多校第四场)
题目大意 给定一个序列a[]，让你求出一个子区间内不同元素个数除以区间长度的最小的一个值。n≤6∗104n\le 6*10^4 ,答案精度不高于10−410^{-4} 分析题目要求的是: min{dif[l][r]r−l+1}(1≤l≤r≤n,dif[l][r]表示区间[l,r]内不同元素的个数) min\{ \frac{dif[l][r]}{r-l+1}
2017-08-11 15:11:20
244
原创 BZOJ 2038 小Z的袜子(莫队模板题)
题目大意 n个数，给出m组询问，每次询问给出一个区间[L,R][L,R]，在区间中任意选则两个数，问这两个数相同的概率是多少. 分析 设一次查询[L,R][L,R]区间中的不同的元素有x,y,z….，每个元素的个数是a,b,c a+b+c=(R-L+1) 那么概率为: C2a+C2b+C2c...C2a+b+c...=a(a−1)2+b(b−1)2+c(c−1)2..
2017-08-09 15:07:55
272
原创 HDU 6078 Wavel Sequence(区间动归 17多校第四场)
题目大意 定义波浪序列为满足a1<a2>a3<a4...a_1<a_2>a_3<a_4...的序列，现在给出两个数组a(长为n)和b(长为m)，从a中选出满足波浪序列一个子序列f，b中选出满足波浪序列的子序列g，求有多少中选法满足f=g。 数组长度n,m≤2000n,m\le 2000，a[i]、b[i]≤2000a[i]、b[i]\le 2000分析题目很像最长公共子序列,从动态规划
2017-08-05 18:53:07
415
原创 HDU 1814(染色)
题目大意 有n个党派，每个党派2个人，这2*n个人之间存在一些敌对关系，现在要从中选出n个人组成一个委员会，要求满足: 1.每个党派中选1个 2.委员会中不存在敌对关系分析题目中第i个党派的成员编号是2n-1与2n，我们将编号减去1就可以通过x^1来得到和x在相同党派的另一个人了。如果a与b敌对，那么a一定与b^1相同颜色。 用染色法来解决这个问题，设1为选中的颜色，2为不选
2017-08-05 10:57:39
315
原创 【模板】强连通分量的kosaraju算法实现
算法思想 kosaraju算法通过对有向图进行两次Dfs得到强连通分量 第一次dfs对每个节点进行标号，在回溯前给顶点标号，完成标号后，越接近图的尾部(搜索树的叶子)，顶点的标号越小。相当于对强连通分量缩点后的DAG进行了一次拓扑排序。 第二次反向dfs，也就是先将图中的边全部反向，在新的图中进行深搜。从标号大的节点(相当于拓扑排序中靠近根节点的节点)开始搜索.
2017-08-04 15:00:16
520
原创 ACM比赛注意事项
ACM比赛注意事项一道题一定要想清楚思路和算法细节后再写，特别是边界条件处理的这种。跟着榜单做题，一道题过的人数就说明了一道题的难易程度，如果一道你认为思维复杂度不高的题过的人数很少那一定是你想简单了，比如大连站的威左夫博弈和2017多校第三场的LCA+DP题。注意在使用long long int的时候是否存在过程中越界。
2017-08-03 08:40:37
2388
原创 基于RMQ的LCA
最近公共祖先问题(LCA)就是: 给定一棵树，不断地询问两个点的最近的公共祖先节点是多少。基于RMQ的方法是一种在线的方法，基本思想是 对树进行DFS，求出树的DFS序，记录下每个节点第一次访问时在DFS序中的位置，我们可以知道： 所询问的两个点的最近公共祖先是这两个节点在DFS序中两个下标的区间内离根最近的那个节点。 所以我们在进行DFS是还需要记录下每个节点的深度信
2017-08-01 11:01:34
438
原创 2017ICPCECIC北方邀请赛
2017ICPCECIC北方邀请赛D题 Birthday present(简单数学)F题 Teacher's Day(二分+贪心)H题 MJF wants to work(贪心)I题 coach’s plan（二分+二分图匹配）
2017-07-30 21:30:29
563
原创 【模式识别】Fisher线性判别
Fisher是一种将高维空间映射到低维空间降维后进行分类的方法1.投影:对xn→\vec {x_n}的分量作线性组合可得标量 yn=w⃗ Txn→y_n=\vec {w}^T\vec{x_n}什么样的映射方法是好的，我们需要设计一个定量的标准去找w⃗ \vec{w}来衡量分类的好坏，或者叫做准则函数。2.基本参量在d维X空间各类样本均值向量m⃗ i\vec m_i mi→=1Ni∑x⃗ ∈
2017-05-31 16:19:44
3148
1
原创 【专题】树形动态规划
AIDreamer2017/5/30树形DP就是状态之间的关系是树状结构的DP【例题一】poj 2342 Anniversary party题目大意 有一群人，每个人有一个欢乐值，这些人之间存在着一些上司和下属关系如A是B的上司，现在让你选出一些人满足这些人之间不存在直接的上司和下属关系并且使得总的欢乐值最大，问最大的欢乐值是多少。分析这种关系画出来是成树形的，节点代表一个人，节点上有一个值表
2017-05-31 13:59:50
582
原创 八数码问题的A*算法实现
问题描述 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。代码实现/*AIDreamer2017/5/27*/#include<iostream>#includ
2017-05-27 19:42:22
1584
TCP-IP详解1,2卷
2013-05-18
编码+隐匿在计算机软硬件背后的语言
2013-05-18
Html+CSS+Javascript.ppt
2013-05-12
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人