A. Problemsolving Log
签到题,对于给出的字符串,用数组记录每个字母出现的次数,然后遍历一边记录数组,如果对应的字母出现次数大于它的位次,则说明该字母对应的题目被解出来了,最后输出解题数量即可
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;
}
B. Preparing for the Contest
简单排序,要有k个升序的数,则前面排1 ~ k即可,后面从n ~ k+1降序排列
void solve()
{
int n,k;
cin >> n >> k;
int i;
for(i=1;i<=k;i++)
{
cout << i << " ";
}
for(int j=n;j>=k+1;j--)
{
cout << j << " ";
}
cout << endl;
}
C. Quests
贪心+暴力题,首先预处理出a的前缀和maxa,并且维护一个maxb[i],表示b[i]前i个数中的最大值,然后从1~n遍历,每一次获得的经验应该是maxa[i] + (k-i)*maxb[i],然后取最大值即可,记得处理一下边界情况
- if(i > k) break;
- (k - i >= 0 ? k - i : 0)
#define int long long
const int N = 2e5 + 10;
int a[N], b[N];
int maxa[N], maxb[N];
void solve()
{
int n, k;
int mmax = 0;
cin >> n >> k;
maxa[0] = maxb[0] = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
maxa[i] = maxa[i - 1] + a[i];
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
maxb[i] = max(maxb[i - 1], b[i]);
}
for (int i = 1; i <= n; i++)
{
if(i > k) break;
int tmp = maxa[i] + maxb[i] * (k - i >= 0 ? k - i : 0);
mmax = max(mmax, tmp);
}
cout << mmax << endl;
}
D. Three Activities
无脑暴力打表,记得关闭io流同步哦,不然会TLE
PII a[N],b[N],c[N];
void solve()
{
int n;
cin >> n;
for(int i=0;i<n;i++)
{
cin >> a[i].first;
a[i].second = i;
}
for(int i=0;i<n;i++)
{
cin >> b[i].first;
b[i].second = i;
}
for(int i=0;i<n;i++)
{
cin >> c[i].first;
c[i].second = i;
}
sort(a,a+n);
sort(b,b+n);
sort(c,c+n);
int max1 = a[n-1].first; //a b c
for(int i=n-1;i>=0;i--)
{
if(b[i].second!=a[n-1].second)
{
max1 += b[i].first;
for(int j = n-1;j>=0;j--)
{
if(c[j].second!=a[n-1].second && c[j].second!= b[i].second)
{
max1 += c[j].first;
break;
}
}
break;
}
}
int max2 = b[n-1].first; // b a c
for(int i=n-1;i>=0;i--)
{
if(a[i].second!=b[n-1].second)
{
max2 += a[i].first;
for(int j = n-1;j>=0;j--)
{
if(c[j].second!=b[n-1].second && c[j].second!= a[i].second)
{
max2 += c[j].first;
break;
}
}
break;
}
}
int max3 = c[n-1].first; //c a b
for(int i=n-1;i>=0;i--)
{
if(a[i].second!=c[n-1].second)
{
max3 += a[i].first;
for(int j = n-1;j>=0;j--)
{
if(b[j].second!=c[n-1].second && b[j].second!= a[i].second)
{
max3 += b[j].first;
break;
}
}
break;
}
}
int max4 = a[n-1].first; //a c b
for(int i=n-1;i>=0;i--)
{
if(c[i].second!=a[n-1].second)
{
max4 += c[i].first;
for(int j = n-1;j>=0;j--)
{
if(b[j].second!=a[n-1].second && b[j].second!= c[i].second)
{
max4 += b[j].first;
break;
}
}
break;
}
}
int max5 = b[n-1].first; //b c a
for(int i=n-1;i>=0;i--)
{
if(c[i].second!=b[n-1].second)
{
max5 += c[i].first;
for(int j = n-1;j>=0;j--)
{
if(a[j].second!=b[n-1].second && a[j].second!= c[i].second)
{
max5 += a[j].first;
break;
}
}
break;
}
}
int max6 = c[n-1].first; //c b a
for(int i=n-1;i>=0;i--)
{
if(b[i].second!=c[n-1].second)
{
max6 += b[i].first;
for(int j = n-1;j>=0;j--)
{
if(a[j].second!=c[n-1].second && a[j].second!= b[i].second)
{
max6 += a[j].first;
break;
}
}
break;
}
}
cout << max({max1,max2,max3,max4,max5,max6}) << endl;
}
E1&&E2 Game with Marbles
只要先按照a+b排序,然后模拟过程即可
int a[N],b[N];
PII c[N];
void solve()
{
int n,sum = 0;
cin >> n;
for(int i=0;i<n;i++)
{
cin >> a[i];
}
for(int i=0;i<n;i++)
{
cin >> b[i];
}
for(int i=0;i<n;i++)
{
c[i].first = a[i] + b[i];
c[i].second = i;
}
sort(c,c+n,[&](PII _1,PII _2){return _1.first > _2.first;});
for(int i=0;i<n;i++)
{
if(i&1)
{
a[c[i].second] = 0;
b[c[i].second] -= 1;
}
else
{
a[c[i].second] -= 1;
b[c[i].second] = 0;
}
}
for(int i=0;i<n;i++)
{
if(a[i]) sum+=a[i];
else sum-=b[i];
}
cout << sum << endl;
}