《暑假每日一题》Week 7：7.18 - 7.24

Day 1 ：AcWing 4519. 正方形数组的数目

题目链接：

AcWing 4519. 正方形数组的数目

关键词：

dfs

题意：

给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组，返回 A 的正方形排列的数目。

思路：

深搜枚举每个位置，确保每次用的是某类数的第一个数

AC代码：

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

const int N = 13;
int w[N];
bool st[N];
int ans;
int n;
    
bool check(int n)
{
    
    int x = sqrt(n);
    return x * x == n;
}

void dfs(int u, int last)
{
    
    if (u == n) ans ++;
    else
    {
    
        for (int i = 0; i < n; i ++)    // 所有的数
        {
    
            if (st[i])  continue;  // 若第i个数被用过了，跳过
            // 第 0 个数一定是某类数的第一个数
            // 前一个数没有被用过，且当前数等于前一个数，说明不是第一个没有被用过的数
            if (i && !st[i - 1] && w[i] == w[i - 1])    continue;   // 若不是某类数第一个没被用过的数，跳过
            if (!check(last + w[i])) continue;      // 不能组成平方数，跳过
            
            // 用当前这个数
            st[i] = true;
            
            dfs(u + 1, w[i]);
            
            // 恢复现场
            st[i] = false;
        }  
    }
     
}


int main()
{
    

    cin >> n;
    for (int i = 0; i < n; i ++)    cin >> w[i];
    sort(w, w + n);
    
    for (int i = 0; i < n; i ++)
        if (!i || w[i] != w[i - 1])         // 若i == 0 或 i 是某一类数的第一个数
        {
    
            st[i] = true;
            dfs(1, w[i]);
            st[i] = false;
        }
        
    cout << ans << endl;
    return 0;
}

Day 2 ：AcWing 3432. 二叉树

题目链接：

AcWing 3432. 二叉树

关键词：

二叉树

题意：

一棵二叉树，给定两个结点 x 和 y，求他们的公共父节点

思路：

每次取 x 和 y 中的小值，进行除 2，直到两个结点相等，就为父结点

AC代码：

#include <iostream>

using namespace std;

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

Day 3 ：AcWing 3559. 围圈报数

题目链接：

AcWing 3559. 围圈报数

关键词：

约瑟夫环，环形链表

题意：

N 个人围成一圈顺序编号，从 1 号开始按 1、2、3 顺序报数，报 3 者退出圈外，其余的人再从 1、2、3 开始报数，报 3 的人再退出圈外，依次类推，按退出顺序输出每个退出人的原序号。

思路：

模拟循环链表

AC代码：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 55;
int ne[N];
int n;

int main()
{
    
    int T;
    cin >> T;
    while (T --)
    {
    
        cin >> n;
        
        // 初始化循环链表
        for (int i = 1; i < n; i ++)    ne[i] = i + 1;
        ne[n] = 1;
        
        
        int pre = n;        // 记录前驱
        for (int i = 0; i < n; i ++)
        {
    
            pre = ne[ne[pre]];
            cout << ne[pre] << ' ';
            ne[pre] = ne[ne[pre]];
        }
        cout << endl;
    }

    return 0;
}

Day 4 ：AcWing 3588. 排列与二进制

题目链接：

AcWing 3588. 排列与二进制

关键词：

组合排列、二进制

题意：

给定一个排列数，算出其二进制表示的后面有多少个连续的零

思路：

二进制末尾有多少个0,就是p(n,m)中有几个2因子， ans = f(n,2)−f(n−m,2)

AC代码：

#include <iostream>

using namespace std;

int f(int n, int p)
{
    
    int res = 0;
    while (n)
    {
    
        res += n / p;
        n /= p;
    }
    return res;
}

int main()
{
    
    int n, m;
    while (cin >> n >> m, n)
    {
    
        cout << f(n, 2) - f(n - m, 2) << endl;
    }
    
    return 0;
}

Day 5 ：AcWing 3555. 二叉树

题目链接：

AcWing 3555. 二叉树

关键词：

二叉树，LCR

题意：

查询的两个结点之间的最短路径长度

思路：

用 dist 数组存放点到根结点的距离，从a -> b的距离就等于dist[a] + dist[b] - dist[c] * 2，其中 c 为a，b的公共父结点

AC代码：

#include <iostream>
using namespace std;

const int N = 1e3 + 5;

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, n, m;
    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 --)                // m个询问
        {
    
            int a, b;
            cin >> a >> b;
            int c = get_lca(a, b);
            cout << dist[a] + dist[b] - dist[c] * 2 << endl;
        }
    }
    return 0;
}

Day 6 ：AcWing 4520. 质数

题目链接：

AcWing 4520. 质数

关键词：

试除法、质数、字符串

题意：

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

思路：

从 1 开始枚举转化为字符串拼接，再利用 stoi 函数将字符串转换为 int，用试除法进行判断素数

AC代码：

#include <iostream>

using namespace std;

bool is_prime(int n)
{
    
    if (n == 1) return false;
    for (int i = 2; i <= n / i; i ++)
        if (n % i == 0)
            return false;
    
    return true;
}

int main()
{
    
    int T, x;
    cin >> T;
    while (T --)
    {
    
        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;
}