qwq
清北学堂日记（1）
{
day one 蒙b了一天。 qaq。 上午将基础算法，划了一天的水，主要讲了些基础算法。
那么，讲一讲上午做了些什么吧 qwq。
题目讲解
{
first 讲了（假的）01背包，今天351突发奇想 相出了状压的方法 qwq
second 热身题 好数 就是到数位dp，如果我学了，肯定会（歪脸） 但是范围挺小的 直接暴力 不解释
third 立体图 由于题目太过毒瘤 大模拟 来的将 总之 先左再右，先下再上，先后再前 这样放立方体
至于旁边的点点怎么打 可一直接全覆盖成点 然后放立方体
forth 二分
{
1 排序 懒得讲 就是快排吗
2 求一个数组中的a【j】满足a【j-1】<a[【j】&&a【j+1】<a【j】
}
划重点 好题一个
{
有一个n*m的矩阵a[i][j]，满足a[i][j]<a[i][j+1],a[i][j]<a[i+1][j]。
问这个矩阵中是否存在数字k。
每次你可以询问一个位置的值，问最坏情况下最少需要询问几次。
O(n+m)
题解 ：
从右上角开始 如果所取值比所要值大就删去一行或列（单调性吗）
这样不但删 最终就能找出所要的值
操作如图
}
fifth 贪心
{
1（伪）石子合并 直接和成一堆 qwq
2 取数游戏 题目过水已隐藏
3 取区间游戏 蛮有意思的 其实是我贪心做太少 看题
有n个区间，第i个区间形如[li,ri]。
要求选择最多的区间，使得任意两个区间都互相不重叠。
n<=10W
sort (r)
MAX 表示已知区间右端点的最大值 MAX=0
for (i=1; i<=n; i++) if (l[i]>MAX) {ans++; MAX=r[i];}
题解 ：
把这些区间按有端点值从小到大排序 遇见能取的就取
理由 如果这个不去 那么取下一根 从这里看是等价的
但是 会影响下面的 明明可以取到的 但因为最右但向右了 就有可能取不到
请感性理解一下
4 打怪兽 也很好（都是我太菜了 别说了 qwq）
有n只怪兽，你可以随便选个顺序打过去，初始你有a滴血，打掉第i 个怪兽会扣掉你bi滴血，扣完后会掉落一个血瓶，
你可以回复ci点血，打完这n个怪兽后你才能去见BOSS。
当你血量<=0时你会挂掉。
问你能否见到BOSS，输出任意一种可行的方案。
n<=10W
题解：
两种怪兽：可以加血的， 以及会扣血
先打加血怪，再打扣血怪（不用解释）
对于加血怪来说：b从小到大打（感性理解）
对于扣血怪来说：c从大到小打（加血怪的逆过程）
}
sixth 分治
{
1 残缺方块问题 就是从中间切两刀 中间放一个三角
划重点 好啊 这题 但是我太菜了 我需要在修炼一下3
Cf goodbye 2018 F 题
一个人想从A点到B点，有n段区域需要经过。第i段区域长为ai。每一段区域可能是——陆地、海洋、岩浆。
它行走速度是5s/单位，游泳速度是3s/单位，飞行速度是1s/单位。
每行走/游一单位距离它能获得1点能量。
每飞行一单位需要消耗1点能量。 一开始没能量。
陆地可以走或飞，海洋可以游或飞，岩浆只能飞。
问至少多少时间能走到。
n,ai<=10W。 G表示陆地 R海洋 Y岩浆 GR 2 2 尽可能让G变成飞，之后再尽可能把游变成飞
G 3
7.5 s + 1.5s 9 s
GY 1 2 5s + 2.5s + 2.5s + 2s = 12s 可以做到只在一处陆地往回走，一处海洋往回游
GY 2 2
G….R….
R前岩浆距离总和a，除了岩浆的距离总和是b，让G所走的路增加a-b
R后（包括R）岩浆距离总和x，其它总和是y，R前余留的能量是z，则R游的路增加x-y-z
处理完往回的情况 GYGY 1 100 100 1
之后，ai就表示第i段路的距离了
f[i]表示第i段路结束后，还剩的能量。 始终要保证 f[i]都>=0
假如把第j段路的本来走的变成飞， f[j], f[j+1] ,.., f[n] - 一个常数
min{f[j],…,f[n]} >= 这个常数
从后往前枚举，再判断后缀最小值是否大于等于一个常数，来决定是否飞。
//尽可能把走的变成飞的 之后再尽可能把游的变成飞的
}
}
qwq 上午差不多就这么多题了
下午主要是考试
题目我会单独来讲
qwq