2020百度C++/PHP笔试部分题解(9.14)

编程题前两题都很快写出来了，奈何不会期望，第三题无了。

第一题

题意

有n个吃的，每个吃的有对应的饱腹感，吃到m就饱了，问最少吃多少个就可以吃饱，分别吃哪几个。吃不饱输出-1。

分析

直接从大到小吃就行了。

参考代码

#include <cstdio>#include <iostream>#include <algorithm>using namespace std;int T, n, m;struct node { int id, val;};node a[1005]小学数学手抄报内容;bool cmp(node x, node y) { return x.val > y.val;}int main() { scanf("%d", &T);while(T--) { int sum = 0, cnt = 0;scanf("%d%d", &n, &m);for (int i=1; i<=n; ++i) { a[i].id = i;scanf("%d", &a[i].val);sum += a[i].val;}if《忆江南》古诗 (sum < m) { printf("-1\n");continue;}sort(a+1, a+1+n, cmp);sum = 0, cnt = 0;for (int i=1; i<=n; ++i) { sum += a[i].val;cnt++;if (sum >= m) { break;}}printf("%d\n", cnt);for (int i=1; i<=cnt; ++i) { printf("%d ", a[i].id);}printf("\n");}return 0;}

第二题

题意

给n个数，m次询问。每次有两种询问：
1 l r，询问区间[l,r]间的乘积为奇数的子序列个数。
2 l r，询问区间[l,r]间的乘积为偶数的子序列个数。爱都是对的 歌词

分析

只有奇数*奇数的乘积是奇数，所以询问1就是询问[l,r]间全是奇数的子序列的个数，设奇数个数为x，则子序列个数为 2 x − 1 2^{x} – 1 2x−1。
询问2就是所有子序列的个数减去奇数子序列的个数，即 ( 2 r − l + 1 − 1 ) − ( 2 x − 1 ) (2^{r-l+1} – 1) – (2^{x} – 1) (2r−l+1−坟地1)−(2x−1)

参考代码

#include <cstdio>#include <iostream>typedef long long ll;const ll MOD = 1e9 + 7;using namespace std;int n, m, x, l, r;int a[200005];ll t[200005];int main() { t[0] = 1LL; a[0] = 0;for (int i=1; i<=200000; ++i) { t[i] = (t[i-1] % MOD * 2LL) % MOD;}scanf("%d%d", &n, &m);for (int i=1; i<=n; ++i) { scanf("%d", &x);a[i] = a[i-1];if (x%2) a[i]++;}ll ans;for (int i=1; i<=m; ++i) { scanf("%d%d%d", &x, &l, &r);int num = a[r] - a[l-1];if (x == 1) { ans = (t[num] - 1LL + MOD) % MOD;} el { ans = (t[r-l+1] - t[num] + MOD) % MOD;}printf("%lld\n", ans % MOD);}return 0;}

本文地址：志愿服务的意义https://blog.csdn.net/Radium_1209/article/details/108588603