JYUACM训练周赛1题解

          _____                _____                    _____                    _____                    _____          
         /\    \              |\    \                  /\    \                  /\    \                  /\    \         
        /::\    \             |:\____\                /::\    \                /::\    \                /::\____\        
        \:::\    \            |::|   |               /::::\    \              /::::\    \              /::::|   |        
         \:::\    \           |::|   |              /::::::\    \            /::::::\    \            /:::::|   |        
          \:::\    \          |::|   |             /:::/\:::\    \          /:::/\:::\    \          /::::::|   |        
           \:::\    \         |::|   |            /:::/__\:::\    \        /:::/  \:::\    \        /:::/|::|   |        
           /::::\    \        |::|   |           /::::\   \:::\    \      /:::/    \:::\    \      /:::/ |::|   |        
  _____   /::::::\    \       |::|___|______    /::::::\   \:::\    \    /:::/    / \:::\    \    /:::/  |::|___|______  
 /\    \ /:::/\:::\    \      /::::::::\    \  /:::/\:::\   \:::\    \  /:::/    /   \:::\    \  /:::/   |::::::::\    \ 
/::\    /:::/  \:::\____\    /::::::::::\____\/:::/  \:::\   \:::\____\/:::/____/     \:::\____\/:::/    |:::::::::\____\
\:::\  /:::/    \::/    /   /:::/~~~~/~~      \::/    \:::\  /:::/    /\:::\    \      \::/    /\::/    / ~~~~~/:::/    /
 \:::\/:::/    / \/____/   /:::/    /          \/____/ \:::\/:::/    /  \:::\    \      \/____/  \/____/      /:::/    / 
  \::::::/    /           /:::/    /                    \::::::/    /    \:::\    \                          /:::/    /  
   \::::/    /           /:::/    /                      \::::/    /      \:::\    \                        /:::/    /   
    \::/    /            \::/    /                       /:::/    /        \:::\    \                      /:::/    /    
     \/____/              \/____/                       /:::/    /          \:::\    \                    /:::/    /     
                                                       /:::/    /            \:::\    \                  /:::/    /      
                                                      /:::/    /              \:::\____\                /:::/    /       
                                                      \::/    /                \::/    /                \::/    /        
                                                       \/____/                  \/____/                  \/____/         
                                                                                                                         

夹心饼干

题目大意

给一个长度为3的字符串，判定是否首尾相同。

思路

一个字符串数组 ，判断是否 即可。

代码

#include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;
    
    if (s[0] == s[2]) cout << "YES";
    else cout << "NO";
    
    return 0;
}

化简分数

题目大意

给两个分数，求两者的和的最简形式。

思路

知识点：最大公约数。

两个分数相加：，接下就是化简 ，化简分数本质就是将分子分母的最大公约数给约掉，所以接下来就是求 和 的最大公约数，再将这两个数都除以最大公约数。

代码

#include <iostream>
#include <algorithm>

using namespace std;

void solve()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    a = a * d + c * b;
    b = b * d;
    int num = __gcd(a, b);
    a /= num;
    b /= num;
    cout << a << ' ' << b << '\n';
}

int main()
{
    int t;
    cin >> t;
    while (t --) solve();
    return 0;
}

子序列的权值最小值

题目大意

给定一组长度为 的数列，求数列的非空子序列的最小权值。

非空子序列权值的定义为：。

思路

知识点：位运算

关于按位与运算，有一个性质是 ，而相与的数越多，结果可能会越小，所以直接全部数进行与运算，结果一定是最小的。

代码

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int res = (1ll << 32) - 1;
    for (int i = 0; i < n; i ++) {
        int x;
        cin >> x;
        res &= x;
    }
    cout << res;
    
    return 0;
}

小R排数字

题目大意

给一个正整数，保证所有数位都不是0，要求将所有数位上的数进行重排，问是否可以组成一个数是4的倍数。

思路

知识点：数学，思维。

因为100是4的倍数，所以所有100的倍数都是4的倍数，于是对于一个数，我们只需要考虑最低两位数是否是4的倍数即可，重排数位相当于找到两位数是4的倍数，如果找不到就不可能组成4的倍数。最后我们还要特殊处理一位数的情况。

代码

#include <iostream>

using namespace std;

void solve()
{
    string s;
    cin >> s;
    
    if (s.size() == 1) {
        if ((s[0] - '0') % 4) cout << "NO" << '\n';
        else cout << "YES" << '\n';
        return ;
    }
    
    for (int i = 0; i < s.size(); i ++)
        for (int j = 0; j < s.size(); j ++) {
            if (i == j) continue;
            int num = (s[i] - '0') * 10 + s[j] - '0';
            if (num % 4 == 0) return void(cout << "YES" << "\n");
        }
    cout << "NO" << '\n';
}

int main()
{
    int t;
    cin >> t;
    while (t --) solve();
    return 0;
}

小红的陡峭值（三）easy

