清北学堂金秋营 day4

%%%zhw

题解

T1

维护单调数列
从右往左枚举
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;
}

T2

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 可以

T3

要求两直线交。
画st图。

绿色值最小即为所求。
事实上，最小的绿色所在处必有交点。
可用反证法证明。
求所有交点，然后再求每只豹子在这个交点的那个时刻的位置。更新答案。n^3。60分。

100分：

转化为求上突起与下突起。

要保证，慢的先跑，快的后跑。如果一只慢又迟到，一只快又早到，这样的话，对于上突起保留后者，对于下突起保留前者。
直线按斜率排序。斜率高的一条会把斜率低的上突起变成自己的。f[i]表示了每个豹子保管的左端点。
下突起也是这个理。

上下两个指针，下突起拐点指针追上突起拐点指针，上突起拐点指针追下突起拐点指针。不断更新答案。

注意处理两个k相等的情况。
特判：

另：
绿线长必定先减后增，二分时刻。上突起斜率大于下突起时，往左，否则，往右。甚至，可以三分绿色。

图论

算法简单，难在拓扑。

• 最短路
• 最小生成树
• 拓扑序
• 二分图最大匹配
• tarjan
• 并查集（冰茶几）
• 网络流：2-sat

最大团

无向图，任意两点间均有一条边联通，即为团。极大团即为最大团。任意两点间均无一条边联通，即为独立点集。

拓扑图上可dp

二分图的判别方法

图中无奇环（环中点的个数为奇数）。

二分图最大匹配

顾名思义，在一个二分图中选择最多的边，使得没有任何一个点有连接它的两条边被选择到。

匈牙利算法。

一些题目

2016集训队互测

n个奇数，写成二进制，只保留其中一个‘1’，使异或和最大。
n<=100,0< ai <2^31

3
5 5 3
101 101 11
001 100 10
111
7

二分图带权匹配。
（笔者糊了，但有大佬做出来了……太强了……）
最大权怎么做？km/网络流，据说匈牙利还不如