1140 1141 1142 1143模拟练习（谜之压轴题）

2024-03-18 19:38:28

1140 Look-and-say Sequence (20 分)

Sample Input:

1 8

Sample Output:

1123123111

Note

1 11 12 1121 122111 112213 12221131 1123123111

题意：没经过一次变换，都用一个数记录之前数出现过的次数
思路：先造一个两倍长的string,循环记录即可

Code

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<string>
#include<fstream>
#include<map>
using namespace std;
const int maxn = 1e4;

int main(){
#ifdef _DEBUG 
	ifstream cin("data.txt");
#endif
	int  step;
	string s, results;
	cin >> s >> step;
	results = s + s;
	while(--step){
		int start = 0;
		int  cnt = 0;
		while(1){
			int i = 1;
			char temp = s[start];
			while(temp == s[start + i] && start + i < s.size()) i++;
			results[cnt++] = s[start]; results[cnt++] = '0' + i;
			if(i + start == s.size()) break;
			start  = i + start; 
		}
		s = results.substr(0, cnt);
		results = s + s;
	}
	cout << s;

#ifdef _DEBUG 
	cin.close();
#endif
	return 0;
}

1141 PAT Ranking of Institutions (25 分)

Sample Input:

10
A57908 85 Au
B57908 54 LanX
A37487 60 au
T28374 67 CMU
T32486 24 hypu
A66734 92 cmu
B76378 71 AU
A47780 45 lanx
A72809 100 pku
A03274 45 hypu

Sample Output:

5
1 cmu 192 2
1 au 192 3
3 pku 100 1
4 hypu 81 2
4 lanx 81 2

Note

