洛谷十月月赛--第二场

Posted on Edited on In Word count in article: 2.1k Reading time ≈ 8 mins.
没有发挥好，进步空间还是很大的

T1

题意

就是问你在一个有 \(n\) 个点的完全图中，从一个点出发，最多能不重复经过多少条边

分析

  • 如果 \(n\) 是奇数，那么完全图中的所有边都可以访问一次，个数为 \(\dbinom n2\)
  • 如果 \(n\) 是偶数，那么就有一些访问不了了，先给结论，可以访问的最多有 \(\frac {n(n-2)}2+1\)

如果是奇数个点，所有点的度数均为偶数，显然是可以走完所有的边的，很显然乱走都可以

如果是奇数个点，就没有那么容易了，为了能让尽量多的边被访问到，那它应该尽量多走，直到不能再走了

证明

首先，对于一张完全图，它的所有的点是等价的，所以对于个数一定的点集的选法，无论怎么选，它们的拓扑结构都是相同的，即方案唯一

  • 对于奇数个点，随机选一个点为起点，那么对于这个点的访问一定是 出、入 。。。。。。 出、入 ；那么其他点的访问一定是都是 入、出。。。。。。入、出 。即对于起点，每次离开它，都一定会有一点边等着它回来，那它总有一次就出不去了；对于不是起点的点，每次进入它，都一定会有一条边等着它出去，那总有一次，他就进不去了。
  • 对于偶数个点，先让所有的点度数都为 \(n-2\)，那它最后一定会回到起点，此时，起点只有一条边可以走了，它最后走的那条边也是这条边对应的点的最后一条边，就真的走不动了

虽然题看上去不难，但是个人水平低下，需要复习复习基础，见谅

Code

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
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline ll __read()
{
    ll x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

ll T, n;

int main()
{
    T = __read();
    while (T--) {
        n = __read();
        if (n & 1) printf("%lld\n", n * (n - 1) / 2);
        else if (n > 2) printf("%lld\n", ((n - 1) * 2 + (n - 2) * (n - 2)) / 2);
        else puts("1");
    }
}

T2

等杨巨把我讲懂了我再来补

T3

等题解出来了再来补

T4

题意

有一个马最开始在 \((0,0)\)，它的每一步可以走一个 \(a\times b\) 的矩形（ 即能够从 \((x,y)\) 到达 \((x\pm a,y\pm b)\) 或 \((x\pm b,y\pm a)\) ）。

若马通过上述移动方式可以到达棋盘中任意一个点，那么 \(p(a,b)=1\)，否则 \(p(a,b)=0\)。

给你 \(T\) 组询问，每组给你一个 \(n\)，让你求： \[ \left(\sum_{a=1}^n\sum_{b=1}^np(a,b)\right)\mod {2^{64}} \]

分析

首先，本质不同的行走方案有四种，即 \((a,b),(b,a),(-a,b),(-b,a)\)，那么设这四种本质不同的分别走了 \(x_1,x_2,x_3,x_4\) 次，那么能够走满这个棋盘的充要条件是： \[ \begin{cases} ax_1+bx_2-ax_3-bx_4=1\\ bx_1+ax_2+bx_3+ax_4=0 \end{cases} \] 只要满足了这个条件，它就可以上下左右移动了，就是说可以走满整张棋盘

那么可以化简一下上式，然后得到： \[ a((x_1+x_2)-(x_3-x_4))+b((x_1+x_2)+(x_3-x_4))=1\\ \Rightarrow a(x-y)+b(x+y)=1 \] 那么此时可以得到两条性质：

  • \(a\perp b\)
  • \(a\not\equiv b\pmod 2\)

第一条的话，就是因为 \(akx+bky=k\gcd(a,b)\)；第二个的话，就是说 \(x-y\) 和 \(x+y\) 一定是奇偶性相同的而且只能是奇数，那么 \(a、b\) 一定一奇一偶，正确性显然

所以可以得到 \(p(a,b)=[a\perp b \land a、b奇偶性不相同]\)

算法一

既然已经知道了 \(a、b\) 奇偶性不同，那么就可以限制谁是奇数谁是偶数，最后 \(\times2\) 就可以

时间复杂度 \(O(n^2)\)，期望得分 \(20\)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>

int n, t;

int gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main()
{
    scanf ("%d", &t);
    while (t--) {
        int ans(0);
        scanf ("%d", &n);
        for (int i = 1; i <= n; i += 2)
            for (int j = 2; j <= n; j += 2) 
                if (gcd(i, j) == 1) ++ans;
        printf("%d\n", ans * 2);
    }
}

算法二

根据算法一，我们知道题目限制了两个数的奇偶性，那么我们先试着表达一下，再看看可以怎么化简 \[ \sum_{a=1}^n\sum_{b=1}^np(a,b)=2\times\sum_{a=1}^n\sum_{b=1}^n[a\perp b且a为偶数b为奇数]\\ \] 又因为 \(a\perp b\) 且 \(a\) 是偶数 \(b\) 是奇数，那么 \(a\rightarrow \frac a2\)，也是可以得到 \(a\perp b\) 的

所以又得到了 \[ \begin{aligned} \sum_{a=1}^n\sum_{b=1}^n[a\perp b且a为偶数b为奇数]&=\sum_{a=1}^{\frac n2}\sum_{b=1}^n[a\perp b且b为奇数]\\ &=\sum_{a=1}^{\frac n2}\sum_{b=1}^n[a\perp b]-\sum_{a=1}^{\frac n2}\sum_{b=1}^n[a\perp b且b是偶数] \end{aligned} \] 感觉这个容斥还是很好想到的，那么就可以继续往下走，定义记号 \(f(n,m)\) \[ \begin{aligned} f(n,m)&=\sum_{a=1}^n\sum_{b=1}^m[a\perp b且a为偶数b为奇数]\\ &=\sum_{a=1}^{\frac n2}\sum_{b=1}^m[a\perp b]-\sum_{a=1}^{\frac n2}\sum_{b=1}^m[a\perp b且b是偶数]\\ &=\sum_{a=1}^{\frac n2}\sum_{b=1}^m[a\perp b]-\sum_{a=1}^{\frac n2}\sum_{b=1}^m[a\perp b且a是奇数b是偶数]\\ &=\sum_{a=1}^{\frac n2}\sum_{b=1}^m[a\perp b]-f(m,\frac n2) \end{aligned} \] 为了方便表述，就令 \[ \begin{aligned} s(n,m)&=\sum_{a=1}^n\sum_{b=1}^m[a\perp b]\\ &=\sum_{a=1}^n\sum_{b=1}^m\sum_{d|\gcd(a,b)}\mu(d)\\ &=\sum_{d=1}^{\min(a,b)}\mu(d)\left\lfloor\frac nd\right\rfloor\left\lfloor\frac md\right\rfloor \end{aligned} \] 所以 \(f(n,m)=s(\frac n2,m)-f(m,\frac n2)\)

然后 \(s\) 的计算可以数论分块，\(f\) 递归计算，所以时间复杂度为 \(O(\log n\sqrt n)\)

Code

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
#include <cstdio>
#include <algorithm>

using namespace std;

typedef unsigned long long ll;
const int maxn = 1e7 + 10;
int n, t, cnt;
ll mu[maxn];
int p[maxn];
bool vis[maxn];

inline void init()
{
    mu[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) p[++cnt] = i, mu[i] = -1;
        for (int j = 1; j <= cnt && i * p[j] < maxn; ++j) {
            vis[i * p[j]] = 1;
            if (i % p[j]) mu[i * p[j]] = -mu[i];
            else break;
        }
    }

    for (int i = 1; i < maxn; ++i) mu[i] += mu[i - 1];
}

