D. Cleaning the Phone
题意
手机里有$n$个应用,每个应用有两个值分别是 占用的内存$a[i]$,点数$b[i]$。
现在要清理内存,至少为$m$,清除内存时点数也会被删除,求删除的最小点数。
如果无解输出$-1$。
思路
首先无解情况为,如果总和加起来都小于$m$的话即无解。
然要要注意看给的范围,点数的取值只有$1$和$2$。
所以将他们分成两个组排序,先把点数为$2$的全部删除,并维护一个$a[i]$的$sum$。
然后将里面的数一个一个拿回来从$1$里删除,维护$sum$的同时记录一下$ans$的最小值即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 200100;
int n ,m;
PII a[N];
void solve()
{
cin >> n >> m;
LL sum = 0;
for(int i = 0; i < n; i ++) cin >> a[i].x, sum += a[i].x;
for(int i = 0; i < n; i ++) cin >> a[i].y;
if(sum < m)
{
cout << "-1" << endl;
return;
}
vector<int> v1, v2;
for(int i = 0; i < n; i ++)
if(a[i].y == 1) v1.push_back(a[i].x);
else v2.push_back(a[i].x);
int n1 = v1.size(), n2 = v2.size();
sort(v1.rbegin(),v1.rend()), sort(v2.rbegin(), v2.rend());
sum = 0;
for(int i = 0; i < n2; i ++)
sum += v2[i];
int j = 0, ans = 1e9;
for(int i = n2; i >= 0; i--)
{
while(sum < m && j < n1)
{
sum += v1[j];
j ++;
}
if(sum >= m) ans = min(ans, i * 2 + j);
if(i) sum -= v2[i -1];
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
while(t --)
solve();
}
E. Advertising Agency
题意
给一个数组,有$n$个元素。在里面选$k$个数,使得$k$个数的$sum$最大。
问有多少种选法,答案取余$1e9+7$。
思路
题意挺简单明了,因为要$sum$最大,所以在排序(逆序)之后,一定是选择前$k$个数,所以只有第$k$大的数可以互相替换。
所以求一下第$k$大的数有多少个,并且需要选择几个。分别设为$a, b$。
答案即为$C^b_a$, 需要注意的是这里计算时除法取余要用逆元。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 200100, mod = 1e9 + 7;
int n ,k;
int a[N];
int qmi(int a, int b)
{
int ans = 1;
while(b)
{
if(b & 1) ans = ans * (LL)a % mod;
a = a * (LL)a % mod;
b >>= 1;
}
return ans;
}
int C(int a , int b)
{
LL x = 1;
LL y = 1;
for(int i = 1; i <= b; i ++)
{
x = x * (a - i + 1) % mod;
y = y * i % mod;
}
return x * (LL)qmi(y, mod - 2) % mod;
}
void solve()
{
cin >> n >> k;
for(int i = 0; i < n; i ++) cin >> a[i];
sort(a, a + n, greater<int>());
int cnt = 0, t = 0;
for(int i = 0; i < n; i ++)
if(a[i] == a[k - 1])
cnt ++;
else if(a[i] > a[k - 1])
t ++;
cout << C(cnt , k - t) << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
while(t --)
solve();
}
F. Unusual Matrix
题意
有$n\times n$的01矩阵,你可以让一列或者一行的元素全部异或$1$。
给你一个原矩阵,问能否变化成目标矩阵。
思路
这个和 acwing 95. 费解的开关 思路一样。
先看操作,全部异或$1$,就是元素全部改变。即:$0->1,1->0$。
然后我们先用列操作把第一行变得和目标矩阵相同。
然后对于后面的数就不需要进行列操作了,我们就只能选择 用行操作或这不用行操作。
即在一行里,只能全部相等,或者全部不相等。否则就是$NO$。
有个方便的操作可以简化代码:
字符‘0’和‘1’与1异或的话就能得到对方。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 1010, mod = 1e9 + 7;
int n;
char g[N][N], s[N][N];
bool st[N];
void solve()
{
cin >> n;
for(int i = 0; i < n; i ++) st[i] = 0;
for(int i = 0; i < n; i ++) cin >> g[i];
for(int i = 0; i < n; i ++) cin >> s[i];
for(int i = 0; i < n; i ++)
if(g[0][i] != s[0][i]) st[i] = 1;
for(int i = 1; i < n; i ++)
{
int t = (g[i][0] ^ st[0]) != s[i][0];
//cout << g[i][0] << ' ' << st[0] << ' ' << t << endl;
for(int j = 1; j < n; j ++)
{
// cout <<(g[i][j] ^ st[j] ^ t) << ' ';
if((g[i][j] ^ st[j] ^ t) != s[i][j])
{
cout << "NO" << endl;
return;
}
}
}
cout << "YES" << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
while(t --)
solve();
}
G. Strange Beauty
题意
给$n$个数,要求所有数满足:在其中任意选两个,其中一个是另一个的因子。
要删除一些数使得剩余的数满足条件。问最少删多少。
思路
DP,状态表示为 f[i]
:选到最大值为i时,最多能够有多少个数。
状态计算:i的所有倍数都可以存这个数,所以用当前点维护后面所有倍数的点。(类似埃及筛)
最后求出最大值则是可以剩余的最大数。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 200010, mod = 1e9 + 7;
int n, m;
int cnt[N];
int f[N]; // i为最大的数时,最长可以有多少个
void solve()
{
m = 0;
memset(cnt, 0, sizeof cnt);
memset(f, 0, sizeof f);
cin >> n;
for(int i = 0; i < n; i ++)
{
int x;
cin >> x;
cnt[x] ++;
m = max(m, x);
}
int ans = 0;
for(int i = 1; i <= m; i ++)
{
f[i] += cnt[i];
for(int j = i + i; j <= m; j += i)
f[j] = max(f[j], f[i]);
ans = max(ans, f[i]);
}
cout << n - ans <<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
while(t --)
solve();
}