Toyota Programming Contest 2023#4（AtCoder Beginner Contest 311）（A-G）

Contest Duration: 2023-07-22(Sat) 20:00 - 2023-07-22(Sat) 21:40 (local time) (100 minutes)

头文件和宏

#include<iostream>
#include<string>
#include<vector>
using namespace std;
#define int long long
#define fer(i,a,b) for(int i=a;i<b;i++)
#define cf int T;cin>>T;while(T--)
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

以下只附主代码

A First ABC

从头开始，找出ABC三个字母都至少出现一次的最小长度

signed main(){
	IOS;
	int n;cin>>n;
	string s;cin>>s;
	bool fa=0,fb=0,fc=0;
	int cnt=0;
	fer(i,0,n){
		if(s[i]=='A')fa=1;
		else if(s[i]=='B')fb=1;
		else if(s[i]=='C')fc=1;
		if(fa&&fb&&fc){
			cnt=i;break;
		}
	}
	cout<<cnt+1;
	return 0;
}

B Vacation Together

找出n人均有空闲的最大天数

signed main(){
	IOS;
	int n,d;cin>>n>>d;
	bool f[d]={0};
	string s;
	fer(i,0,n){
		cin>>s;
		fer(j,0,d){
			if(s[j]=='x')f[j]=1;
		}
	}
	int cnt=0,mx=0;
	fer(i,0,d){
		if(f[i]==0){
			cnt++;
			mx=max(mx,cnt);
		}else cnt=0;
	}
	cout<<mx;
	return 0;
}

C Find it!

有向图，N个结点，N条边，一个结点只会指向另外一个结点，产生一条边。题目要求输出任意环。
这种方式形成的有向图一定有环，最小的环是M=2，最大的环是M=N，所以只要顺着找N+1次，必然会出现环，res里最后一个结点必然在环里。即使重复在一个环里循环也无妨，只需从后向前截取这个环作为结果。

const int N=2e5+5,mod=1e9+7;
int a[N];
signed main(){
	IOS;
	int n;cin>>n;
	fer(i,1,n+1)cin>>a[i];
	vector<int>res;res.clear();
	int j=1;
	res.pb(j);
	fer(i,0,n+1){
		res.pb(a[j]);
		j=a[j];
	}
	int k;
	for(int i=n-1;i>=0;i--){
		if(res[i]==res[n]){
			k=i;break;
		}
	}
	cout<<n-k<<endl;
	for(int i=k;i<n;i++){
		cout<<res[i]<<" ";
	}
	return 0;
}

D Grid Ice Floor

滑冰，如果玩过类似的4399小游戏会感到熟悉。
在冰面上只能朝指定方向滑行，直到遇到障碍物停下，中途不能改变方向。问最多能滑过多少块冰。问题在于：如何判定停止递归？不能只是单纯遇到走过的点就停止。比如下图中的红线是可以走的，但如果“遇到走过的点就停止”，那么就不会递归这条红线的情况，这是错误的。
请添加图片描述
因此我设置了两个布尔数组，f代表走过的点，用来计数；f2代表该点是否作为过停留的结点向四个方向递归，如果f2==1，那么我们不必重复去递归

