我要评论编程题前两题都很快写出来了，奈何不会期望，第三题无了。
第一题
题意
有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;
} else {
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
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论