Algorithms&Data Structures

Codeforces Round #664集锦

准备Div.1和Div.2放在一起做个集锦,快要蓝桥杯了抱抱佛脚

A.Boboniu Likes to Color Balls

题目大意:给出三原色三种颜色的球,还有白色球,每次操作可以把三原色中的球各取一个变白,求是否能操作使这些球按一定顺序排列构成回文

Solution

球总数是奇数和偶数分开判断,是奇数则四种颜色仅有一种颜色是奇数就可以,偶数则所有颜色均为偶数就可以,我们可以发现每次操作改变一次奇偶性,所以最多进行两次操作即可判断

Code

B.Boboniu Plays Chess

题目大意:给出一个n*m的矩阵,每个矩阵的数互不相同,每次操作可以移动到当前行或者当前列的任一位置,给出起始位置,求矩阵每个数都经过一次的序列

Solution

既然可以在当前行或当前列任意跳,我们就直接把这行的跳完,行跳完跳列,直到行和列都被跳完时说明矩阵里的每一个位置都被跳过了,用数组来记录某行或者某列是否被跳完

Code

C.Boboniu and Bit Operations

题目大意:给出ab两个序列,对于1\leq i\leq n,选择一个j(1\leq j\leq m),令c[i]=a[i]\&b[j],使得c[1]|c[2]|c[3]|...|c[n]最小,求这个最小值

Solution

手玩了好久,还以为有什么规律,首先可以想到,如果a序列中的数某个二进制位为0的话,在进行与操作后还是为0,所以我们的任务是尽可能使二进制位为1的在与操作变为0,这样在或操作时才能尽可能使所得的数小,想了好久,以为是个非常nb的贪心,结果发现答案范围在[0,2^8)区间内,nm的数量级也为10^2,这才明白原来正解直接暴力枚举答案,然后暴力选择判断即可→_→

Code

D.Boboniu Chats with Du

题目大意:给出n个数,每天选择一个数,如果选的数大于m接下来的d天将不能再选,求选的所有数最大值

Solution

又是cf经典的思维题,很明显是个贪心,怎么才能更贪是这种题的精髓,我的思维过程在这里记录一下方便日后总结,首先想到将大于m的从大到小排序,小于等于m的从小到大排序,用一个大于m的就会有d个小于等于m的不能用,用前缀和辅助判断是否选择这个大于m的,这种情况只针对小于等于m的数足够多,而小于等于m的数较少的话,完全可以用小于等于m的数进行填充,在最后一个再填上大于m的数,这种情况也并不全面,例如我们能够通过计算得知最多能填充多少个大于m的数,那么我们在选择前面几个大于m的数的时候可以选择用用不到的大于m的数进行消耗,使得最后能够填充的小于等于m的数尽可能多,说了这么多其实还不够清晰,网上有个大神的思路非常清晰,假设我们需要x个大于m的数,那么需要占(x-1)*(d+1)+1个位置,所以我们只需要考虑这个条件是否满足即可,剩下n-(x-1)*(d+1)-1个位置就直接从大到小填充小于m的数即可,需要注意的是(x-1)*(d+1)会爆int,还有需要特判没有大于等于m的情况

Code

 

发表评论

邮箱地址不会被公开。 必填项已用*标注