首页 > 其他分享 >トヨタ自動車プログラミングコンテスト2024#9（ABC370）

トヨタ自動車プログラミングコンテスト2024#9（ABC370）

时间：2024-09-08 17:26:21浏览次数：9  
标签：自動車 void sym 2024 int read getchar ABC370 define

A.Raise Both Hands \(\texttt{Diff }11\)

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define void inline void
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define test(i) cout<<"test: "<<i<<endl
#define testp(i,j) cout<<i<<" "<<j<<endl
#define testd(i) cout<<i<<" "
#define end cout<<"\n"
#define div <<" "<<
#else
#define test(i)
#define testp(i,j)
#define testd(i)
#define end false
#define div ,
#endif
template<typename T>
void read(T& x){
	x=0;bool sym=0;char c=getchar();
    while(!isdigit(c)){sym^=(c=='-');c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    if(sym)x=-x;
}
template<typename T,typename... Args>
void read(T& x,Args&... args){
    read(x);read(args...);
}
int main(){
	int l,r;
	cin>>l>>r;
	if(l==1 and r!=1){
		cout<<"Yes";
	}
	else if(l!=1 and r==1){
		cout<<"No";
	}
	else{
		cout<<"Invalid";
	}
}

B.Binary Alchemy \(\texttt{Diff }84\)

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define void inline void
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define test(i) cout<<"test: "<<i<<endl
#define testp(i,j) cout<<i<<" "<<j<<endl
#define testd(i) cout<<i<<" "
#define end cout<<"\n"
#define div <<" "<<
#else
#define test(i)
#define testp(i,j)
#define testd(i)
#define end false
#define div ,
#endif
template<typename T>
void read(T& x){
	x=0;bool sym=0;char c=getchar();
    while(!isdigit(c)){sym^=(c=='-');c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    if(sym)x=-x;
}
template<typename T,typename... Args>
void read(T& x,Args&... args){
    read(x);read(args...);
}
int n;
int a[101][101];
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=i;++j){
			cin>>a[i][j];
		}
	}
	int st=1;
	for(int i=1;i<=n;++i){
		if(st>=i){
			st=a[st][i];
		}
		else{
			st=a[i][st];
		}
	}
	cout<<st<<endl;
	
}

C.Word Ladder \(\texttt{Diff }228\)

给你两个字符串 \(S,T\)，长度相等，要求你每次改变 \(S\) 一个字符，最后令 \(S=T\)，要求在过程中的每一步都使 \(S\) 字典序尽可能最小，输出过程

