@poorpool
2017-10-05T20:09:54.000000Z
字数 1372
阅读 1071
%%%zhw
维护单调数列
从右往左枚举
b[i]表示玫瑰
q[i]表示在单调数列中第i个位置是n个人中的哪个
for(int i=n;i>=1;i--){
while(r && s[r]<=h[i])r--;
b[q[r]]+=a[i];
s[++r]=h[i];
q[r]=i;
}
30:枚举吃或不吃
50:发现长方形一定卡着糖果。枚举上下左,求最小的右。把长方形扩大成正方形。
离散化:
int cmp(node i, node j){
return i.y<j.y;
}
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
t[i].x=i;
t[i].y=a[i];
}
sort(t+1,t+1+n,cmp);
for(int i=1;i<=n;i++){
if(t[i].y!=t[i-1]y)now++;
p[now]=a[t[i].x];
a[t[i].x]=now;
}
80:枚举完上下,求得左边为1的情况下右边是什么。
左边向右移,右边必定向右。
左至多移n次,右至多也n次。总共2n次。
n^3
100:n^2log n,常数大的n^2
注意到答案连续,即,x可行,则x+1也能覆盖c个糖果
x不可行,则x-1不可能覆盖c个
二分答案。
二分答案搞出个mid后,怎么判定?
枚举上边在哪,上边卡糖果,下边位置则固定,则知道那些糖果被夹在里头。O(n)
求左边为1的情况下右边是什么。
左边向右移,右边必定向右。
左至多移n次,右至多也n次。总共2n次。这个宽t至少是多少。
t>mid 不行
t<=mid 可以
要求两直线交。
画st图。
绿色值最小即为所求。
事实上,最小的绿色所在处必有交点。
可用反证法证明。
求所有交点,然后再求每只豹子在这个交点的那个时刻的位置。更新答案。n^3。60分。
100分:
转化为求上突起与下突起。
要保证,慢的先跑,快的后跑。如果一只慢又迟到,一只快又早到,这样的话,对于上突起保留后者,对于下突起保留前者。
直线按斜率排序。斜率高的一条会把斜率低的上突起变成自己的。f[i]表示了每个豹子保管的左端点。
下突起也是这个理。
上下两个指针,下突起拐点指针追上突起拐点指针,上突起拐点指针追下突起拐点指针。不断更新答案。
注意处理两个k相等的情况。
特判:
另:
绿线长必定先减后增,二分时刻。上突起斜率大于下突起时,往左,否则,往右。甚至,可以三分绿色。
算法简单,难在拓扑。
无向图,任意两点间均有一条边联通,即为团。极大团即为最大团。任意两点间均无一条边联通,即为独立点集。
图中无奇环(环中点的个数为奇数)。
顾名思义,在一个二分图中选择最多的边,使得没有任何一个点有连接它的两条边被选择到。
匈牙利算法。
n个奇数,写成二进制,只保留其中一个‘1’,使异或和最大。
n<=100,0< ai <2^31
3
5 5 3
101 101 11
001 100 10
111
7
二分图带权匹配。
(笔者糊了,但有大佬做出来了……太强了……)
最大权怎么做?km/网络流,据说匈牙利还不如