对于训练赛的赛题整合。
文章目录
2033D - Kousuke’s Assignment
题意：
找出数组中最多有多少子段使子段和为0。
题解：
思考某个子段和为零会什么情况出现？子段和的下一个数与其相加，和等于这个数，那我们就利用这个特点，用前缀和和set,去解决这个问题。
如果能在set中找到与前缀和想等的数，ans++,清空set，重新从当前位置计算前缀和。如果没有，将前缀和insert到set里。
代码
#include<bits/stdc++.h>
using namespace std;
int a[1000000],ans;
long long sum=0;
set<long long> s;
void solv()
{
ans=0,sum=0,s.clear(),s.insert(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
if(s.count(sum))
{
sum=0,ans++,s.clear(),s.insert(0);
}
else s.insert(sum);
}
cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while(t--) solv();
return 0;
}
2033C- Sakurako’s Field Trip
题意
通过交换下标为i与n-i+1的数，使满足aj=aj+1的数量最少，最少是多少
题解
若交换后的干扰数量小于交换前的干扰数量，则将两个数交换，反之则不交换
代码
#include<bits/stdc++.h>
using namespace std;
void sov()
{
int n;
cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int pre,re;
for(int i=2;i<=n/2;i++)
{
int pre=(a[i]==a[i-1])+(a[n-i+2]==a[n-i+1]);
int re=(a[i]==a[n-i+2])+(a[n-i+1]==a[i-1]);
if(pre>re) swap(a[i],a[n-i+1]);
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(a[i]==a[i-1])
ans++;
}
cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while(t--) sov();
return 0;
}
2022B -Kar Salesman
题意
有n种型号的汽车，每种类型有ai辆，现在每位顾客最多购买x辆不同类型的车，现在最多需要来几位顾客才能将车卖空？
题解
因为每个顾客买的车不是同一个类型的，所以我们至少需要max{a1,a2,…an}个顾客。也就是说来的人数要是是汽车数量最多。
又因为每个顾客只能买x台，所以我们至少需要(a1+a2+…an)/x位顾客。注意要向上取余。
代码
#include <iostream>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
long long n,x,sum=0,mx=0,in;
cin>>n>>x;
while(n--){
cin>>in;
mx=max(mx,in);
sum+=in;
}
cout<<max(mx,sum/x+(sum%x!=0))<<"\n";
}
return 0;
}
2025C-New Game
题意
有n张扑克牌，n张卡牌，每张卡牌上有一个整数ai，每个回合他可以拿一张数字为 x 或数字为 x+1 的卡牌，所拿卡牌上写的不同数字的数量不得超过 k。确定在游戏中可以从牌堆中拿到的最大卡牌数量
题解
1.将所有卡牌从小到大排序，记录每个数字出现的次数,存入map
2.通过遍历，类似滑动窗口，用ans记录每次的最大值
3.如果所选数字不满足x=s,或者x=s+1(即拿牌规律时)，重新计算，更新最大值
4.如果所选数字的数量大于k,就减去所选第一个数，向后遍历，更新最大值
代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define fi first
#define se second
#define PII pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
void solve()
{
int n,k;
cin>>n>>k;
map<int,int> m;
int ans=0,sum=0,cnt=0,base=0,s=0;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
m[x]++;
}
for(auto i : m )
{
int x=i.fi,y=i.se;
if(sum==0)
{
sum+=y;
s=x;
base=x;
cnt++;
}
else
{
if(x-s>1)
{
sum=0;
cnt=0;
base=x;
}
else if(cnt==k)
{
sum-=m[base];
base++;
cnt--;
}
s=x;
cnt++;
sum+=y;
}
ans=max(ans,sum);
}
cout<<ans<<endl;
}
signed main()
{
IOS;
int t=1;
cin>>t;
while(t--)
solve();
}