Processing math: 100%

HDU多校第一场

补题进度:6/7(11)

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


1001. Maximum Multiple

x+y+z=n=>x/n+y/n+z/n=1a=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

遇事不决先打表
打出 ai的表观察:

  • ai是奇数:1次(除了1)
  • ai是偶数: 2k|i=>k+1次(最大的k)

有一个很神奇的规律

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

注意二分出来的an可能取不到所有an,要用an1算,再把余下的an的数量加上去


1008. RMQ Similar Sequence

RMQ+分治

待补


1009. Lyndon Substring

论文题再见


1010. Turn Off The Light

大模拟再见

1011. Time Zone

签到