字符串的题目按以前的写法超时了，要时刻学习一下别人优秀的思路和题解
前四道简单的模拟题略过
基于文化课的算法学习
这一题需要注意如下几个点：1.我们要更改的一定要在main和return之外
2.是第一个main和最后一个return之间就不符合题意
3.从右边开始找使用rfind左边开始找使用find 但是注意pos应该pos>pos2+5是小于找到return后的后三个位置因为返回的索引是r的位置
4.如果没有main或return 应该输出wrong
点击查看代码
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
string s1,s2;
cin>>n>>s1>>s2;
int pos1=s2.find("main");
int pos2=s2.rfind("return");
if(pos1==-1||pos2==-1) {
cout<<"wrong";
return;
}
//解决main前面的
while(1)
{
int pos=s2.find(s1);
if(pos==-1||pos>pos1+3) break;
else s2.replace(pos,3,"zxz");//第一个是开始的位置，第二个位置是替换的字符的长度
//因为替换了当前位置的s1所以开始下次循环时会在新的位置找到s1
}
//解决return后面的
while(1)
{
int pos=s2.rfind(s1);
if(pos==-1||pos<pos2) break;
else s2.replace(pos,3,"zxz");
}
cout<<s2;
}
int main()
{
solve();
}
奶茶袋收集
这题本质上其实是一个贪心，记录一下每两个相邻数的差分，然后从大到小排序一下，如果划分为n段就就减去n-1个的最大值
记录这个差分可以用如下的代码可以省一大步
点击查看代码
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n,m,sum=0;
cin>>n>>m;
vector<int>ve(n+1);
//记录差分
for(int i=1;i<=n;i++)
{
int x,last;
cin>>x;
if(i>=2)
{
ve.emplace_back(x-last);
sum+=x-last;
}
last=x;
}
sort(ve.begin()+1,ve.end(),greater<int>());//记得从1开始排序
for(int i=1;i<=m-1;i++)
{
sum-=ve[i];
}
cout<<sum;
}
int main()
{
solve();
}
该加训啦
这题感谢欧哥通俗易懂的解释，首先要具备几个知识点
1.当a异或a的时候肯定是0
2.通过真值表可以把题目的条件转变成f（a,b）=a^b
3.理解异或数组的前缀和
题意的意思为我们举个例子f（2，6）=2 ^ 3^4 ^ 5^ 6,而前缀和异或数组a【6】=1 ^2 ^3 ^4 ^5 ^6，我们需要把1 给它抵消掉，那么用上第一个知识点只需要a[6]*a[2-1]即可所以最后就是输出a[l-1] * a[r]即可
点击查看代码
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n,a[200005],s[200005],m;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) s[i]=s[i-1]^a[i];
cin>>m;
while(m--)
{
int l,r;
cin>>l>>r;
cout<<(s[l-1]^s[r])<<endl;
}
}
int main()
{
solve();
}
cy的倒金字塔工厂
这道题是一道stl的模拟题，感觉没什么技巧就是根据文字多写多练，理清条件，代码中有详细的注解
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
int n,k;
stack<int> m;//主流水线
stack<int>box;//盒子
stack<int>half;//半成品的数量
queue<int>rub;//按顺序丢弃的积木
void solve()
{
int k,n;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
m.push(x);
}
while(!m.empty()||!box.empty())//直到流水线和盒子的积木全为空
{
if(!m.empty())//当流水线上有积木
{
int now=m.top();
m.pop();
if(half.empty()) half.push(now);//如果当前没有底座。将now作为底座
else{//如果已经有底座
if(now>half.top()&&now-half.top()<=k) half.push(now);//检查流水线上这块积木是否大于当前底座这块并且差值小于k否
else {//流水线的不符合要求，检查盒子的是否符合要求
if(!box.empty()&&box.top()>half.top()&&box.top()-half.top()<=k)
{//盒子不空且顶部这块大于底座这块且在差值之内
half.push(box.top());
box.pop();
}
box.push(now);//把流水线这块不符合的放入盒子里
}
}
}
if(m.empty())//流水线没有积木
{
if(half.size()>=2){//如果半成品的积木数量大于2
while(!half.empty()){
cout<<half.top()<<" ";
half.pop();
}
cout<<endl;
}
else rub.push(half.top()),half.pop();//只有一块放在垃圾堆里
stack<int>t;//为了清空盒子
while(!box.empty())
{
t.push(box.top());
box.pop();
}
while(!t.empty())
{
m.push(t.top());
t.pop();
}
}
}
while(!rub.empty())//半成品积木只有一块 则丢弃该积木
{
cout<<rub.front()<<" ";
rub.pop();
}
}
signed main()
{
int t=1;
while(t--)
{
solve();
}
return 0;
}
swj学长的精灵融合
这道题用欧桑的解法，非常的简洁，就是一个dfs树图，然后vector内放融合材料和经验值，注意学习一下图的遍历，算经验记得把等差部分和不等差的分开再加起来会好算点，题目很臭很长但是读懂了就会发现不难
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
long long exp1[105],ex2[105],exp3[105];
const int N=1e5+5;
int n,m,a,b,c,d,ans=0;
vector<pii>ve[N];//用[]就是表示二维n行存父节点每行后面的数就是子节点
void dfs(int x)
{
for(auto to:ve[x]){
ans+=to.second;
dfs(to.first);//图的遍历 二维的vector
}
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a>>b>>c>>d;
//计算经验把前两个不是等差数列的拿出来 最后再加上去
int ex=1;
if(d==1) ex=0;
if(c==2) ex+=(d-2)*(2+(d-2)*2)/2;
if(c==1) ex+=(d-2)*(1+(d-2))/2;
if(c==3) ex+=(d-2)*(5+(d-2)*5)/2;
//cout<<ex<<" ";
ve[a].emplace_back(b,ex);
}
dfs(n);
cout<<ans;
}
int main()
{
int t=1;
while(t--)
{
solve();
}
}