Day 18

1.爱吃素

爱吃素

1.1解析

1.2代码

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

bool isprim(long long x)
{
    if(x<2)return false;//1是不做判断的
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)return false;
    return true;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long a,b;
        cin>>a>>b;//x=a*b
        if((a==1&&isprim(b))||(b==1&&isprim(a)))cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

2.AB33 相差不超过k的最多数

AB33 相差不超过k的最多数
滑动窗口

2.1解析

2.2代码

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

int n,k;
int main()
{
    cin>>n>>k;
    vector<int> arr(n);
    for(int i=0;i<n;i++)cin>>arr[i];
    //排序+滑动窗口
    sort(arr.begin(),arr.end());
    int l=0,r=0,ret=1;
    while(r<n)
    {
        while(l<n&&arr[r]-arr[l]>k)//判断
        {
            l++;
        }
        //更新结果
        ret=max(ret,r-l+1);
        r++;
    }
    cout<<ret<<endl;
    return 0;
}

3.DP19 最长公共子序列(一)

DP19 最长公共子序列(一)
动态规划

3.1解析

3.2代码

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

int main()
{
    int n,m;
    cin>>n>>m;
    string s1,s2;
    cin>>s1>>s2;

    //1.创建dp表
    vector<vector<int>> dp(n+1,vector<int>(m+1));
    //2.填表
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}