2022牛客寒假算法基础集训营5

文章目录

• • A 疫苗小孩
  • B 乒乓小孩
  • C 战棋小孩
  • D 数位小孩
  • E 复苏小孩
  • F 飞车小孩
  • G 163小孩
  • H 一六三小孩
  • I 兔崽小孩
  • J 三国小孩
  • K 造梦小孩

A 疫苗小孩

没读懂不想补

B 乒乓小孩

C 战棋小孩

D 数位小孩

题意： 给定 [l, r]， 求区间内多少个数满足：

1. 每相邻两个数位和为素数
2. 至少一个数位为1
3. 没有前导0

思路： 见代码

const int N = 1e7 + 10;
int ans[N], p[20], l, r, cnt;

void dfs(int x, int f) {
	if(x > r) return ;
	if(f) ans[cnt++] = x;
	int pre = x % 10;
	for (int i = 0; i < 10; i++) if(p[pre + i]) dfs(x * 10 + i, f | (i == 1));
} 

void solve() {
	cin >> l >> r;
	p[2] = p[3] = p[5] = p[7] = p[11] = p[13] = p[17] = 1;
	for (int i = 1; i < 10; i++) dfs(i, i == 1);
	int res = 0;
	for (int i = 0; i < cnt; i++) if(ans[i] >= l) res ++;
	cout << res << endl;
}

E 复苏小孩

F 飞车小孩

G 163小孩

签到

cout << 18395 << endl;

H 一六三小孩

I 兔崽小孩

题意： 找出时间间隔大于k的段数，问每段除去k之和能否大于p。

思路：
	1. 前缀和 + 二分

void solve() {
    int n, m; cin >> n >> m;
    vi a, b;
    int last = -1;
    // 求出间隔，并排序
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        if(i) a.pb(x - last);
        last = x;
    }
    sort(all(a));
    b.resize(a.sz);
    // b是前缀数组
    for (int i = 0; i < a.sz; i++) {
        if(i) b[i] = b[i - 1] + a[i];
        else b[i] = a[i];
    }
    while(m--) {
        int k, p; cin >> k >> p;
        int idx = lb(a, k);
        int tmp = 0;
        if(idx >= 1) tmp = b[idx - 1]; // 这里tmp代替是偷懒了差分数组的写法
        if(b[b.sz - 1] - tmp - (b.sz - idx) * k >= p) puts("Yes");
        else puts("No");
    }
}

J 三国小孩

签到，随便蒙的

void solve() {
	int n, m, k; cin >> n >> m >> k;
    puts(n + m > k ? "YES" : "NO");
}

K 造梦小孩