2022夏暑假每日一题（六）

一、正方形数组的数目（dfs）

任意门
题意：很基础的dfs，就是给你n个数，然后让你给这些数排序，然后每相邻的两个之和是一个完全平方数，然后问你有多少种解法。

#include <bits/stdc++.h>
using namespace std;
int a[20];
int n,res;
bool st[20];
bool check(int num)
{
    
    int p=(int)sqrt(num);
    return p*p==num;
}

void dfs(int u,int last)
{
    
    if(u>=n)
    {
    
        res++;
        return;
    }
    for(int i=0;i<n;i++)
    {
    
        if(i>0&&!st[i-1]&&a[i]==a[i-1])continue;
        if(st[i])continue;
        if(check(last+a[i]))
        {
    
            st[i]=true;
            dfs(u+1,a[i]);//递归下一位置
            st[i]=false;
        }
    }
}

int main()
{
    
    cin>>n;
    for(int i=0;i<n;i++)
    {
    
        cin>>a[i];
        st[i]=false;//没有访问过
    }
    sort(a,a+n);//排序，方便删除重复元素
    for(int i=0;i<n;i++)
    {
    
        if(i&&a[i]==a[i-1])continue;
        st[i]=true;
        dfs(1,a[i]);
        st[i]=false;
    }
    cout<<res<<endl;
    return 0;
}

二、二叉树（找规律）

任意门
题意：给你一个二叉树，然后再给你两个数，让你找他们的公共父节点。

我的写法：
其实根本都不用建树那些的，只用找到根和左右儿子之间的关系即可。

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

int main()
{
    
    int x,y;
    cin>>x>>y;
    if(x>y)
    {
    
        int res=x;
        x=y;
        y=res;
    }
    while(x||y)
    {
    
       // cout<<x<<" "<<y<<endl;
        if(y==x)
        {
    
            cout<<x<<endl;
            return 0;
        }
        if((y-1)%2==0)y=(y-1)/2;
        else y/=2;
        if(y<x)
        {
    
            if((x-1)%2==0)x=(x-1)/2;
            else x/=2;
        }
    }


    return 0;
}

然而，y总的更加简洁

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

int main()
{
    
    int x,y;
    cin>>x>>y;
   while(x!=y)
   {
    
       if(x>y)x/=2;
       else y/=2;
   }


    return 0;
}

三、围圈报数（模拟、链表）

任意门
题意：有n个人开始1，2，3报数，每次报到3的那个人就得退出去，直到所有的人都退出去。

我们可以运用环形链表来求解。

#include <bits/stdc++.h>
using namespace std;
const int N=55;
int ne[N];

int main()
{
    
    int T,n;
    cin>>T;
    while(T--)
    {
    
        cin>>n;
        for(int i=1;i<n;i++)
            ne[i]=i+1;
        ne[n]=1;
        int p=n;
        for(int i=0;i<n;i++)
        {
    
            p=ne[ne[p]];//每次都是跳两个
            cout<<ne[p]<<" ";
            ne[p]=ne[ne[p]];
        }
        cout<<endl;
    }
    return 0;
}

四、排列与二进制（数论、阶层分解）

任意门
题意：给两个数，看这两个数组合成的排列数中有多少个因子2。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(int n,int m)
{
    
    ll res=0;
    for(int i=n-m+1;i<=n;i++)
    {
    
        if(i%2==0)
        {
    
            int k=i;
            while(k)
            {
    
            if(k%2!=0)break;
            res++;
            k/=2;
            }
        }
    }
    return res;
}
int main()
{
    
    int n,m;
    while(cin>>n>>m,n&&m)
    {
    
       ll ans=f(n,m);
        cout<<ans<<endl;
    }
    return 0;
}

阶层分解

y总这道题用的是一个公式，阶层分解

f(n,p)后面的表达式表示的是n！中包含p元素的个数是多少

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(int n,int m)
{
    
    ll res=0;
    for(int i=n-m+1;i<=n;i++)
    {
    
        if(i%2==0)
        {
    
            int k=i;
            while(k)
            {
    
                  if(k%2!=0)break;
            res++;
           k/=2;
            }
        }
    }
    return res;
}
int main()
{
    
    int n,m;
    while(cin>>n>>m,n&&m)
    {
    
       ll ans=f(n,m);
        cout<<ans<<endl;
    }
    return 0;
}

五、二叉树（图上最短路–dfs,dijkstra、lca最近公共祖先问题）

任意门
题意：二叉树中询问两个结点中的最短距离。
这道题目的数据范围为：

所以，我们只用把数据范围控制到$n^2$以内即可。

树上的两个结点之间的距离是唯一的。所以dfs就可以了。

树上最短路径—》LCA

如果是最近公共祖先（LCA）来做题的话，我们就要找到他们的最近公共节点，然后算出两个点到这个公共节点的距离相加即可。

我们这里就是用最短路径LCA来求的。

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=1010;
int l[N],r[N],p[N];//左儿子、右儿子、父节点
int dist[N];

void dfs(int u,int d)
{
    
    dist[u]=d;
    if(l[u]!=-1)dfs(l[u],d+1);
    if(r[u]!=-1)dfs(r[u],d+1);
}

int get_lca(int a,int b)
{
    
    if(dist[a]<dist[b])return get_lca(b,a);
    while(dist[a]>dist[b])a=p[a];
    while(a!=b)a=p[a],b=p[b];
    return a;
}

int main()
{
    
    int T;
    cin>>T;
    while(T--)
    {
    
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
    
            int a,b;
            cin>>a>>b;
            l[i]=a,r[i]=b;
            if(a!=-1)p[a]=i;
            if(b!=-1)p[b]=i;
        }
        dfs(1,0);
        while(m--)
        {
    
            int a,b;
            cin>>a>>b;
            int c=get_lca(a,b);
            cout<<dist[a]+dist[b]-2*dist[c]<<endl;
        }
    }

	return 0;
}

六、质数（bfs、dfs、试除法、暴力枚举）

任意门

题意：即题目，给定一个正整数 X，请你在 X 后面添加若干位数字（至少添加一位数字；添加的数不能有前导0），使得结果为质数，在这个前提下所得的结果应尽量小。

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

bool is_prime(int x)//试除法
{
    
    if(x<2)return false;
    for(int i=2;i*i<=x;i++)
        if(x%i==0)return false;
    return true;
}

int main()
{
    
    int T;
    cin>>T;
    while(T--)
    {
    
        int x;
        cin>>x;
        for(int i=1;;i++)
        {
    
            string str=to_string(x)+to_string(i);//先用字符串拼接起来
            int y=stoi(str);//然后再转化为数字
            if(is_prime(y))
            {
    
                cout<<y<<endl;
                break;
            }
        }
    }
    
    return 0;
}