第一题：输出两个有序链表的公共部分
直接用了STL的list
以后手写实现一下。
#include <iostream>
#include <list>
using namespace std;
int m,n,temp;
int main(){
cin>>m;
list<int> a;
for (int i=1;i<=m;i++){
cin>>temp;
a.push_back( temp );
}
cin>>n;
list<int> b;
for (int i=0;i<n;i++){
cin>>temp;
b.push_back(temp);
}
list<int>::iterator p = a.begin();
list<int>::iterator q = b.begin();
while( p!=a.end() && q!=b.end()){
if(*p < *q)
q++;
else if(*p > *q)
p++;
else
{
cout<<*p<<" ";
p++;
q++;
}
}
cout<<endl;
return 0;
}
第二题：并查集
n个人，其中有m个组，组内信息互通，求最终和编号为0的人能通信的人有几个
直接并查集，一个组的合并一下即可
0号的人不用特地去管它，它自然会合并。
最终查看下有哪些人和0号的父亲相同即可。
还有，这个题坑死人，说了n个人，但是编号是0~n，也就是其实有n+1个人，我忍不住******。
#include<iostream>
#include<queue>
using namespace std;
int f[1000500];
int find(int x){
if (f[x]==x) return x;
else return f[x]=find(f[x]);
}
int main(){
int a,b;
int n,m,p;
while (cin>>n>>m){
for (int i=0; i<=n; i++){
f[i]=i;
}
for (int i=1; i<=m; i++){
cin>>p;
cin>>a;
int fa=find(a);
for (int j=1; j<p; j++){
cin>>b;
int fb=find(b);
if (fa!=fb) f[fb]=fa;
}
}
//for (int i=0; i<n; i++) cout<<f[i]<<" ";
int ans=0;
int s=find(0);
for (int i=0; i<=n; i++) {
//cout<<find(i)<<" ";
if (find(i)==s) ans++;
}
cout<<ans<<endl;
}
return 0;
}
第四题： 动态规划
题目描述：
n个歌曲，求在m的规定下，最多播放多少分钟
解题思路：
如果在第m-1分钟播放了一首新歌，虽然m时间已到，但是仍然会播放完，所以很容易想到：先找出最长的歌曲A,在除了最长的歌曲之外的n-1首歌中求出一个和为s的组合，使s最接近m-1，答案就是s+A。
其中在n个数中求一个最接近s的组合，使用01背包实现，参考：https://blog.csdn.net/qq_21989927/article/details/108502783
证明解题思路：
答案一定包含最长的歌曲吗？
首先答案一定包含最长的歌曲A。
要是答案中没有最长歌曲，则完全可以把最后播放的那首歌曲换成最长的歌曲，答案肯定是更优的。
那最长的歌曲不在最后出现会怎么样？因为我们本意是在除最长歌曲的n-1首中寻找最接近m的，那如果最长的歌曲A参与拼凑S可以更接近m，这种情况怎么处理？
假设最长歌曲参与了拼凑m，那么最后播放的一定是除了参与拼凑的m之外的最长的歌曲B。
我们把A和B调换位置，对于答案是没有影响的，所以也不用担心这种情况。
代码：（原始代码丢了，这个应该也对，没法测试）
#include<iostream>
#include<algorithm>
using namespace std;
int a[1005];
int f[100005];
int n,m;
int main(){
cin>>n;
for (int i=1; i<=n; i++) cin>>a[i];
cin>>m;
sort(a+1,a+n+1);
for (int i=1; i<=n-1; i++){
for (int j=m-1; j>=a[i]; j--){
f[j]=max(f[j],f[j-a[i]]+a[i]);
}
}
cout<<f[m-1]+a[n]<<endl;
return 0;
}
总结:
体验很差，最开始登不上，还有第二题恶心，第三题第五题都没来得及写。。。
| 
转播
