1475D

题意：

有n个软件，每个软件都有一个内存空间和重要度，重要度只有1和2，现在至少要减少m的内存，问最少减少的重要度是多少；

思路：

每个软件可以有选和不选两种情况，但是数据范围太大没法直接做，注意到只有两种重要度，那么，可以枚举一种重要度的物品，然后得出另一种物品至少需要多少，使用二分+前缀和即可实现

题解：

#include <bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define lowbit(x) x&(-x)
#define INF 0x7fffffff
#define eb emplace_back
#define divUp(a,b) (a+b-1)/b
#define mkp(x,y) make_pair(x,y)
#define lb lower_bound
#define ub upper_bound
#define int long long
using namespace std;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);};
bool checkP2(int n) {return n > 0 and (n & (n - 1)) == 0;};
const int N = 200010;
int a[N];
int n, m;
vector<int> v1, v2;
int s1[N], s2[N];
int n1, n2;
void solve() {
	v1.clear(), v2.clear();
	cin >> n >> m;
	int x;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		cin>>x;
		if(x==1) v1.eb(a[i]);
		else v2.eb(a[i]);
	}
	sort(v1.begin(), v1.end(), greater<int>());
	sort(v2.begin(), v2.end(), greater<int>());
	s1[0] = s2[0] = 0;
	n1 = v1.size(), n2 = v2.size();
	for (int i = 0; i < n1; i++) {
		s1[i + 1] = s1[i] + v1[i];
	}
	for (int i = 0; i < n2; i++) {
		s2[i + 1] = s2[i] + v2[i];
	}
	int res = 1e9;
	for (int i = 0; i <= n1; i++) {
		int cur = m - s1[i];//剩余的从v2里面选；
		int p = lb(s2, s2 + 1 + n2, cur)-s2;
		if (p != n2 + 1)//除去没找到的情况；
			res = min(res, i + p * 2);
	}
	if(res==1e9) res=-1;
	cout<<res<<'\n';
}
signed main() {
	IOS;
	int _; cin >> _; while (_--) solve();
	return 0;
}

1475E

题意：

有n个数字，找到前k大个数字的和为s，问有多少种方法选取k个数和为s，（只要有一个不同就算一种方法）；

思路：

典型的排列组合问题，c[x1][y1]c[x2][y2]c[x3][y3]*....,其中x是前k个数中a得到个数，y是数组中所有a的个数，意思就是从y个数中选择x个数字，根据乘法原理，相乘就是答案

题解：

#include <bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define lowbit(x) x&(-x)
#define INF 0x7fffffff
#define eb emplace_back
#define divUp(a,b) (a+b-1)/b
#define mkp(x,y) make_pair(x,y)
#define lb lower_bound
#define ub upper_bound
#define int long long
using namespace std;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);};
bool checkP2(int n) {return n > 0 and (n & (n - 1)) == 0;};
const int N = 1010, mod = 1e9 + 7;
int a[N];
int c[N];
int d[N];
int f[N][N];
void init() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++) {
			if (!j) f[i][j] = 1;
			else f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % mod;
		}
	}
}
void solve() {
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) c[i] = 0, d[i] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		c[a[i]]++;
	}
	sort(a + 1, a + 1 + n, greater<int>());
	int sum = 0;
	for (int i = 1; i <= k; i++) {
		sum += a[i];
		d[a[i]]++;
	}
	int res = 1;
	for (int i = 1; i <= n; i++) {
		int x = c[i], y = d[i];
		res = (res * f[x][y]) % mod;
	}
	cout << res % mod << endl;
}
signed main() {
	IOS;
	init();
	int _; cin >> _; while (_--) solve();
	return 0;
}