HDU多校第一场

Posted on | In ,

补题进度：6/7(11)

遇事不决先打表 乱搞不会瞎贪心 没人过题搜论文

1001. Maximum Multiple

$$
x+y+z=n => x/n+y/n+z/n=1
设a=x/n,b=y/n,c=z/n (a<=b<=c)
则=>a<=1/3
$$
再枚举一下即可

1002. Balanced Sequence

题解

子序列！！！

预处理出所有字符串合法的()之后会.
先把每个字符串贪心匹配下，形成若干个形如 )))((( 的字符串,并分别记为二元组 （a,b），按照一定顺序排序就可以

Johnson流水线调度规则

51nod1205 流水线调度

和这个很相似，按照b-a的正负性不同分别排序

要将 $a<b$放到$a>=b$前面

  • a< b, 按照a从小到大排序
  • a>=b, 按照b从大到小排序

对b-a的正负性不同分别排序

  • $b>=a$ , 按照a从小到大排序
  • $ b< a$ , 按照b从大到小排序 
1
2
3
4
5
6
7
8
9
10
11
12
struct node{
    int a,b;
    friend bool operator < (node x, node y){
        if(x.a >= x.b &&  y.a<y.b)
            return false;
        if(x.a < x.b && y.a >= y.b)
            return true;
        if(x.a>=x.b && y.a>=y.b)
            return x.b>y.b;
        return x.a < y.a;
    }
}pa[maxn];

1003. Triangle Partition

签到

1004. Distinct Values

可以发现最优的一定是每个数都尽可能的小，双指针枚举，用set维护一下这个过程即可

1005. Maximum Weighted Matching

留坑

1006. Period Sequence

留坑

1007. Chiaki Sequence Revisited

遇事不决先打表
打出 $a_i$的表观察：

  • $a_i$是奇数：1次(除了1)
  • $a_i$是偶数： $2^k|i => k+1$次(最大的k)

有一个很神奇的规律

末尾是x(包括全部的x)的总共项数=
$$
2^0(1+2+…+x)+2^1(1+2+…+x/2)+2^2(1+2+..+x/4)+…+2^k(1+2+…+x/(2^k))
$$
所以二分$a_n$,等比数列求上面数列的和即可

注意二分出来的$a_n$可能取不到所有$a_n$，要用$a_n-1$算，再把余下的$a_n$的数量加上去

1008. RMQ Similar Sequence

RMQ+分治

待补

1009. Lyndon Substring

论文题再见

1010. Turn Off The Light

大模拟再见

1011. Time Zone

签到