TJPC 11th 進階班比賽題解

前情

題目

PA 基礎DFS - 首殺 : wonderhoi

Tag : DFS
顧名思義 就是DFS
看著題目下去實作就AC了
阿這題開了嚴格比對來搞人ㄏㄏ

題解

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define ph push
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
const int maxn=2e5+5;
const int mod=10007;
int n;
vector<set<int>> g;
bool vis[maxn];
vector<int> ans;
void dfs(int node)
{
	ans.pb(node);
	vis[node]=true;
	for(auto id=g[node].begin();id!=g[node].end();id++){
		int w=*id;
		w=-w;
		if(!vis[w]){
			dfs(w);
			ans.pb(node);
		}
	}
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	g.resize(n+1);
	for(int i=0;i<n-1;i++){
		int a,b;
		cin>>a>>b;
		g[a].insert(-b);
		g[b].insert(-a);
	}
	dfs(1);
	for(int i=0;i<ans.size();i++){
		cout<<ans[i];
		if(i!=ans.size()-1){
			cout<<' ';
		}
		else{
			cout<<'\n';
		}
	}
}

PB 牛排 - 首殺 : asdfg

Tag : greedy
能發現只要由左往右greedy就行

題解

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll n, x; cin >> n >> x;
	vector<ll> v(n); for(auto &d : v) cin >> d;
	ll ans = 0;
	for(int i = 0; i < n-1; i++) {
		ll tmp = v[i] + v[i+1];
		if(tmp > x) {
			ll r = min(v[i+1], tmp - x); 
			tmp -= r;
			v[i+1] -= r;
			ans += r;
			if(tmp > x) {
				ans += (tmp-x);
				v[i] -= (tmp-x);
			}
		}
	}
	cout << ans << '\n';
	
}

PC A+B+C - 首殺 : asdfg

Tag : brute + stl
就單純暴力過去然後用stl存答案就行了

題解

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define Blameazu ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
 
int main() {
	Blameazu;
	int n; cin >> n;
	vector<int> a(n); for(int &d : a) {cin >> d;}
	int m; cin >> m;
	vector<int> b(m); for(int &d : b) {cin >> d;}
	int l; cin >> l;
	vector<int> c(l); for(int &d : c) {cin >> d;}
	set<ll> se;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			for(int k = 0; k < l; k++) {
				se.insert(a[i]+b[j]+c[k]);
			}
		}
	}
	int q; cin >> q;
	while(q--) {
		int a; cin >> a;
		cout << (se.count(a) ? "Yes\n" : "No\n");
	}
}

PD 簡單的數列 - 首殺 : wonderhoi

Tag : Priority_queue, Multiset, queue
只要會STL基本上就AC了

題解

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int q; cin >> q;
	deque<int> dqq;
	multiset<int> mst;
	while(q--) {
		int a; cin >> a;
		if(a == 1) {
			int x; cin >> x;
			dqq.emplace_front(x);
		} else if(a == 2) {
			if(mst.size()) {
				cout << *(--mst.end()) << '\n';
				mst.erase(--mst.end());
			} else {
				cout << dqq.back() << '\n';
				dqq.pop_back();
			}
		} else {
			for(int &d : dqq) {
				mst.insert(d);
			}
			dqq.clear();
		}
	}
	
}

PE 鐵巨人 - 首殺 :

Tag : bfs
就比較難做一點的BFS而已

題解

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define ph push
#define vvi vector<vector<int>>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
const int maxn=2e5+5;
const int mod=1e9+7;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void solve()
{
	int n,m,k;
	cin>>n>>m>>k;
	vector<vector<int>> g;
	vector<vector<bool>> vis;
	vis.resize(n+1,vector<bool>(m+1));
	g.resize(n+1,vector<int>(m+1));
	int Ix=0,Iy=0;
	int Tx=0,Ty=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char t;
			cin>>t;
			int h;
			cin>>h;
			g[i][j]=h;
			if(t=='T'){
				Tx=i;
				Ty=j;
			}
			if(t=='I'){
				Ix=i;
				Iy=j;
			}
		}
	}
	queue<pair<pii,int>> d;
	d.ph({{Ix,Iy},0});
	while(d.size()){
		int x=d.front().f.f;
		int y=d.front().f.s;
		int step=d.front().s;
		d.pop();
		//cout<<x<<' '<<y<<' '<<step<<'\n';
		if(vis[x][y]) continue;
		vis[x][y]=true;
		if(x==Tx and y==Ty){
			cout<<step<<'\n';
			return;
		}
		if(g[Tx][Ty]>=g[x][y] and abs(x-Tx)+abs(y-Ty)==1 and g[x][y]+k>=g[Tx][Ty]){
			cout<<step<<'\n';
			return;
		}
		for(int i=0;i<4;i++){
			int wx=x+dx[i];
			int wy=y+dy[i];
			if(wx>=1 and wx<=n and wy>=1 and wy<=m and !vis[wx][wy] and g[wx][wy]-g[x][y]<=1){
				d.ph({{wx,wy},step+1});
			}
		}
	} 
	cout<<"QwQ"<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--){
    	solve();
    }
}

PF 不會出DP - 首殺 :

Tag : DP
這題就防破台題ㄏㄏ

詳解

我也不會

Bonus

這樣開會比較快嗎???

ios::sync_with_stdio(false);
cin.tie(0);
ios::sync_with_stdio(false);
cin.tie(0);
ios::sync_with_stdio(false);

TLE大賽