Toyota Programming Contest 2024#3(AtCoder Beginner Contest 344)(A,B,C,D,E,F)

2024-03-10 12:20

本文主要是介绍Toyota Programming Contest 2024#3(AtCoder Beginner Contest 344)(A,B,C,D,E,F),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

比赛链接

这场偏简单,C是暴力,D是变种背包,E是map+链表,F是四维dp。DF出的很好,建议做。


A Spoiler

题意:

给你一个由小写英文字母和 | 组成的字符串 S S S S S S 中保证包含两个 |

请删除两个|之间的字符,包括|本身,并打印得到的字符串。

思路:

stringfind_first_of()find_last_of() 成员函数可以很容易找到 | 的位置,然后再用 substr() 成员函数提取字串即可。

code:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;string str;int main(){cin>>str;int a=str.find_first_of("|"),b=str.find_last_of("|");cout<<str.substr(0,a)<<str.substr(b+1);return 0;
}

B Delimiter

题意:

给你 N N N 个整数 A 1 , A 2 , … , A N A_1,A_2,\dots,A_N A1,A2,,AN,每行一个,共 N N N 行。但是,输入中没有给出 N N N
此外,下面的内容是有保证的:

  • A i ≠ 0 A_i \neq 0 Ai=0 ( 1 ≤ i ≤ N − 1 1 \le i \le N-1 1iN1 )
  • A N = 0 A_N = 0 AN=0

按此顺序打印 A N , A N − 1 , … , A 1 A_N, A_{N-1},\dots,A_1 AN,AN1,,A1

思路:

因为要逆序输出,用个栈存一下,读到 0 0 0 就停止读入然后输出。

code:

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;int t;
stack<int> s;int main(){do{cin>>t;s.push(t);}while(t);while(!s.empty()){cout<<s.top()<<endl;s.pop();}return 0;
}

C A+B+C

题意:

给你三个序列 A = ( A 1 , … , A N ) A=(A_1,\ldots,A_N) A=(A1,,AN) B = ( B 1 , … , B M ) B=(B_1,\ldots,B_M) B=(B1,,BM) C = ( C 1 , … , C L ) C=(C_1,\ldots,C_L) C=(C1,,CL)

此外,还给出了一个序列 X = ( X 1 , … , X Q ) X=(X_1,\ldots,X_Q) X=(X1,,XQ)。针对每个 i = 1 , … , Q i=1,\ldots,Q i=1,,Q 求解下面的问题:

问题:能否从 A A A B B B C C C 中各选择一个元素,使它们的和为 X i X_i Xi

思路:

发现数据范围很小, N , M , L N,M,L N,M,L 最多就 100 100 100,因此直接暴力即可。枚举三个数组中的每个元素,算出所有可能的结果,最后把得到的所有数放进set里,之后查询即可

code:

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int maxn=105;int a[5][maxn],Q;int main(){for(int i=1;i<=3;i++){cin>>a[i][0];for(int j=1;j<=a[i][0];j++)cin>>a[i][j];}set<int> s;for(int i=1;i<=a[1][0];i++)for(int j=1;j<=a[2][0];j++)for(int k=1;k<=a[3][0];k++)s.insert(a[1][i]+a[2][j]+a[3][k]);for(cin>>Q;Q;Q--){int t;cin>>t;puts((s.find(t)==s.end())?"No":"Yes");}return 0;
} 

D String Bags

题意:

最初有一个空字符串 S S S
此外,还有袋子 1 , 2 , … , N 1, 2, \dots, N 1,2,,N,每个袋子都包含一些字符串。
i i i 包含 A i A_i Ai 个字符串 S i , 1 , S i , 2 , … , S i , A i S_{i,1}, S_{i,2}, \dots, S_{i,A_i} Si,1,Si,2,,Si,Ai

i = 1 , 2 , … , N i = 1, 2, \dots, N i=1,2,,N 重复以下步骤:

  • 选择并执行以下两个操作之一:
    • 支付 1 1 1 日元,从袋子 i i i 中选择一个字符串,并将其连接到 S S S 的末尾。
    • 不做任何操作。

给定字符串 T T T,求使最后的 S S S 等于 T T T 所需的最小金额。
如果无法使最后的 S S S 等于 T T T,则打印 -1

