TOYOTA SYSTEMS Programming Contest 2024（AtCoder Beginner Contest 377)A-D题解
TOYOTA SYSTEMS Programming Contest 2024（AtCoder Beginner Contest 377)
A - Rearranging ABC
Problem Statement
You are given a string \(S\) of length \(3\) consisting of uppercase English letters.
Determine whether it is possible to rearrange the characters in \(S\) to make it match the string ABC.
根据题意求解即可
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define TLE (double)clock() / CLOCKS_PER_SEC <= 0.95
#define int long long
#define double long double
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 1e6 + 5, M = 1e6 + 5, S = 1e6 + 5, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int a, b, x;
map<char,int>mp;
void solve()
{
string s;
cin>>s;
for(auto i:s){
mp[i]=1;
}
if(mp['A']==0){
cout<<"No"<<endl;
return;
}
if(mp['C']==0){
cout<<"No"<<endl;
return;
}
if(mp['B']==0){
cout<<"No"<<endl;
return;
}
cout<<"Yes"<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
for (int i = 1; i <= T; i++)
{
solve();
}
return 0;
}
B - Avoid Rook Attack
Problem Statement
There is a grid of \(64\) squares with \(8\) rows and \(8\) columns. Let \((i,j)\) denote the square at the \(i\)-th row from the top \((1\leq i\leq8)\) and \(j\)-th column from the left \((1\leq j\leq8)\).
Each square is either empty or has a piece placed on it. The state of the squares is represented by a sequence \((S_1,S_2,S_3,\ldots,S_8)\) of \(8\) strings of length \(8\). Square \((i,j)\) \((1\leq i\leq8,1\leq j\leq8)\) is empty if the \(j\)-th character of \(S_i\) is ., and has a piece if it is #.
You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.
A piece placed on square \((i,j)\) can capture pieces that satisfy either of the following conditions:
- Placed on a square in row \(i\)
- Placed on a square in column \(j\)
For example, a piece placed on square \((4,4)\) can capture pieces placed on the squares shown in blue in the following figure:
How many squares can you place your piece on?
开两个数组，记录可以吃到的行和列，然后遍历找出行和列都不能被吃到的点即可
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define TLE (double)clock() / CLOCKS_PER_SEC <= 0.95
#define int long long
#define double long double
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 1e6 + 5, M = 1e6 + 5, S = 1e6 + 5, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int a, b, x;
char arr[10][10];
int vis1[10];
int vis2[10];
void solve()
{
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
cin>>arr[i][j];
if(arr[i][j]=='#'){
vis1[i]=1;
vis2[j]=1;
}
}
}
int ans = 0;
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
if(vis1[i]==0&&vis2[j]==0){
ans++;
}
}
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
for (int i = 1; i <= T; i++)
{
solve();
}
return 0;
}
C - Avoid Knight Attack
Problem Statement
There is a grid of \(N^2\) squares with \(N\) rows and \(N\) columns. Let \((i,j)\) denote the square at the \(i\)-th row from the top \((1\leq i\leq N)\) and \(j\)-th column from the left \((1\leq j\leq N)\).
Each square is either empty or has a piece placed on it. There are \(M\) pieces placed on the grid, and the \(k\)-th \((1\leq k\leq M)\) piece is placed on square \((a_k,b_k)\).
You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.
A piece placed on square \((i,j)\) can capture pieces that satisfy any of the following conditions:
- Placed on square \((i+2,j+1)\)
- Placed on square \((i+1,j+2)\)
- Placed on square \((i-1,j+2)\)
- Placed on square \((i-2,j+1)\)
- Placed on square \((i-2,j-1)\)
- Placed on square \((i-1,j-2)\)
- Placed on square \((i+1,j-2)\)
- Placed on square \((i+2,j-1)\)
Here, conditions involving non-existent squares are considered to never be satisfied.
For example, a piece placed on square \((4,4)\) can capture pieces placed on the squares shown in blue in the following figure:
How many squares can you place your piece on?
一共有\(n^{2}\)个格子。把题目中给的棋子和它们能吃到的点全部扔到一个set里，输出\(n^{2}-set.size()\)即可
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define TLE (double)clock() / CLOCKS_PER_SEC <= 0.95
#define int long long
#define double long double
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 1e6 + 5, M = 1e6 + 5, S = 1e6 + 5, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void solve()
{
int n,m;
cin>>n>>m;
set<pii>mp;
while(m--){
int i,j;
cin>>i>>j;
pii temp ={i,j};
mp.emplace(temp);
int x1,y1;
x1 = i+2,y1=j+1;
if(x1>=1&&x1<=n&&y1>=1&&y1<=n){
pii temp ={x1,y1};
mp.emplace(temp);
}
x1=i+1,y1=j+2;
if(x1>=1&&x1<=n&&y1>=1&&y1<=n){
pii temp ={x1,y1};
mp.emplace(temp);
}
x1=i-1,y1=j+2;
if(x1>=1&&x1<=n&&y1>=1&&y1<=n){
pii temp ={x1,y1};
mp.emplace(temp);
}
x1=i-2,y1=j+1;
if(x1>=1&&x1<=n&&y1>=1&&y1<=n){
pii temp ={x1,y1};
mp.emplace(temp);
}
x1=i-2,y1=j-1;
if(x1>=1&&x1<=n&&y1>=1&&y1<=n){
pii temp ={x1,y1};
mp.emplace(temp);
}
x1=i-1,y1=j-2;
if(x1>=1&&x1<=n&&y1>=1&&y1<=n){
pii temp ={x1,y1};
mp.emplace(temp);
}
x1=i+1,y1=j-2;
if(x1>=1&&x1<=n&&y1>=1&&y1<=n){
pii temp ={x1,y1};
mp.emplace(temp);
}
x1=i+2,y1=j-1;
if(x1>=1&&x1<=n&&y1>=1&&y1<=n){
pii temp ={x1,y1};
mp.emplace(temp);
}
}
int g = mp.size();
cout<<n*n-g<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
for (int o = 1; o <= T; o++)
{
solve();
}
return 0;
}
D - Many Segments 2
Problem Statement
You are given two sequences of positive integers of length \(N\), \(L=(L_1,L_2,\ldots,L_N)\) and \(R=(R_1,R_2,\ldots,R_N)\), and an integer \(M\).
Find the number of pairs of integers \((l,r)\) that satisfy both of the following conditions:
- \(1\le l \le r \le M\)
- For every \(1\le i\le N\), the interval \([l,r]\) does not completely contain the interval \([L_i,R_i]\).
对于每一个点，在1到这个点这段区间可以形成的小区间个数就是 \(i\)（题意中自己也可以,所以要加上自己）。如果这段区间中包含了一个题目中给出的不能包含的区间，那么形成的子区间数量就是 \(i-(l+1)+1\) ( \(l\) 是不能包含的那个区间的左端点)。假设中间包含了多个不能包含的区间，那么应该取左端点最大的那一个
一开始我们先把左端点记录到右端点上，然后向右扩散就行，一直取最大的即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n, m;
cin >> n >> m;
vector<int>l(n+1);
vector<int>r(n+1);
vector<int>ans(m+1,1);
for(int i=1;i<=n;i++){
cin>>l[i]>>r[i];
ans[r[i]] = max(ans[r[i]],l[i]+1);
}
for(int i=1;i<=m;i++){//向右扩散
ans[i] = max(ans[i],ans[i-1]);
}
int cnt = 0;
for(int i=1;i<=m;i++){
cnt+=(i-ans[i]+1);
}
cout<<cnt<<endl;
}