2023牛客寒假算法基础集训营5
A
很好理解
题目大意是找k个小于等于x的物品（最多k个）的和最大是多少
我们可以先把所有的a排序，然后求前缀和
然后每次询问，我们需要的是小于等于x的物品，我们可以用upper_bound来找到第一个大于x的位置，那么我们可以用到的就是这个位置前面的所有物品（我们可以选择）,由于我们先前是按照从大到小的排序，所以我们这k个选择后k个，这样值就是大的
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+10;
int n,q;
int a[maxn];
int sum[maxn];
int b[maxn];
signed main ()
{
cin>>n>>q;
for (int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(a+1,a+1+n);
for (int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
}
while (q--)
{
int k,x;
cin>>k>>x;
int pos=upper_bound(a+1,a+1+n,x)-a;
//cout<<pos<<' ';
if (pos==1)
{
cout<<0<<'\n';
continue;
}
if (a[pos]>x&&pos>1)
{
int ans=0;
pos--;
if (pos>k)
{
ans=sum[pos]-sum[pos-k];
}
else
{
ans=sum[pos];
}
cout<<ans<<'\n';
}
else
{
int ans=sum[n]-sum[n-k];
cout<<ans<<'\n';
}
}
return 0;
}
B
这题大意是有n个数，两个人可以选择任意个数，然后每个人每次得到的数可以组成一个字符串，谁的字典序小谁就赢了，一样就是双赢
如果要小的字典序，选手每次都会尽量选小的，所以选手每一次都会选1，那么，如果是偶数，那么两个人是一样的字符，如果是奇数，那么后手赢
#include <bits/stdc++.h>
using namespace std;
int n;
int main ()
{
cin>>n;
if (n&1)
{
cout<<"Yaya-win!\n";
}
else cout<<"win-win!\n";
return 0;
}
C
这道题在比赛的时候死活没有看懂题意，后来根据这个其他人的代码，我感觉好像懂了一点点
我觉得，这个题是给你里两个字符a,b,然后我们有10个数字（0到9）有任意一种映射关系，比如3可以变成5,7可以变成2这种的，然后对于各种不同的映射关系，我们知道了映射之前的a,b之间的关系，如果所有的关系都是大于，输出大于号，都是小于号，输出小于号，都是等于，输出等于号，否则，输出感叹号，说明大小关系不明
然后这道题还有一个很关键的信息（我觉得）
那就是还可能存在前导零
所以这里的比较大小是带有前导零的，如果短的那一个，就会有前导零（我看了代码就有一种这样的感受），这是我在比赛过程中没有想到的
至于具体分析过程看代码吧
#include <bits/stdc++.h>
using namespace std;
string a,b;
//我们要清楚是有可能是前导零
int main ()
{
cin>>a>>b;
int len1=a.size(),len2=b.size();
if (len1==len2)
{
if (a==b)//如果是一样，不管怎么变化都是一样的
{
cout<<"=";
return 0;
}
cout<<"!";//如果是不一样的，大的可以变成小的，小的可以变成大的，所以a和b之间的关系可大于，可小于
return 0;
}
char ans='>';//我们保证a是那个较长的字符串，题目中还提及了a,b那些字符串可能存在前导零
//那么就很好判断了
if (len2>len1)
{
swap(a,b);
ans='<';
swap(len1,len2);
}
int len=len1-len2;
//对于b,比起a,还要需要len个前导零，故，对于a来说，只要a前len个字符有两个以上的字符，那么就一定会大于b,
//因为字符串的变化中只有一个字符可以变成0，那么其他的一定会变成非0的数，那么前len个已经出现了非0的数，而b还是0，故不管怎么样，a一定大于b
char ch=a[0];
for (int i=0;i<len;i++)
{
if (a[i]!=ch)
{
cout<<ans;
return 0;
}
}
a.erase(a.begin(),a.begin()+len);
if (a==b)//如果说前len个只有一种字符串，后面都是一样的，我们要把ch变成0只有一种情况，故等于的情况只有一种，其他的都是大于
{
cout<<"!";
return 0;
}
for (int i=0;i<len2;i++)//没有前导0就是ans,有前导0的话，只要b在a的非0的且和a不一样的位置变成0的时候还是大于
{
if (a[i]!=b[i])
{
if (b[i]==ch)
{
cout<<ans;
}
else cout<<"!";//不是变成0那就可能变大，也可能变小
return 0;
}
}
return 0;
}
D
这个题大意是每到达一个地方，可以得到一段线段，有两个人，每个人的所获得的线段都不同，对于此事可到达的最远距离是从0到r(所有的线段合并起来，0到r是连续的）而我们需要的是从比较两个人谁到的最远，领先多少
在比赛过程中，我的重点有点偏了，我之前还考虑到可不可以到达那一个点，拿到那一段线段，后来看代码原来不需要考虑到这儿，然后我的线段合并过程也可能有点小问题，就直接借鉴其他人的了
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+10;
int n;
struct node
{
int l,r;
friend bool operator < (const node x,const node y)
{
return x.l>y.l;
}
}a[maxn],b[maxn];
priority_queue<node>q1,q2;
int r1,r2;
//这道题我觉得不太需要考虑可不可以到达那一关，而只需要考虑从1到r即可（多段区间合并，连续）
void update1()//线段合并
{
while (!q1.empty())
{
node now=q1.top();
q1.pop();
if (now.l<=r1+1)
{
r1=max(r1,now.r);
}
else
{
q1.push(now);
break;
}
}
return ;
}
void update2()
{
while (!q2.empty())
{
node now=q2.top();
q2.pop();
if (now.l<=r2+1)
{
r2=max(r2,now.r);
}
else
{
q2.push(now);
break;
}
}
return ;
}
signed main ()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i].l>>a[i].r;
}
for (int i=1;i<=n;i++)
{
cin>>b[i].l>>b[i].r;
}
for (int i=1;i<=n;i++)
{
q1.push(a[i]);
update1();
q2.push(b[i]);
update2();
if (r1>r2)
{
cout<<"sa_win!\n"<<r1-r2<<'\n';
}
else if (r1<r2)
{
cout<<"ya_win!\n"<<r2-r1<<'\n';
}
else
{
cout<<"win_win!\n"<<0<<'\n';
}
}
return 0;
}
F
题意很简洁（很少有这么短小精悍的题目描述了）
有一个长度为 n 的字符串，他有 kkk 次操作，每次操作可以任意选择一个字符，将其移动到字符串的最后。 小沙想问你，找到恰好操作 k 次之后，字典序最大的字符串是怎样的
直接看代码吧
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
string s;
string s1,s2,s3;
//s1是移动到前面的，s2是那些要移动到后面的字符，
//s3是那些还没有选择移动到后面或者不移动即会移动到前面的这两个都没有选择的字符，这种情况是k太少了导致的
queue<int>pos[30];
signed main ()
{
cin>>n>>k;
cin>>s;
s=" "+s;
for (int i=1;i<=n;i++)
{
pos[s[i]-'a'+1].push(i);
}
int l=1;
while (k)
{
for (int i=26;i>=1;i--)
//这个是选择是找出此时在有k个操作的时候，我们可以让一个最大的字符移动nxt步
//nxt小于k,l到nex-1这一段的字符需要移动到后面，只要是选择移动的字符我们都把他们存在s2里面，但是哪一个字符的移动 先移动，哪一个后移动，我们可以随意选择
//我们可以尽量的让移动的字符按照从大到小的顺序来移动，故s2里面的字符一定是从大到小的
{
while (!pos[i].empty()&&pos[i].front()<l)
{
pos[i].pop();
}
if (pos[i].size()&&pos[i].front()<=l+k)
{
int nxt=pos[i].front();
k-=(nxt-l);
while (l<nxt)//从l到nxt-1这一段都是需要往后移动的，让nxt这个位置的字符到前面去
{
s2.push_back(s[l]);
l++;
}
s1.push_back(s[l]);//s2是记录保留不动的字符
l++;
break;
}
}
if (l==n+1) break;
}
for (int i=l;i<=n;i++)
{
s3.push_back(s[i]);//还没有到的
}
while(k&&!s1.empty()&&s3.empty())//如果每一个位置都已经选择好了（s3为空），但是还需要一些操作，我们让原本保留的s1的最后一个改变选择，由原来的 保留不动而改变成移动到后面
{
s2+=s1[s1.size()-1];
s1.pop_back();
k--;
}
sort(s2.begin(),s2.end());
reverse(s2.begin(),s2.end());
string ans=s1+s3+s2;
cout<<ans<<'\n';
return 0;
}
H
这个题直接模拟
题意是最初有一个单价为x,但是每次我们卖出了k件物品，单价会增加y,然后n个顾客，1到n个顾客，每个顾客会买n,n-1,n-2....1，这样的数量个物品，问我们我们在最早多少个人的时候可以卖出t元，就输出卖给了ans个人了，如果所有人都买完了，还是没有t元，输出-1
直接判断在某个人的时候已经卖出多少物品，我们根据这个直接求出单价，然后求销售总值
#include <bits/stdc++.h>
using namespace std;
#define int long long
int x,y,k,n,t;
signed main ()
{
cin>>x>>y>>k>>n>>t;
int cnt=0;
bool yes=false;
int sum=0;
int ans=0;
for (int i=n;i>=1;i--)
{
ans++;
int now=x;
if (cnt)
{
now+=(cnt/k)*y;
}
sum+=now*i;
cnt+=i;
if (sum>=t)
{
yes=true;
break;
}
}
if (yes)
{
cout<<ans<<'\n';
}
else cout<<-1<<'\n';
return 0;
}
I
这个我也是一顿懵
哎呀
题目大意是有m个灵石，n个赌局，我们可以压x个灵石（在某一轮赌局），赢了可以得到x个灵石就跑，输了就要失去x个灵石
我们需要一个方案最优的方案，让赌完后一定不要亏灵石
设a[i]为赌局i的压的灵石数
那么a[i+1]>=a[1]+...+a[i]
所以我们总结出
a[i+1]>=s[i],s[i]是1到i的前缀和
s[i+1]-s[i]>=s[i]
s[i+1]>=2s[i]
而且我们知道s[n]=m
根据这一个意思
我们可以得到这样一个方程
s[i-1]=s[i]/2
但是我们还要注意还要灵石不够的情况，得注意
然后我们看代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
#define int long long
int s[maxn];
int n,m;
signed main ()
{
cin>>n>>m;
s[n]=m;
for (int i=n;i>1;i--)
{
if (s[i]>=2)
{
int now=s[i]/2;
s[i-1]=now;
s[i]-=now;
}
}
for (int i=1;i<=n;i++)
{
if (s[i]==0)
{
cout<<-1<<'\n';
return 0;
}
}
for (int i=1;i<=n;i++)
{
cout<<s[i]<<" ";
}
return 0;
}
K
就是抱团游戏，我们现在有n个人，我们需要最少多少个指令才让人数最少
（指令就是假如现在有x人，指令为y（y<=x),有x%y个人会被淘汰）
然后我发现如果此时的人小于等于2时就不太可以淘汰人了
然后我们发现要想最快淘汰最多的人，是指令为此时人数除二加一（我发现的，当时就感性的觉得就是这样的）
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
signed main ()
{
cin>>n;
int ans=0;
while (n>2)
{
n=n/2+1;
ans++;
}
cout<<ans<<'\n';
return 0;
}
L
这一个题是上面的题目大hard版
就是指令有限制，有m个限制，每个限制有代价
然后我们需要知道到让人数最少的指令的最小价值
想起这道题就气
在这里就一下这次的惨痛教训
memset(dp,0x3f,sizeof(dp))
这里面dp的值并不是0x3f,而是代表一个很大的数，下次要是来判断dp里有没有更新就不要用0x3f来比较了
真的惨痛
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+10;
int n,m,b[maxn],x[maxn];
int dp[maxn];
signed main ()
{
cin>>n>>m;
for (int i=1;i<=m;i++)
{
cin>>b[i]>>x[i];
}
if (n==1||n==2)
{
cout<<0<<'\n';
return 0;
}
memset(dp,0x3f,sizeof(dp));//0x3f不是值里面的值一定是0x3f，而是代表着dp是一个很大很大的值，后面我们如果要比较的话一定不要拿ox3f来比较，可以拿一个很大的数，反正就不是0x3f
dp[n]=0;
for (int i=n;i>=2;i--)
{
for (int j=1;j<=m;j++)
{
if (x[j]<i) dp[i-(i%x[j])]=min(dp[i]+b[j],dp[i-i%x[j]]);
}
}
int ans=0;
for (int i=1;i<=n;i++)
{
if (dp[i]>=2e9) continue;
ans=dp[i];
break;
}
cout<<ans<<'\n';
return 0;
}