题目大意

定义字符串的陡峭值为：所有相邻字符的Ascii 码差值的绝对值之和。 现给定一个长度为 的由小写字母组成的字符串，求所有长度为 的连续子串的陡峭值之和。

思路

知识点：前缀和。

要处理长度为 的连续子串的陡峭值之和，如果是暴力的枚举所有长度为 的连续子串肯定是不可行的，所以要优化这一步，即用什么办法可以让我们用接近 的时间复杂度获得长度为 的连续子串的陡峭值，可以观察到这长度为 的字符串陡峭值就是整个字符串陡峭值的一个长度为 的区间之和，快速求区间和的算法可以联想到前缀和算法。

先预处理所有的陡峭值，然后做前缀和，接下就是枚举所有长度为 的连续子串的陡峭值求和。

代码

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10;

int main()
{
    int n, k;
    cin >> n >> k;
    
    string s;
    cin >> s;
    
    auto func = [](char a, char b) -> ll {
        ll num1 = a - 'a' + 1;
        ll num2 = b - 'a' + 1;
        return abs(num1 - num2);
    };
    
    vector<ll> a;
    a.emplace_back(0);
    for (int i = 1; i < n; i ++) 
        a.emplace_back(a.back() + func(s[i], s[i - 1]));
    
    ll res = 0;
    for (int i = k - 1; i < n; i ++)
        res += a[i] - a[i - k + 1];
    
    cout << res;
    
    return 0;
}

旅游

题目大意

给一棵无向树，每次选择的节点都会自动覆盖相邻节点，从 s 出发，求最大覆盖点集个数。

思路

知识点：树形DP

一道很板的树形DP。

一个选择的节点会自动覆盖相邻节点，意味着我们选择的点集一定是不相邻，而每个点存在两个性质：选或不选。

了解完题目的性质后，我们开始进行dp的套路。

定义dp数组：

• ：不选 节点时，以 为根的子树的最大覆盖点集个数。

• ：选 节点时，以 为根的子树的最大覆盖点集个数。

完成转移方程：

• 不选 节点时，它的子节点 可以选也可以不选，那我们就选一个最大的，所以 。
• 选 节点时，它的子节点一定不可以选，所以 。

数组初始化：

明显的，当 节点被选，就有一个点了，所以所有的 。

最后就是跑树进行dp了。

代码

#include <iostream>
#include <vector>

using namespace std;

const int N = 5e5 + 10;

int n, s;
vector<int> g[N];
int dp[N][2];

void dfs(int u, int fa)
{
    dp[u][1] = 1;
    for (auto v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        
        dp[u][1] += dp[v][0];
        dp[u][0] += max(dp[v][1], dp[v][0]);
    }
}

int main()
{
    cin >> n >> s;
    for (int i = 1; i < n; i ++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    
    dfs(s, -1);
    cout << dp[s][1];
    
    return 0;
}

白兔的字符串

题目大意

给定一个字符串 ，和 个字符串 ，询问每一个字符串 ，有多少个子串是和 循环同构的。

循环同构：对于一个字符串a，每次把a的第一个字符移动到最后一个，如果操作若干次后能够得到字符串b，则a和b循环同构。

思路

知识点：字符串哈希，二分。

快速查询子串是否是字符串 的循环同构，可以联想到哈希，试过STL的unordered_map会超时，所以这题必须手写哈希。

我们可以预处理字符串 的所有循环同构，得到哈希值后存起来进行排序。

对于每一个字符串 ，也做一遍哈希，然后截取子串的哈希值用二分查找字符串 的所有循环同构中是否有相等的哈希值，如果有就记1。

代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef unsigned long long ull;

const int P = 131, N = 2e6 + 10;

int n;
string t;
ull h[N], p[N];
ull hh[N], pp[N];
vector<ull> a;

ull get(int l, int r) 
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> t;
    int len = t.size();
    t += t;
    t = '0' + t;
    p[0] = 1;
    for (int i = 1; i < t.size(); i ++) {
        h[i] = h[i - 1] * P + t[i] - 'a';
        p[i] = p[i - 1] * P;
    }
    
    for (int i = 1; i <= len; i ++) {
        ull x = get(i, i + len - 1);
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    
    pp[0] = 1;
    for (int i = 1; i < N; i ++) pp[i] = pp[i - 1] * P;
    
    cin >> n;
    while (n --) {
        string s;
        cin >> s;
        
        s = '0' + s;
        for (int i = 1; i < s.size(); i ++) hh[i] = hh[i - 1] * P + s[i] - 'a';
        
        int res = 0;
        for (int i = 1; i + len - 1 < s.size(); i ++) {
            ull x = hh[i + len - 1] - hh[i - 1] * pp[len];
            int pos = lower_bound(a.begin(), a.end(), x) - a.begin();
            if (pos != a.size() && a[pos] == x) res ++;
        }
        
        cout << res << '\n';
    }
    return 0;
}