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; }