inline int min(int x, int y)
{
    if (x < y) return x;
    return y;
}

ll solve(int n, int m) 
{
    ll sum(0);
    if (n > m) swap(n, m);
    for (int l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        sum += (mu[r] - mu[l - 1]) * (n / l) * (m / l);
    }
    return sum;
}

ll gc(int n, int m)
{
    if (m == 1) return 0;
    if (n == 1) return m / 2;
    ll total = solve(n, m / 2), cut = gc(m / 2, n);
    return total - cut;
}

int main()
{
    init();
    scanf ("%d", &t);
    while (t--) {
        scanf ("%d", &n);
        ll total = solve(n / 2, n), cut = gc(n / 2, n);
        ll ans = (total - cut) * 2;
        printf ("%llu\n", ans);
    }
}

满分做法

算法二的瓶颈在于空间，开不了 \(10^{11}\) 的数组，所以考虑使用杜教筛或者 \(\rm{Min_{25}}\) 筛啥的，就可以过题了

至于这个的时间复杂的的话，个人感觉是 \(O(\log n\sqrt n+n^{\frac 32})\)，不知道对不对

希望有大佬能告诉我正确的时间复杂的

Code

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
#include <cstdio>
#include <map>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
const int maxn = 1e7 + 10;
ll n, t, cnt;
ull mu[maxn];
int p[maxn];
bool vis[maxn];

inline void init()
{
    mu[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) p[++cnt] = i, mu[i] = -1;
        for (int j = 1; j <= cnt && i * p[j] < maxn; ++j) {
            vis[i * p[j]] = 1;
            if (i % p[j]) mu[i * p[j]] = -mu[i];
            else break;
        }
    }

    for (int i = 1; i < maxn; ++i) mu[i] += mu[i - 1];
}

inline ll min(ll x, ll y)
{
    if (x < y) return x;
    return y;
}

map <ll, ull> Mu;

ull MMu(ll x)
{
    if (x <= maxn) return mu[x];
    if (Mu[x]) return Mu[x];
    ll Ans(1);
    for (ll l(2), r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        Ans -= (r - l + 1) * MMu(x / l);
    }
    return Mu[x] = Ans;
}

ull solve(ll n, ll m) 
{
    ull sum(0);
    if (n > m) swap(n, m);
    for (ll l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        sum += (MMu(r) - MMu(l - 1)) * (n / l) * (m / l);
    }
    return sum;
}

ull gc(ll n, ll m)
{
    if (m == 1) return n / 2;
    if (n == 1) return 0;
    ull total = solve(n / 2, m), cut = gc(m, n / 2);
    return total - cut;
}

inline ll __read()
{
    ll x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int main()
{
    init();
    t = __read();
    while (t--) {
        n = __read();
        ull ans = gc(n, n) * 2;
        printf ("%llu\n", ans);
    }
}