欢迎24级新生

2020级新生赛

A 1的个数

lowbit操作

根据计算机负数表示的特点,我们将一个正整数和他的负数表示按位相与,可以截取这个正整数最后一个1后面的所有位。如一个数字原码是10001000,他的负数表示形式是补码,就是反码+1,反码是01110111,加一则是01111000,二者按位相与得到了1000,这种操作被称为lowbit操作。

所以每次减去lowbit得到的值,直到数字减到0。减的次数就是1的个数。

B 排队

前面有 a_i 个人,且总人数是 n ,所以后面就有 n-a_i-1 个人

C 卡牌游戏

按题意进行模拟即可

D 历史战绩

定义三个变量分别记录胜、平、负的次数即可

E 最强选手

先从前往后遍历整个数组,找到最高的评分。然后再从前往后遍历一遍数组,输出评分等于最高评分的人即可。

F 合法日期

先分别剥离出年、月、日。因为年份一定合法,所以我们只要判断平闰年,然后判断月、日是否合法即可

G 判断回文串

定义两个变量 i,j ,一开始让 i 指向字符串的开头,让 j 指向字符串的末尾。假设字符串为str,判断当前str[i]是否等于str[j],如果相等,就让 i++,j-- 。如果不相等,则代表该字符串不是回文串。如果当i>j时,str[i]与str[j]仍然相等,就代表该字符串为回文串

H 明日方舟

本题是一道标准的完全背包问题

f[i][j] 表示在前i种充值方案中选,且总价格不超过j的情况下能获得的最大源石数量。

v[i]表示第i种充值方案的充值金额,w[i]为第i种充值方案能获得的源石数量

f[i][j] = (f[i][j-v[i]]+w[i],f[i-1][j])

I 明日方舟2

因为首充优惠只有一次,且充值方案只有6种。所以我们可以使用二进制来枚举所有的首充方式。然后求出使用该种首充方式能得到的源石数量以及需要花费的预算。

然后问题就可以转换成上一题的完全背包模型了

J 遗憾

因为本题的数据范围很小,所以我们可以用一个数组cnt记录每个数是否已经出现,cnt[i]=0表示这个数没有出现,cnt[i]=1表示这个数已经出现了。然后从一到n依次遍历一遍,第一个没有出现过的数就是答案

K 花之祭

设最多能准备 x 朵花,那么一共需要 x * m 朵花,且同一种花色的花最多能用 x 次。设我们总共可以使用的花为tot

tot= \Sigma ^ {n} _ {i=1} min(a_i ,x)

当tot > x * m 时,即供大于求

当tot < x * m 时,即供小于求

所以我们可以通过二分 x 的值来求解本题答案

L a * b

因为x=a+b,y=a-b

所以(x+y)/2=a,x-a=b

M a和b

同上