腾讯后台&综合笔试 9-6 4.05a

T1 两个顺序数组求交集没啥好说的第二个数组读入的时候一边读一边扫第一个数组就行

#include <iostream>
#define maxn 1000001
using namespace std;
int a[maxn];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n;i ++) {
		cin >> a[i];
	}
	int pos = 0;
	int m;
	cin >> m;
	for (int i = 0; i < m; i ++) {
		int temp;
		cin >> temp;
		while (a[pos] > temp) {
			pos ++;
		}
		if (a[pos] == temp) {
			cout << temp << " ";
			pos ++;
		}
	}
}

T2 我好像似乎在哪里见过这道题就一堆小团体小团体一个人知到这个消息 = 所有人都知道这个消息给0号传递个消息问最后多少个人知道很简单的无向图每个团体的第一个人和剩下的团体内的其余人拉个无向边就行之后从0跑bfs

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define maxn 100010
using namespace std;
vector<int>G[maxn];
bool vis[maxn];
void addedge(int from, int to) {
	G[from].push_back(to);
	G[to].push_back(from);
}
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i ++) {
		int k;
		cin >> k;
		int temp;
		cin >> temp;
		for (int j = 1; j < k; j ++) {
			int c;
			cin >> c;
			addedge(temp, c);
		}
	}
	queue <int> que;
	que.push(0);
	vis[0] = 1;
	int ans = 1;
	while (!que.empty()) {
		int k = que.front();
		que.pop();
		for (int i = 0; i < G[k].size(); i ++) {
			int u = G[k][i];
			if(!vis[u]) {
				que.push(u);
				++ans;
				vis[u] = 1;
			}
		}
	}
	cout << ans;
}

T3 给个n个数字的数列输出n行第i行输出删掉第i个数字剩下的数列的中位数而且题目还tm保证n时偶数，这题。。。。应该放第一题感觉

#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 200001
using namespace std;
int data[maxn], orderedData[maxn];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i ++) {
		cin >> data[i];
		orderedData[i] = data[i];
	}
	sort(orderedData, orderedData + n);
	int k1 = orderedData[n/2 - 1], k2 = orderedData[n/2];
	for (int i = 0; i < n; i ++) {
		if (data[i] <= k1) {
			cout << k2;
		} else {
			cout << k1;
		}
		cout << " " << endl;
	}
}

T4 给n个字符串输出出现次数最大的前k个和后k个相同次数输出字典序小的 stl应用题 map一下排个序没有任何思想含量

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
#define maxn 100010
using namespace std;
map<string, int>mapsi;
struct ele{
	string s;
	int times;
	ele(string s, int times):s(s),times(times){};
	ele(){};
}eles[maxn];
bool comp1(const ele &a, const ele&b) {
	return a.times != b.times ? a.times < b.times : a.s < b.s;
}
bool comp2(const ele &a, const ele&b) {
	return a.times != b.times ? a.times > b.times : a.s < b.s;
}
int main() {
	int n,k;
	cin >> n >> k;
	for (int i = 0; i < n; i ++) {
		string s;
		cin >> s;
		int t = mapsi[s];
		mapsi[s] = ++t;
	}
	auto ite = mapsi.begin();
	int pos = 0;
	while (ite != mapsi.end()) {
		eles[pos++] = ele(ite->first, ite->second);
		ite++;
	}
	sort(eles, eles + pos, comp2);
	for (int i = 0; i < k; i ++) {
		cout << eles[i].s << " " << eles[i].times << endl;
	}
	sort(eles, eles + pos, comp1);
	for (int i = 0; i < k; i ++) {
		cout << eles[i].s << " " << eles[i].times << endl;
	}
	
}

T5 摸了一个小时摸出来了0.05知到自己哪里错了但就是不会写

#腾讯笔试##笔试题目##腾讯#