用户工具

站点工具


2020-2021:teams:manespace:atcoder_aising_programming_contest_2020

AIsing Programming Contest 2020

A,B

日常考语法,略。

C

题意:给定一个函数$f(x,y,z)=x^2+y^2+z^2+xy+yz+xz(x,y,z≥1)$,求满足f的值等于1到n的x,y,z分别由多少组。

题解:数据很小,可以大致划分一个范围(小于$\lfloor\sqrt{n}\rfloor+1$),然后暴力枚举即可。

D

题意:定义$popcount(n)$为n的二进制表达中1的个数,设定一次操作为将n变成$n \% popcount(n)$,令把$n$变成0的操作个数为$f(n)$,给定一个长度小于等于$2*10^5$的二进制数,问分别将他每一位经行反转后,各自的到的新数的$f$值为多少?

题解:其实这题的最难的地方就在于处理一开始那个一次操作,之后的操作都可以存进$int$变量中,不难发现,不管是把1变成0,还是把0变成1都会对模数产生1影响,所以可以预处理出1的个数,假设为k,之后$O(n)$预处理出$2^m$模$k-1$和模$k+1$的结果,存入数组,之后累加即可,总复杂度$O(n\log{n})$。

E

题意:有一些物品,现已知第i个物品放在前$k_i$位置时产生的贡献为$l_i$,否则产生的贡献为$r_i$,问如何排布才能使总贡献取到最大?

题解:这题设计多条件限制最值。思路如下:首先可以将所有数分成两组,一组是满足l>r的,另一组是满足r>l的,显然第一组的物品尽量往前靠,后一组的物品尽量往后靠,其实两组通过划归可以归为一个问题,不妨考虑第一组,每个数都有基础贡献$r_i$,之后考虑$k_i$,k越小越要排前面,所以将第一组按照k的值排序,同时开一个小根堆维护l-r的值,遍历第一组的物品,一旦k的值小于堆的总量就插入,否则若k等于堆的总量,则比较l-r的值。这样最后将堆中的数加进答案即可。对于放后面的情况可以转化为前面的情况。总复杂度$O(n\log n)$

2020-2021/teams/manespace/atcoder_aising_programming_contest_2020.txt · 最后更改: 2020/07/15 16:24 由 iuiou