AtCoder Beginner Contest 335

康复训练

打的有点昏啊

A - 2023

#include <bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;

void solve(){
	string s;
	cin >> s;
	s[s.size()-1]='4';
	cout <<s<<endl;

}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	//cin >> T;
	while(T--) solve();
    return 0;
}

B - Tetrahedral Number

#include <bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;

void solve(){
	int n;
	cin >> n;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			for(int k=0;k<=n;k++)
				if(i+j+k<=n)
					cout<<i<<" "<<j<<" "<<k<<endl;

}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	//cin >> T;
	while(T--) solve();
    return 0;
}

C - Loong Tracking

#include <bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;

void solve(){
	int n,q;
	cin >> n >>q;
	deque<pair<int,int>> path;
	for(int i=1;i<=n;i++)
		path.push_back({i,0});
	while(q--){
		int x;
		cin>>x;
		if(x==1){
			char c;
			cin>>c;
			int u=path[0].first;
			int v=path[0].second;
			 if(c=='U') path.push_front({u,v+1});
			 else if(c=='D') path.push_front({u,v-1});
			 else if(c=='L') path.push_front({u-1,v});
			 else if(c=='R') path.push_front({u+1,v});
			 path.pop_back();
		}else{
			int y;
			cin>>y;
			cout <<path[y-1].first<<" "<<path[y-1].second<<endl;
		}
	}

}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	//cin >> T;
	while(T--) solve();
    return 0;
}

D - Loong and Takahashi

#include <bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;

int board[100][100];

void solve(){
	int n;
	cin>>n;
	memset(board,0,sizeof board);
	int x=0,y=1;
	int cnt=0;
	while(cnt<n*n){
		while(x+1<=n&&board[x+1][y]==0) board[++x][y]=++cnt;
		while(y+1<=n&&board[x][y+1]==0) board[x][++y]=++cnt;
		while(x-1>0&&board[x-1][y]==0)  board[--x][y]=++cnt;
		while(y-1>0&&board[x][y-1]==0)  board[x][--y]=++cnt;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if((n+1)/2==i&&i==j) cout<<"T ";
			else 				 cout<<board[i][j]<<" ";
		}
		cout<<endl;
	}
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	//cin >> T;
	while(T--) solve();
    return 0;
}

E - Non-Decreasing Colorful Path

将有向图变为无向图
每条边一定是从权值小的指向权值大的点（若a[u]>a[v]则 v->u）
如果a[u]==a[v]则将他们并入一个并查集中 (有点像缩点，但不需要跑tarjin)
建完图在图上按拓扑序跑dp就可以求出正解

因为我们的边都是从小的指向大的，所以将点按权值从小到大排序，排出来的结果就是拓扑序。

#include <bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;

const int N = 2e5 + 10;
vector<int> G[N];
int n,m;
int a[N];
int fa[N];
int dp[N];

int Find(int x){
	return x==fa[x] ? x : fa[x] = Find(fa[x]);
}

int cmp(int x,int y){
	return a[x]<a[y];
}

void solve(){
	cin >> n >> m;
	vector<int> path;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
		fa[i] = i;
		dp[i] = -999999999;
		path.push_back(i);
	}
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin >> u >> v;
		if(a[u] == a[v]){
			int ta=Find(u);
			int tb=Find(v);
			fa[ta] = tb;
		}else{
			if(a[u]>a[v]) swap(u,v);
			G[u].push_back(v);
		}
	}

	dp[Find(1)] = 1;
	sort(path.begin(),path.end(),cmp);
	for(auto u:path)
		for(auto v:G[u])
			dp[Find(v)] = max(dp[Find(v)],dp[Find(u)]+1);

	cout << max(dp[Find(n)],0) <<endl;
	
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	//cin >> T;
	while(T--) solve();
    return 0;
}

F - Hop Sugoroku

根号分治+dp

#include <bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;

const int N = 2e5 + 10 , M = 500;
const int mod = 998244353;
int n;
int a[N] , res[M][M];
int dp[N];

void solve(){
	cin >> n;
	for(int i = 1; i <= n;i++) cin>>a[i];

	long long ans = 0;
	dp[1] = 1;
	for(int i = 1; i<=n ; i++)
	{
		for(int j = 1; j<M ; j++)
		{
			dp[i] = (dp[i] + res[i%j][j]) % mod;
		}
		if(a[i]>=M)
		{
			for(int j = i + a[i];j<=n;j+=a[i])
				dp[j] = (dp[j] + dp[i]) %mod;
		}
		else
		{
			res[i%a[i]][a[i]] = (res[i%a[i]][a[i]] + dp[i]) % mod;
		}
		ans = (ans + dp[i]) % mod;
	}
	cout << ans <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	//cin >> T;
	while(T--) solve();
    return 0;
}