K-th Number(主席树)

2:K-th Number

  1. 对问题的分析设计过程

    题目要求找区间第k大,是一道典型的可持久化权值线段树的例题。

  2. 程序中用到的数据机构和算法

    本程序使用可持久化权值线段树实现,在权值的离散化上直接使用动态申请权值线段树节点来解决该问题。可持久化权值线段树(又称主席树)的详细实现方法可自行百度或参考代码。

  3. 程序的运行情况

    该程序提交了一次即通过。0E0D469A-5839-4D00-A632-9AB4B92CAD25

  4. 在实习过程中得到的经验和体会

    可持久化权值线段树在维护某些区间信息上有很大的作用,是一种非常好的思路。

Code:

 

A Simple Problem with Integers(线段树)

题目链接

对问题的分析设计过程

题目要求对序列进行下列操作

  • 区间加法
  • 区间求和

因此可以考虑使用两个树状数组带懒标记维护的线段树来实现

程序中用到的数据机构和算法

该程序使用了带懒标记的线段树来实现上述操作。具体来说对线段树上的每个节点新增一个属性Lazy表示该区间被同时加上Lazy。在更新时若该节点区间被更新区间覆盖则直接更新Lazy,无需继续对其子节点进行修改。查询时在访问其儿子节点的同时将其Lazy下传至儿子节点。可证明单次修改以及查询其时间复杂度均为$O(\log n)$。总时间复杂度为$O(n+q\log n)$。 详细实现过程见代码。

程序的运行情况

该程序一共提交了3次,运行情况如下图所示:

错了两次的主要原因是因为对于lazy操作有点不太熟悉。

在实习过程中得到的经验和体会

线段树真的好用好写,在维护序列上强无敌。

Lazy操作需要考虑许许多多各种各样的方面需要小心一点

Code:

 

随笔

今天是5月1号。。接下来几天就是我的19岁生日了。。。

这是步入大学的第一个生日,最近也在忙各种各样的事情,期中考,大作业,分专业种种事情,跟高中的生活相比截然不同同时也多了很多各种各样的感想。。。

我觉得现在对我来说还是搞清楚我究竟想干什么,这几天在处理分专业的时候也想了很多,跟计算机在一起是没有多大问题,但更重要的自己想干什么方向的,科学方向还是工程方向,对于各种各样的事物有没有自己特别喜欢的东西,自己究竟想这个世界留下什么,我想了很多。依旧没有答案,所以自己一直告诉自己要多去接触各种各样不同的东西。我相信不管如何东西学多了总归是没有多大问题的。

说到学习,我期中考试的数分挂了。。这是我4年来第一次不及格。。不过我发现很多人根本没有考过不及格。。。这是让我比较震惊的一件事。。。虽然说自己的不及格也有试卷的因素在内,不过自己现在的排名,分数什么的都不算太好(中下游水平),我感觉这样下去同样可能会失去挺多的机会,毕竟自己并不想要去后悔,还是要多多利用平时的时间去搞搞学习。。

然后自己最近还打了两场GCJ,通过打gcj我发现我的状态下降的好多啊。。。小朋友们都吊打我了。。。代码复杂一点的题目就写不出来了。。。不应该啊。。最近要校赛了还是要多花时间来提高自己的编程能力啊(毕竟身边有好多小伙伴感觉在代码实现方面吊打我。。。)

总而言之。。生日愿望就是。。。好好学习,找自己真正喜欢的东西(不管是人还是别的),多做运动,保持好的生活习惯(这个东西是我最做不到的了。。。最近生物钟还出现了点问题。。昨天。。哦不今天6点才睡觉。。。)能把各种各样的任务给保质保量的做好。希望几年之后的自己能不对自己刚才写下的文字后悔啊。

TEST

本文专为LATEX语法测试

  • 自然坐标系中:$\vec v = \dot s \hat e_t$ , $\vec a =\dot v\hat e_t+ \frac{v^2}{\rho}\hat e_n$

$\dot v$ 切向加速度 $\frac {v^2} \rho $ 法向加速度

  • 密切圆半径 :$y=y(x) $ $\rho _n =|\frac{(1+y’^2)^\frac3 2}{|y”|}|$

  • 极坐标系中:$\vec v = \dot \rho \hat e_\rho + \rho\dot\varphi \hat e_\varphi$ , $\vec a = (\ddot \rho -\rho \dot \varphi^2) \hat e_\rho +(\rho \ddot \varphi+2\dot \rho \dot \varphi )\hat e_\varphi$

