1.乒乓球框

思路：

无思路

代码：

#include <iostream>
using namespace std;int main() {string a;string b;int mp[26]={0};cin>>a>>b;for(int i=0;i<b.size();i++){int u=b[i]-'A';mp[u]++;}for(int i=0;i<a.size();i++){int u=a[i]-'A';mp[u]--;}for(int i=0;i<26;i++){if(mp[i]>0){cout<<"No"<<endl;return 0;}}cout<<"Yes"<<endl;return 0;
}

2.组队竞赛

 

思路：

在n*3个人里面选n个人，这n个人每个人都可以在剩下的2*n个人里找出一个比他小的和比他大的，刚好组成n个队伍。要求这n个人值的和最大。

首先排个序，前n个选手成为“配件”，用来充当队伍最低水平那个。所以我们能提前为每一个队伍都选好了水平最低的选手。

接下来从后2*n个选手里面选n个，一定能组成一大一小的关系，于是我们间隔着组就行了。小的那个就是队伍的中间水平。

代码：

#include <iostream>
#include<algorithm>
using namespace std;
const int N=3e5+10;
int a[N];
int main() {int n;cin>>n;for(int i=1;i<=3*n;i++)cin>>a[i];sort(a+1,a+3*n+1);long long ans=0;for(int i=3*n-1;i>=n+1;i-=2){ans+=a[i];}cout<<ans<<endl;return 0;
}

3.删除相邻数字的最大分数

思路：

背包问题。对于值为i的元素，要么选，要么不选。选了值为i的元素,i-1的元素就不能选。

于是dp[i]=max(dp[i-1],dp[i-2]+i*mp[i])

其中dp[i]表示从值为[mi，i]里选的最大值。mi为元素值的左端点。mp[i]表示值为i的元素出现的个数 。选了i,获得的分数就是mp[i]*i。

代码：

#include <iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N=1e5+10;
int a[N];
int dp[10010];
int main() {int n;cin>>n;unordered_map<int,int> mp;int mx=0;int mi=1e9;for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]++;mx=max(mx,a[i]);mi=min(mi,a[i]);}for(int i=mi;i<=mx;i++){dp[i]=max(dp[i-1],dp[i-2]+mp[i]*i);}cout<<dp[mx]<<endl;return 0;
}