AtCoder Beginner Contest 344 （A~F）

本文主要是介绍AtCoder Beginner Contest 344 （A~F），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

比赛地址传送门

A - Spoiler

#include <bits/stdc++.h>
using namespace std;
int main()
{string line;cin>>line;int l=0,r=line.length()-1;while(line[l]!='|') l++;while(line[r]!='|') r--;for(int i=0;i<line.length();i++) {if(i<l||i>r) cout<<line[i];}return 0;
}

B - Delimiter

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{vector<ll> ans;int x;while(cin>>x) {ans.push_back(x);if(x==0) break;}reverse(ans.begin(),ans.end());for(auto temp: ans) {cout<<temp<<'\n';}return 0;
}

C - A+B+C

可以发现数据范围不大，可以将所有求和结果提前枚举放进集合里，每次查询就看看集合里面有没有这个数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{ios::sync_with_stdio(false),cin.tie(0);int n,m,l;cin>>n;vector<ll> a(n);for(int i=0;i<n;i++) cin>>a[i];cin>>m;vector<ll> b(m);for(int i=0;i<m;i++) cin>>b[i];cin>>l;set<ll> c;for(int i=0;i<l;i++) {int x;cin>>x;for(int j=0;j<n;j++) {for(int k=0;k<m;k++) {c.insert(x+a[j]+b[k]);}}}int t;cin>>t;while(t--) {ll q;cin>>q;cout<<(c.count(q)?"Yes":"No")<<'\n';}return 0;
}

D - String Bags*

有点像 是分组背包问题，考虑维护数组 dp[i][j] 表示第 i 组中选好了前 j 个字符的最小花费。那么对于每一组中的每个单词，枚举所有 $k\in [0,S.length)$ 看看这个单词是否能放在第 k 个位置，如果可以的话，那么 dp[i][j] = min(dp[i-1][k-1]+1)
可以用滚动数组优化空间

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int tlen,len,a;
string t;
bool cmp(string a,string b)
{return a.length()>b.length();
}
void solve(vector<int> &f)
{vector<int> temp(110,1e9);for(int j=1;j<=a;j++) {string word;cin>>word;len=word.length();for(int k=0;k<=tlen-len;k++) {if(t.substr(k,len)==word) {if(k==0) temp[len-1]=1;else temp[k+len-1]=min(temp[k+len-1],f[k-1]+1);}}}for(int k=0;k<=tlen;k++)f[k]=min(f[k],temp[k]);
}
int main()
{int n;cin>>t>>n;tlen=t.length();vector<int> f(110,1e9);for(int i=1;i<=n;i++) {cin>>a;solve(f);}if(f[tlen-1]==1e9) cout<<-1;else cout<<f[tlen-1]<<'\n';return 0;
}

E - Insert or Erase

典型链表问题，普通链表插入 $O(1)$，查询 $O(n)$，但本题中每个数组仅会出现一次，可以用 map 将查询操作变为 $O(logn)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// int nex[200010],pre[200010];
map<int,int> nex,pre;
int _front=-1;
int main()
{ios::sync_with_stdio(false),cin.tie(0);int n;cin>>n;int last=-1;for(int i=1;i<=n;i++) {int x;cin>>x;nex[x]=-1,pre[x]=-1;if(_front==-1) _front=x;if(last!=-1) nex[last]=x;pre[x]=last;last=x;}int q;cin>>q;while(q--) {int op,x,y;cin>>op>>x;if(op==1) {cin>>y;nex[y]=nex[x];pre[y]=x;if(nex[x]!=-1) pre[nex[x]]=y;nex[x]=y;} else {int z=pre[x];if(nex[x]!=-1) pre[nex[x]]=z;if(z==-1) {pre[nex[x]]=-1;_front=nex[x];} else {nex[z]=nex[x];}}}while(_front!=-1) {cout<<_front<<' ';_front=nex[_front];}return 0;
}

F - Earn to Advance

乍一看很简单，直接bfs搜索即可，但是试了一下发现第二个样例就过不去，时间复杂度过高，于是又想到了 dp ，用 dp[i][j] 来简单维护到坐标 $(i,j)$ 的最短花费，贪心的想如果钱不够就留下来挖宝，如果够了就出发，想一会就发现不对。

开摆！

又到了观摩大佬代码的时间~
大佬题解
因为充值一次的代价是相同的，那么选择充钱多的点来充钱一定是最优解。如果起点钱最多，那完全可以在起点充好钱一股气走到终点，如果中间有个点钱很多，那么我们可以在起点充钱充到足够支持我们走到那个钱更多的点。不难发现，假设我们选择充钱的点为 $a_1、a_2、a_3、...$ 那么，当且仅当 $M_{a_1}＜M_{a_2}<M_{a_3}...$ 时才是最优的（M是钱数），对于每个点 x，dp维护它能走到的所有比它钱多的点 y 的花费， 如果从 x 走向 y 的花费更小或者两者花费相同但是从 x 走钱更多，则用 x 点更新 y 点

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{ios::sync_with_stdio(false),cin.tie(0);int n;cin>>n;vector p(n,vector<int>(n));vector r(n,vector<int>(n-1));vector d(n-1,vector<int>(n));for(auto &i: p) {for(auto &j: i) {cin>>j;}}for(auto &i: r) {for(auto &j: i) {cin>>j;}}for(auto &i: d) {for(auto &j: i) {cin>>j;}}vector dp(n,vector<array<ll,2>>(n,{(ll)1e18,0}));dp[0][0]={0,0};for(int i=0;i<n;i++) {for(int j=0;j<n;j++) {vector dist(n,vector<ll>(n,1e18));dist[i][j]=0;for(int k=i;k<n;k++) {for(int l=j;l<n;l++) {if(k) dist[k][l]=min(dist[k][l],dist[k-1][l]+d[k-1][l]);if(l) dist[k][l]=min(dist[k][l],dist[k][l-1]+r[k][l-1]);}}for(int k=i;k<n;k++) {for(int l=j;l<n;l++) {if(k!=n-1&&l!=n-1&&p[k][l]<p[i][j]) continue;ll step=dp[i][j][0],money=dp[i][j][1];ll cost=max(0ll,(dist[k][l]-money+p[i][j]-1)/p[i][j]);ll _money=money+cost*p[i][j]-dist[k][l];ll _step=step+cost+(k-i)+(l-j);if(_step<dp[k][l][0]||_step==dp[k][l][0]&&_money>dp[k][l][1])dp[k][l]={_step,_money};}}}}cout<<dp[n-1][n-1][0]<<'\n';return 0;
}

这篇关于AtCoder Beginner Contest 344 （A~F）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---