-------------------------------------------------------------------------------- 1001-1167（已更新至最新！）

链接：https://pan.baidu.com/s/1JFKRoZO8ZaX_2DE_EOnqVQ 提取码：c5oi -------------------------------------------------------------------------------- 更多详见>>

OJ题解系列 目录导航帖 --------------------------------------------------------------------------------

PAT (Advanced Level) Practice --------------------------------------------------------------------------------

算法标签: 树，二叉树 DFS 注意点: 如下 1.前序 中序遍历建树 2.从根结点出发DFS公共最大前缀串遍历，记录路径，寻求路径 3.判断最大串是否最大。U、V，输出LCA（U，V）即可。 最后，注意与1143题的异同，因为1151时间的复杂性比较宽松(1万ms)，有很多方法；1143题加强了时间限制(200ms)，因此DFS遍历需剪枝

#include<bits/stdc .h> using namespace std; int M,N; int pre[10005]; int in[10005];  struct node{ 
          int data;  node* lchild;  node* rchild; }; node* newnode(int v){ 
          node* Node = new node; Node->data = v; Node->lchild = NULL; Node->rchild = NULL; return Node; } node* Create(int preL,int preR,int inL,int inR){ 
          if(preL>preR){ 
          return NULL; } node* root = newnode(pre[preL]); int k; for(int i=inL;i<=inR;i++){ 
          if(pre[preL] == in[i]){ 
          k = i; break; } } int numleft = k-inL; root->lchild = Create(preL+1,preL+numleft,inL,inL+numleft-1); root->rchild = Create(preL+numleft+1,preR,inL+numleft+1,inR); return root; } vector<int> ans1; vector<int> ans2; vector<int> path1; vector<int> path2; int search1(node* root,int v,int depth){ 
          if(root->data == v){ 
          path1.push_back(v); ans1 = path1; path1.pop_back(); return 1; } if(root->lchild){ 
          path1.push_back(root->data); search1(root->lchild,v,depth+1); path1.pop_back(); } if(root->rchild){ 
          path1.push_back(root->data); search1(root->rchild,v,depth+1); path1.pop_back(); } return 0; } int search2(node* root,int v,int depth){ 
          if(root->data == v){ 
          path2.push_back(v); ans2 = path2; path2.pop_back(); return 1; } if(root->lchild){ 
          path2.push_back(root->data); search2(root->lchild,v,depth+1); path2.pop_back(); } if(root->rchild){ 
          path2.push_back(root->data); search2(root->rchild,v,depth+1); path2.pop_back(); } return 0; } int main(){ 
          scanf("%d%d",&M,&N); node* root = NULL; for(int i=1;i<=N;i++){ 
          scanf("%d",&in[i]); } for(int i=1;i<=N;i++){ 
          scanf("%d",&pre[i]); } root = Create(1,N,1,N); for(int i=1;i<=M;i++){ 
          int U,V; scanf("%d%d",&U,&V); path1.clear(); path2.clear(); ans1.clear(); ans2.clear(); int f1 = search1(root,U,0); int f2 = search2(root,V,0); if(!ans1.size() && !ans2.size()){ 
          printf("ERROR: %d and %d are not found.\n",U,V); }else if(!ans1.size() && ans2.size()){ 
          printf("ERROR: %d is not found.\n",U); }else if(ans1.size() && !ans2.size()){ 
          printf("ERROR: %d is not found.\n",V); }else{ 
          int k = -1; bool f = false; for(int i=0;i<ans1.size() && i<ans2.size();i++){ 
          if(ans1[i] == ans2[i]){ 
          f = true; continue; }else{ 
          k = i-1; break; } } if(f && k==-1){ 
          k = min(ans1.size(),ans2.size())-1; } if(ans1[k] == U){ 
          printf("%d is an ancestor of %d.\n",U,V); }else if(ans1[k] == V){ 
          printf("%d is an ancestor of %d.\n",V,U); }else{ 
          printf("LCA of %d and %d is %d.\n",U,V,ans1[k]); } } } return 0; } 

算法标签: 字符串 + 模拟

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
int a[maxn];
int L,K;
int isprime(long long a){ 
        
	for(long long i =2;i<=sqrt(a);i++){ 
        
		if(a%i==0){ 
        
			return 0;
		}
	}
	return 1;
}
int main(){ 
        
	string str;
	cin >> L >> K;
	cin >> str;
	for(int i=0;i<L;i++){ 
        
		a[i] = str[i] - '0';
	}
	bool flag = false;
	for(int i=0;i<L-K+1;i++){ 
        
		long long num = 0;
		for(int j=0;j<K;j++){ 
        
			num = num *10+a[i+j];
		}
		if(isprime(num)){ 
        
			for(int j=0;j<K;j++){ 
        
				cout << a[i+j];
			}
			flag = true;
			break;
		}
	}
	if(flag==false){ 
        
		cout << "404" << endl;
	}
	return 0;
}

算法标签: 字符串 + 排序

#include<bits/stdc++.h>
using namespace std;
struct node { 
        
    string t;
    int value;
};
bool cmp(const node &a, const node &b) { 
        
    return a.value != b.value ? a.value > b.value : a.t < b.t;
}
int main() { 
        
    int n, k, num;
    string s;
    cin >> n >> k;
    vector<node> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].t >> v[i].value;
    for (int i = 1; i <= k; i++) { 
        
        cin >> num >> s;
        printf("Case %d: %d %s\n", i, num, s.c_str());
        vector<node> ans;
        int cnt = 0, sum = 0;
        if (num == 1) { 
        
            for (int j = 0; j < n; j++)
                if (v[j].t[0] == s[0]) ans.push_back(v[j]);
        } else if (num == 2) { 
        
            for (int j = 0; j < n; j++) { 
        
                if (v[j].t.substr(1, 3) == s) { 
        
                    cnt++;
                    sum += v[j].value;
                }
            }
            if (cnt != 0) printf("%d %d\n", cnt, sum);
        } else if (num == 3) { 
        
            unordered_map<string, int> m;
            for (int j = 0; j < n; j++)
                if (v[j].t.substr(4, 6) == s) m[v[j].t.substr(1, 3)]++;
            for (auto it : m) ans.push_back({ 
        it.first, it.second});
        }
        sort(ans.begin(), ans.end(),cmp);
        for (int j = 0; j < ans.size(); j++) printf("%s %d\n", ans[j].t.c_str(), ans[j].value);
        if (((num == 1 || num == 3) && ans.size() == 0) || (num == 2 && cnt == 0)) printf("NA\n");
    }
    return 0;
}

算法标签: 图论 + 枚举法 注意点: 依次枚举每条边，检查顶点颜色是否相同，即验证是否为合理的染色