26.1.4

Problem - 3B - Codeforces

题目大意:

        有2 种船,分别大小为1、2,每个船有自己的价值,你能收大小和为v的船,最多价值多少

解析:

        直接通过性价比排序即可,注意的特殊点是当v=3时 虽然2只大小为1的船能大于一只大小为2的船所以,当v%2时可以直接先取最大的单个船然后再开始贪心即可各种情况判一下即可,可以用前缀和优化算法时间复杂度

Problem - C - Codeforces

题目大意:

        给定一个字符串,求最大成串的长度和个数

解析:

        观察可发现((()))和(()())是一样的所以可以直接将一个完整的()变为1其余变为0,查找最大连续1就行

Problem - 22D - Codeforces

题目大意:

        给定n个封条 分别是从L_i到R_i,要使每个封条最少贴一个钉子,问最少几个钉子,分别处于哪个位置

解析:

        一个比较基础的贪心,排序后不停的加入左端点然后一直更新最小右端点,直到左端点>右端点时将ans++就可以了然后舍弃之前的记录重新开始

Problem - 37C - Codeforces

题目大意:

                给定一个长度为n的数组,A_i代表要输出的字符串的长度,要输出n个01字符串保证每个字符串不是别的字符串的前缀

解析:

    这题目前有三种解析:     1.生成一个满二叉树,子树的个数为 个,直接每次从大到小每次选择一个01串的时候把他的所有前缀路径删了,然后继续计算,相对麻烦

    2.字典树解法,从小到大排序,然后每次走到一个子树的前一个父节点时走向另一个分叉

    3.用哈夫曼编码解题就行