Day 5
考试题解
T1 blocks
签到成功。
100分做法：
假设有三个序号分别为(i),(i+1),(i+2)的三个积木，那么可以分为两种情况讨论：(i+1)先和(i)相等或者(i+2)先和(i+1)相等。为什么不能(i+2)直接和(i)相等呢？
假设(i+2)直接和(i)相等，那么可以分为两种情况：1.(i+1)超过了(i)，然后(i+2)和(i)相等。但是这样的话，(i+1)会先与(i)持平。由于两块积木一直以1的差距缩小，所以肯定会出现相等的情况。2.(i+1)还没超过(i+2)。那么也就是说，(i)在和(i+2)持平的时候，已经超过了(i+1)。同理，因为(i)和(i+1)每次高度也只缩小1，所以肯定会在(i)和(i+2)持平之前就已经和(i+1)持平了。综上所述：(i)和(i+2)持平时不可能是最优答案，那么答案就转化为了相邻两个积木的高度差（因为每次都缩短1，高度差即是时间）。将3块积木通过数学归纳法拓展，即可证明贪心结论正确。
考试时猜到了这个结论，但是没有严谨证明，直接口胡上然后拿暴力拍。拍过了之后知道结论没问题，所以其实考场上想到了结论可以直接写完拍，大不了拍出错再想别的。万一对了就赚大了。不用花费时间去证明。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
ll n,ans=1000000000;
ll h[100005];
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&h[i]);
}
for(int i=1;i<=n-1;i++){
ans=min(ans,h[i]-h[i+1]);
}
printf("%lld
",ans);
return 0;
}
T2 sort
80分做法：
优先队列，将前半个序列和后半个序列的值和下标分别存入优先队列，每次取出和插入，总时间复杂度为(O(nlogn))。考试时我就是这么写的，由于清北神机太快A了。。。
100分做法：
统计出前半部分排名在n/2名之后的和后一半排名在n/2之前的和相减即可。开longlong，时间复杂度O(n)。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long int ll;
ll n,a[500005],b[500005],sum1,sum2;
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
for(int i=1;i<=n/2;i++){
if(a[i]>b[n/2]){
sum1+=i;
}
}
for(int j=n/2+1;j<=n;j++){
if(a[j]<=b[n/2]){
sum2+=j;
}
}
printf("%lld
",sum2-sum1);
return 0;
}
T1和T2代码真的短，出题人好评
T3 string
30分做法：
指数级大爆搜。（我考试时就是这么打的，但是好像爆搜都打错了，全(TLE)了，30分白给）
60分做法：
区间(dp)
100分做法：
字典树：
T4 dinner
40分做法：
每次输入一段区间就将区间内的数全部标记为1，如果将两个存在矛盾的人都标记为了1，那么说明存在矛盾，否则则没有，时间复杂度为$O(
80分做法：
假设(i)和(j)有矛盾，那么使用线段树维护与j有矛盾的最靠右的端点，然后每次判断一下
100分做法：
1.压位
2.40分+80分做法
数据结构
一般可得部分分。
优先队列
中位数
用两个优先队列维护，一个维护前一半，一个维护后一半。
线段树
支持单点修改，区间修改，单点查询，区间查询
树状数组
需要区间可合并并满足区间减法，用([1,r]-[1,l])得到([l,r])之间的答案。
ST算法
可交区间的合并。
Hotel
（好像做过）。用线段树维护左子树右端点向左的长度，维护右子树左端点向右的长度。
动态联通块
？？？？？？？？？？？？？？？
Atlantis
给出(n)个矩形，求矩形的面积并。
扫描线法：
https://www.cnblogs.com/scau20110726/archive/2013/03/21/2972808.html
也可以用标记永久化来实现
思考题：
？？？？？？？？？？？？？？？？？？？？？？
Mishka and Interesting sum
？？？？？？？？？？？？？？？？？？
莫队算法是什么？
Present
最小值最大问题做法一般都是二分答案。
如果一盆花
对(A)数组进行差分得到(B)数组，(A)数组一段加上一个数，就相当于(B)数组中两个端点加上这个数。求前缀和就可以得到原数列。
hash表
映射的思想，与离散化类似。一般采用变为一个整数或者(p)进制然后对质数取%的方式，用(vector)存储较多，模数在10^6左右。
一般用来判重。
字符串HASH
(p)要大于字符串长度大小，双模数，一般值相同就大概率是相同的字符串。跟(map)类似，但时间复杂度更低。（https://www.cnblogs.com/zyf0163/p/4806951.html
https://blog.csdn.net/cindy_zhong/article/details/10465263
）
好处：可以代替很多字符串算法
？
如何用字符串(Hash)求最长连续回文串（(manacher)算法）
二分答案，从左到右枚举中心点，还要分奇偶两种情况讨论。
单调栈
栈内元素有单调性，一般作为工具在预处理数据的时候使用。
例题
决策单调性
方法：用栈来维护数据，由于决策单调性，新决策肯定由老决策转移而来，配合二分查找。如果新决策更优，那么全额抛弃老决策，因为它们不可能更优。反之，则从老决策中二分查找，找到最优决策，然后新决策进栈。
玩具装箱
写出(n^2)转移方程，仔细思考（打表）发现结果有单调性，所以使用单调栈优化。
Arr
假设选了所有(a)中的数，然后没有的数在不、中的第一次出现的位置是(x)，在(c)中第一次出现的位置是(y)，则有坐标(（x，y）)。
？？？？？？？？？？？？？？？？？？？？？？？
分块
两种暴力相结合，从序列的第一个元素起，每连续(S)个元素组成一个块，总共分成(n/S)个块。
基本题
暴力1：维护前缀和，每次修改暴力(O(n))修改前缀和，然后(O(1))查询
暴力2：写出前缀和，然后用数组记录下每一次修改，这样修改是(O(1))，但是查询是(O(m))
中和两种方法：