题意： A,B,T类考生，权重为1， 1/1.5， 1.5，对学校排序首先满足总分降序，其次人数升序，最后名称字典序。总分相同的排名相同。
思路： myhash记录id到标号的映射，node型results记录结果参与排序
刚开始看到以为是简单题，想不到这个反而是这个bug存在时间最长，原因在于算权重时保留的是double，排序输出时tws改为int.(最主要还是因为自己画蛇添足题目根本没让round，导致查了很长时间）。

Code

#include<iostream>
#include<algorithm>
#include<vector>
#include<fstream>
#include<queue>
#include<string>
#include<cstring>
#include<map>
using namespace std;
const int maxn = 1e7;
map<string, int> myhash;
int cnt = 1;
struct node{
	string school;
	double tws;
	int ns;
};
bool cmp(node a, node b){
	if( a.tws == b.tws) {
		if(a.ns == b.ns) return a.school < b.school;
		else return a.ns < b.ns;
	}else{	
		return a.tws > b.tws;
	}
}

int main(){ 
#ifdef _DEBUG
	ifstream cin("data2.txt");
#endif
    int num, i;
	map<char, double> rule;
	rule['A'] = 1; rule['T'] = 1.5; rule['B'] = 0.66667;
	cin >> num;
	vector<node> results;
	for( i = 0; i < num; i++){
		string name, tempschool;
		node temp;
		int tempscroe;
		cin >> name >> tempscroe >> tempschool;
		transform(tempschool.begin(),tempschool.end(),tempschool.begin(),::tolower);
		if(myhash[tempschool] == 0){
			myhash[tempschool] = cnt++;
			temp.school = tempschool;
			temp.ns = 1;
			temp.tws = rule[name[0]] * tempscroe;
			results.push_back(temp);
		}else{	
			results[myhash[tempschool] - 1].ns++;
			results[myhash[tempschool] - 1].tws +=rule[name[0]] * tempscroe; 
		}
	}
    for(i = 0; i < results.size(); i++){    
        results[i].tws =  results[i].tws;;
    }	
	sort(results.begin(), results.end(), cmp);
	int rank = 1, last = -1;
    cout << results.size() << endl;
	for( i = 0; i < results.size(); i++){
		if( (int)results[i].tws !=  last){
			rank = i + 1;
		}      
		cout <<rank  << " "<< results[i].school <<  " " <<  (int)results[i].tws << " " << results[i].ns << endl;
		last =(int) results[i].tws;
	}	
#ifdef _DEBUG
	 cin.close();
#endif
	return 0;

 
}

1142 Maximal Clique (25 分)

Sample Input:

8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
3 4 3 6
3 3 2 1

Sample Output:

Yes
Yes
Yes
Yes
Not Maximal
Not a Clique

Note

题意：找到最大的集合，其中任意两个元素都相连，
思路： a[maxn][maxn] 记录边的情况，visited map记录存在的节点，include记录要查询的节点，暴力遍历
一开始想用dfs但是思路很不清晰，根本不感写，最后看了眼别人的博客，草都没打直接写，没想到就ac了。。。

Code

#include<iostream>
#include<vector>
#include<map>
#include<fstream>
using namespace std;
const int maxn = 1e4;
int a[maxn][maxn];
map<int, bool> visited;
int main(){ 
#ifdef _DEBUG
	ifstream cin("data3.txt");
#endif
    int i, j, k, num, edge, queries, tempnum, tempa, tempb;
    cin >> num >> edge;
    for(i = 0; i < edge; i++){  
        cin >> tempa >> tempb;
		tempa --;
		tempb --;
        a[tempa][tempb] = a[tempb][tempa] = 1;
        visited[tempa] = visited[tempb] = 1;
    }
    cin >> queries;
    while(queries--){ 
        map<int, bool> includes;
        int flag = 0, cnt = 0;
        cin >> tempnum;
        for(i = 0; i < tempnum; i++){   
            cin >> tempa;
			tempa -- ;
            includes[tempa] = 1;
        }
        for(i = 0; i < num&& flag != 1; i++){   
            cnt = 0;
            for(j = 0; j < num; j++){
                if(includes[i] == 1 && includes[j] == 1 && a[i][j] == 0 && i != j){
					flag = 1; 
					break;
				}
                else if(visited[i] == 1 &&includes[i] == 0 && includes[j] == 1 && a[i][j] == 1) 
					cnt++;
            }
            if(cnt == tempnum) flag = 2;
        }
        if(flag == 1) cout << "Not a Clique" << endl;
        else if(flag == 2) cout << "Not Maximal" << endl;
        else cout << "Yes" << endl;
    }

#ifdef _DEBUG
	cin.close();
#endif
	return 0;
}

1143 Lowest Common Ancestor (30 分)

Sample Input:

6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99

Sample Output:

LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

Note

题意：输入先序遍历序列，找bst中的最近公共祖先
思路：bst中左节点小于根，右节点大于等于根，因此只要找到一个节点在a与b之间，即为他们的公共最近祖先。

心路历程：

LCA?不是不考动态规划吗WTF?
BST先序序列建树，好像没写过，好难哇
既然要找的是祖先，二叉树性质就不重要了struct设置成depth ancestor data是不是是就可以了
哦对了，题目没说id正好是1-num哇，还要建一个map<int,int> myhash映射一下？
找祖先函数自己尝试着写了个递归形式的，递归边界是不是考虑完整了啊？会不会超时啊
整体思路输入-》myhash映射-》BST+PRE建树-》寻找最近公共祖先》分类讨论》输出。
BST+PRE建树和寻找最近公共祖先已经很难了，还要注意myhash和分类，真的好难哇
看了眼别人的博客，卒。

Code

#include<iostream>
#include<map>
#include<vector>
using namespace std;
map <int, bool> visited;
int main(){ 
    vector<int> pre;
    int num, i, edge, temp, queries, tempa, tempb;
    cin >> queries >> edge;
    for(i = 0; i < edge; i++){  
        cin >> temp;
        pre.push_back(temp);
        visited[temp] = 1;
    }
    while(queries--){   
        cin >> tempa >>  tempb;
        for(i = 0; i < pre.size(); i++){    
            temp = pre[i];
            if((tempa <= temp && tempb >= temp )|| (tempa >= temp && tempb <= temp)) break;
        }
        if(visited[tempa] == 0 && visited[tempb] == 0) cout << "ERROR: " << tempa<<" and "<<tempb <<" are not found." <<endl;
        else if(visited[tempa] == 0) cout << "ERROR: " << tempa<<" is not found." <<endl;
        else if(visited[tempb] == 0) cout << "ERROR: " << tempb<<" is not found." <<endl;
		else if(temp == tempa || temp == tempb){int out =  (tempa == temp) ? tempb : tempa;  cout << temp << " is an ancestor of "<< out << "." << endl;}
        else cout << "LCA of "<<tempa << " and " << tempb <<" is "<< temp << "." << endl;
    }
    return 0;
}

码农公寓

1140 Look-and-say Sequence (20 分)

Sample Input:

Sample Output:

Note

Code

1141 PAT Ranking of Institutions (25 分)

Sample Input:

Sample Output:

Note

Code

1142 Maximal Clique (25 分)

Sample Input:

Sample Output:

Note

Code

1143 Lowest Common Ancestor (30 分)

Sample Input:

Sample Output:

Note

心路历程：

Code

相关文章