限制因素
  • T T T 是由小写英文字母组成的字符串,长度在 1 1 1 100 100 100 之间(含)。
  • N N N 是介于 1 1 1 100 100 100 之间的整数,包含在内。
  • A i A_i Ai是介于 1 1 1 10 10 10之间的整数,包括 1 1 1 10 10 10
  • S i , j S_{i,j} Si,j是由小写英文字母组成的字符串,长度在 1 1 1 10 10 10之间(包括 1 1 1 10 10 10)。

思路:

看清楚题,注意是按顺序从第 i i i 个袋子中取一个,不能回头取,也不能一个袋子取多个。所有 A C × 57 / W A × 1 AC\times57/WA\times1 AC×57/WA×1 的大概率是一个袋子取了多个字符串(也就是说不能滚动数组优化)。

读懂题之后,这个题其实就是比较明显的背包了。设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示从前 i i i 个袋子中拼到 j j j 长度的最少花费,如果不从第 i i i 个袋子选字符串,那么就可以转移到 d p [ i + 1 ] [ j ] dp[i+1][j] dp[i+1][j],如果从第 i i i 个袋子中选取一个字符串,如果这个字符串长度为 l e n len len 并且这个字符串与 T T T 串的 j ∼ j + l e n − 1 j\sim j+len-1 jj+len1 部分子串正好相同,这个字符串就可以拼到这里,状态转移到 d p [ i + 1 ] [ j + l e n ] dp[i+1][j+len] dp[i+1][j+len]

由于第 i i i 个袋子只能选一个字符串,所以不能滚动数组优化,乖乖二维DP。

code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=105;
const int inf=1e9;int n,m;
string t;
vector<vector<int> > dp(maxn,vector<int>(maxn,inf));int main(){cin>>t;n=t.length();t=" "+t;cin>>m;for(int i=0;i<=m;i++)dp[i][0]=0;for(int i=1,_;i<=m;i++){for(cin>>_;_;_--){string s;int len;cin>>s;len=s.length();for(int j=1;j<=n;j++){dp[i][j]=min(dp[i][j],dp[i-1][j]);if(j-len>=0 && t.substr(j-len+1,len)==s)dp[i][j]=min(dp[i][j],dp[i-1][j-len]+1);}}}if(dp[m][n]==inf)cout<<-1<<endl;else cout<<dp[m][n]<<endl;return 0;
}

E - Insert or Erase

题意:

给你一个长度为 N N N 的序列 A = ( A 1 , … , A N ) A=(A_1,\ldots,A_N) A=(A1,,AN) A A A 中的元素是不同的。

请按照给出的顺序处理 Q Q Q 个查询。每个查询属于以下两种类型之一:

  • 1 x y:在 A A A 中元素 x x x 后面紧接着插入 y y y。当给出此查询时,保证 x x x 存在于 A A A 中。
  • 2 x:从 A A A 中删除元素 x x x。当给出此查询时,保证 x x x存在于 A A A中。

保证在处理完每一个查询后, A A A都不是空的,并且其元素都是不同的。

处理完所有查询后,打印 A A A

思路:

对操作 1 1 1,需要查找 x x x 的位置,然后在它后面插入 y y y,对操作 2 2 2,需要查找 x x x 的位置,然后删掉它。因为题目非常贴心地告诉我们每个元素值都不一样,所以可以用 m a p map map 建立起值到位置的映射,而插入删除,就需要使用链表了。

code:

这里写的 头节点为 0 0 0 的循环双向链表。

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
const int maxn=2e5+5;int n,Q;
int nxt[maxn<<1],pre[maxn<<1],a[maxn<<1],cnt;
map<int,int> mp;int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]=i;nxt[i-1]=i;pre[i]=i-1;}cnt=n;for(cin>>Q;Q;Q--){int op,x,y,p;cin>>op;if(op==1){cin>>x>>y;p=mp[x];a[++cnt]=y;mp[y]=cnt;pre[cnt]=p;nxt[cnt]=nxt[p];pre[nxt[p]]=cnt;nxt[p]=cnt;}else {cin>>x;p=mp[x];mp.erase(x);nxt[pre[p]]=nxt[p];pre[nxt[p]]=pre[p];}}for(int p=nxt[0];p;p=nxt[p]){cout<<a[p]<<" ";}return 0;
}

F - Earn to Advance

题意:

有一个网格,网格中有 N N N 行和 N N N 列。让 ( i , j ) (i,j) (i,j) 表示从上面起第 i i i 行和从左边起第 j j j 列的正方形。

高桥最初在 ( 1 , 1 ) (1,1) (1,1) 个方格中的钱为零。

