Welcome to My Blog
IT | Microsoft | Computer Science | Daily | Robot | Student
西雅图-Day1 西雅图-Day1
呃,终于可以好好坐在酒店的床上写一篇博客了。也不知道这是第一天还是第二天,算了,加起来一块写吧。 报到北京时间早上8:30分抵达清华大学FIT(Future Internet Technology)楼报到,然后有一个简短的开营仪式。开营仪式
2019-02-09
集合型DP 集合型DP
集合型动态规划如何用一个数表示集合?bitset:用一个二进制数 $\cup$:s1 | s2$\cap$:s1 & s2 查询是否有第i位:(1<<i) & s 补集:((1<<n)-1) ^ s
2019-01-29
基环数DP 基环数DP
基环树DP:一个数加一条边骑士 题目 有n个骑士,每个骑士痛恨另一个骑士,每一个骑士拥有一个战斗力值。选出一个战斗力最强的军团,军团中没有骑士痛恨另一个骑士。 思路 $dp[u][0],dp[u][1]$分别表示u取或者v取,然后就可以
2019-01-29
期望DP 期望DP
麻球繁衍 题目 有k只麻球,每只活一天就会死亡。每只麻球临死前会生出新的麻球,生i只麻球的概率为Pi。求m天以后所有麻球都死亡的概率 思路 考虑一只麻球 $f(i)=P_0+P_1f(i-1)+P_2f^2(i-1)+……+P_{n-1
2019-01-29
数位DP 数位DP
数位DP不要62 分析 $dp[pos][state][limit]$ 表示当前枚举到第pos位,前几位的状态为state,前几位有无limit限制时符合条件的数字的个数 $$dp[pos][state][limit]=dp[pos-1]
2019-01-29
lowbit函数 lowbit函数
lowbit函数lowbit(10010)=10 lowbit(10010001)=1 lowbit(100100000)=100000 正数的原码、补码都是它自己 负数(-5为例): 原码:10000100 反码:111110110 补
2019-01-29
树形DP 树形DP
二叉苹果树 思路 $dp[u][j表示节点u留下j条边的最大价值,每一次决策只有三种情况:剪左子树,剪右子树,两个都不剪 剪左边:$dp[u][j]=dp[rson][j-1]+v[rson]$,同理,剪右边:$dp[u][j]=dp[ls
2019-01-29
高精度模板 高精度模板
高精度模板 define N 1e5 struct bign { int len; int v[N]; // 赋值 bign=bign bign operator = (char* s) {
2019-01-29
济南Day3 坐标型动态规划及背包 济南Day3 坐标型动态规划及背包
花店橱窗布置 思路 $f[i][j]$表示前i个花瓶前j个花束的最大美学价值 $f[i][j]=max(f[i-1][k],f[i][j])$ 当然还有另外一种思路(太强了!!!): 整张表都是向右下方走的,向下走加上数值,向右走无影响
2019-01-29
济南Day2 随记 济南Day2 随记
今天是第二天,收获颇丰。 也不知道什么时候我定了一个6:00的闹钟,基本上响了之后就没怎么睡觉了。早上6:50起床,洗漱之后穿好衣服就去餐厅吃饭。这个酒店的楼梯很玄学,我的房间旁边的小楼梯直达上课的会议室和餐厅后门,感觉像是Minecraf
2019-01-28
随机数基本使用方法 随机数基本使用方法
基本公式:要取得[a,b)的随机整数,使用(rand() % (b-a))+ a;要取得[a,b]的随机整数,使用(rand() % (b-a+1))+ a;要取得(a,b]的随机整数,使用(rand() % (b-a))+ a + 1;通
2019-01-28
济南 Day2 济南 Day2
动态规划最长公共子序列 $O(nlogn)$做法: 转换成最长不下降子序列 具体做法: 数组b[i]表示当前长度为i最长不下降子序列 如果$c_i \ge a[len]$ 那么就可以构造更长的序列,所以$len++, \ b[len]=c
2019-01-28
济南Day1 随记 济南Day1 随记
终于,还是决定出去闯一闯。不知为何,我似乎是厌倦了学校的生活,每一次上下课的铃声似乎在震颤着我的内心。 希望能有所收获。 第一次知道飞机票打起折来居然比高铁票还便宜。 然后买了早上十一点的飞机票。 很早就起来了,老爸把我送上机场大巴,我
2019-01-27
期末考试…… 期末考试……
该来的终究还是来了,欠下的终究是要还的同时祝大佬们冬令营集训顺利!
2019-01-20
线段树基础 线段树基础
线段树是一种数据结构,主要用来解决区间相关问题 基本思路我们把一个区间像归并排序一样构建一个完全二叉树,每一次修改或者查询区间都不需要全部修改,只需要改动上层包含这一子区间的区间即可
2019-01-12
STL(持续更新) STL(持续更新)
C++ STL 之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector, string, list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组,list封装了链表,map
2019-01-11
四子连棋 四子连棋
这是我到目前为止写过最长的代码之一…… 题意 4*4的棋盘,一共有三种属性:白棋,黑棋,空格(有且仅有两个),每一次可以移动一颗棋子,黑白棋交替进行,只能移到空格的地方。求达成四子连棋局面(横竖斜都算)所需的最小步数 分析 广搜,和八数
2019-01-11
2 / 3