$\ddot \rho $ 径向长度加速度 -$\rho\dot\varphi^2$ 向心加速度

$\rho\ddot\varphi$ 切向速度加速度 $2\dot \rho \dot \varphi $ 科里奥利加速度

  • 定轴转动中

$\vec v_A= \frac {\vec v_A}{dt } = \vec \omega \times \vec r_A$

$\vec a_A = \frac { d\vec v_A }{dt} = \dot {\vec \omega} \times \vec r_A +\vec \omega \times \dot {\vec r_A} = \dot {\vec \omega} \times \vec r_A + \vec \omega \times (\vec \omega \times \vec r_A)$

​ (切向加速度)(法向加速度)

  • 湿摩擦:$ \vec f = -\gamma \vec v$

  • 绝对速度=牵连速度(平动+转动)+相对速度

$\vec v = \vec {v_{o’}}+\frac{d \vec r}{dt} = \vec {v_{o’}}+\vec \omega \times \vec r ‘ + \vec v ‘$

  • 参考系的转换:

$\vec v = \vec v’ + \vec \omega \times \vec r’ + \vec v_a$

$\vec a = \vec a’ + \vec a_a+\vec {\dot{\omega}} \times \vec r’ + \vec \omega \times (\vec \omega \times \vec r’) + 2 \vec \omega \times \vec r’$

  • 惯性力: $\vec F = -m(\vec a_a+\vec {\dot{\omega}} \times \vec r’ + \vec \omega \times (\vec \omega \times \vec r’) + 2 \vec \omega \times \vec r’)$

  • 质心坐标: $\vec r_c=\frac{1}{M}\sum_i \vec r_i\Delta m_i=\frac{1}{M}\int \vec r dm$

  • 常见的转动惯量:

圆环:$I=MR^2$ 圆盘:$I=\frac{1}{2}MR^2$ 球壳:$I=\frac{2}{3}MR^2$ 球:$I=\frac{2}{5}MR^2$

  • 平行轴定理: $I_{(O)}=I_{(C)}+M\vec d^2$

  • 动量矩定理:$J_(c)=\sum_i M_i \vec r_i \times \vec v_i=I\vec \omega$

  • 刚体的总动能:$T = \frac{1}{2}Mv_c^2+\frac{1}{2}I_{(C)}\omega ^2$

  • 流量守恒原理: $v_AS_A=v_BS_B$

  • 伯努利方程:$\frac{v^2}{2g}+h+\frac{P}{\rho g}=$常量 $\Longleftrightarrow$ $\frac{1}{2}\rho v^2+\rho gh+P=$ 常量

  • 有心运动的基本方程:

  • 动量矩守恒: $J=mr^2\dot\theta=mrv_\theta=j_0$

  • 机械能守恒: $E=\frac{1}{2}m(\dot r^2 + r^2 \dot \theta^2)+V(r)=\frac{1}{2}mv^2+V(r)=E_0$

  • 比耐公式:

已知

$F(r)=m(\ddot r+r\dot\theta^2) \Longleftrightarrow \frac{1}{2}m(\dot r^2+r^2\dot \theta^2)+V(r)=E_0$

$mr^2\omega = J_0$

令 $u=\frac{1}{r},h=\frac{J_0}{m}$ 有 $-h^2u^2(\frac{d^2u}{d\theta^2}+u)=\frac{f(r)}{m}$

  • 平方反比力场中的轨道

$F=-\frac{k}{r^2}$

$r=\frac{p}{\pm1+e cos\theta}$ 其中 $p=\frac{J_0^2}{m|k|},e=\sqrt{1+\frac{2E_0J_0^2}{mk^2}}$ 当$k>0$时取正号

当$k>0$时,轨迹为双曲线

当$k<0$时,$E_0<0$ 椭圆, $E_0=0$ 抛物线,$E_0>0$ 双曲线

$\ddot x + \omega^2_0x+2\beta \dot x = 0$

$Ae^{-\beta t}cos(\sqrt{(\omega_0^2-\beta^2)} t+\varphi) $

$Ae^{-\beta t}(t+B)$

$Ce^{-\beta t}ch(\sqrt{\beta^2-\omega^2_0}t+\alpha)$

BZOJ 3208: 花神的秒题计划Ⅰ

这就是一道滑雪嘛= =

所有操作都爆力,求路径就dp,完了

CODE:

 

BZOJ 3404: [Usaco2009 Open]Cow Digit Game又见数字游戏(博弈论)

一开始被题意坑了= =,题目是说这个数字的最大和最小,不是个位的最大和最小= =

