MOGG

每日一题-1

3/29/2021 算法Codeforces

每日一题保持手感，主要做codeforces 1600 - 2200的题

难题有的时候一天做不了一道，补知识点

每次记录一周

# 1500A Going Home

Codeforces Round #707 1500A Going Home

tags： 暴力

题目链接 (opens new window)

这题真的是brain fuck

就是纯暴力，但是乍一看你会觉得暴力会超时

然鹅只要一个和值出现超过四次（见官方题解），一定有解，所以上限是，怎么暴力都能出结果……

点击展开 
#include <bits/stdc++.h>

using namespace std;
//c++14 数字分位符
const int ms = 200'000 + 20;

unordered_map<int, set<int>> m;
int a[ms];

int main(int argc, char const *argv[])
{
    int n;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (size_t i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (size_t i = 1; i <= n; i++)
    {
        for (size_t j = i + 1; j <= n; j++)
        {
            int v = a[i] + a[j];
            m[v].insert(i);
            m[v].insert(j);
            if (m[v].size() >= 4)
            {
                bool flag = false;
                for (int x : m[v])
                {
                    for (int y : m[v])
                    {
                        if (x == y)
                            continue;
                        for (int z : m[v])
                        {
                            if (z == x || z == y)
                                continue;
                            for (int w : m[v])
                            {
                                if (w == x || w == y || w == z)
                                    continue;
                                if (a[x] + a[y] == a[w] + a[z])
                                {
                                    cout << "YES\n";
                                    cout << x << " " << y << " "
                                         << z << " " << w << "\n";
                                    return 0;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << "NO\n";

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

# 1500B Two chandeliers

Codeforces Round #707 1500B Two chandeliers

tags: 二分，数论，中国剩余定理

题目链接 (opens new window)

官方题解写的太迷了……

有两个整数序列，序列初始时，每一个值是不同的。然后，将这两个序列将无限循环的重复下去，即。求最小的长度len，使得[1,len]里包含k个点满足

不难想到使用二分，对每个mid求有多少个点满足

直接求不容易求，但是我们可以求有多少个点满足

假设初始序列中，,那么将会在位置使得

pos 需要满足

pos可以使用中国剩余定理求得（pos 不一定存在）

因为初始序列中的值是不重复的，所以在 里pos只会出现一次，所以我们可以先处理出所有可能的pos

点击展开 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int ms = 500000 + 5;
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    ll gcd = exgcd(b, a % b, x, y);
    ll tp = x;
    x = y;
    y = tp - a / b * y;
    return gcd;
}
ll excrt(const vector<ll> &ai, const vector<ll> &mi)
{
    ll ans = ai[0], M = mi[0]; //第一个式子的解
    for (int i = 1; i < ai.size(); i++)
    {
        ll a = M, b = mi[i], c = (ai[i] - ans % b + b) % b, x, y;
        ll gcd = exgcd(a, b, x, y);
        if (c % gcd != 0)
        {
            return -1; //无解
        }
        ll bg = b / gcd;
        x = c / gcd * x;
        ans += x * M;
        M = bg * M;
        ans = (ans % M + M) % M;
    }
    return (ans % M + M) % M;
}

ll a[ms * 2], b[ms], cover[ms], cnt;

ll count(ll x)
{
    return upper_bound(cover, cover + cnt, x) - cover;
}

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n, m, k;
    cin >> n >> m >> k;
    ll lcm = n * m / gcd(n, m);
    vector<ll> mi = {n, m};
    ll ax;
    for (int i = 0; i < n; i++)
    {
        cin >> ax;
        a[ax] = i + 1;
    }
    for (int i = 0; i < m; i++)
    {
        cin >> b[i];
        if (a[b[i]] > 0)
        {
         	// 预处理出所有可能的pos
            ll tmp = excrt({a[b[i]], i + 1}, mi);
            if (tmp != -1)
            {
                if (tmp == 0)
                    tmp = lcm;
                cover[cnt++] = tmp;
            }
        }
    }
    sort(cover, cover + cnt);
	// 两个序列的对应情况以LCM(n,m)为周期循环
    // 我们可以先算出进行了几个循环，然后处理剩下的
    // 为了方便起见，我们使 1<=k<=n 
    ll base = lcm - count(lcm), res = 0;
    res = (k - 1) / base * lcm;
    k -= (k - 1) / base * base;

    ll l = k, r = lcm + 1, mid, ans = 0;
    while (l < r)
    {
        mid = (l + r) / 2;
        ll rm = mid - count(mid);
        if (rm < k)
        {
            l = mid + 1;
        }
        else
        {
            r = mid;
            ans = mid;
        }
    }
    cout << res + ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

# 1499D The Number of Pairs

Educational Codeforces Round 106 (Rated for Div. 2) (opens new window)

tags：数论，dp

给定三个正整数，求有多少对正整数满足

假设，那么A,B互质，原式变为,

由裴蜀定理可得，，即gcd是x的因数，式子右边的值域是有限的，并且可以在的时间内得出

那么对于可以推出多少个AB？因为AB是互质的，所以对于的某个质因数，只能分配到A，B中的某个上，比如，所有2只能都在A或者都在B上。这个问题我们可以用dp解决。

表示x的最小质因数，表示可以推出多少个AB

点击展开 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#ifdef DEBUG
const int ms = 100 + 5;
#else
const int ms = 2e7 + 5;
#endif

int minPrime[ms], numPrime[ms];
// 埃氏筛求最小素数
void eratosthenes()
{
    int i = 2;
    for (; i * i < ms; ++i)
    {
        if (minPrime[i] == 0)
        {
            minPrime[i] = i;
            for (int j = i * i; j < ms; j += i)
            {
                if (minPrime[j] == 0)
                    minPrime[j] = i;
            }
        }
    }
    for (; i < ms; ++i)
        if (minPrime[i] == 0)
            minPrime[i] = i;
}
void dp()
{
    for (int i = 2; i < ms; i++)
    {
        int j = i / minPrime[i];
        numPrime[i] = numPrime[j];
        if (minPrime[i] != minPrime[j])
        {
            numPrime[i]++;
        }
    }
}
int t, c, d, x;
int solve()
{
    ll res = 0;
    for (int i = 1; i * i <= x; ++i)
    {
        if (x % i != 0)
            continue;
        if ((x / i + d) % c == 0)
        {
            res += 1ll << numPrime[(x / i + d) / c];
        }
        if (i * i != x && (i + d) % c == 0)
        {
            res += 1ll << numPrime[(i + d) / c];
        }
    }
    return res;
}

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t;
    eratosthenes();
    dp();
    while (t--)
    {
        cin >> c >> d >> x;
        cout << solve() << "\n";
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

# 1497E1 Square-free division (easy version)

Codeforces Round #708 (Div. 2) (opens new window)

tags：数论，dp，贪心

给定一个n个正整数的序列，问最少可以划分成几个序列，使得序列中任意两个数的乘积不是某个正整数的平方

一个数a可以表示为质数的乘积,一个数是平方数，当且仅当每个指数都为偶数时成立

那么我们将a处理为

这题就变为判断一个序列里是否有数字出现两次

求a‘的思路和上一题类似

抵消一个新增一个

点击展开 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#ifdef DEBUG
const int ms = 100 + 5;
#else
const int ms = 1e7 + 5;
#endif

int minPrime[ms], numPrime[ms];
// 埃氏筛求最小素数
void eratosthenes()
{
    int i = 2;
    for (; i * i < ms; ++i)
    {
        if (minPrime[i] == 0)
        {
            minPrime[i] = i;
            for (int j = i * i; j < ms; j += i)
            {
                if (minPrime[j] == 0)
                    minPrime[j] = i;
            }
        }
    }
    for (; i < ms; ++i)
        if (minPrime[i] == 0)
            minPrime[i] = i;
}
void dp()
{
    numPrime[1] = 1;
    for (int i = 2; i < ms; i++)
    {
        int j = i / minPrime[i];
        if (numPrime[j] % minPrime[i] == 0)
            numPrime[i] = numPrime[j] / minPrime[i];
        else
            numPrime[i] = numPrime[j] * minPrime[i];
    }
}
int main(int argc, char const *argv[])
{
    eratosthenes();
    dp();
    int t;
    cin >> t;
    while (t--)
    {
        int n, x, res = 0;
        cin >> n >> x;
        set<int> s;
        while (n--)
        {
            cin >> x;
            if (s.count(numPrime[x]))
            {
                s.clear();
                res++;
            }
            s.insert(numPrime[x]);
        }
        if (!s.empty())
        {
            res++;
        }
        cout << res << "\n";
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
Last Updated: 5/24/2021, 6:17:53 AM