【HT-050-Div.4】核桃新手组周赛个人题解

· · 题解

0.序言

上难度了

100+95+100+100=395

T1

极品模拟。

用两个变量来记录借位，按计算方法模拟即可。时间复杂度 O(1)。

#include <bits/stdc++.h>
using namespace std;
int a[4][4];
int main()
{
    for (int i = 1; i <= 3; i++)
    {
        int x[7], f=0, g=0;
        for(int i = 1;i <= 6; i++) cin>>x[i];
        if(x[6]-x[3]<0) f=1,a[i][3]=60+x[6]-x[3];
        else a[i][3] = x[6]-x[3];
        if(x[5]-x[2]-f<0) g=1,a[i][2]=60-f+x[5]-x[2];
        else a[i][2] = x[5]-x[2]-f;
        a[i][1] = x[4]-x[1]-g;
    }
    for(int i = 1;i <= 3; i++)
    {
        for(int j = 1; j <= 3; j++) cout<<a[i][j] << " ";
        cout << endl;
    }
}

T2

史上最强 T2。

我不到正解咋样啊，我用 Miller-Rabin 测试法做的。

首先对于偶数 n，要将其拆分为两个质数的乘积，由奇偶数乘法原理，奇数乘偶数或偶数乘偶数结果才为偶数,必然会有一个质数为 2，因为 2 为唯一偶质数。那么我们只需要判断 \frac{n}{2} 是否为质数即可。

注意到 n\le10^{12}，那么 \frac{n}{2}\le5\times 10^{11}，使用传统的循环枚举法来判断质数不现实，于是我选择了更高效的 Miller-Rabin 测试法。

简而言之，Miller-Rabin 是一种概率测试，通过选择适当的基可以确定性地较快地检测素数。参考文献。

模板位于洛谷的U287941。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool check(ll n) {
    if (n <= 1) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;
    vector<ll> example = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (ll p : example)
        if (n % p == 0) return n == p;
    ll d = n - 1;int s = 0;
    while (d % 2 == 0)
    {
        d /= 2;
        s++;
    }
    vector<ll> NEKO = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (ll a : NEKO) {
        if (a >= n) continue;
        __int128 x = 1,a_mod = a,mod = n;ll temp = d;
        x = 1; a_mod = a % mod;
        while (temp > 0)
        {
            if (temp % 2 == 1)
                x = (x * a_mod) % mod;
            a_mod = (a_mod * a_mod) % mod;
            temp /= 2;
        }
        if (x == 1 || x == mod - 1) continue;
        bool flag = true;
        for (int i = 0; i < s - 1; ++i)
        {
            x = (x * x) % mod;
            if (x == mod - 1)
            {
                flag = false;
                break;
            }
        }
        if (flag)
            return false;
    }
    return true;
}
int main()
{
    ll n;
    cin >> n;
    if (n == 2)
    {
        cout << -1 << endl;
        return 0;
    }
    ll k = n / 2;
    if (check(k)) cout << 2 << " " << k << endl;
    else cout << -1 << endl;
    return 0;
}

T3

考虑模拟，枚举字符串，并记录 s_i 和 s_{i+1} 的起重是否互异，如果两者轻重相同则答案为 F，否则为 T。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int T, n;
    cin >> T >> n;
    while (T--)
    {
        string s;
        cin >> s;
        int book[27] = {0};
        for (char c : s) book[c - 'a']++;
        bool flag = true;
        for (int i = 0; i < n - 1; ++i)
        {
            bool now = book[s[i] - 'a'] > 1;
            bool nex = book[s[i+1] - 'a'] > 1;
            if (now == nex)
            {
                flag = false;
                break;
            }
        }
        cout << (flag ? 'T' : 'F') << '\n';
    }
    return 0;
}

T4

哇这题我比赛做过!

直接模拟每一次操作肯定不现实，所以我们选择记录每一行与每一列被操作的次数，最后遍历每一个格子，按照该格子所处的行列操作次数输出即可。具体而言，a_{i,j} 最终的颜色，取决于第 i 行的操作次数 r_i 和第 j 列的操作次数 c_j，若操作次数为偶数就无需变化，否则变为相反颜色即可。

注意 long long，时间复杂度 O(k)。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N, M, K;
    cin>>N>>M>>K;
    vector<bool> r(N, false), c(M, false);
    int R = 0, C = 0;
    while (K--)
    {
        char op;int x;
        cin >> op >> x;x--;
        if (op == 'R')
        {
            if (r[x]) R--;
            else R++;
            r[x] = !r[x];
        }
        else
        {
            if (c[x]) C--;
            else C++;
            c[x] = !c[x];
        }
    }
    long long ans = (long long)R * (M - C) + (long long)C * (N - R);
    cout << ans;
    return 0;
}