Toyota Programming Contest 2023#4(AtCoder Beginner Contest 311)
A - First ABC (atcoder.jp)
记录一下\(ABC\)是否都出现过了然后输出下标
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int n;
string s;
cin >> n >> s;
bitset<3> v;
for(int i = 0;i < n;i ++){
v[s[i] - 'A'] = 1;
if(v[0] && v[1] && v[2]){
cout << i + 1<< endl;
break;
}
}
return 0;
}
B - Vacation Together (atcoder.jp)
数据范围小暴力寻找即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int n,d;
cin >> n >> d;
vector<string> g(n);
for (int i = 0; i < n; ++i) {
cin >> g[i];
}
int ans = 0;
for(int i = 0;i < d ;i++){
for(int j = d;j >= i; j--){
bool f = true;
for(auto k : g){
if(k.substr(i,j - i + 1) != string(j - i + 1,'o'))
f = false;
}
if(f) ans = max(ans, j - i + 1);
}
}
cout << ans << endl;
return 0;
}
还是jiangly的思路巧妙啊,用一个初始化全为\(true\)的bool数组就好了, 每次去跑一遍字符串,将对应位置\(x\)更新为\(false\),最后找出连续最长的\(true\)就好了,这个比暴力找快了7,8倍
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, D;
std::cin >> N >> D;
std::vector<bool> ok(D, true);
for (int i = 0; i < N; i++) {
std::string s;
std::cin >> s;
for (int j = 0; j < D; j++) {
if (s[j] == 'x') {
ok[j] = false;
}
}
}
int ans = 0;
int len = 0;
for (auto x : ok) {
len = x ? 1 + len : 0;
ans = std::max(ans, len);
}
std::cout << ans << "\n";
return 0;
}
C - Find it! (atcoder.jp)
题意就是找出一个环
哎,我还是传统dfs的
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int n;
cin >> n;
vector<int> g[n + 1];
vector<int> fa(n + 1);
iota(fa.begin(),fa.end(),0);
for(int i = 1,a ;i <= n;i ++){
cin >> a;
g[i].push_back(a);
}
bool ok = false;
vector<int> ans;
bitset<N> vis;
int len = 1;
function<void(int,int)> dfs = [&](int u,int v) -> void {
for(auto i : g[u]){
if(vis[i]){
int p = 0;
for(auto j : ans){
if(j != i)
p++;
else
break;
}
cout << len - p << endl;
for(int j = p;j < ans.size();j ++ ){
cout << ans[j] << ' ';
}
exit(0);
}
if(i == v) continue;
len++;
ans.push_back(i);
vis[i] = 1;
dfs(i,u);
len--;
vis[i] = 0;
ans.pop_back();
}
};
for(int i = 1;i <= n;i ++){
vis.reset();
len = 1;
vis[i] = 1;
ans.push_back(i);
dfs(i,i);
ans.pop_back();
}
return 0;
}
每日佩服jiangly(
他的思路很巧妙啊(或许是我太傻了,用一个链表的思路就解决了
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N;
std::cin >> N;
std::vector<int> A(N);
for (int i = 0; i < N; i++) {
std::cin >> A[i];
A[i]--;
}
std::vector<bool> vis(N);
int i = 0;
while (!vis[i]) {
vis[i] = true;
i = A[i];
}
int j = i;
std::vector<int> ans;
do {
ans.push_back(j);
j = A[j];
} while (j != i);
std::cout << ans.size() << "\n";
for (int i = 0; i < ans.size(); i++) {
std::cout << ans[i] + 1 << " \n"[i == ans.size() - 1];
}
return 0;
}
D - Grid Ice Floor (atcoder.jp)
借鉴jiangly,其实赛时我感觉咱的思路也和他很接近了,但是一直没调出来,看了jiangly的才发现他是一个vis数组判断是否走过,一个pass数组记录走过的路径,而我是一个vis数组将两个功能一起合体了(或许就是这里错了吧
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int n,m;
cin >> n >> m;
vector<string> g(n);
vector<bitset<320>> vis(320),pass(320);
for(auto &i : g) cin >> i;
int u[] = {0,0,-1,1};
int v[] = {1,-1,0,0};
queue<pair<int,int>> Q;
Q.emplace(1,1);
pass[1][1] = vis[1][1] = true;
while(Q.size()){
auto [x,y] = Q.front();
Q.pop();
for(int i = 0;i < 4;i ++){
int dx = x;
int dy = y;
while(g[dx][dy] == '.'){
pass[dx][dy] = true;
dx += u[i];
dy += v[i];
}
dx -= u[i];
dy -= v[i];
if(!vis[dx][dy]){
vis[dx][dy] = true;
Q.emplace(dx,dy);
}
}
}
int ans = 0;
for(int i = 1;i < n;i ++)
for(int j = 1;j < m;j ++)
ans += pass[i][j];
cout << ans << endl;
return 0;
}
- Contest Programming Beginner AtCoder Toyotacontest programming beginner atcoder contest programming securities beginner contest programming beginner registry contest programming beginner keyence contest programming beginner systems beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332