A
题意
给你一些书，你可以将其分为两堆，只能从每一堆中选择书籍编号最大的书，求最大页数和。
方法
最后一本书必选，我们只需要选择从剩下的书中选择最大的就可以了。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
int maxn=0;
int tmp=0;
for(int i=0;i<n;i++)
{
int x; cin>>x;
if(i<n-1) maxn=max(maxn,x);
if(i==n-1) tmp=x;
}
cout<<tmp+maxn<<"\n";
}
int main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
|
B
题意
有若干块饼，最初价格都是\(a\)，可以选择若干块\(k\)改变价格：满足\(b-i+1\)，其中\(1\leq k \le min(n,b)\)，求利润最大。
方法
注意分类讨论：
- \(b<a\)，直接不选。
- \(b>a\)：需要讨论一下，可能会全选，也可能是选择一部分，剩下按照\(a\)出售。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
ll n,a,b; cin>>n>>a>>b;
ll i=b-a+1;
ll ans=0;
if(b>a)
{
if(i>n)
{
i=n;
ans=1ll*(b+b-i+1)*i/2;
}
else ans=1ll*(b+a)*i/2+(n-i)*a;
}
else ans=1ll*n*a;
cout<<ans<<"\n";
}
int main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
|
C
题意
判断能否找出一个\(n\)的全排列，满足\(|p_1-1|+|p_2-2|+······+|p_n-n|=k\)，如果存在还需要可能的全排列。
方法
其实不难想到先按照从小到达的顺序排列，然后每次交换当前\(a_i\)与可以到达的最大值\(a_j\)，并且更新\(k\)，如果\(k<2*(a_j-a_i)\)，那么直接交换\(a_i\)和\(a_{i+k}\)，这两个肯定都未进行交换，\(k\)更新为0。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
ll k; cin>>k;
std::vector<int> p(n+1,0);
if(k&1)
{
cout<<"NO\n";
return;
}
else
{
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=n/2;i++)
{
if(k>=2*(n-i+1-i))
{
swap(p[i],p[n+1-i]);
k-=2*(n-i+1-i);
if(k==0) break;
}
else
{
k/=2;
swap(p[i],p[i+k]);
k=0;
}
}
}
if(k) cout<<"NO\n";
else
{
cout<<"YES\n";
for(int i=1;i<=n;i++) cout<<p[i]<<" \n"[i==n];
}
}
int main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
|
D
感觉比C简单。。。
题意
现在进行一场投票，每个候选人的粉丝是固定的，此外还有一些自由选民，他们会将票投给编号最小的候选人。现在你可以踢出若干候选人（他们的粉丝会变成自由选民，并且符合上述规则），要求你计算最少可以踢出多少个候选人，使得第\(i\)个候选人获胜。
方法
不难想到：如果是最大的，肯定不用踢。
如果\(ith\)是在最大的前面：那么\(ith\)肯定需要踢出排在他前面的所有人。如果还是小于\(maxn\)，那么踢出\(maxn\)候选人即可。
如果再最大的后面，那么\(ith\)前面的所有人都需要被踢出。
需要考虑特别的情况：可能出现重复的\(maxn\)，针对第一个\(maxn\)，不需要踢出任何人，其他情况则需要踢出位于前面的所有人。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
ll c; cin>>c;
std::vector<ll> a(n,0);
ll maxn=0,id=0;
a[0]=c;
for(int i=0;i<n;i++)
{
ll x;
cin>>x;
a[i]+=x;
if(maxn<a[i])
{
maxn=a[i];
id=i;
}
}
std::vector<ll> s;
s=a;
for(int i=1;i<n;i++)
{
s[i]=s[i-1]+s[i];
}
std::vector<int> ans(n,0);
for(int i=0;i<n;i++)
{
if(a[i]==maxn)
{
if(i==id) ans[i]=0;
else
{
ans[i]=i;
}
continue;
}
if(id<i)
{
ans[i]=i;
}
else
{
ll tot=s[i];
ans[i]=i;
if(tot<maxn)
{
ans[i]++;
}
}
}
for(int i=0;i<n;i++) cout<<ans[i]<<" \n"[i==n-1];
}
int main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
|