当高桥在 ( i , j ) (i,j) (i,j) 号方格时,他可以在一次行动中完成以下其中一项:

  • 停留在同一位置并增加 P i , j P_{i,j} Pi,j个数字。
  • 从他的钱中支付 R i , j R_{i,j} Ri,j 并移动到 ( i , j + 1 ) (i,j+1) (i,j+1) 格。
  • 从他的钱中支付 D i , j D_{i,j} Di,j 并移动到 ( i + 1 , j ) (i+1,j) (i+1,j) 格。

他不能走会使他的金钱变为负数或使他离开棋盘的一步棋。

如果高桥采取最优行动,他需要下多少步棋才能到达 ( N , N ) (N,N) (N,N) 位置?

思路:

当看到 N ≤ 80 N\le80 N80 的时候就不对劲起来了。可以跑 N 4 N^4 N4,甚至还能带点常数。

我们到达某个位置的时候,最少需要描述:横坐标,纵坐标,时间,剩余金钱 四个状态参数。而金钱这东西我们可以先在一个地方打很长时间的工,赚很多钱再向后走,这样可能是更优的。而我们在打工的时候很难知道赚多少合适,也不知道后面有没有更好的打工地点。那么如何解决呢?

考虑到我们走过一个路径到达 ( i , j ) (i,j) (i,j) 点的时候,路径上经过的所有点我们都可以提前在那打工,显然我们在最赚钱的地方打工。对这个打工地点,我们如果在 ( i , j ) (i,j) (i,j) 上需要钱,那么之前离开这个打工地点之前,可以先不走,留下来多赚几天钱。也就是说我们相当于可以随时随地回到前面路径上的任何一个点来赚钱。

但是我们并不知道我们是如何到达 ( i , j ) (i,j) (i,j) 的,自然也不知道路径上有什么点。但是我们只关心经过的最赚钱的那个地点,也就是我们返回前面打工的地点,加上这题可以跑 N 4 N^4 N4 ,那么我们就可以把这个点放进 d p dp dp 里,具体来说,设 d p [ i ] [ j ] [ x ] [ y ] dp[i][j][x][y] dp[i][j][x][y] 表示到达 ( i , j ) (i,j) (i,j) 并在 ( x , y ) (x,y) (x,y) 打工的最少花费时间和最多剩余金钱。

这里 d p dp dp 是个 p a i r pair pair 类型,存储最少花费时间和最多剩余金钱。那么哪种值算最优?答案是花费时间最少的最优,其次剩余金钱最多的最优。因为我们可以随时回去赚钱,所以我们不挣闲钱,只要钱够就绝对不多花一天时间挣钱。因为我们推最优状态的最优推理时,经过的路径上的点一定是越来越挣钱的,你转移过来的时候剩余的最多的金钱最多不会超过前面路径上的 最赚钱地点上 一天赚的钱,也就小于在 ( x , y ) (x,y) (x,y) 上一天赚的钱,花费时间少的多花一天时间在 ( x , y ) (x,y) (x,y) 挣钱,手上的钱一定更多。因此这样排序是正确的。

d p [ i ] [ j ] [ x ] [ y ] dp[i][j][x][y] dp[i][j][x][y] 可以由 d p [ i − 1 ] [ j ] [ x ] [ y ] dp[i-1][j][x][y] dp[i1][j][x][y] d p [ i ] [ j − 1 ] [ x ] [ y ] dp[i][j-1][x][y] dp[i][j1][x][y] 转移得到,而转移过来时,分别需要花费 D [ i − 1 ] [ j ] D[i-1][j] D[i1][j] R [ i ] [ j − 1 ] R[i][j-1] R[i][j1] 的代价,这时候就可能需要去 ( x , y ) (x,y) (x,y) 赚钱。

假设从 d p [ i − 1 ] [ j ] [ x ] [ y ] dp[i-1][j][x][y] dp[i1][j][x][y] 转移过来,设在 ( i , j ) (i,j) (i,j) 这里花费了 t m tm tm 时间挣钱,手上剩余 l s t lst lst 钱,挣钱效率 c = P [ x ] [ y ] c=P[x][y] c=P[x][y],转移代价 w = D [ i − 1 ] [ j ] w=D[i-1][j] w=D[i1][j],需要花费 k k k 天来赚钱,就有: l s t + k ∗ c − w ≥ 0 lst+k*c-w\ge 0 lst+kcw0 k ≥ w − l s t c k\ge \frac{w-lst}{c} kcwlst k = ⌈ w − l s t c ⌉ k=\left\lceil\frac{w-lst}{c}\right\rceil k=cwlst

