@poorpool
2017-10-05T13:06:19.000000Z
字数 2394
阅读 1088
%%%zhw
a了好多人。
要考虑到)(
这种情况。
左往右扫,扫到)
就观察左边有无(
,有就抵消,无则变为(
。扫完后,右边一定剩下一堆左括号。把其中一半的(
变为)
。
剥离出模型。
当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;
主要操作:区间加,区间查询最大值。
可用线段树。
(笔者糊了)
或:不停地让上车,超载就踢掉终点最靠后的。
数据分级超良心的。
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]),还需要特判恰好改变一个数。
优化法:
把每个物品朴素拆开。
把每个物品拆成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])
连成了环。
拆链加倍。
要防止结果长度>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.
(笔者疯掉了,话都说不利索)
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!...
次大公因数=最大公因数/最小公质因数