考虑到当 \(S_{i}\lt T_{i}\) 的时候应该最先改，否则应该最后改. 因此正着遍历一遍跑出 \(S_{i}\lt T_{i}\) 的，剩下的倒着跑出来即可.

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define void inline void
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define test(i) cout<<"test: "<<i<<endl
#define testp(i,j) cout<<i<<" "<<j<<endl
#define testd(i) cout<<i<<" "
#define end cout<<"\n"
#define div <<" "<<
#else
#define test(i)
#define testp(i,j)
#define testd(i)
#define end false
#define div ,
#endif
template<typename T>
void read(T& x){
	x=0;bool sym=0;char c=getchar();
    while(!isdigit(c)){sym^=(c=='-');c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    if(sym)x=-x;
}
template<typename T,typename... Args>
void read(T& x,Args&... args){
    read(x);read(args...);
}
string s,t;
vector<string>ss;
int main(){
	cin>>s>>t;
	while(s!=t){
		for(int i=0;i<=s.length()-1;++i){
			if(s[i]>t[i]){
				s[i]=t[i];
				ss.push_back(s);
			}
		}
		for(int i=s.length()-1;i>=0;--i){
			if(s[i]<t[i]){
				s[i]=t[i];
				ss.push_back(s);
			}
		}
	}
	cout<<ss.size()<<endl;
	for(string i:ss) cout<<i<<endl;
}

D.Cross Explosion \(\texttt{Diff }1088\)

给定 \(H\times W\) 的矩阵，初始全是墙，\(Q\) 次询问，每次给出一个坐标 \((x,y)\) 进行如下操作：

  • 若 \((x,y)\) 是墙，直接摧毁
  • 否则，摧毁 \((x,y)\) 在上下左右四个方向上距离最近的墙，该方向上没有墙则不摧毁

求最终的墙数

\(H\times W\le 4\times 10^{5},Q\le 2\times 10^{5}\)

考察对 STL 的用法

考虑对横行和数列分别建 set，记录当前行/列存在墙的坐标，每次删除的时候，只需要进入对应行/列的 set 直接查找删除即可

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define void inline void
 #define ONLINE_JUDGE
//#ifndef ONLINE_JUDGE
//#define test(i) cout<<"test: "<<i<<endl
//#define testp(i,j) cout<<i<<" "<<j<<endl
//#define testd(i) cout<<i<<" "
//#define div <<" "<<
//#else
//#define test(i)
//#define testp(i,j)
//#define testd(i)
//#define end false
//#define div ,
//#endif
template<typename T>
void read(T& x){
	x=0;bool sym=0;char c=getchar();
    while(!isdigit(c)){sym^=(c=='-');c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    if(sym)x=-x;
}
template<typename T,typename... Args>
void read(T& x,Args&... args){
    read(x);read(args...);
}
int n,m,q;
set<int>mp[400001],mp2[400001];
int main(){
	read(n,m,q);
	int ans=n*m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			mp[i].insert(j);
			mp2[j].insert(i);
		}
	}
	while(q--){
		int x,y;
		read(x,y);
		auto it=mp[x].lower_bound(y);
		if(it!=mp[x].end() and *it==y){
			mp[x].erase(it);
			mp2[y].erase(mp2[y].lower_bound(x));
			ans--;
		}
		else{
			if(it!=mp[x].begin()){
				it--;
				mp2[*it].erase(mp2[*it].lower_bound(x));
				mp[x].erase(it);
				ans--;
			}
			auto it2=mp[x].upper_bound(y);
			if(it2!=mp[x].end()){
				mp2[*it2].erase(mp2[*it2].lower_bound(x));
				mp[x].erase(it2);
				ans--;
			}
			auto it3=mp2[y].lower_bound(x);
			if(it3!=mp2[y].begin()){
				it3--;
				mp[*it3].erase(mp[*it3].lower_bound(y));
				mp2[y].erase(it3);
				ans--;
			}
			auto it4=mp2[y].upper_bound(x);
			if(it4!=mp2[y].end()){
				mp[*it4].erase(mp[*it4].lower_bound(y));
				mp2[y].erase(it4);
				ans--;
			}
		}
	}
	cout<<ans<<endl;
}

需要注意 set 一定要用内置的 lower_bound() 函数！！ ，否则复杂度直接多一个 \(n\log n\)

本题还有并查集做法，参见 \(\color{Red}\text{l}\color{black}\text{xyt}\ 大佬\) 的提交

E.Avoid K Partition \(\texttt{Diff }1453\)

给定一个数列，划分为若干非空子序列，要求没有任何子序列的和等于 \(K\)，求方案数

\(N\le 2\times 10^{5}\)

考虑设计 \(f_{i}\) 表示考虑前 \(i\) 位的方案数，那么我们在从大到小枚举 \(i\) 的同时寻找断点，容易得到

\[f_{i}=\sum\{f_{j}[sum_{i}-sum_{j}\neq K]\} \]

其中 \(sum\) 为前缀和数组.