另外我们在 ( i , j ) (i,j) (i,j) 的时候,可以把之后挣钱的地点改为 ( i , j ) (i,j) (i,j),这时 d p [ i ] [ j ] [ i ] [ j ] dp[i][j][i][j] dp[i][j][i][j] 可以由所有 d p [ i ] [ j ] [ x ] [ y ] ( 1 ≤ x ≤ i , 1 ≤ y ≤ j ) dp[i][j][x][y]\quad(1\le x\le i,1\le y\le j) dp[i][j][x][y](1xi,1yj) 推过来。

code:

#include <iostream>
#include <cstdio>
#include <queue>
#define mk make_pair
using namespace std;
typedef long long ll;
const int maxn=85;
const ll inf=1e18;int n;
vector<vector<ll> > P(maxn,vector<ll>(maxn));
vector<vector<ll> > R(maxn,vector<ll>(maxn));
vector<vector<ll> > D(maxn,vector<ll>(maxn));vector<vector<vector<vector<pair<ll,ll> > > > > dp(maxn,vector<vector<vector<pair<ll,ll> > > >(maxn,vector<vector<pair<ll,ll> > >(maxn,vector<pair<ll,ll> >(maxn,mk(inf,0)))));pair<ll,ll> g(pair<ll,ll> x,pair<ll,ll> y){if(x.first!=y.first)return (x.first<y.first)?x:y;return (x.second>y.second)?x:y;
}int main(){cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>P[i][j];for(int i=1;i<=n;i++)for(int j=1;j<n;j++)cin>>R[i][j];for(int i=1;i<n;i++)for(int j=1;j<=n;j++)cin>>D[i][j];dp[1][1][1][1]=mk(0,0);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int x=1;x<=i;x++){for(int y=1;y<=j;y++){ll k,c,tm,lst,w;if(i>1 && i-1>=x){tm=dp[i-1][j][x][y].first;//花了多少时间 lst=dp[i-1][j][x][y].second;//剩了多少钱 w=D[i-1][j];//走过来需要花的钱 c=P[x][y];//挣钱的效率 k=max(0ll,(w-lst+c-1)/c);//需要花多长时间挣钱 dp[i][j][x][y]=g(dp[i][j][x][y],mk(tm+k+1,lst+k*c-w));}if(j>1 && j-1>=y){tm=dp[i][j-1][x][y].first;lst=dp[i][j-1][x][y].second;w=R[i][j-1];c=P[x][y];k=max(0ll,(w-lst+c-1)/c);dp[i][j][x][y]=g(dp[i][j][x][y],mk(tm+k+1,lst+k*c-w));}dp[i][j][i][j]=g(dp[i][j][i][j],dp[i][j][x][y]);}}}}cout<<dp[n][n][n][n].first<<endl;return 0;
}

这篇关于Toyota Programming Contest 2024#3(AtCoder Beginner Contest 344)(A,B,C,D,E,F)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/794227

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

高效录音转文字:2024年四大工具精选!

在快节奏的工作生活中,能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候,一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具! 365在线转文字 直达链接:https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具,它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件,只

2024网安周今日开幕,亚信安全亮相30城

2024年国家网络安全宣传周今天在广州拉开帷幕。今年网安周继续以“网络安全为人民,网络安全靠人民”为主题。2024年国家网络安全宣传周涵盖了1场开幕式、1场高峰论坛、5个重要活动、15场分论坛/座谈会/闭门会、6个主题日活动和网络安全“六进”活动。亚信安全出席2024年国家网络安全宣传周开幕式和主论坛,并将通过线下宣讲、创意科普、成果展示等多种形式,让广大民众看得懂、记得住安全知识,同时还

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快

免费也能高质量!2024年免费录屏软件深度对比评测

我公司因为客户覆盖面广的原因经常会开远程会议,有时候说的内容比较广需要引用多份的数据,我记录起来有一定难度,所以一般都用录屏工具来记录会议内容。这次我们来一起探索有什么免费录屏工具可以提高我们的工作效率吧。 1.福晰录屏大师 链接直达:https://www.foxitsoftware.cn/REC/  录屏软件录屏功能就是本职,这款录屏工具在录屏模式上提供了多种选项,可以选择屏幕录制、窗口