[数据结构与算法]南昌理工学院2021级新生入队考核（三） 题解

A — 波吉大冒险

若一个数为偶数 那么这个数的最后一个数必定为偶数。
从这里下手的话，可以得知

只要给出的数最后一个数为偶数，答案为 0
第一个数为偶数，只要翻转整个数 就可以得到偶数，答案为 1

若不满足以上两个条件，那么如果整个数字中若有偶数，那么只要翻转这个偶数，将这个偶数变到第一个位置上去，再翻转整个数，即可得到偶数，答案为 2（先要判断这个数中是否含有偶数）

核心代码为

	string str; //将数字换成字符串处理
    cin >> str;
    int len = str.size() - 1; //字符串默认下标从0开始，所以要长度-1
    if((str[len] - '0') % 2 == 0){ //判断最后一个数是否为0
        printf("0\n");
        return;
    }	
    if((str[0] - '0') % 2 == 0){ //判断第一个数是否为0
        printf("1\n");
        return;
    }

    int p = 0;
    for (int i = 0; i < len; i ++ ){ //判断字符串中是否含有偶数
        if((str[i] - '0') % 2 == 0){
            printf("2\n");
            return;
        }
    }
    printf("-1\n");

B — 波吉的聚会

首先，组成的队伍里面要有两个国家的其中一个人之一，所以答案最多为 n, m 里面最少的一个
其次，组成的队伍最多只能由 (n + m) / 4支
所以答案就取两种情况的最小值
min((n + m)) / 4,min(n, m))

C — 波吉买花花

首先，先将给定的数组排序（肯定从小价钱的花开始买，买的花才最多）， 那么只要

a[i] >= x && a[i] <= y 
m - a[i] >= 0

那么这束花就是可以买的

所以核心代码为

	int n, x, y, m;
    scanf("%d%d%d%d", &n, &,x, &y, &m);
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    sort(a + 1, a + 1 + n); //排序 ,没学过C++的可以用冒泡排序
    
    int ans = 0;
    for (int i = 1; i <= n; i ++ ){
        if(a[i] < x || a[i] > y) continue; //价格不符合
        if(m - a[i] < 0) break; //这束花买不起  后面更贵的花也买不起 
        m -= a[i]; //买
        ans ++;
    }
    printf("%d\n", ans);

D — 波吉不是笨蛋

水题，用个强制转换就可以

	char n;
    cin >> n;
    cout << (int)n << endl;

E && F

首先想到的是统计每个数的出现次数，用一个数组存就行，用这个思路可以过F，但是因为E题的数据范围开到了1e9， 那么是开不到这么大的数组的（内存不够） 所以就要换个思路。

我们可以将这个数组排序（更方便的统计出现次数），依次统计每个数的出现次数
例如我要统计排序后的数组 1 1 2 2 3 3 4 5 5
令con为统计次数,若a[i] != a[i - 1] 那么con重新定义为1
那么循环的过程con的值为 1 2 1 2 1 2 1 1 2
当i = 8的时候 要改变con的值 发现上一个con的值是奇数 就输出上一个数
所以我们每次再将con重新定义为1的时候 去查询上一个数字的出现次数是否为奇数，如果为奇数就输出
所以核心代码为

	sort (a + 1, a + 1 + n);
	
	int con = 1;//每个第一次出现的数都是第一个数
	for (int i = 2; i <= n; i ++ ){
		if(a[i] == a[i - 1]) con ++;
		else{
            if(con % 2 != 0){ //上一个数出现了奇次
				cout << a[i - 1] << endl;//输出上一个数
				return 0;
			}
            con = 1;//每个第一次出现的数都是第一个数
        } 
	}
	//如果到最后都没有输出数，因为题目保证了一定有解，那么最后一个数就是解
    cout << a[n] << endl;

G — 波吉的迷语

首先如果这个字符串不全是 0 或 1 那么就要对这个字符串进行拆分，拆到只剩 0 或者 1 为止 如果这个区间不全是0或者1，我们可以用递归去拆分区间，每次以中间为节点进行拆分

void solve(int l, int r) l, r 分别表示左端点和右端点

int mid = (l + r) / 2;
solve(l ,mid);
solve(mid + 1, r);

每次进入函数之前 都判断一下是否全为0或者1

	int p = 0; //判断是否区间内都为相同的数
	for (int i = l + 1; i <= r; i ++ ){
	    if(s[i] != s[i - 1]){
	        p = 1;
	        break;
	    }
	}
	if(p == 0){
	    if(s[l] == '0') printf("A");
        else printf("B");
	    return;
	}

所以完整核心代码为

void solve(int l, int r)
{
	int p = 0;
	for (int i = l + 1; i <= r; i ++ ){
	    if(s[i] != s[i - 1]){
	        p = 1;
	        break;
	    }
	}
	if(p == 0){
	    if(s[l] == '0') printf("A");
        else printf("B");
	    return;
	}
	
    printf("C");
    int mid = l + r >> 1;
 	solve(l, mid);
	solve(mid+ 1, r);
	return;
}

H — 诅咒之气

没啥好说的，直接上代码吧

	long long ans = 1, n, x;
	scanf("%lld%lld", &n, &x);
	for (int i = 1; i <= n; i ++ )
	{
		ans = ans + x * ans;
	}
	printf("%lld", ans);