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

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

文章目录

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 造梦小孩


上一篇:Postgresql - 先group 然后根据不同group,用同一行 不同列展示


下一篇:Centos7源码升级内核至5.16.10