牛客小白月赛50

A.跳跃

签到题

需要注意的一个坑就是，题目没有特别说明，那么除法就应该不是整除的，所以把除法的分母乘过去即可

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include<unordered_map>
#include <unordered_set>

using namespace std;

typedef long long ll;
const int N = 100002;
const int MOD = 1e9 + 7;

int n, k;
int a[N];
int main() {
    
	scanf("%d %d", &n, &k);
	scanf("%d", &a[0]);
	int res = 0;
	for (int i = 1; i < n; i++) {
    
		scanf("%d", &a[i]);
		if ((a[i] > a[i - 1] * k) || (a[i] * k < a[i - 1]))
			res++;
	}
	printf("%d", res);
	return 0;
}

B.减法和除法

数学

要求最少的操作数，即每次操作之后得到的数更小，也就是操作之前比较 n / 2 和 n - x 的大小，选择小的那个操作

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
const int N = 1e4 + 5;
const int MOD = 1e9 + 7;

int main() {
    
	int n, x;
	scanf("%d %d", &n, &x);
	int res = 0;
	while (n > 0) {
    
		if (n / 2 < n - x) {
    
			n /= 2;
		} else {
    
			n -= x;
		}
		res++;
	}
	printf("%d", res);
	return 0;
}

C.减法和求余

数学

首先要分析出来，只有0 1 2 这三种情况，0 是全是0，不用操作了。1 是进行一次操作一，或者一次操作二
一次操作二：全是1，减一即可
一次操作一：同时对一个>=2的数取余，余数为0，说明，这一堆数字有非 1 的 最大公约数

剩下的都是操作两次的

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
// 只可能是 0 1 2 三种情况
int n;
int a[N];
int f0 = 1, f1 = 1; // 分别判断是否全是0，或者是否全是1 / 0

int gcd_(int a, int b) {
    
	return b == 0 ? a : gcd_(b, a % b);
}
int main() {
    
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
    
		scanf("%d", &a[i]);
		if (a[i] != 0) f0 = 0; // 并非全是0
		if (a[i] > 1) f1 = 0;
	}
	if (f0) puts("0");
	// 对于 1 步，那就是 要么全是 1 / 0，要么就是他们有相同的gcd
	else {
    
		int g = a[0];
		for (int i = 1; i < n; i++) {
    
			g = gcd_(g, a[i]); // 求 gcd
		}
		if (g > 1 || f1) puts("1");
		else puts("2");
	}
	return 0;
}

D.生日

计算贡献

总的方案数就是 2^n
总共分三种情况，第 i 天，与第 2i 和 2i + 1 天有关

第一种情况，确定了两个数字，还剩下 2^n - 2^种方案数
第二种情况，确定了三个数字，还剩下2^n - 3^种方案数

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include<unordered_map>
#include <unordered_set>

using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
const ll MOD = 1e9 + 7;

int n;
ll a[N];
ll p2[N]; // 预处理 2 ^n
int main() {
    
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
    
		scanf("%lld", &a[i]);
	}
	p2[0] = 1;
	for (int i = 1; i < n + 6; i++) {
    
		p2[i] = p2[i - 1] * 2ll % MOD;
	}
	ll res = 0;
	for (int i = 1; i <= n; i++) {
    
		if (n < 2 * i) {
    
			break;
		}
		else if (n < 2 * i + 1) {
    
			res = res + p2[n - 2] * (a[i] ^ a[2 * i]) % MOD;
			res %= MOD;
		} else {
    
			res = res + p2[n - 3] * ((a[i] ^ a[2 * i]) + (a[i] ^ a[2 * i + 1]) + (a[2 * i + 1] ^ a[2 * i]) + (a[i] ^ a[2 * i] ^ a[2 * i + 1])) % MOD;
			res %= MOD;
		}
	}
	printf("%lld", res);
	return 0;
}