2020年冬季PAT甲级

代码懒得修了，写的特别烂

1

题目

思路

直接求就好了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll f[120]={0,1};
ll n,dif=1e9,ans=1;
int main(){
	cin>>n;
	for(int i=2;i<=60;i++){
		f[i]=f[i-1]+f[i-2];
		//cout<<f[i]<<endl;
	}
	for(int i=1;i<=60;i++){
		if(abs(n-f[i])<dif){
			ans=f[i];
			dif=abs(n-f[i]);
		}
	}
	cout<<ans<<endl;
	return 0;
}

2

题目

思路

直接匹配可能超时，从子序列串第一个字母在母串出现的位置开始匹配。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s,q;
vector<int>st;
string ans;
int len=1e9;
int main(){
	cin>>s>>q;
	if(q.size()==1){
		cout<<q<<endl;
		return 0;
	}
	for(int i=0;i<s.size();i++){
		if(s[i]==q[0]){
			st.push_back(i);
		}
	}
	for(int i=0;i<st.size();i++){
		int l=st[i],p=1;
		
		for(int j=l+1;j<s.size();j++){
			if(s[j]==q[p]){
				p++;
			}
			if(p==q.size()){
				int t=j-l+1;
				if(t<len){
					len=t;
					ans=s.substr(l,t);
				}
				break;
			}
		}
	}
	if(len!=1e9) cout<<ans<<endl;
	else{
		cout<<endl;
	}
	return 0;
}

3

题目

思路

直接建树求。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
string s;
int lasdep[1020];
struct E{
	string s;
	int f;
}e[1020];
map<string,int>mp;
void dfs(int d){
	if(e[d].f!=-1){
		dfs(e[d].f);
	}
	if(e[d].f!=-1){
		cout<<"->";
	}
	cout<<e[d].s;
	
}
int main(){
	cin>>n;
	getline(cin,s);
	for(int i=1;i<=n;i++){
		getline(cin,s);
		int l=0;
		for(l=0;l<s.size();l++){
			if(s[l]!=' ') break;
		}
		string cur=s.substr(l);
		mp[cur]=i;
		e[i].s=cur;
		lasdep[l]=i;
		if(l==0){
			e[i].f=-1;
			continue;	
		}
		e[i].f=lasdep[l-1];
	}
	cin>>m;
	string q;
	for(int i=1;i<=m;i++){
		cin>>q;
		if(!mp[q]){
			cout<<"Error: "<<q<<" is not found."<<endl;
		}
		else{
			dfs(mp[q]);
			cout<<endl;
		}
	}
	return 0;
}

4

题目

思路

dfs枚举制造m个所有的情况，然后排序。

一开始读错题，然后猜了一下题意。

==重载写错，改了就过了。

如果是更难的题意，extend应该能骗点分。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
int n,m,k;
void ot(int x){
	if(x>=10){
		cout<<x;
	}
	else{
		cout<<'0'<<x;
	}
}
int num(string x){
	int ret=0;
	if(x[0]=='+'){
		return -2;
	}
	else if(x[0]=='-'){
		return -1;
	}
	for(int i=0;i<x.size();i++){
		ret*=10;
		ret+=x[i]-'0';
	}
	return ret;
}
string s;
int c[120];
int w[120];
int pro[120];
struct E{
	vector<int>v;
	void print(){
		//sort(v.begin(),v.end());
		for(int i=0;i<v.size();i++){
			if(i!=0){
				cout<<" + ";
			}ot(v[i]);
		}
	}
	bool operator<(const E x)const{
		
		for(int i=0;i<min(v.size(),x.v.size());i++){
			if(v[i]==x.v[i]) continue;
			return v[i]<x.v[i];
		}
		return v.size()<x.v.size();
	}
	bool operator==(const E x)const{
		return v==x.v;
	}
};
vector<E>pth[120];
vector<vector<E>>ans;
vector<E>tmp;
map<int,int>mp;
bool check(int u,int i){
	E cur=pth[pro[u]][i];
	for(int i=0;i<cur.v.size();i++){
		if(mp[cur.v[i]]||w[cur.v[i]]==0) return false;
	}
	return true;
}
void mer(int u,int i){
	E cur=pth[pro[u]][i];
	for(int i=0;i<cur.v.size();i++){
		mp[cur.v[i]]++;
	}
}
void invmer(int u,int i){
	E cur=pth[pro[u]][i];
	for(int i=0;i<cur.v.size();i++){
		mp[cur.v[i]]--;
	}
}
void dfs(int u){
	//cout<<u<<":\n";
	if(u==m+1){
		ans.push_back(tmp);
		return;
	}
	for(int i=0;i<pth[pro[u]].size();i++){
		//cout<<u<<' '<<i<<endl;
		if(check(u,i)){
			tmp.push_back(pth[pro[u]][i]);
			mer(u,i);
			dfs(u+1);
			invmer(u,i);
			tmp.pop_back();
		}
	}
}
int cmp(vector<E> x,vector<E> y){
	for(int i=0;i<x.size();i++){
		if(x[i]==y[i]) continue;
		return x[i]<y[i];
	}	
}
void output(vector<E> x){
	for(int i=0;i<m;i++){
		x[i].print();
		cout<<" -> ";
		ot(pro[i+1]);
		cout<<endl;
	}
}
bool mg(E &x,E &y){
	int len=x.v.size();
	for(int i=0;i<y.v.size();i++){
		for(int j=0;j<len;j++){
			if(y.v[i]==x.v[j]) return false;
		}
		x.v.push_back(y.v[i]);
	}
	return true;
}
void extd(){
	for(int i=0;i<=99;i++){
		for(int j=0;j<pth[i].size();j++){
			for(int k=0;k<pth[i][j].v.size();k++){
				int add=pth[i][j].v[k];
				if(pth[add].size()==0) continue;
				for(int l=0;l<pth[add].size();l++){
					E nex=pth[i][j];
					int p=nex.v[k];
					nex.v.erase(nex.v.begin()+k);
					if(mg(nex,pth[add][l])){
						sort(nex.v.begin(),nex.v.end());
						pth[i].push_back(nex);
					}
				}
				
			}
		}
	}
}
int main(){
	//io_opt;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		c[i]=num(s);
		w[c[i]]++;
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>s;
		pro[i]=num(s);
	}
	cin>>k;
	for(int i=1;i<=k;i++){
		E cur;
		while(cin>>s){
			int t=num(s);
			if(t==-1) break;
			if(t==-2) continue;
			cur.v.push_back(t);
		}
		cin>>s;
		int t=num(s);
		pth[t].push_back(cur);
	}
	//extd();
	for(int i=0;i<=99;i++){
		E cur;
		cur.v.push_back(i);
		pth[i].push_back(cur);
	}
	dfs(1);
	sort(ans.begin(),ans.end(),cmp);
	//if(ans.size()>1) while(1);
	output(ans[0]);
	/*for(int i=0;i<ans.size();i++){
		output(ans[i]);
	}*/
	return 0;
}