TOYOTA MOTOR CORPORATION Programming Contest 2023#2 (AtCoder Beginner Contest 302)
Contest Duration: 2023-05-20(Sat) 20:00 - 2023-05-20(Sat) 21:40 (local time) (100 minutes)
暴搜场，1个小时出了4道，以为很有机会，结果E交了十发没过
记得赛后补题
A Attack 2 sec 1024 MB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fer(i,a,b) for(int i=a;i<b;i++)
#define mem(x, y) memset(x, y, sizeof(x))
#define cf int T;cin>>T;while(T--)
const int N1=1e6+10,N2=1e14,mod=1e9+7;
const int INF=0x3f3f3f3f;
signed main(){
int a,b;cin>>a>>b;
int res=a/b;
if(a%b!=0)res++;
cout<<res;
return 0;
}
B Find snuke 2 sec 1024 MB
dfs找snuke，一开始题意理解错了，以为可以八个方向找，后来发现每次找只能固定一个方向
正解
char s[101][101];
bool f=0;
int dx[8]={0,0,-1,1,-1,-1,1,1};
int dy[8]={1,-1,0,0,-1,1,-1,1};
int n,m;
char target[5]={'s','n','u','k','e'};
int res[5][2];
void dfs(int i,int j,int t,int t1){
if(t==5){
f=1;return;
}
if(t1==-1){
fer(k,0,8){
if(!f&&i+dx[k]>=0&&i+dx[k]<n&&j+dy[k]>=0&&j+dy[k]<m){
if(s[i+dx[k]][j+dy[k]]==target[t]){
res[t][0]=i+dx[k];
res[t][1]=j+dy[k];
dfs(i+dx[k],j+dy[k],t+1,k);
}
}
}
}else{
if(!f&&i+dx[t1]>=0&&i+dx[t1]<n&&j+dy[t1]>=0&&j+dy[t1]<m){
if(s[i+dx[t1]][j+dy[t1]]==target[t]){
res[t][0]=i+dx[t1];
res[t][1]=j+dy[t1];
dfs(i+dx[t1],j+dy[t1],t+1,t1);
}
}
}
}
signed main(){
cin>>n>>m;
fer(i,0,n){
cin>>s[i];
}
fer(i,0,n){
fer(j,0,m){
if(s[i][j]=='s'&&!f){
res[0][0]=i;res[0][1]=j;
dfs(i,j,1,-1);
}
}
}
fer(i,0,5){
cout<<res[i][0]+1<<" "<<res[i][1]+1<<endl;
}
return 0;
}
题意理解错的解
差别只在这个是每次都找8个方向，正解只在第一次确定八个方向中的一个
char s[101][101];
bool f=0;
int dx[8]={0,0,-1,1,-1,-1,1,1};
int dy[8]={1,-1,0,0,-1,1,-1,1};
int n,m;
char target[5]={'s','n','u','k','e'};
int res[5][2];
void dfs(int i,int j,int t){
if(t==5){
f=1;return;
}
fer(k,0,8){
if(!f&&i+dx[k]>=0&&i+dx[k]<n&&j+dy[k]>=0&&j+dy[k]<m){
if(s[i+dx[k]][j+dy[k]]==target[t]){
res[t][0]=i+dx[k];
res[t][1]=j+dy[k];
dfs(i+dx[k],j+dy[k],t+1);
}
}
}
}
signed main(){
cin>>n>>m;
fer(i,0,n){
cin>>s[i];
}
fer(i,0,n){
fer(j,0,m){
if(!f&&s[i][j]==target[0]){
res[0][0]=i;res[0][1]=j;
dfs(i,j,1);
}
}
}
fer(i,0,5){
cout<<res[i][0]+1<<" "<<res[i][1]+1<<endl;
}
return 0;
}
C Almost Equal 2 sec 1024 MB
开始想的是排序，后来发现不对，有点像数电的逻辑相邻，n只有8，全排列暴搜。可以直接用next_permutation
string s[8];
int n,m;
bool f=0;
bool use[8];
string res[8];
void dfs(int t){
if(t==n){//全排列完毕，看能否组成目标
bool flag=1;
fer(i,1,n){
int cnt=0;
fer(j,0,m){
if(res[i][j]==res[i-1][j])continue;
else{
cnt++;
if(cnt>=2){
flag=0;break;
}
}
}
if(!flag)break;
}
if(flag)f=1;
// fer(i,0,n){
// cout<<s[i]<<endl;
// }
// cout<<endl;
}
fer(i,0,n){
if(use[i]==0){
use[i]=1;
res[t]=s[i];
dfs(t+1);
use[i]=0;
}
}
}
signed main(){
cin>>n>>m;
fer(i,0,n)cin>>s[i];
fer(i,0,n){
if(!f){
use[i]=1;
res[0]=s[i];
dfs(1);
use[i]=0;
}
}
if(f)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
dfs
D Impartial Gift 2 sec 1024 MB
排序，双指针
二分也可以
signed main(){
int n,m,d;cin>>n>>m>>d;
fer(i,0,n)cin>>a[i];
fer(i,0,m)cin>>b[i];
sort(a,a+n);
sort(b,b+m);
int resa=-1,resb=-1;
int i=n-1,j=m-1;
while(i>=0&&j>=0){
if(abs(a[i]-b[j])<=d){
resa=a[i];resb=b[j];break;
}else{
if(a[i]>b[j])i--;
else j--;
}
}
if(resa==-1)cout<<-1<<endl;
else cout<<resa+resb<<endl;
return 0;
}
E Isolation
这道题大吐特吐，集合TLE了26个，vectorTLE4个，把endl改\n以后TLE了2个，最后也没出来，删邻边没想出好办法。看题解！！
TLE2个测试点的代码
int n,q;
scanf("%lld%lld",&n,&q);
vector<int> v[n+1];
int cnt=n,op,a,b;
while(q--){
scanf("%lld",&op);
//cin>>op;
if(op==1){
scanf("%lld%lld",&a,&b);
//cin>>a>>b;
if(v[a].size()==0)cnt--;
if(v[b].size()==0)cnt--;
v[a].pb(b);
v[b].pb(a);
printf("%lld\n",cnt);
//cout<<cnt<<"\n";
}else{
//cin>>a;
scanf("%lld",&a);
if(v[a].size()!=0)cnt++;
vector<int>::iterator it;
fer(i,0,v[a].size()){
b=v[a][i];
it=find(v[b].begin(),v[b].end(),a);
v[b].erase(it);
if(v[b].size()==0)cnt++;
}
v[a].clear();
printf("%lld\n",cnt);
//cout<<cnt<<"\n";
}
}
E就卡了后面三道压根没看
