签到题,对于给出的字符串,记录每个字母出现的次数,然后遍历一遍,如果对应的字母出现的次数大于它的位次,则说明该题被解出来了,最后输出解题数量即可
点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
const int N = 2*1e5 + 10;
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
int st[27] = { 0 };
int count = 0;
for (int i = 0; i < s.size(); i++)
{
st[s[i] - 'A' + 1]++;
}
for (int i = 1; i < 27; i++)
{
if (st[i] >= i) count++;
}
cout << count << endl;
}
int main() {
int t;
cin >> t;
while (t--)
solve();
return 0;
}
排序问题,兴奋 \(k\) 次,即前 \(1-k\) 按照升序排列,剩下的按照降序排序即可
点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) { //最大公约数
while (y ^= x ^= y ^= x %= y);
return x;
}
ll lcm(ll x, ll y) { //最小公倍数
return x * y / gcd(x, y);
}
void solve() {
int x, k;
cin >> x >> k;
int no = 0;
for (int i = 1; i<=x; i++)
{
if (k != 0)
cout << i << " ";
else
{
no = i;
break;
}
k--;
}
for (int i = x; i >= no; i--)
{
cout << i << " ";
}
cout << endl;
}
int main() {
int t;
cin >> t;
while (t--)
solve();
return 0;
}
暴力贪心,先用前缀和预处理数组 \(a\) ,之后对于数组 \(b\) ,用一个数组 \(d[i]\) 表示前 \(i\) 个中最大的 \(b\) ,最后遍历一遍, \(ans\) 取最大的 \(c[i] + (y-i)\times d[i]\)
点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) { //最大公约数
while (y ^= x ^= y ^= x %= y);
return x;
}
ll lcm(ll x, ll y) { //最小公倍数
return x * y / gcd(x, y);
}
void solve() {
ll x, y;
cin >> x >> y;
vector<ll>a(x+1);
vector<ll>b(x+1);
vector<ll>c(x + 1);
vector<ll>d(x + 1);
d[0] = 0;
c[0] = 0;
ll ans = 0;
for (int i = 1; i <=x; i++)
{
cin >> a[i];
c[i] = a[i] + c[i - 1];//前缀和
// cout << c[i] <<" ";
}
for (int i = 1; i <=x; i++)
{
cin >> b[i];
d[i] = max(d[i - 1], b[i]);//最大
}
for (int i = 1; i <=min(x,y); i++)
{
ll sum = c[i] + (y - i) * d[i];
//cout << sum << " ";
ans = max(ans, sum);
}
cout << ans << endl;
}
int main() {
int t;
cin >> t;
while (t--)
solve();
return 0;
}
暴力打表,先将每一个活动都排序(找出最多人数的3天),然后这3天互相排列组合,去除天数相同的,剩下的找最大值即是答案
点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll gcd(ll x, ll y) { //最大公约数
while (y ^= x ^= y ^= x %= y);
return x;
}
ll lcm(ll x, ll y) { //最小公倍数
return x * y / gcd(x, y);
}
struct no {
ll num;
ll day;
}a[N],b[N],c[N];
bool cmp(no x, no y)
{
return x.num > y.num;
}
void solve() {
ll x;
cin >> x;
for (int i = 0; i < x; i++)
{
cin >> a[i].num;
a[i].day = i;
}
for (int i = 0; i < x; i++)
{
cin >> b[i].num;
b[i].day = i;
}
for (int i = 0; i < x; i++)
{
cin >> c[i].num;
c[i].day = i;
}
sort(a, a + x, cmp);
sort(b, b + x, cmp);
sort(c, c + x, cmp);//由大到小排序
ll ans = 0;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
for (int k = 0; k < 3; k++)
{
if (a[i].day != b[j].day && a[i].day != c[k].day && b[j].day != c[k].day)
ans = max(a[i].num + b[j].num + c[k].num, ans);
}
}
}
cout << ans << endl;
}
int main() {
int t;
cin >> t;
while (t--)
solve();
return 0;
}
贪心排序问题,这一题 \(easy\) 和 \(hard\) 差别不大, \(easy\) 应该暴力模拟可以过。计算每一组的权值, \(Alice\) (简称 \(A\) ), \(Bob\) (简称 \(B\) ) 对于 \(A\) 来说,选择的一组所获得的权值是 \(a_i+b_i-1\) (消除 \(b_i\) 等于加 \(b_i\) 与 \(B\) 拉开了 \(b_i\) 的差距且保留了自己的剩余的 \(a_i-1\) ,因此是 \(a_i+b_i-1\) );同理,对于 \(B\) 来说,也是这样,因此无论是 \(A\) 操作时还是 \(B\) 操作时,所选择的都是 \(a_i+b_i\) 最大值那一组 (每一组的权值都有 -1 因此可以仅比较 \(a_i+b_i\)) , 使用结构体存储每一组石子的数量和和组号,对石子数量进行排序,之后由大到小进行模拟即可。
点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll gcd(ll x, ll y)
{ //最大公约数
while (y ^= x ^= y ^= x %= y);
return x;
}
ll lcm(ll x, ll y) { //最小公倍数
return x * y / gcd(x, y);
}
struct non {
ll num;
ll step;
}v[10];
bool cmp(non x, non y) {
return x.num < y.num;
}
void solve() {
ll x;
cin >> x;
vector<ll>a(x + 1);
vector<ll>b(x + 1);
// vector<ll>v(x + 1);
for (int i = 0; i < x; i++)
{
cin >> a[i];
}
for (int i = 0; i < x; i++)
{
cin >> b[i];
}
for (int i = 0; i < x; i++)
{
v[i].num = a[i] + b[i] - 1;
v[i].step = i;
}
sort(v, v + x,cmp);
//for (int i = 0; i < x; i++)
//{
// cout << v[i].num << " ";
//}
ll sum = 0;
int j = 1;
if (x % 2 == 0)
{
for (int i = x-1; i>=0; i--)
{
//cout << v[i] << " ";
if (j == 1)
{
sum += a[v[i].step] - 1;
}
else
sum -= b[v[i].step] - 1;
j *= -1;
}
}
else
{
for (int i = x - 1; i >= 0; i--)
{
if (i ==0)
{
sum += a[v[i].step] - 1;
break;
}
else
{
if (j == 1)
{
sum += a[v[i].step] - 1;
}
else
sum -= b[v[i].step] - 1;
}
j *= -1;
}
}
cout << sum << endl;
}
int main() {
int t;
cin >> t;
while (t--)
solve();
return 0;
}