H,E题

H题方法一：贪心求上升子序列的最少个数

#include<bits/stdc++.h>
using namespace std;

int n,m,cnt,a[5005],f[5005];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    
    vector<int> b;
    for(int i=1;i<=n;i++)//贪心求上升子序列的最少个数
    {
        int idx=0,gap=0x3f3f3f3f;
        for(int j=0;j<b.size();j++)
            if(b[j]<=a[i] && a[i]-b[j]<gap)gap=a[i]-b[j],idx=j;

        if(gap==0x3f3f3f3f)b.push_back(a[i]);
        else b[idx]=a[i];
    }
    cnt=b.size();
    
    if(cnt>m)cout<<"Karashi lovelove"<<endl;//非法
    else cout<<"Karashi cblcd"<<endl;//合法
    
    return 0;
}

贪心做法因为vector b数组是有序的，所以内层循环可以用二分优化为nlogn，可以试一试，数据比较小不优化n^2也能过

H题方法二：动态规划，根据Dilworth定理转换为最长不升子序列的长度问题

#include<bits/stdc++.h>
using namespace std;

int n,m,cnt,a[5005],f[5005];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
        
    //根据Dilworth定理：上升子序列的最少个数==最长不升子序列的长度
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
            if(a[i]<=a[j])f[i]=max(f[i],f[j]+1);
        cnt=max(cnt,f[i]);
    }
    
    if(cnt>m)cout<<"Karashi lovelove"<<endl;//非法
    else cout<<"Karashi cblcd"<<endl;//合法
    
    return 0;
}

E题:数论

暴力是n^2,会超时，想办法处理原等式，需要对算术基本定理有一定的了解

Ai^2==k×Aj， 根据算术基本定理，想要Aj变为平方数，即将Aj 中奇数次幂的质因子变为偶数次幂，所以k就为Aj的每种质因数的偶次幂组合出来的。 所以我们可以先求出最小的k为X，其他的k是在X的基础上乘以其他Aj的质因数偶次幂而来的，所以一定有sqrt(k)%sqrt()==0，故sqrt(X×Aj)一定是Ai=sqrt(k×Aj)的约数，所以倒序枚举先将后面所有的sqrt(X×Aj)存入桶中统计个数，枚举Ai的约数，然后累加其约数之前出现的次数即可

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,res,a[100005];

int f(int x)//返回(X×Aj)
{
    int ans=x;
    for(int i=2;i<=x/i;i++)//分解质因数
    {
        if(x%i==0)
        {
            int cnt=0;
            while(x%i==0)
            {
                cnt++;
                x/=i;
            }
            if(cnt&1)ans*=i;
        }
    }
    if(x>1)ans*=x;
    return ans;
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    
    map<int,int> h;//用于桶计数
    for(int i=n;i>=1;i--)
    {
        int t=a[i];
        for(int j=1;j<=t/j;j++)//枚举a[i]的约数
        {
            if(t%j==0)
            {
                res+=h[j];
                if(t/j!=j)res+=h[t/j];//注意约数是否成对存在
            }
        }
        
        int k=f(t);
        h[sqrt(k)]++;
    }
    
    cout<<res<<endl;
    return 0;
}