题目链接：http://codeforces.com/contest/1475/problem/D
题目大意为有n个app,每个app会占用ai的内存，以及具有bi的重要性。求卸载的app内存至少为m以上，同时重要性最小。
这道题第一眼看上去应该就是重要性为1的app的数量要尽可能多，同时重要性为2的app的数量要尽可能少。
第二步就是重要性为1且内存大的app数量要尽可能多，重要性为2且内存大的app数量要尽可能多。
为此，我们需要对重要性为1和2的内存进行降序排列。
先计算重要性为2的全部内存之和，并在此基础之上减去重要性2的内存加上重要性为1的内存，同时进行重要性的比较取最小值。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 const int INF = 0x3f3f3f3f; 6 const int N = 2e5 + 10; 7 8 void solve() 9 { 10 int n, m; 11 cin >> n >> m; 12 vector<int> a, b; 13 vector<int> v; 14 for (int i = 0; i < n; i++) { 15 int e; 16 cin >> e; 17 v.push_back(e); 18 } 19 for (int i = 0; i < n; i++) { 20 int e; 21 cin >> e; 22 if (e == 1) { 23 a.push_back(v[i]); 24 } 25 else { 26 b.push_back(v[i]); 27 } 28 } 29 sort(a.rbegin(), a.rend()); 30 sort(b.rbegin(), b.rend()); 31 ll sumb = accumulate(b.begin(), b.end(), 0ll); 32 ll suma = 0; 33 int r = b.size(); 34 int ans = INF; 35 for (int i = 0; i <= a.size(); i++) { 36 while (r > 0 && suma + sumb - b[r - 1] >= m) { 37 r--; 38 sumb -= b[r]; 39 } 40 if (suma + sumb >= m) { 41 ans = min(ans, 2 * r + i); 42 } 43 if (i != a.size()) { 44 suma += a[i]; 45 } 46 } 47 cout << (ans == INF ? -1 : ans) << endl; 48 } 49 50 int main() 51 { 52 int t; 53 cin >> t; 54 while (t--) { 55 solve(); 56 } 57 }
题目链接：http://codeforces.com/contest/1475/problem/E
题目大意：n个人，每个人都有ai个粉丝。现在要从中选出k个人使他们的粉丝数最多。求选的方案数。
很简单的一道题，只需要统计出粉丝数相同的有几个人，再按粉丝数从大到小排序，如果粉丝数相同的人的数量比k小，就遍历下一个粉丝数比它小的，同时k要减去该粉丝数相同的人数。如果比k大就粉丝数相同的人数里面选出k个人。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
int c[N][N];
void init()
{
for (int i = 0; i <= 1e3; i++) {
c[i][i] = 1;
c[i][0] = 1;
}
for (int i = 1; i <= 1e3; i++) {
for (int j = 1; j <= 1e3; j++) {
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
}
void solve()
{
int n, k;
cin >> n >> k;
map<int,int> m;
vector<int> v;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (!m[x]) {
v.push_back(x);
}
m[x]++;
}
//cout << v.size() << endl;
sort(v.rbegin(), v.rend());
ll ans = 1;
for (int i = 0; i < v.size(); i++) {
if (m[v[i]] < k) {
k -= m[v[i]];
}
else {
ans *= c[m[v[i]]][k] % mod;
break;
}
}
cout << ans << endl;
}
int main()
{
init();
int t;
cin >> t;
while (t--) {
solve();
}
}
题目链接：http://codeforces.com/contest/1475/problem/F
题目大意：给定两个01矩阵，问是否能从第一个矩阵变为第二个矩阵。操作为：把某一列的所有元素都与1异或或者把每一行都与1异或。因此只需要按列模拟一遍，再按行模拟一遍。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
void solve()
{
int n;
cin >> n;
string s = "";
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
char x;
cin >> x;
s += x;
}
}
char c = getchar();
string s1 = "";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
char x;
cin >> x;
s1 += x;
}
}
for (int i = 0; i < n; i++) {
if (s[i] != s1[i]) {
for (int j = i; j < n*n; j += n) {
if (s[j] == '0') {
s[j] = '1';
}
else {
s[j] = '0';
}
}
}
}
for (int i = n; i < n * n; i += n) {
if (s[i] != s1[i]) {
for (int j = i; j < i+n; j++) {
if (s[j] == '0') {
s[j] = '1';
}
else {
s[j] = '0';
}
}
}
}
if (s == s1) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
int main()
{
int t;
cin >> t;
while (t--) {
solve();
}
}
题目链接：http://codeforces.com/contest/1475/problem/G
题目大意，给n个数，求要使两两可以相除要移除的最小元素数量。其实就是求可以两两相除的最大元素个数。
这道题。。。一个sort排序卡了我半天，最后看题解只需要从1筛到2e5就可以。。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int a[N], dp[N];
void solve()
{
int n;
cin >> n;
memset(a, 0, sizeof(a));
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++) {
int x;
cin >> x;
a[x]++;
}
int ans = -INF;
for (int i = 1; i <N; i++) {
if (a[i]) {
dp[i] += a[i];
for (int j = i + i; j <= N; j += i) {
dp[j] = max(dp[i], dp[j]);
}
}
ans = max(dp[i], ans);
}
cout << n - ans << endl;
}
int main()
{
int t;
cin >> t;
while (t--) {
solve();
}
}