不知道怎么做只能递推了,必胜态就是存在能到达必败态的,必败态就是只能到达必胜态的

CODE:

 

BZOJ 3401: [Usaco2009 Mar]Look Up 仰望(离线+平衡树)

刷银组刷得好开心= =

离线按权值排序,从大到小插入二叉树,查找树中比这个数大的

CODE:

 

BZOJ USACO 银组 水题集锦

最近刷银组刷得好欢快,好像都是水题,在这里吧他们都记录一下吧(都是水题大家一定是道道都虐的把= =)几道比较神奇的题到时再列出来单独讲一下吧= =(其实我会说是BZOJ蹦了无聊再来写的么 = =)

[Usaco2004 Dec]Bad Cowtractors牛的报复  很明显是最大生成树了吧,跟最小生成树一样做就行了 = =(排序时按从大到小的顺序排)

[Usaco2004 Dec]Cleaning Shifts安排值班  贪心,按开始时间从小到大排,然后对于已经安排的时间,取在此时间开始的最晚结束的做为下一个值班就行了。(细节有点多= =)

[Usaco2004 Dec]Tree Cutting网络破坏 大意是在树中找是否存在一个点其中一棵子树的大小超过lim吧(没题目= =)直接递归查找,找出其子树的大小推出自身的大小,然后再找出与父亲相连的那个子树大小(不知道怎么说= =)(n-sum[u]就是了)

[Usaco2005 Jan]Sumsets 求和 给一个数,求用2的幂组成这个数有多少种方法 f[i]=sigma(f[i-w[j]]) w[j]为2的k次幂 (本来想用数学方法的QAQ,不过看到范围什么的还是直接dp吧 = =)

[Usaco2005 Mar]Checking an Alibi 不在场的证明 说白了就是找所有点有多少点离1的距离小于t,直接spfa什么的就行了吧= =

[Usaco2006 Feb]Stall Reservations 专用牛棚 贪心,还是按开始时间从小到大排序,然后用堆维护当前最小的时间是否能让牛使用,如果不行就牛棚数+1,否则就更新时间

[Usaco2006 Feb]Treats for the Cows DP f[i][j]表示第i次左边拿到j的最大值,有f[i][j]=max(f[i-1][j-1]+a[j]i,f[i-1][j]+a[n-i+j+1]i)

[Usaco2006 Oct]Another Cow Number Game 奶牛的数字游戏 明显3N+1问题好吧= =直接模拟就行了

[Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富 dp[j][k]表示走到第j,k得到最大的

[Usaco2007 Dec]Building Roads 修建道路 最小生成树

[Usaco2007 Dec]宝石手镯 01背包= =

[Usaco2007 Dec]穿越泥地 种子染色,直接广搜找最短路

[Usaco2007 Feb]Cow Party 找最短路啦,floyed会超时,n次spfa就行啦

[Usaco2007 Jan]Balanced Lineup排队 RMQ问题= =,o(nlogn)+O(logn)解决

[Usaco2007 Jan]Running贝茜的晨练计划 很有名的一道题,dp f[i][j] 表示第i秒疲劳度为j的运动距离,特殊的f[i][0]=max(f[i-j][j]);

[Usaco2007 Jan]Telephone Lines架设电话线 二分+spfa判断离n的距离是否可行

[Usaco2007 Mar]Monthly Expense 月度开支 二分答案,然后判断= =

[Usaco2007 Nov]Best Cow Line 队列变换 贪心,每次取前和后取决于从前往后数或从后往前数谁大

[Usaco2007 Oct]Bessie’s Secret Pasture 贝茜的秘密草坪 dp f[i][j]表示i个草坪拼成面积j的方案数

[Usaco2008 Dec]Hay For Sale 购买干草 01背包= =

[Usaco2008 Feb]Eating Together麻烦的聚餐 dp  f[i][j]表示前i个人最后一个编号为j的最小方案,然后f[i][j]=f[i-1][k]+1 (0<k<=j) a[i]!=j 或 f[i][j]=f[i-1]k

[Usaco2008 Feb]Line连线游戏 枚举两点,化简,然后判断是否出现

[Usaco2008 Feb]Meteor Shower流星雨 广搜= =,输出最短路

[Usaco2008 Jan]Cow Contest奶牛的比赛 floyed求两点间是否联通

[Usaco2008 Mar]Cow Travelling游荡的奶牛 f[i][j][k]表示走i步到点[j][k]的路径数

[Usaco2008 Mar]River Crossing渡河问题 递推f[i]表示前i只羊渡河的时间 f[i]=min(f[j]+m+m+sigma(ak)) 前缀和优化

[Usaco2008 Mar]The Loathesome Hay Baler麻烦的干草打包机  保证了是一棵树,那么直接dfs求就行了

[Usaco2008 Nov]Buying Hay 购买干草 无限背包

[Usaco2008 Nov]Guarding the Farm 保卫牧场 说白了就是找连通块个数,把点从高到低排序,然后染色,只能走到<=自己的点上

[Usaco2008 Nov]Time Management 时间管理 贪心,按结束时间从大到小排,从后往前推,完成

[Usaco2008 Open] Clear And Present Danger 寻宝之路 floyed求最短路

[Usaco2008 Open]Cow Cars 奶牛飞车 贪心,按速度排序,算出每头奶牛最多能作为第几只

[Usaco2008 Open]Roads Around The Farm分岔路口 直接模拟= =,递归算出

[Usaco2009 Dec]Music Notes乐谱 贪心= =,题目看不到= =
[Usaco2009 Dec]Selfish Grazing 自私的食草者 贪心,同[Usaco2004 Dec]Cleaning Shifts安排值班

[Usaco2009 Mar]Cow Frisbee Team 奶牛沙盘队 可以发现,和为k的倍数可以变成模为0的情况,f[i][j]表示前i个人模为j的方案数

[Usaco2009 Mar]Look Up 仰望 明显的二叉排序树= =

[Usaco2009 Nov]找工作 这道题不错,吧点拆成2个,然后用路径的正权值作为花费,负权值作为收益,spfa,注意判负环

[Usaco2009 Open]Cow Digit Game又见数字游戏 递推,必胜态在于有一个必败态,必败态在于都是必胜态

[Usaco2009 Open]Cow Line 直线上的牛 直接模拟,用双端队列实现

[Usaco2009 Open]Hide and Seek 捉迷藏 spfa啦,然后统计一下就行啦~~

[Usaco2010 Dec]Apple Delivery spfa 然后计算距离啦

[Usaco2010 Dec]Treasure Chest 藏宝箱 dp f[i][j]表示距离为i开头为j的最大收益,f[i][j]=sum[j+i-1]-sum[j-1]-min(f[i][j],f[i][j+1]) 然后滚动数组优化

[Usaco2010 Feb]Chocolate Buying 贪心?(没看到题目= =)

[Usaco2010 Feb]Chocolate Giving spfa点1 然后就没了 = =

[USACO2011 Open]Corn Maze玉米迷宫 广搜= =

[Usaco2012 Nov]Clumsy Cows 记(为1,)为-1 从前往后算和,如果出现负数那么ans++,sum+=2;然后答案为ans+sum/2

[Usaco2014 Jan]Cross Country Skiing 二分答案,然后遍历,貌似递归会爆栈

[Usaco2014 Mar]Watering the Fields 又是最小生成树= =

完了,貌似一堆最短路,一堆二分,一堆dp,一堆搜索,一堆最小生成树,一堆贪心= =

BZOJ 1004: [HNOI2008]Cards(群论)

题目链接

好吧我就是蒟蒻根本没听说过群论(虽说听叉姐说几万年都不会考)

我也讲不太来,直接戳VFK大神的blog啦 = = http://vfleaking.blog.163.com/blog/static/17480763420119685112649/

然后在加上2001年的论文Pólya原理及其应用 应该能做了吧= =

反正数论题就是各种小心

CODE:

 

1023: [SHOI2008]cactus仙人掌图(DP+单调队列优化)

题目链接

这道题吗= =首先解决了我多年以来对仙人掌图的疑问,原来这种高大上的东西原来是这个啊= =

然后,看到这种题,首先必须的就是缩点= =

缩点完之后呢,变成在树上找最长路了= =直接树形dp了

那么那些环呢,就是一个环形dp了,可以先把它拆成一条链,然后注意到最长路径=max(f[i]+f[j]-dist(i,j))  拆成链的话dist(i,j)=i-j 然后就发现dist(i,j)有单调性,就可以用单调队列优化了= =

这样写就可以a了= =

ps1:今天发现有人给我留言了真开心QAQ 感觉自己写了这么久还是有人看到的QAQ 继续加油吧!!!

ps2:bzoj的808端口坏了现在上都得改网址真麻烦QAQ

ps3:刷了好久感觉没啥精神了这个月感觉刷不了多少了QAQ 所以众多STOI补番队的成员啊,这个月的占领头版计划就交给你们了QAQ

CODE: