1.吃饭吃饱 大到小排贪心,AC
#include <bits/stdc++.h> using namespace std; int main() { using P = pair<int,int>; int T; cin >> T; while (T--) { int n,m; cin >> n >> m; vector<P> vec; int res = 0; for (int i = 1; i <= n; i++) { int v; cin >> v; vec.push_back({v,i}); } vector<int> r; sort(vec.begin(),vec.end(),[](P& x, P& y){return x.first > y.first;}); for (int i = 0; i < n; i++) { res += vec[i].first; r.push_back(vec[i].second); if (res >= m) break; } if (res >= m) { cout << r.size() << endl; for (auto v : r) { cout << v << " ";} cout << endl; } else cout << -1<<endl; } }2. 区间内乘积为奇数或者偶数的个数,通过50%,猜想可能是应为区间内没有去重
求出所求区间奇数的个数n和偶数个数m, 如果求奇数个数则结果为 2^n-1,如果为偶数的个数则结果为(2^m-1)*2^n
#include <bits/stdc++.h> using namespace std; int main() { int n,m; cin >> n >> m; vector<int> vec(n+1,0); for (int i = 1; i <= n; i++){ int v; cin >> v; v %= 2; vec[i] = vec[i-1] + v; } int odd; int ou; int lr , l, r; long long res; while (m--) { cin >> lr >> l >> r; odd = vec[r] - vec[l-1]; ou = r-l+1-odd; res = 1; while(odd--) res = (res<<1)%1000000007; if (lr == 1){ res--; } else { long long t = 1; while(ou--) { t = (t<<1)%1000000007; } res = res*(t-1)%1000000007; } cout << res <<endl; } }
3. 求期望,不会
全部评论
(2) 回帖