526互联

AtCoder Beginner Contest 335

发布时间 2024-01-07 23:04:10作者: yufan1102

A image

#include<bits/stdc++.h>
using namespace std;
void solve(){
	string s;
	cin>>s;
	for(int i=0;i<s.size()-1;i++){
	  cout<<s[i];
	}
	cout<<"4";
}
int 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 - Tetrahedral Number

image

#include<bits/stdc++.h>
using namespace std;
void solve(){
  int n;
  cin>>n;
  for(int i=0;i<=n;i++){
    for(int j=0;i+j<=n;j++){
      for(int z=0;i+j+z<=n;z++){
        if(i+j+z<=n){
        	cout<<i<<" "<<j<<" "<<z<<"\n";
		}
      }
    }
  }
}
int 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 - Loong Tracking

image
image

在线查询一条龙的身体部位的位置，每一个部位是跟着上个部位在动

思路：暴力的肯定不行，我的想法是既然每个部位是跟着上个部位在动，那么归根结底就是看1号怎么动，每个部位的行踪是1号的子数组，所以前缀和记忆化一下就行

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
map<int,pair<int,int>>ans;
void solve(){
	int n,m;
	cin>>n>>m;
	int cnt=0;
	int a=0,b=0;
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		if(x==1){
			cnt++;
			char c;
			cin>>c;
			if(c=='U'){
				b++;
			}else if(c=='D'){
				b--;
			}else if(c=='L'){
				a--;
			}else{
				a++;
			}
			ans[cnt]={a,b};
		}else{
			int y;
			cin>>y;
			int k=y-1;
			int t1=y;
			int t2=0;
			int p=max(0,min(cnt,k));
			t1-=p;
			if(cnt-k>=1){
				t1+=ans[cnt-k].first;
				t2+=ans[cnt-k].second;
			}
			cout<<t1<<" "<<t2<<"\n";
		}
	}
}
int 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;
}

D - Loong and Takahashi

image
image

当时看这个要求以及答案，感觉贪吃蛇是符合条件的，没想到猜对了

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int arr[50][50];
int vis[50][50];
int main(){
	int n;
	cin>>n;
	arr[1][1]=1;
	vis[1][1]=1;
	int t=0;
	int x=1;
	int y=1;
	for(int i=2;i<=n*n;i++){
		int nx=x+dx[t];
		int ny=y+dy[t];
		if(nx>n||ny>n||nx<=0||ny<=0||vis[nx][ny]){
			t++;
			if(t>3)t=0;
		}
		x=x+dx[t];
		y=y+dy[t];
		vis[x][y]=1;
		arr[x][y]=i;	
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==(n+1)/2&&j==(n+1)/2){
				cout<<"T ";
				continue;
			}
			cout<<arr[i][j]<<" ";
		}
		cout<<"\n";
	}
	return 0;
}

E - Non-Decreasing Colorful Path

image

要求是发现一条从1到n的路s，s的元素代表的值是非减的，找出满足这个条件的路其中元素的值不同的个数的最大值

思路：BFS + 优先队列

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
vector<ll>a[N];
ll d[N],w[N];
void solve(){
	ll n,m,u,v;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		if(w[v]>=w[u])a[u].push_back(v);
		if(w[u]>=w[v])a[v].push_back(u);
	}
	priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>q;
	q.push({w[1],1});
	d[1]=1;
	while(q.size()){
		ll u=q.top().second;
		q.pop();
		for(auto c:a[u]){
			if (d[c] < d[u] + (w[c] != w[u])) {
                    d[c] = d[u] + (w[c] != w[u]);
                    q.push({w[c],c});
                }
		}
	}
	cout<<d[n];
}
signed main(){
	solve();
	return 0;
}