A. Nearest Interesting Number
水题
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+7;
bool check(int x) {
int sum = 0;
while (x) {
sum += x%10;
x /= 10;
}
if (sum % 4 == 0) return true;
else return false;
}
int main() {
int a; cin >> a;
for (int i = a; ; i++) {
if( check(i) ){
cout << i << endl;
break;
}
}
return 0;
}
B. Equalize Prices
题意：给定n个整数 a1,a2,…,an，和一个数k，让所有数都变成b, 且满足|ai - b| <= k。问b的最大值是多少。
题解：找到最大值和最小值，如果min和max的差值超过了2*k就不可能，否则ans = min+k。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+7;
int main() {
int T; cin >> T;
while (T--) {
int n, k; cin >> n >> k;
int minn = 0x3f3f3f3f, maxn = 0;
for (int i = 0; i < n; i++) {
int t; cin >> t;
if (t < minn) minn = t;
if (t > maxn) maxn = t;
}
int cha = maxn - minn;
if (cha > 2*k) cout << -1 << endl;
else cout << minn + k << endl;
}
return 0;
}
C
题意：给定总量k，每次可以消耗a或b（a>b），要消耗n次。如果n次后总量k<=0则输出-1，否则让a的消耗次数越多越好，问a的消耗次数的最大值。
题解：简单计算。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+7;
int main() {
int T; cin >> T;
while (T--) {
ll k, n , a, b;
cin >> k >> n >> a >> b;
if (n * b >= k) cout << -1 << endl;
else {
ll t = k - n*b - 1;
ll ans = min(t / (a - b), n);
cout << ans << endl;
}
}
return 0;
}
D. Candy Box (easy version)
题意：给n个糖果，ai表示第i个糖果的种类。问怎么取最多的糖果，且满足每种糖果取得个数都不相同。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int maxn = 2e5+100;
int dis[maxn];
int cmp(int a,int b)
{
return a>b;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int i,j;
for(i=0; i<=n; i++)
dis[i] = 0;
for(i=1; i<=n; i++)
{
int x;
scanf("%d",&x);
dis[x]++;
}
long long ans=0;
sort(dis+1,dis+n+1,cmp);
ans +=dis[1];
int pre=dis[1];
for(i=2;i<=n; i++)
{
if(dis[i]==0||pre==0)
break;
if(dis[i]>=pre)
{
if(pre==0)
break;
ans+=pre-1;
pre=pre-1;
}
else
{
ans+=dis[i];
pre=dis[i];
}
}
printf("%lld\n",ans);
}
return 0;
}
E. Subsequences (easy version)
题意：给定一个长度为n的字符串s和数字k。要从s中取出k个不同的子序列，每个子序列的花费为 n - 子序列的长度。问最小的花费。
题解：一开始用了dfs枚举子序列，加剪枝。应该是优化的不好，会超时。
看了题解发现是用了bfs，从最长的子序列开始枚举，每次删除一个字符，然后入队，同时用set去重。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+10;
const int INF = 0x3f3f3f3f;
int n, k;
string s;
set<string> se;
queue<string> que;
void bfs() {
que.push(s);
se.insert(s);
while (!que.empty()) {
string str = que.front();
que.pop();
for (int i = 0; i < str.size(); i++) {
string tmp = str;
tmp.erase(i, 1);
if (se.count(tmp) == 0 && se.size() + 1 <= k) {
se.insert(tmp);
que.push(tmp);
}
}
}
}
int main() {
cin >> n >> k;
cin >> s;
bfs();
if (se.size() < k) {
cout << -1 << endl;
return 0;
}
int ans = 0;
for (auto i : se) {
ans += n - i.size();
}
cout << ans << endl;
return 0;
}
G. Candy Box (hard version)
题意：在D题的基础上，给每个糖果加了一个0或1的标记。希望在取的糖果数尽量多的前提下，多取标记为1的糖果。
题解：优先队列维护即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
struct node {
int cnt, like;
bool operator < (const node &x) const {
if (cnt == x.cnt) return like < x.like;
else return cnt < x.cnt;
}
};
int c[N], l[N];
int main() {
int T; cin >> T;
while (T--) {
int n; scanf("%d", &n);
map<int, int> mp;
for (int i = 0; i < n; i++) {
int t1, t2; scanf("%d%d", &t1, &t2);
c[t1]++;
if (t2) l[t1]++;
mp[t1] = 1;
}
priority_queue<node> que;
for (auto it : mp) {
int i = it.first;
if (c[i]) {
node t;
t.cnt = c[i]; t.like = l[i];
que.push(t);
}
}
int maxn = que.top().cnt - 1;
int anscnt = que.top().cnt, anslike = que.top().like;
que.pop();
while(maxn > 0 && !que.empty()) {
node t = que.top(); que.pop();
if (t.cnt > maxn) {
t.cnt = maxn;
t.like = min(t.like, t.cnt);
que.push(t);
continue;
}
anscnt += t.cnt;
anslike += t.like;
maxn = t.cnt - 1;
}
cout << anscnt << ' ' << anslike << endl;
for (auto it : mp) {
int i = it.first;
c[i] = 0; l[i] = 0;
}
}
return 0;
}
