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;
}