【强训笔记】day14

NO.1

思路：用一个哈希表，先遍历s1，统计哈希表内的字符个数，在遍历s2，s2中的字符在哈希表中减去，如果哈希表中的字符个数小于0那么就输出No。

代码实现：

#include <iostream>
#include<string>
using namespace std;

int main() {
    string s1,s2;
    while(cin>>s1>>s2)
    {
         int hash[26]={0};
        for(auto ch:s1) hash[ch-'A']++;
        bool ret=true;
        for(auto ch:s2)
        {
           if(--hash[ch-'A']<0)
           {
            ret=false;
            break;
           }
        }
           cout<<(ret?"Yes":"No")<<endl;
    }
}

NO.2

思路：先进行排序，再从倒数第二位每隔一位相加起来，最后输出。

代码实现：

#include <iostream>
#include<algorithm>
using namespace std;

int n;
const int N=1e5+10;
long long arr[3*N];
int main() {
    cin>>n;
    for(int i=0;i<3*n;i++) cin>>arr[i];
    sort(arr,arr+3*n);
    long long sum=0;
    int count=0;
    for(int i=3*n-2;i>=0;i-=2)
    {
     sum+=arr[i];
     count++;
     if(count==n) break;
    }

    cout<<sum<<endl;    
}

NO.3

思路：线性dp+哈希，先将出现的数据存入哈希表中，相同的数进行加和，最后dp推导状态转移方程。

代码实现：

#include <iostream>
using namespace std;

const int N=1e5+10;
int sum[N];
int f[N],g[N];
int n;

int main() {
    cin>>n;
    int x;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        sum[x]+=x;
    }

    for(int i=1;i<N;i++)
    {
        f[i]=sum[i]+g[i-1];
        g[i]=max(f[i-1],g[i-1]);
    }

    cout<<max(f[N-1],g[N-1])<<endl;
}