清北学堂金秋营 day3

%%%zhw

题解

T1

a了好多人。
要考虑到)(这种情况。
左往右扫，扫到)就观察左边有无(，有就抵消，无则变为(。扫完后，右边一定剩下一堆左括号。把其中一半的(变为)。

T2

剥离出模型。

当m为1，会退化为经典问题。

有n个区间，找尽可能多的区间使得区间之间互不相交。
solve:按右端点从小到大排序，枚举每个区间，能取就取。

先按右端点排序。当然是能取就取。（倘若一个区间好好的不取了但是取下一个，突出了一截，必不更优）
维护一个f数组 f[i]表示i这个时刻 车上已经坐了几只怪兽了。

[X,Y] Z
for (int i=X; i<Y; i++)
  MAX=max(MAX,f[i]);
t=min(Z,M-MAX);
for (int i=X; i<Y; i++) f[i]+=t;
ans+=t
cout<<ans;

主要操作：区间加，区间查询最大值。
可用线段树。
（笔者糊了）
或：不停地让上车，超载就踢掉终点最靠后的。

T3

数据分级超良心的。
20：暴力八重循环；
40：求矩阵和用前缀和到O(1)，左上方，右下方，修改的，各n^2
60：修改的数已知(修改最小的或者不修改那个)，预处理矩阵最小值。
100：
前置知识：假如不要求修改，查询最大子矩阵，怎么做？
我们不枚举端点，枚举端点在哪一行。n2确定了上下界。对于每一列，要么同时被选择，要么同时不被选择。把他们当作点来看。即：有n个数，查询最大子段和。

for(int i=1; i<=n; i++)
    f[i] = max(f[i-1]+a[i],a[i];
    //O(n)
    //the ans is max{f[i]}

要求我们修改数，修改的一定是矩阵最小的。我们也用预备知识的方法，求出每一列min。
f[i][0]以i结尾并且没有数被修改过的最大和。
fi以i结尾并且有数被修改过的最大和 。
a[i]是第i列的和。

for (int i=1; i<=n; i++){
  f[i][0]=max(f[i-1][0]+a[i],a[i]);
  f[i][4]=max(f[i-1][5]+a[i],f[i-1][0]+a[i]-MIN[i]+P,a[i]-MIN[i]+P);
}

min是列最小值。
答案是max(f[?][0/1])，还需要特判恰好改变一个数。

动态规划

优化法：

• 1D1D经典优化（决策单调性，二分）
• 前缀和/最大值优化
• 斜率优化
• 矩阵乘法加速转移
• 数据结构
• 买新电脑

部分背包

把每个物品朴素拆开。
把每个物品拆成1，2，4，8，...剩余。
而单调队列优化可以做到O(nm)。

烽火传递

n非负整数，选若干数，每连续k数至少选出一个，要求和尽可能小。
即相邻两个被选出的数字距离<=k
dp[i]表示只考虑i～1，第i个是被选出的，最小和
dp[i]=min{dp[j]}+a[i],i-k<=j<=i-1

(K=3)
注意到求min，可联想到单调队列。

最大子段和

dp。
sum贪心。
维护前缀和s[i],

ans=max(ans,s[i]-minn)
minn=min(minn,s[i])

最大子段和plus

连成了环。
拆链加倍。
要防止结果长度>n

l～r，s[r]-s[l-1]
枚举r时
r-n<=l<=r
枚举的r不断增加，l区间右端点左端点只会增加。

装喷头

dp[i]，前i个位置都满足条件最少装多少。dp[j]，
1~j满足。2a<=i-j<=2b。
dp[i]=min{dp[j]}+1，2a<=i-j<=2b。
对于限制内的i[l,r)，dp[i]=+oo。
（interesting）

瑰丽华尔兹

即最多走多少布。
先考虑向右走
min energy = all time - max step
区间i结束时在(j,k)的maxStep：dp[i][j][k]=max(dp[i-1][j][k-x]+x),x<=t && no barrier，x指移动步数
复杂度O(T*n^3)
x<=t --> k>=k-x>=k-t, [k-t,k]
k的增加，k-t与k都会增加，单调队列

每次在插入进队列之前，把队列中所有元素+1，通过一个变量来维护（类似于noip2016的蚯蚓）。

为什么要+1呢？因为单调队列中的每一个数都远了一点，都要加1.
（笔者疯掉了，话都说不利索）

puzzling puzzle

n*n martix, exactly 2 棋子 per row/col，方案总数mod p?
dp[i][j][k]前i行，有j列放1子，有k列无子。
对于i+1:(0,0),(1,1),(0,1)
dp[i+1][j+2][k-2] dp[i+1][j-2][k]
dp[i+1][j][k-1]
转移是：dp[i+1][j+2][k-2]+=dp[i][j][k]*c(k,2)
dp[i+1][j-2][k]+=dp[i][j][k]*c(j,2)
dp[i+1][j][k-1]+=dp[i][j][k]*j*k

ans is dp[n][0][0]
n^3
事实上，容易算出k=n-(2*i-j)/2-j，干掉一维。
O(n)：
以块为单位
dp[i]表示i*i这个矩阵，满足条件的方案总数。
g[i]表示第一行第n个，第二行第n个一定放了的总数。
交换任意两行，原符合还符合，原不符还不符。
第一行和第二行其它子在同一列时g[i]+=dp[i-2]*(i-1)
else g[i]+=dp[i-1]*2
dp[i]=c(i,2)*g[i]
（笔者依然不会）

单调队列写法

出题人的邪恶脑洞

二分性质：只有log n个点会被访问。
二分结束后能得到限制，其中有x个点<=m(k>mid) 有y个点是>m。
x+y==log n
ans = A(m,x) * A(n-m,y) * (n-x-y)!
n好大的！那就预处理100000!,200000!...

次大公因数=最大公因数/最小公质因数

模意义背包