I feel like I'm redeeming the sin of not practicing the algorithm well in College for three years π
1. Summary of knowledge points
The knowledge points involved in this operation include:
- string manipulation
- STL + sort
- graph theory
- BST tree (time complexity)
| Title number | difficulty | Knowledge points |
|---|---|---|
| 1140 | πΈ | String and number conversion + English Reading Comprehension |
| 1141 | πΈ | STL + sorting (involving basic string processing) |
| 1142 | πΈ | Graph theory (the basis of graph Foundation) π οΌ Little knowledge (almost) |
| 1143 | πΈπΈπΈ | Search and establishment of BST tree + time complexity optimization π I'm most afraid of the question with ideas but time card (if I haven't recited the template, it should be easier to find the rules in the examination room π) |
2 sub problem solution
2.1 question 1
1140 look and say sequence (20 points)
Idea:
- Find the rule: the number of occurrences + the number of consecutive occurrences of the number... And so on
- String processing: conversion between string and int
#include<bits/stdc++.h>
using namespace std;
int d,n;
//1 2 3 4 5 6 7 8
//D D1 D111 D113 D11231
bool vis[10];
int Count(string str, char ch){
int ans=0;
for(int i=0;i<str.length();i++){
if(str[i]==ch){
ans++;
}
}
return ans;
}
string getAns(){
//Calculate the n th of d
string nth=to_string(d);
string n1th="";
for(int i=1;i<n;i++){
//initialization
//for(int k=0;k<10;k++)vis[k]=false;
n1th="";
for(int j=0;j<nth.size();j++){
int temp=1;
n1th+=nth[j];
while(j+1<nth.size()&&nth[j]==nth[j+1]){
j++;
temp++;
}
n1th+=to_string(temp);
}
nth=n1th;
//cout<< nth<<endl;
}
return nth;
}
int main(){
scanf("%d%d",&d,&n);
cout<<getAns();
return 0;
}
2.2 question 2
1141 PAT Ranking of Institutions (25 points)
Idea:
Basic string processing + sorting, no pit
A new string usage learned:
Because tower () only supports character by character modification, you can quickly convert a string below (in fact, it's not hard to write the conversion function yourself) π)
transform(iid.begin(),iid.end(),iid.begin(),::tolower);
#include<bits/stdc++.h>
using namespace std;
struct Institution{
string name;
int TWS=0;
int Ns=0;
int scoreA=0;
int scoreB=0;
int scoreT=0;
};
map<string,Institution>mp;
int n;
string id;
int score;
string iid;
vector<Institution>v;
bool cmp(Institution a,Institution b){
if(a.TWS!=b.TWS){
return a.TWS>b.TWS;
}else if(a.Ns!=b.Ns){
return a.Ns<b.Ns;
}else{
return a.name<b.name;
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
cin>>id>>score>>iid;
//Pay attention to the writing
transform(iid.begin(),iid.end(),iid.begin(),::tolower);
if(id[0]=='A'){
mp[iid].scoreA+=score;
}else if(id[0]=='B'){
mp[iid].scoreB+=score;
}else if(id[0]=='T'){
mp[iid].scoreT+=score;
}
mp[iid].Ns++;
mp[iid].name=iid;
}
printf("%d\n",mp.size());
for(map<string,Institution>::iterator it=mp.begin();it!=mp.end();it++){
Institution temp=it->second;
//temp
temp.TWS=temp.scoreA+temp.scoreB/1.5+temp.scoreT*1.5;
v.push_back(temp);
}
sort(v.begin(),v.end(),cmp);
int rank=1;
for(int i=0;i<v.size();i++){
if(i&&v[i].TWS!=v[i-1].TWS){
rank=i+1;
}
cout<<rank<<" "<<v[i].name<<" "<<v[i].TWS<<" "<<v[i].Ns<<endl;
}
return 0;
}
2.3 question 3
1142 maximum clique (25 points)
Idea:
Basic graph theory
- First, judge whether the given point set is connected in pairs (and mark the points in the point set at this time)
- Secondly, judge whether a point does not belong to the point set but is connected to all points in the point set
- Because I don't have much time, violence is basically OK
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int num;
const int maxn=206;
int a,b;
bool graph[maxn][maxn]={false};
int v[maxn];
int vis[maxn]={0};
bool isADJ(int num){
for(int i=0;i<num;i++){
vis[i]=k;
for(int j=i+1;j<num;j++){
if(!graph[v[i]][v[j]]){
return false;
}
}
}
return true;
}
bool canADD(int num,int sign){
bool flag=false;
for(int id=1;id<=n;id++){
if(vis[id]!=sign){
for(int i=0;i<num;i++){
if(graph[v[i]][id]==false){
break;
}
if(i==num-1&&graph[v[i]][id]==true){
return true;
}
}
}
}
return false;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
graph[a][b]=true;
graph[b][a]=true;
}
scanf("%d",&k);
for(int i=0;i<k;i++){
scanf("%d",&num);
for(int j=0;j<num;j++){
scanf("%d",&v[j]);
}
//Any two vertices have adjacent edges
if(!isADJ(num)){
printf("Not a Clique\n");
}else if(canADD(num,k)){
printf("Not Maximal\n");
}else{
printf("Yes\n");
}
//There is no way to add any more adjacent edges
}
return 0;
}
2.4 question 4
[1143 lowest common ancester (30 points)]( Topic details - 1143 lowest common ancester (30 points) (pintia.cn))
Whoa, whoa, whoa, whoa
The idea at the beginning:
- Establish a tree (template, it is recommended to be familiar with)
- For a given two nodes, first Find to see if they exist, and save the parent node (that is, the passing node) in the process of finding
- Compare whether the parent nodes passing along the road have nodes of the same size on the same layer. If so, it is a public parent node (special judgment is required for specific circumstances. If the two nodes are equal and equal to the parent node, it belongs to the case of X is an ancester of Y)
First Edition: 18 / 30
#include<bits/stdc++.h>
using namespace std;
//Lowest ancestor
int m,n;
int v;
struct Node{
int val;
Node *right=NULL;
Node *left=NULL;
};
Node *build(int val,Node*root){
if(root==NULL){
root=new Node;
root->val=val;
}else if(val<root->val){
root->left=build(val,root->left);
}else{
root->right=build(val,root->right);
}
return root;
}
//Find the youngest parent node
int a,b;
vector<int>v1;
vector<int>v2;
bool Find(int val,Node*root,int sign){
if(root==NULL){
return false;
}else if(root->val==val){
if(sign==1){
v1.push_back(root->val);
}else{
v2.push_back(root->val);
}
return true;
}else{
//Save values on path
if(sign==1){
v1.push_back(root->val);
}else{
v2.push_back(root->val);
}
if(val<root->val){
return Find(val,root->left,sign);
}else{
return Find(val,root->right,sign);
}
}
}
map<int,bool>mp;
int main(){
scanf("%d%d",&m,&n);
Node *root=NULL;
for(int i=0;i<n;i++){
scanf("%d",&v);
mp[v]=true;
root=build(v,root);
}
for(int i=0;i<m;i++){
v1.clear();
v2.clear();
scanf("%d%d",&a,&b);
if(!mp[a]||!Find(a,root,1)){
if(!mp[b]||!Find(b,root,2)){
printf("ERROR: %d and %d are not found.\n",a,b);
}else{
printf("ERROR: %d is not found.\n",a);
}
}else if(!mp[b]||!Find(b,root,2)){
printf("ERROR: %d is not found.\n",b);
}else{
//Find common point on path
int ans=-1;
for(int i=0;i<min(v1.size(),v2.size());i++){
if(v1[i]==v2[i]){
ans=v1[i];
}
}
if(ans==a&&ans!=b){
printf("%d is an ancestor of %d.\n",ans,b);
}else if(ans==b&&ans!=a){
printf("%d is an ancestor of %d.\n",ans,a);
}else if(ans==a&&ans==b){
printf("%d is an ancestor of %d.\n",ans,a);
}else{
printf("LCA of %d and %d is %d.\n",a,b,ans);
}
}
}
return 0;
}
Second Edition: try to optimize Find and store the parent node in the build part, or not 18 / 30
#include<bits/stdc++.h>
using namespace std;
//Lowest ancestor
int m,n;
int v;
struct Node{
int val;
Node *right=NULL;
Node *left=NULL;
};
map<int,bool>mp;
map<int,vector<int> >path;
Node *build(int val,Node*root){
if(root==NULL){
root=new Node;
root->val=val;
path[val].push_back(val);
}else if(val<root->val){
path[val].push_back(root->val);
root->left=build(val,root->left);
}else{
path[val].push_back(root->val);
root->right=build(val,root->right);
}
return root;
}
//Find the youngest parent node
int a,b;
int main(){
scanf("%d%d",&m,&n);
Node *root=NULL;
for(int i=0;i<n;i++){
scanf("%d",&v);
mp[v]=true;
root=build(v,root);
}
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
if(!mp[a]){
if(!mp[b]){
printf("ERROR: %d and %d are not found.\n",a,b);
}else{
printf("ERROR: %d is not found.\n",a);
}
}else if(!mp[b]){
printf("ERROR: %d is not found.\n",b);
}else{
//Find common point on path
int ans=-1;
for(int i=min(path[a].size(),path[b].size())-1;i>=0;i--){
if(path[a][i]==path[b][i]){
ans=path[a][i];
break;
}
}
if(ans==a&&ans!=b){
printf("%d is an ancestor of %d.\n",ans,b);
}else if(ans==b&&ans!=a){
printf("%d is an ancestor of %d.\n",ans,a);
}else if(ans==a&&ans==b){
printf("%d is an ancestor of %d.\n",ans,a);
}else{
printf("LCA of %d and %d is %d.\n",a,b,ans);
}
}
}
return 0;
}
After reading Liu Shen's thought, I realized that there was no need to build a tree π οΌ We investigate the structure of BST tree array
Revised ideas:
Analysis: Map < int, bool > MP is used to mark all the nodes in the tree, traverse the pre array and mark the current node as a. if u and v are on the left and right of a respectively, or one of u and v is the current a, it means that the common lowest ancestor a is found, exit the current cycle ~ finally output the results as required
#include<bits/stdc++.h>
using namespace std;
int m,n;
vector<int>pre;
map<int,bool>mp;
int u,v;
int main(){
scanf("%d%d",&m,&n);
pre.resize(n);
for(int i=0;i<n;i++){
scanf("%d",&pre[i]);
mp[pre[i]]=true;
}
for(int i=0;i<m;i++){
scanf("%d%d",&v,&u);
if(!mp[v]){
if(!mp[u]){
printf("ERROR: %d and %d are not found.\n",v,u);
}else{
printf("ERROR: %d is not found.\n",v);
}
}else {
if(!mp[u]){
printf("ERROR: %d is not found.\n",u);
}else{
//eureka
int ans=-2;
int temp;
for(int j=0;j<n;j++){
temp=pre[j];
if(temp<u&&temp>v||temp<v&&temp>u||temp==u||temp==v){
ans=temp;
break;
}
}
if(temp!=v&&temp!=u){
printf("LCA of %d and %d is %d.\n",v,u,ans);
}else{
printf("%d is an ancestor of %d.\n",ans,ans==v?u:v);
}
}
}
}
}