第一题：AC 【有序链表求交集】签到题，求两个链表的交集
思路：线性扫描，谁大谁就后移，相等就存入答案
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0);
const int maxn = 1000005;
int a[maxn];
int b[maxn];
int ans[maxn];
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("a.txt", "r", stdin);
#endif
int n, m;
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
cin >> m;
for(int i = 1; i <= m; ++i) cin >> b[i];
int i = 1, j = 1;
int t = 0;
while(i <= n && j <= m) {
if(a[i] < b[j]) {
++j;
} else if(a[i] > b[j]) {
++i;
} else {
ans[++t] = a[i];
++i;
++j;
}
}
for(i = 1; i <= t; ++i) {
if(i < t) cout << ans[i] << " ";
else cout << ans[i] << endl;
}
return 0;
}
第二题：AC 【并查集】n个人，m个小团队，从0号开始，最多有几个人有关联关系
思路：并查集，注意合并的时候，需要把每一个节点都合并，包括中间节点，减小高度，提高查询效率
以小的id为根，相当于多棵树的集合，找0根的集合的大小（调试了40min，最后用set集合辅助A掉了）
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0);
const int maxn = 100005;
int f[maxn];
int arr[105];
int find(int x) {
return (f[x] == x) ? x : (f[x] = find(f[x]));
}
void merge(int x, int y) {
int fx = find(x);
int fy = find(y);
if(fx < fy) {
f[y] = fx;
} else if(fx > fy) {
f[x] = fy;
}
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("b.txt", "r", stdin);
#endif
int n, m, x;
while(cin >> n >> m) {
for(int i = 0; i < n; ++i) f[i] = i;
set<int> s;
while(m--) {
cin >> x;
for(int i = 0; i < x; ++i) {
cin >> arr[i];
s.insert(arr[i]);
}
sort(arr, arr + x);
for(int i = 1; i < x; ++i) {
int rt = find(arr[0]);
int u = find(arr[i]);
if(u != rt) merge(arr[i], arr[0]);
}
}
int ans = 0;
for(int i : s) if(find(i) == 0) ++ans;
cout << ans << endl;
}
return 0;
}
第三题：AC【map操作】查找k个高频率和k个最低频率的字符串以及出现的次数
思路：用map统计，分析可行性：数据量n最大1e5, 总的字符串长度和最大1e5, 所以不会出现极端的情况
要么n较小，要么字符串很短，所以直接用map统计是可行的。
最后就是剩下排序了，根据题目要求，分两轮排序即可
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0);
using psi = pair<string,int>;
auto de = [](const psi& l, const psi& r){
if(l.second == r.second) return l.first < r.first;
return l.second > r.second;
};
auto en = [](const psi& l, const psi& r){
if(l.second == r.second) return l.first < r.first;
return l.second < r.second;
};
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("c.txt", "r", stdin);
#endif
int n, k;
while(cin >> n >> k) {
string s;
map<string, int> mp;
for(int i = 1; i <= n; ++i) { cin >> s; mp[s]++; }
vector<psi> t(mp.begin(), mp.end());
sort(t.begin(), t.end(), de);
for(int i = 0; i < k; ++i) {
cout << t[i].first << " " << t[i].second << endl;
}
sort(t.begin(), t.end(), en);
for(int i = 0; i < k; ++i) {
cout << t[i].first << " " << t[i].second << endl;
}
}
return 0;
}
第四题：AC【思维题】如果删除一个元素，求其余的n-1个数的中位数
思路：直接把每一个数据放到结构体，信息包含：值，索引（i 即pos），按值进行升序排序，然后取出每个位置的元素的pos
注意隐藏的信息：
1.减少一个数据后是奇数个，所以中间的那个就是中位数（前提是排序后）
2.如果pos <= n/2， 说明n/2+1就是中位数，如果pos >= n/2 + 1，说明n/2就是中位数
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0);
const int maxn = 200005;
struct Node {
int val;
int idx;
};
Node a[maxn];
int b[maxn];
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("c.txt", "r", stdin);
#endif
int n;
while(cin >> n) {
if(n <= 0) continue;
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i].val);
a[i].idx = i;
}
sort(a+1, a+n+1, [](const Node& l, const Node& r){return l.val < r.val;});
for(int i = 1; i <= n/2; ++i) {
int pos = a[i].idx;
b[pos] = a[n/2+1].val;
}
for(int i = n/2+1; i <= n; ++i) {
int pos = a[i].idx;
b[pos] = a[n/2].val;
}
for(int i = 1; i <= n; ++i) printf("%d\n", b[i]);
}
return 0;
}
第五题：5%【特殊排序】每个数据的属性包括颜色和值，需要分别把同颜色的排序，不同的颜色不需要考虑
思路：暂无，希望路过的大佬可以提供点思路，非常感谢！
代码如下：
全部评论
(2) 回帖