因此有了 \(n^{2}\) 的解法，注意到 \(sum_{i}-sum_{j}=K\) 的数极少，因此可以提前处理出 \(\sum_{j}^{i-1}f_{j}\)，然后直接减去不合法的即可，寻找不合法元素可以用 set 实现，复杂度 \(O(n\log n)\)

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define void inline void
template<typename T>
void read(T& x){
	x=0;bool sym=0;char c=getchar();
    while(!isdigit(c)){sym^=(c=='-');c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    if(sym)x=-x;
}
template<typename T,typename... Args>
void read(T& x,Args&... args){
    read(x);read(args...);
}
#define tests int cases;read(cases);while(cases--)
#define pb bush_back
const int p=998244353;
long long n,k,a[200001];
int main(){
	read(n,k);
	for(int i=1;i<=n;++i){
		read(a[i]);
	}
	map<long long,long long>mp;
	mp[0]=1;
	long long ans=1;
	long long sum=0;
	for(int i=1;i<=n;++i){
		sum+=a[i];
    	int res;
		if(mp.count(sum-k)) res=ans-mp[sum-k];
		else res=ans;
    	mp[sum]=(mp[sum]+res+p)%p;
		ans=(ans+res+p)%p;
    	if(i==n) cout<<((res+p)%p)<<endl;
	}
}

F.Cake Division

\(N\) 个元素的环形数列，分成 \(K\) 个连续段，最大化每个连续段和的最小值

并且求出在所有可能的方案中，哪两个元素在所有方案中都在同一个连续段内

\(N\le 2\times 10^{5}\)

标签：自動車,void,sym,2024,int,read,getchar,ABC370,define
From： https://www.cnblogs.com/HaneDaCafe/p/18403151

相关文章

  • 【2024华为杯E题】中国研究室数学建模竞赛E题思路+代码+论文
    订阅本专栏，认真钻研，保省级及以上奖项！若无获奖，本博主免费提供任意两份本博客初级版专栏代码！......
  • 【2024华为杯B题】中国研究室数学建模竞赛B题思路+代码+论文
    订阅本专栏，认真钻研，保省级及以上奖项！若无获奖，本博主免费提供任意两份本博客初级版专栏代码！......
  • LOJ4218 「IOI2024」尼罗河船运 题解
    题目描述有\(n\)件手工艺品，第\(i\)件重量为\(w_i\)，有参数\(a_i\)和\(b_i\)。每艘船最多可以运输两件手工艺品：如果只运输第\(i\)件，重量没有要求，代价为\(a_i\)。如果同时运输第\(i\)和第\(j\)件，要求\(|w_i-w_j|\leD\)，代价\(b_i+b_j\)。\(q\)次询问，给......
  • 利用ChatGPT完成2024 年高教社杯全国大学生数学建模竞赛题目【A/B/C/D/E题】完整思路
    利用ChatGPT来辅助数学建模比赛，可以帮助你加快建模、数据分析、算法设计等过程。以下是一些具体的步骤，结合ChatGPT的能力，如何在不同类型的数学建模问题中使用它。使用网站：https://new.chatgpt-plus.top/1.数据预处理与分析在数学建模比赛中，常常会遇到复杂的数据处......
  • 20240911_190441 公共基础 栈
    什么是栈栈的特点栈的出入演练习题31习题30习题b习题b习题习题a习题c......
  • ZR 2024 NOIP 十连 & CSP 七连
    NOIPday1T1简单建图跑bfs，vector会被卡空间，用前向星才能过。T2注意到原串是否确定不重要，因为无非是把每种可能的转移都多做一遍。把所有可能出现的回文串的一半插进AC自动机中，就可以转移了。CSPday1T3设\(nxt_i\)表示下一个与\(a_i\)值相同的位置到\(i\)的距......
  • 【赛后总结】トヨタ自動車プログラミングコンテスト2024#9（待补完）
    AtCoderBeginnerContest370赛后总结成绩速览：展开目录目录AtCoderBeginnerContest370赛后总结ARaiseBothHands-100ptsBBinaryAlchemy-200ptsCWordLadder-300ptsARaiseBothHands-100pts展开翻译高桥君决定制作章鱼烧，并给苏介君吃。他告诉苏介君，如果想......
  • NOIP2024模拟赛5 总结
    NOIP2024模拟赛5总结T1天才俱乐部特判了\(sum-s<0\)，但没有考虑\(sum-s=0\)。挂为0pts。T2实战教学由于写的不够优，贪心+二分的思路TLE了。由于不明原因，输出\(\max(a_i+b_i)\)能过。非常神奇。T3穿越银匙之门T4绳网委托一句话总结：挂分挂成sb了。......
  • 一键解锁创意未来：AE 2024最新版安装包下载及安装教程
    一键解锁创意未来：AE 2024最新版安装包下载及安装教程一键解锁创意未来：AE2024最新版安装包下载及安装教程在数字创意领域，AdobeAfterEffects（简称AE）一直是行业标杆，为无数设计师、动画师和视频编辑者提供了强大的工具，帮助他们将创意变为现实。随着技术的不断进步，Adobe公司也在不断......
  • 官方直链，安全高效：After Effects 2024安装包下载与安装教程
    官方直链，安全高效：After Effects 2024安装包下载与安装教程官方直链，安全高效：AfterEffects2024安装包下载与安装教程AdobeAfterEffects2024是一款强大的视频后期制作软件，广泛应用于电影、电视、广告等领域。它提供了丰富的特效和动画工具，帮助用户创建令人惊叹的视觉效果。本......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99