吉比特笔试编程题题解（2021.4.29

吉比特4.29笔试
编程第一题 常规分解

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


int main()
{
  int ans=0;
  for(int i=2;i*i<=n;i++)
  {
    while(n%i==0)
    {
      ans++;
      n/=i;
    }
  }
  if(n>1)
    ans++;
  cout<<ans<<endl;
}

编程第二题 不会做 直接无脑搜了，
直接搜过了40%
加了剪枝过了80%

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char a[50];
char b[50];
int len1,len2;
int ans=0;
ull h[50];
ull p[50];
ull base=233;
ull getl(int l,int r)
{
  return h[r]-h[l-1]*p[r-l+1];
}
void dfs(int id,int now,unordered_map<char,ull>mp,unordered_map<char,int>mpp,unordered_map<ull,int>vis,unordered_map<ull,char>viss)
{
     int l=now;
     if(len2-now<len1-id)
      return ;
     if(id==len1+1&&now==len2+1)
     {
        ans++;
        return ;
     }
     if(id>len1||now>len2)
      return ;
     if(mp[a[id]])
     {
        int r=l+mpp[a[id]];
        if(mp[a[id]]!=getl(l,r))
          return ;
        dfs(id+1,r+1,mp,mpp,vis,viss);
        return ;
     }
     for(int r=now;r<=len2;r++)
     {    

          if(len2-r<len1-id-1)
            break;
          ull v=getl(l,r);
          if(vis[v]&&viss[v]!=a[id])
            continue;
          mp[a[id]]=getl(l,r);
          mpp[a[id]]=r-l;
          vis[v]++;
          viss[v]=a[id];
          dfs(id+1,r+1,mp,mpp,vis,viss);
          mp[a[id]]=0;
          mpp[a[id]]=0;
          vis[v]--;
     }
}
int main()
{
    scanf("%s",a+1);
    scanf("%s",b+1);
   // cin>>a+1>>b+1;
    len1=strlen(a+1);
    len2=strlen(b+1);
    p[0]=1;
    for(int i=1;i<=len2;i++)
    {
         p[i]=p[i-1]*base;
         h[i]=h[i-1]*base+b[i];
    }
    unordered_map<char,ull>mp;
    unordered_map<char,int>mpp;
    unordered_map<ull,int>vis;
    unordered_map<ull,char>viss;
    dfs(1,1,mp,mpp,vis,viss);
    printf("%d\n",ans);
}