int a[202][202];bool f[202][202],f2[202][202];
int cnt=0;
void solve(int x,int y,int op){//1上 2下 3左 4右 

	if(f[x][y]==0){
		cnt++;f[x][y]=1;
	}
	if(op==0&&f2[x][y]==0){
		f2[x][y]=1;
		if(a[x-1][y])solve(x-1,y,1);
		if(a[x+1][y])solve(x+1,y,2);
		if(a[x][y-1])solve(x,y-1,3);
		if(a[x][y+1])solve(x,y+1,4);
		return;
	}else if(op==1){
		if(a[x-1][y])solve(x-1,y,1);
		else solve(x,y,0);
	}else if(op==2){
		if(a[x+1][y])solve(x+1,y,2);
		else solve(x,y,0);
	}else if(op==3){
		if(a[x][y-1])solve(x,y-1,3);
		else solve(x,y,0);
	}else if(op==4){
		if(a[x][y+1])solve(x,y+1,4);
		else solve(x,y,0);
	}
}
signed main(){
	IOS;
	int n,m;cin>>n>>m;
	string s;
	fer(i,0,n){
		cin>>s;
		fer(j,0,m){
			if(s[j]=='.')a[i+1][j+1]=1;
		}
	}
	solve(2,2,0);
	cout<<cnt<<endl;
//	fer(i,1,n+1){
//		fer(j,1,m+1)cout<<f[i][j]<<" ";
//		cout<<endl;
//	}
	return 0;
}

下面是非递归的版本，用的是队列，这种方式开销较小

vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
int main(){
  int N, M;
  cin >> N >> M;
  vector<string> S(N);
  for (int i = 0; i < N; i++){
    cin >> S[i];
  }
  vector<vector<bool>> used(N, vector<bool>(M, false));
  used[1][1] = true;
  vector<vector<bool>> used2(N, vector<bool>(M, false));
  used2[1][1] = true;
  queue<pair<int, int>> Q;
  Q.push(make_pair(1, 1));
  while (!Q.empty()){
    int x = Q.front().first;
    int y = Q.front().second;
    Q.pop();
    for (int i = 0; i < 4; i++){
      int x2 = x, y2 = y;
      while (S[x2 + dx[i]][y2 + dy[i]] == '.'){
        x2 += dx[i];
        y2 += dy[i];
        used2[x2][y2] = true;
      }
      if (!used[x2][y2]){
        used[x2][y2] = true;
        Q.push(make_pair(x2, y2));
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < N; i++){
    for (int j = 0; j < M; j++){
      if (used2[i][j]){
        ans++;
      }
    }
  }
  
  cout << ans << endl;
  for (int i = 0; i < N; i++){
    for (int j = 0; j < M; j++){
      cout<<used2[i][j]<<" ";
      }
      cout<<endl;
    }
    return 0;
}

参考：Submission #43834581

E Defect-free Squares

问无洞正方形有多少个。动态规划
dp初始化为最大值3000+

  • 如果该点是洞，该点dp[i][j]=0；
  • 如果不是：
    • 如果是最底下一行和最右面一列，dp[i][i]=1
    • 如果不是：dp[i][i]=min(dp ,dp[i+1][j]+1,dp[i][j+1]+1,dp[i+1][j+1]+1)，也就是取（自身、右面+1、下面+1、右下+1）中的最小值。

如果右面或者下面是洞，都影响自身构建无洞正方形

bool f[3001][3001];
int dp[3001][3001];
signed main(){
	IOS;
	int h,w,n;cin>>h>>w>>n;
	int a,b;
	fer(i,1,n+1){
		cin>>a>>b;
		f[a][b]=1;
	}
	fer(i,1,h+1){
		fer(j,1,w+1)dp[i][j]=3005;
	}

	int sum=0;
	for(int i=h;i>=1;i--){
		for(int j=w;j>=1;j--){
			if(i==h||j==w)dp[i][j]=1;
			if(i<h)dp[i][j]=min(dp[i][j],dp[i+1][j]+1);
			if(j<w)dp[i][j]=min(dp[i][j],dp[i][j+1]+1);
			if(i<h&&j<w)dp[i][j]=min(dp[i][j],dp[i+1][j+1]+1);
			if(f[i][j])dp[i][j]=0;
			sum+=dp[i][j];	
		}
	} 
	cout<<sum<<endl;
	return 0;
}

参考：Submission #43837221

F Yet Another Grid Task

给一个网格，有黑块有白块。小明要把白块涂成黑块使得网格变beautiful,beautiful的定义如下：一个黑块的下面一块和右下角的一块也是黑块。问有多少种涂法。
动态规划，dp初始化为1，按列dp，对每列找到黑块出现的最早一次位置，在这位置之后的块的可能次数均为0（因为黑块之下必须是黑块，已经被定好了），在这位置之前的块，可能次数是自身的可能次数+下方块的可能次数，然后dp整体下移

const int N=2e5+1,mod=998244353;
signed main(){
	IOS;
	int n,m;cin>>n>>m;
	vector<string>s(n);
	fer(i,0,n)cin>>s[i];
	vector<int> dp(n+1,1);
	fer(i,0,m){
		int x=0;
		while(x<n&&s[x][i]=='.')x++;
		for(int j=x+1;j<=n;j++){
			dp[j]=0;
		}
		for(int j=n-1;j>=0;j--){
			dp[j]+=dp[j+1];
			dp[j]%=mod;
		}
		for(int j=n;j>0;j--){
			dp[j]=dp[j-1];
			dp[j]%=mod;
		}
	} 
	cout<<dp[0];
	return 0;
}

参考：Submission #43851107

G One More Grid Task

在网格内拉一个矩形，求(矩形内和x矩形内最小值)的最大值
s存放该列数字的和，t存放该列数字的最小值，待想

signed main(){
	IOS;
	int n,m;cin>>n>>m;
	vector<vector<int> > a(n,vector<int>(m));
	fer(i,0,n){
		fer(j,0,m)cin>>a[i][j];
	}
	int ans=0;
	fer(u,0,n){
		vector<int>s(m),t(m,1e9);
		fer(d,u,n){
			fer(i,0,m){
				s[i]+=a[d][i];
				t[i]=min(a[d][i],t[i]);
			}
			vector<int> l(m,-1),r(m,m),stk;
			fer(i,0,m){
				while(!stk.empty()&&t[i]<t[stk.back()]){
					r[stk.back()]=i;
					stk.pop_back();
				}
				if(!stk.empty())l[i]=stk.back();
				stk.pb(i);
			}
			vector<int> pre(m+1);
			fer(i,0,m)pre[i+1]=pre[i]+s[i];
			fer(i,0,m)ans=max(ans,t[i]*(pre[r[i]]-pre[l[i]+1]));
		}
	}
	cout<<ans;
	return 0;
}

参考：Submission #43853592

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/45873.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【时间复杂度】

【时间复杂度】

旋转数组 题目 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 k 是非负数。 /* 解题思路&#xff1a;使用三次逆转法&#xff0c;让数组旋转k次 1. 先整体逆转 // 1,2,3,4,5,6,7 // 7 6 5 4 3 2 1 2. 逆转子数组[0, k - 1] // 5 6 7 4 3…
阅读更多...
Pytorch个人学习记录总结 03

Pytorch个人学习记录总结 03

目录 Transeforms的使用 常见的transforms Transeforms的使用 torchvision中的transeforms&#xff0c;主要是对图像进行变换&#xff08;预处理&#xff09;。from torchvision import transforms transeforms中常用的就是以下几种方法&#xff1a;&#xff08;Alt7可唤出…
阅读更多...
多源BFS-- 矩阵距离

多源BFS-- 矩阵距离

关于多源BFS&#xff0c;基本上就是单源BFS的简单升级了一下&#xff0c;比如在queue中队头开始时只有一个&#xff0c;我们通过这一个队头去推导其他的东西。而多源最短路就是队头一开始有1-n个可能的数&#xff0c;一个一个去BFS。 题目思路&#xff1a; 这个题就直接把所有的…
阅读更多...
0成本搭建自己的云数据库

0成本搭建自己的云数据库

第一步&#xff0c;租免费的云服务器 www.aliyun.com 阿里云的&#xff0c;可以免费租三个月 进入主页后选择云服务器ESC 选择这款&#xff0c;点击试用就行 第二步&#xff0c;配置服务器 在配置服务器系统的时候选择centos&#xff0c;省事&#xff0c;别选ubuntu&#x…
阅读更多...
[Spring] 三级缓存解决循环依赖详解

[Spring] 三级缓存解决循环依赖详解

什么是循环依赖 注册一个bean对象的过程&#xff1a; Spring扫描class得到BeanDefinition – 根据得到的BeanDefinition去生成bean – 现根据class推断构造方法 – 根据推断出来的构造方法&#xff0c;反射&#xff0c;得到一个对象 – 填充初始对象中的属性(依赖注入) – 如果…
阅读更多...
服务器中了360后缀勒索病毒，360后缀勒索病毒介绍解密数据恢复

服务器中了360后缀勒索病毒，360后缀勒索病毒介绍解密数据恢复

360后缀勒索病毒&#xff0c;是BeijingCrypt勒索家族中的一种勒索软件病毒&#xff0c;这种恶意软件一旦攻击了企业的服务器就会利用自身独特的加密技术来全盘扫描系统文件&#xff0c;并对用户的全部文件进行加密&#xff0c;并要求用户支付赎金以解锁文件。近期&#xff0c;我…
阅读更多...
C# 数据结构】Heap 堆

C# 数据结构】Heap 堆

【C# 数据结构】Heap 堆 先看看C#中有那些常用的结构堆的介绍完全二叉树最大堆 Heap对类进行排序实现 IComparable<T> 接口 对CompareTo的一点解释 参考资料 先看看C#中有那些常用的结构 作为 数据结构系类文章 的开篇文章&#xff0c;我们先了解一下C# 有哪些常用的数据…
阅读更多...
CNNdebug尝试

CNNdebug尝试

这算是啥问题&#xff1f;&#xff1f; 接着根据群里大佬提供的指示&#xff0c;将train和validate中的nums_work改成0即可 此处因为数据已经打乱了&#xff0c;所以在这里就不用打乱数据&#xff0c;把shuffle True修改成为False 后面查看指定目录下&#xff0c;竟然没有这个…
阅读更多...
性能测试工具 Jmeter 引入 jar 包踩过的坑

性能测试工具 Jmeter 引入 jar 包踩过的坑

目录 前言&#xff1a; Jmeter 中调用自己编写 jar 中的类出错 错误日志&#xff1a; 出现以上错误的原因&#xff1a; 解决方法&#xff1a; 前言&#xff1a; JMeter 是一种开源的性能测试工具&#xff0c;可以帮助我们快速地进行网站、应用程序等的性能测试和压力测试…
阅读更多...
20230720在ubuntu22.04系统下载+解密+合并ts切片的步骤（STEP-BY-STEP版本）

20230720在ubuntu22.04系统下载+解密+合并ts切片的步骤（STEP-BY-STEP版本）

20230720在ubuntu22.04系统下载解密合并ts切片的步骤&#xff08;STEP-BY-STEP版本&#xff09; 2023/7/20 23:06 https://app1ce7glfm1187.h5.xiaoeknow.com/v2/course/alive/l_64af6130e4b03e4b54da1681?type2&app_idapp1cE7gLFM1187&pro_idterm_645c69388953e_Nhew…
阅读更多...
C# List 详解七

C# List 详解七

目录 42.Sort() 43.ToArray() 44.ToString() 45.TrimExcess() 46.TrueForAll(Predicate) C# List 详解一 1.Add(T)&#xff0c;2.AddRange(IEnumerable)&#xff0c;3.AsReadOnly()&#xff0c;4.BinarySearch(T)&#xff0c; C# List 详解二 5.Cl…
阅读更多...
TEE GP(Global Platform)认证规范

TEE GP(Global Platform)认证规范

TEE之GP(Global Platform)认证汇总 一、GP认证规范库 二、TEE GP认证规范文档 如果需要TEE对应的GP认证规范文档&#xff0c;请按照下方选择框选择TEE&#xff0c;然后Search&#xff0c;共查询到31个相关规范文档。 参考&#xff1a; GlobalPlatform Certification - Global…
阅读更多...
[回馈]ASP.NET Core MVC开发实战之商城系统(一)

[回馈]ASP.NET Core MVC开发实战之商城系统(一)

经过一段时间的准备&#xff0c;新的一期【ASP.NET Core MVC开发实战之商城系统】已经开始&#xff0c;今天着重讲解布局设计&#xff0c;环境搭建&#xff0c;系统配置&#xff0c;及首页商品类型&#xff0c;banner条&#xff0c;友情链接等功能的开发。 首页布局设计 首页是…
阅读更多...
工程安全监测无线振弦采集仪在建筑物中的应用

工程安全监测无线振弦采集仪在建筑物中的应用

工程安全监测无线振弦采集仪在建筑物中的应用 工程安全监测无线振弦采集仪是一种用于建筑物结构安全监测的设备&#xff0c;它采用了无线传输技术&#xff0c;具有实时性强、数据精度高等优点&#xff0c;被广泛应用于建筑物结构的实时监测和预警。下面将从设备的特点、应用场…
阅读更多...
（原创）自定义DialogFragment以及解决其内存泄漏问题

（原创）自定义DialogFragment以及解决其内存泄漏问题

前言 日常开发中&#xff0c;dialog是常见的功能&#xff0c;我们时常需要弹出来一些弹框提示用户 今天就定义了一个方便的dialog基类BaseSimpleDialogFragment&#xff0c; 支持快速地显示一个dialog 主要功能有&#xff1a; initAnimation&#xff1a;设置入场和出场动画 ge…
阅读更多...
【C进阶】指针进阶(1)_二次复习版

【C进阶】指针进阶(1)_二次复习版

目录 1. 字符指针 1.1常量字符串的修改 加上const解决问题 打印常量字符串 1.2数组存放的字符串 1.3例题:数组创建与常量池的区别 2. 指针数组 2.1字符指针数组 2.2整型指针数组 2.3使用3个一维数组,模拟实现一个二维数组 2.4例题: 3.数组指针 3.1 数组指针的定义…
阅读更多...
同步网盘使用中的五大突出优势

同步网盘使用中的五大突出优势

同步网盘是一种流行的云存储解决方案&#xff0c;它可以将您本地计算机上的文件与云端存储空间同步&#xff0c;以保证文件的备份和访问。那么&#xff0c;同步网盘使用中的突出优势是什么呢&#xff1f;下面就为您详细介绍。 一、数据备份 同步网盘最大的优势之一就是可以自动…
阅读更多...
错误解决：Failed to create Spark client for Spark session

错误解决：Failed to create Spark client for Spark session

错误解决&#xff1a;Failed to create Spark client for Spark session "Failed to create Spark client for Spark session"的错误通常表示无法为Spark会话创建Spark客户端。这可能是由于以下一些常见问题导致的&#xff1a; Spark配置错误&#xff1a;请检查Spar…
阅读更多...
智慧园区楼宇合集：数字孪生管控系统

智慧园区楼宇合集：数字孪生管控系统

智慧园区是指将物联网、大数据、人工智能等技术应用于传统建筑和基础设施&#xff0c;以实现对园区的全面监控、管理和服务的一种建筑形态。通过将园区内设备、设施和系统联网&#xff0c;实现数据的传输、共享和响应&#xff0c;提高园区的管理效率和运营效益&#xff0c;为居…
阅读更多...
ubuntu开机自启动

ubuntu开机自启动

ubuntu开机自启动 1、建一个test.sh脚本&#xff0c;并写入 #!/bin/sh gnome-terminal -x bash -c ‘cd /home/文件路径/;python3 main.py’ exit 0 2、:wq!保存 3、创建rc-local.service文件&#xff08;sudo vim /etc/systemd/system/rc-local.service&#xff09;&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023