新熊君-CSDN博客

原创单调栈总结

单调栈总结目录定义性质功能例题 HDU 1506HDU 5033PKU 2796PKU 3250定义性质下面引自百度百科单调递增或单调减的栈，跟单调队列差不多，但是只用到它的一端，利用它可以用来解决一些ACM/ICPC和OI的题目，如RQNOJ 的诺诺的队列等。单调栈是一种特殊的栈，特殊之处在于栈内的元素都保持一个单调性。假设下图是一个栈内元素的排列情况(单调递增的

2017-04-11 23:28:05 19909 3

原创论文笔记 |【sosr 16】CacheFlow：Dependency-Aware Rule-Caching for Software-Defined Networks

作者：新熊君知乎：新熊君ABSTRACTSDN允许控制应用程序在基础交换机中安装细粒度的转发策略， TCAM可以使用灵活的通配规则模式在硬件交换机上实现规则的快速查找，但是TCAM的高成本和高功耗限制了交换机可以支持的规则数量，同时也无法支持规则表的快速更新。这篇论文（CacheFlow）展示了如何通过结合硬件和软件的优点来实现高速转发，支持大规模的规则表及快速更新。CacheFlow...

2020-02-26 15:38:26 806

原创高中数学如何解决阿里面试算法题

大家好，我是新熊君。今天跟大家分享一道阿里的算法面试题。题目描述给定一个正整数nnn，把它拆分为若干个数的和，记这若干个数的积为MMM，求MMM的最大值。题目分析这道题正常的思路是使用动态规划算法。假设 dp[n]dp[n]dp[n] 为正整数 nnn 拆分后能够得到最大的积。状态转移时只需要遍历小于nnn的每一个正整数 kkk ，取 k∗dp[i−k]k*dp[i-k]k∗dp[...

2020-02-19 17:19:37 491

原创疫情严重，推迟开学，在家如何高效学习

前言我曾经深受在家学习低效率的困扰。网上主流的：制定计划、固定学习时间、番茄钟、费曼技巧我都试过，可通通没有用。因为这不是方法的问题，归根到底是缺乏行动力。学习方法再好，学习技巧再牛逼，可你就是放不下手机，不想去学习，哪怕面对书本也难以集中注意力。在家变成了行动力的矮子，怎么办呢？别着急，往下看。01 早起首先，最重要的一点：早起如果作息混乱，每天精神萎靡还谈什么学习！早起往...

2020-02-07 13:12:56 2780 1

原创 [INFOCOM 2016] DDoS Attack Detection under SDN Context

论文Xu Y , Liu Y . DDoS attack detection under SDN context[C]// IEEE INFOCOM 2016 - IEEE Conference on Computer Communications. IEEE, 2016.0 Abstract软件定义网络（Software Defined Networking, SDN）已经成为了一种...

2019-05-08 00:38:26 552 1

原创 Bohatei: Flexible and Elastic DDoS Defense

文献：Fayaz S K, Tobioka Y, Sekar V, et al. Bohatei: flexible and elastic DDoS defense[C]// Usenix Conference on Security Symposium. 2015.0 Abstract

2019-05-01 12:44:00 860

项目先问了简历上面的项目，着重问了一个和本校研究生合作的一个NLP课题，因为是用深度学习做的，问了一些深度学习的基本知识，和自己对深度学习的理解。然后问了一下我在项目中起的作用，我提到了通过复现其他paper来比较实验效果，然后面试官让我举一个复现论文的例子，我就给他讲了一个机器学习的例子，从word embedding到word2vec再到训练和测试过程，method方面我提到了朴素贝叶斯分...

2019-03-20 01:10:10 515 1

原创 Learning from Bullying Traces in Social Media

1 摘要网络欺凌(cyberbulling)是一种严重影响青少年身心健康的社交现象，而以往一些对于网络欺凌的社交研究总是被数据存在的隐私问题所阻碍。这篇工作的贡献首先是证明了社交软件的数据，通过合适的自然语言处理技术，能够成为研究网络欺凌的丰富数据来源，此外，我们提出了几个NLP的关键问题，包括文本分类，角色标记，情感分析和主题建模，并提供了基线结果。2 数据集及处理首先使用Twitter ...

2019-03-06 13:40:44 638

原创 [Tencent/WeChat] 面试算法题及解题报告

说明算法部分一共面了四道题解题思路仅供参考，可能存在更好的解法。题目1题意层序遍历二叉树，每个节点有一个值（val），以链表的形式返回遍历节点对应的val。树和链表定义如下：struct TreeNode {int val;TreeNode* Left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(N...

2019-02-27 15:35:42 567

原创 [Alibaba] 四数乘积问题

题意给定一个长度为nnn的数组aaa和一个正整数kkk，从数组中选择四个数，要求四个数的乘积小于等于kkk，求方案总数。数组中可能出现多个值相同的数。每次选择四个数时，同一个数不能被选择两次，而值相同的两个不同的数可以同时被选。1≤n≤1031 \leq n \leq 10^31≤n≤1031≤a[i]≤106(1≤i≤n)1 \leq a[i] \leq 10^6 (1 \leq...

2019-02-16 22:26:42 748

原创 [Alibaba] 猜数游戏

题意为了进一步宣传，Alibaba决定策划一个猜数游戏。游戏开始前，Alibaba会随机保密地选择一个不大于nnn的正整数xxx让玩家来猜，并提供一个长度为nnn的数组aaa，a[i]a[i]a[i]表示玩家选择整数iii时需要付出的金钱。每一轮游戏，玩家可以任意选择一个整数并付出相应的价钱，如果猜中了，即选择的数是xxx，则游戏结束，否则Alibaba的漂亮小姐姐会告诉玩家xxx比玩家...

2019-02-16 21:52:30 346

原创 [Hulu] 数组最大价值

题意给定一个包含nnn个正整数的数组aaa，另外有一个长度为nnn的价值数组bbb，表示第iii个正整数的价值为b[i]b[i]b[i]。我们可以选择任意个不相交区间[i,j][i, j][i,j]，需要满足i&lt;ji &lt; ji<j 且a[i]=a[j]a[i] = a[j]a[i]=a[j]，随后我们可以获得区间[i,j][i, j][i,j]所有数的价值，即b...

2019-02-16 21:33:30 412

原创 HDU 5730 FFT + 分治

题目链接题意：给定一个数组aaa，定义a[i]a[i]a[i]表示连续iii个珍珠可以装饰的方案数，求n个珍珠的项链可以装饰的方案总数。思路：定义：F[i]F[i]F[i]：iii个珍珠的项链可以装饰的方案总数则很明显是一个动态规划，得：F[0]=1F[0] = 1F[0]=1F[i]=∑j=1ia[j]∗F[i−j]F[i] = \sum_{j=1}^i a[j]*F[i-j...

2018-10-24 13:05:31 309

原创牛客网暑期ACM多校训练营（第三场）D 字符串匹配 FFT

题目链接题意：给定两个串A，B，问A中有多少个长度等于B的子串与B相似，两个同样长度的字符串相似的条件是：对于对应位置上的字符，差的绝对值不大于1思路：可以类似于FFT用于字符串匹配的算法。假设AAA的长度为mmm，BBB的长度为nnn，且下标均从1开始则相似子串的个数：Ans=∑j=0m−1[∑i=1n(Ai+j−Bi)2∗((Ai+j−Bi)2−1)=0]Ans = \sum_...

2018-10-12 12:05:26 244

原创 HDU 5528 狄利克雷卷积

题目链接题意：给定T(≤2e4)T (\leq 2e4)T(≤2e4)组数据，每组数据给出一个整数n(n≤1e9)n(n \leq 1e9)n(n≤1e9)，求：Ans=∑m∣n∑i=0m−1∑i=0m−1[(i∗j)%m&amp;gt;0]Ans = \sum_{m|n}\sum_{i=0}^{m-1}\sum_{i=0}^{m-1}[(i*j) \% m &amp;gt; 0]Ans=...

2018-10-10 21:47:43 314

原创 ACM-ICPC 2018 焦作赛区网络预赛 J 大数开方

题目链接题意：给定一个数nnn，判断nnn和n(n−1)/2n(n−1)/2n(n-1)/2是否是完全平方数思路：使用Java的BigInteger，对这两个数开方以后，再对得到的数进行平方，判断是否相等。所以套上一个大数开方的模板即可。代码：import java.math.BigDecimal;import java.math.BigInteger;im...

2018-09-15 19:30:59 558 1

原创 ACM-ICPC 2018 焦作赛区网络预赛 E 树链剖分

题目链接题意：给定一棵以111为根的节点，存在路径加，路径乘，路径的节点权值取反，查询路径和等四个操作。思路：典型的树链剖分题目。对于取反，可以转化成减法操作，比如： 00011取反为：11100 等价于 (11111 - 00011) = 11100 即将原值乘上（-1），再加上 2len−12len−12^{len} - 1， lenlenlen为二进制的位数...

2018-09-15 18:51:16 260

原创 HDU 6438 | 2018CCPC网络赛思维贪心优先队列

题目链接题意：给定nnn天的股票价格，每天你可以选择买入一支股票或者卖出一支股票或者什么也不干，问能够得到的最大利润值为多少？输出最大利润值和达到该利润值需要的最少交易次数。思路：思路类似于一道经典的贪心题夹克老爷的逢三抽一用优先队列来维护股票的状态。对于第iii天的股票，如果前i−1i−1i-1天的股票价格都不小于当天的股票价格，那么这一天什么也不做否则找...

2018-08-27 15:29:16 344

原创 HDU 6372 Lucas定理

题目链接题意：给定三个整数ccc，nnn，kkk。假设ppp为第ccc个质数，下面给出一个矩阵AnAnA_n的定义： AnAnA_n的sizesizesize为pn∗pnpn∗pnp^n * p^n，且An[i][j]=(Cji(mod&amp;nbsp;p)&amp;gt;0?1:0)An[i][j]=(Cij(mod&amp;nbsp;p)&amp;gt;0?1:0)A_n[i][j] = (C_i^j ...

2018-08-13 21:41:56 306

原创 HDU 6363 容斥定理

题目链接题意：将nnn个相同的小球放入kkk个不同的箱子，箱子可以为空。假设对于一个方案，cnt[i]cnt[i]cnt[i]表示第iii个箱子中的小球数，则该方案的价值为：gcd(2Fib[cnt[1]]−1,2Fib[cnt[2]]−1,2Fib[cnt[3]]−1,...,2Fib[cnt[k]]−1)gcd(2Fib[cnt[1]]−1,2Fib[cnt[2]]−1,2Fib[...

2018-08-08 20:38:53 279

原创牛客网暑期ACM多校训练营(第五场) B Pell方程

题目链接题意：定义好数nnn满足在区间[n2+1,n2+2n][n2+1,n2+2n][n^2+1, n^2+2n]存在一个数xxx满足x|n4x|n4x|n^4 给定一个正整数mmm，求不小于mmm的最小好数。 m≤101000m≤101000m \leq 10^{1000}思路：数论好题~ 设x=n2+ax=n2+ax = n^2 + a 则可得：n2+a|n4...

2018-08-03 16:39:47 379

原创牛客练习赛22 E 树状数组 + DFS + 拓展欧几里德定理

题目链接题意：给定一个长度为nnn的序列，进行mmm次操作，操作有两类： 111 LLL RRR vvv ：区间[L,R][L,R][L, R]的每个数加上vvv 222 LLL RRR ppp ：查询a[L]a[L+1]a[L+2]...a[R]&nbsp;mod&nbsp;pa[L]a[L+1]a[L+2]...a[R]&nbsp;mod&nbsp;pa[L] ^ {a[L...

2018-08-01 22:07:17 228

原创 HDU 6333 分块 | 莫队算法

题目链接题意：给定n,mn,mn,m，求出∑mi=0Cin∑i=0mCni\sum_{i = 0}^m C_{n}^i，一共有1e51e51e5组询问。思路：记F[n][m]=∑i=0mCinF[n][m]=∑i=0mCniF[n][m] = \sum_{i = 0}^m C_{n}^i则结合杨辉三角，可得：F[n+1][m]=2∗F[n][m]−CmnF[n+...

2018-08-01 20:30:45 418

原创牛客网暑期ACM多校训练营（第四场）A 拓展欧拉定理/降幂定理

题目链接题意：给一个⻓度为nnn的三进制串，有这样⼀个操作：在每个222后⾯插⼊⼀个111 ，每个111后⾯插⼊⼀个000，然后删掉第⼀个字符。问经过多少次操作后，该串变为空串。思路：考虑遍历串的每一位，根据当前已经有过的操作次数(记为xxx)和当前位的情况来求解删除当前位及其产生的后续影响需要的操作次数。假如当前位为000，则其始终为一个000，故操作次数+1+1+1...

2018-07-31 15:53:43 308

原创牛客网暑期ACM多校训练营（第三场）B 数论

题目链接题意：现在给定一颗树的压缩方式：（按如下步骤） 1. 先选择一个大小为kkk的节点子集 2. 对于不存在于子集中的所有节点，动态删去所有度为1的节点（即如果一个节点原本度为2，一个度为1的儿子被删去了，则该节点随后也应该被删去） 3. 对于不存在于子动态集中的所有节点，动态删去所有度为2的节点，随后将其两边所练节点连接起来。 4. 随后剩下的一棵树即为压缩以后的树问...

2018-07-30 11:13:54 199

原创牛客网暑期ACM多校训练营（第三场）F 思维 + 线段树

题目链接题意：给定一个长度为nnn的十六进制数，和mmm次询问，询问格式为(op,x,y)(op,x,y)(op, x, y)，当op=1op=1op = 1，表示将第xxx个数位的数字改为yyy，当op=2op=2op = 2时，问区间[x,y][x,y][x,y]的价值为多少，其中区间[l,r][l,r][l,r]区间的价值定义为：取出[l,r]中的所有子串vvv（不要求连续）...

2018-07-29 01:10:01 308

原创牛客网暑期ACM多校训练营（第三场）G 数论 + BFS

题目链接题意：给定一颗nnn个节点的树和kkk种颜色，每个节点可以染任意一种颜色，显然一共有knknk^n种染色方案。定义一个染色方案的鲜艳度为：任意两个相同颜色的节点间距离的最小值。最后给定一个整数DDD，询问存在多少种方案满足其鲜艳度等于DDD。思路：定义F[D]F[D]F[D]为鲜艳度大于等于DDD的方案数，则答案可以表示为：F[D]−F[D+1]F[D]−F...

2018-07-28 19:38:31 254

原创牛客网暑期ACM多校训练营（第三场）C rope / Splay

题目链接题意：给定一个包含1...n1...n1...n的数列，nnn个数顺序排放，随后有mmm次操作，每次选定一个连续的区间，将该区间的所有数移动到数列的最前端，问mmm次操作以后的数列是什么？思路：队友用Splay一发过的，赛后看群内大佬们聊天记录才发现还可以用roperoperope水过。在g++头文件中，同时需要使用特定的命名空间：#include&lt;e...

2018-07-27 16:13:42 374

原创牛客网暑期ACM多校训练营（第三场）A 多维DP + 方案状态压缩

题目链接题意：给定nnn个物品，每个物品有四维的costcostcost和一个valvalval，选择若干个物品，每个物品只能选取一次，问在不超过给出的思维限制的情况下，能够达到的最大的valvalval是多少？输出选择方案(spjspjspj) 所有参数均&amp;amp;lt;=36&amp;amp;lt;=36O(n5)O(n5)O(n^5)的数组来回溯，对于内存消耗来说相当危险。因为n&amp;amp;lt;=36n&

2018-07-27 15:27:55 198

原创 HDU 6305 笛卡尔树

题目链接题意：给定一个数组aaa，现在存在一个数组bbb，其元素值在[0,1][0,1][0,1]随机生成，若数组a,ba,ba,b生成的笛卡尔树同构，则数组bbb的价值为∑b[i]∑b[i]\sum b[i]，否则为000，求数组bbb的期望价值为多少？思路：首先构建aaa数组的笛卡尔树，此时有一个结论是： bbb数组与aaa数组同构的概率是p=∏i=1n1size[i...

2018-07-24 22:40:13 489

原创牛客网暑期ACM多校训练营（第二场）C 二分 + 凸包

题目链接题意：给定nnn条斜率不为0的直线的参数aaa,bbb（y=ax+by=ax+by = ax + b），有mmm次询问，每次给出一条直线的参数ccc,ddd(y=cx+dy=cx+dy = cx + d)，该直线与这nnn条直线的交点中，横坐标最大为多少？思路：对于两条直线y=ax+by=ax+by = ax + b 和 y=cx+dy=cx+dy = cx + d...

2018-07-24 17:36:58 266

原创牛客网暑期ACM多校训练营（第二场) G 二分 + 双指针

题目链接题意：在一维坐标轴上给定nnn个箱子的坐标，第iii个箱子的坐标为x[i]x[i]x[i]，同时每个箱子里装有一些货物，第iii个箱子装有a[i]a[i]a[i]个货物，将第iii个箱子的一个货物移动到第jjj个箱子的代价为2∗abs(x[i]−x[j])2∗abs(x[i]−x[j])2*abs(x[i] - x[j])，问在总代价不超过TTT的情况下，通过移动最多能让多少个...

2018-07-24 14:14:18 229

原创牛客网暑期ACM多校训练营（第二场）H 树形DP

题目链接题意：给定一棵树，从中取333条不相关路径(没有节点被两条及以上的路径所覆盖)，问经过的点权和的最大值为多少？拓展：如果是取kkk 条不相关路径呢？思路：有一个O(nk2)O(nk2)O(nk^2)的树形DP的算法。定义数组： dp[i][j]dp[i][j]dp[i][j] : 以iii为根的子树包含jjj条不相交路径的最大值那么所要求取的答案...

2018-07-22 12:23:29 438

原创 51Nod 1296 构造排列 + DP

题目链接题意：给定N，要求构造满足要求的排列，对于其中的一些成员，值大于左右邻居，对于另一些成员，值小于左右邻居。输出满足条件的排列种数。思路：设dp[i][j]dp[i][j]dp[i][j]为前iii 个数构成的满足条件的合法排列，且末尾为jjj的个数。那么对于第iii个数，我们只需要考虑其与左邻居的关系（第i个数与右邻居的关系等价于第(i+1)个数与左邻居的关系）...

2018-07-13 21:47:43 270

原创 51Nod 1275 双指针 + 双端队列

题目链接题意：给定一个数组aaa和一个整数kkk，问有多少个连续区间的最大值和最小值的差不大于kkk思路：首先对于固定起点的连续区间，随着终点的增大，其区间最大值一定非递减，区间最小值一定非递增，故区间最大值和最小值的差一定是非递减的。故可以利用双指针来快速求出合法区间的个数。但该过程还需要快速求出区间最小值和最大值，故使用双端队列来实现滑动窗口。保持队列的单调...

2018-07-12 07:49:26 342

原创 ZOJ 3822 | 2014区域赛牡丹江站概率DP

题目链接题意：给定一个n*m的棋盘，每天等概率选择一个空的位置放上棋子，当棋盘的每一行和每一列都存在棋子时，下棋结束。问下棋结束时棋盘上棋子数的期望。思路：定义：dp[i][j][k]dp[i][j][k]dp[i][j][k]表示使用k个棋子，覆盖了iii行jjj列的概率。考虑当前下一个新的棋子，对于棋盘情况的改变有四种情况： 1. 覆盖的行数+1，而列数不变。 ...

2018-06-01 14:35:55 198

原创 2018CCPC女生赛 C 二分+取整Log

题目链接题意：给定三个整数a,b,Ka,b,Ka,b,K，求使得na⌈log2n⌉b&lt;=Kna⌈log2n⌉b&lt;=Kn^a {\lceil log_2n\rceil}^b nnn的最大值。思路：因为函数单调，显然可以直接二分nnn去验证。此题有两个需要注意的地方：一是对于log以2为底的函数取整，不能直接使用log函数来求，会带来精度的误差。需要模拟计算...

2018-05-29 15:33:30 495

原创 51Nod 1463 离线+线段树

题目链接题意：给定：两个长度为n的数列A 、B 一个有m个元素的集合K 询问Q次每次询问[l,r]，输出区间内满足|Bi-Bj|∈K 的最大Ai+Aj数据约定： n,Q&lt;=100000 m &lt;= 10 0&lt;=A[i]&lt;=1000000000 1&lt;=B[i]&lt;=n 1&lt;=K[i]&lt;=n 保证B[i

2018-05-14 00:39:49 181

原创 HDU 5029 树链剖分+权值线段树

题目链接题意：给定一颗n个结点的树，进行m次染色操作，对于每一次染色操作是选择树上的一条路径，将路径上所有节点都染上第zzz种颜色。输出m次操作以后，每一个节点上染色次数最多的颜色。 1&lt;=n,m,z&lt;=1e51&lt;=n,m,z&lt;=1e51[L,R][L,R][L,R]，我们在LLL处加1，R+1R+1R+1处减111，最后扫一遍即可。那对于多种颜色，虽...

2018-05-07 12:41:37 330

原创 51Nod 1556 默慈金数(Motzkin numbers)

题目链接题意：有一个1*n的矩阵，固定第一个数为1，其他填正整数，且相邻数的差不能超过1，求方案数%1e9+71e9+71e9+7的结果。思路：显然：如果第iii个格子的数是1，则第i+1i+1i+1个格子只有111或者222两种可能而如果第iii个格子的数不为1，则第i+1i+1i+1个格子一定有三种可能。则当考虑1∗n1∗n1*n矩阵填法的方案数时，如果我...

2018-04-21 11:25:59 500

空空如也

空空如也