周赛 Round#3 题解

又不能放图片，又不能写学校，你让我怎么办啊！！

系列文章目录

1.周赛 Round#1
2.周赛 Round#2

前言

这是周赛第三轮。//涉及隐私原因，博文里不放题目，要看的去http://0241:101:610:801.22222

划分字符串	贪心&动态规划
组合线段	递推
美味沙拉
最大化运算式
汤姆猫与台球
小组长

T1 划分字符串 parse

本题考查：贪心&动态规划
通过简单地分析易得出结论：最优解一定只含1或2长度的字串，所以最好理解的方法就是贪心，首先默认长度是1，再通过与前一个的比较判断是否需要i++;只用两个字符串就行。

T2 组合线段 segment

这道题真的是水上加水，真不知道那些没A的怎么想的！！
——某BCS同学

因为线段不能动，所以直接算出某一纵轴上的线段，取最大值不就完了吗！！我还去厕所打了下草稿（这是真的别不信）。
题解上的递推式太复杂了，虽然可以O(1),但此题时间限制居然2000ms,硬是给我看蒙了，我还以为本题不是递推。
我找到了一个规律：
从3开始，i=2,每次a[i] = a[i-1] + i; 而每隔两次计算i++;简单一个O(n)循环就能实现。
说实话，评讲的时候方法太多了，我们来一个个的列举下。

1

就是上文说的方法，也是我考试时想到的，核心代码：

for(int i = 3; i <= n; i++){s+=j;if(i % 2 ==0) j++;}
cout << s;

2

与第一种方法本质是一样的，只不过推理方法不同：
算出某一纵轴上的线段，取最大值：

3

在2的方法下更进一步，用一个表格可以来表示2的轴上长度为几的线段格出现了几次，通过表格我们也可以得到规律从而地推完成。

4

其实3可以算作是一个等差数列的递推，我们再把单数和双数合并下就变成经典的两行代码那不是更好吗，利用单数和双数%2的性质，再利用c++/2只取整的“漏洞”即可。