主页
Featured image of post ACM比赛总结——2020年 校十月月赛(初赛)

ACM比赛总结——2020年 校十月月赛(初赛)

2020.10.24 ——2020年 校十月月赛(初赛)

文章字数:5274
预计阅读时长: 分钟

比赛链接

题解文件

总结范围

  • *A
  • *C
  • D
  • E
  • *G
  • H
  • J
  • K

注:前面带*号的题因题目简单,为简略总结。

  • D、E因简单而未总结。
  • J因时间原因暂未总结。

*A - 落单水禽

比赛情况:WA

个人方法

利用map映射,找到只出现一次的。

WA原因
字符串操作问题。

使用resizescanf读入的时候,
需注意重新读入时不会删去之前的字符串

如第一次读入了个2333331919,之后又用这个字符串读了个114514
则新的字符串是1145141919

标准思路

采用位运算

$2n+1$个数中,其中只有$1$个数只出现了奇数次
则对所有数进行异或,则可找出出现奇数次的数。

*C - 新概念丢手绢

比赛情况:未完成(看过题目不知道方法)

不难的题,没去认真思考。

思考后会发现:按$1,2, \cdots ,n$这样排列,就是最高分,即输出$n$。

*G - 生活委员

比赛情况:AC

  • 知识点:$\gcd(Fib(a), Fib(b)) = Fib(\gcd(a, b))$

H - 胖生的数学题

比赛情况:未完成(看过题目不知道方法)

题面搬运

题面搬运

题目描述

  • 连乘符号:$\prod_{i=a}^bn=n_an_{a+1}\cdots*n_{b-1}*n_b$

最近,小胖生学习了一个新的东西:GCD,他发现GCD真是一个神奇的东西,今天,老师给他布置了一道关于GCD的题,他很快就算出来了,因此,为了寻找优越感,他想考考你,看你会不会。

题目如下:

输入一行包含六个正整数$a,b,c,d,x,y$,求$\prod_{i=a}^{b}\prod_{j=c}^{d}\gcd(x^{i},y^{j}) \mod 998244353$。

注:这里$\gcd(a,b)$表示a和b的最大公约数。

  • 题目理解补充:
    这里两个连乘符号代表的是分别乘$\gcd(x^{a\sim b},y^{c\sim d})$。

    如:
    $a=1,b=2$;$c=3,d=4$
    则为:$\gcd(x^1,y^3)\gcd(x^1,y^4)\gcd(x^2,y^3)*\gcd(x^2,y^4)$

数据范围

$0 \le a,b,c,d \le 3e6$
$a \le b$
$c \le d$

$0<x,y \le 1e9$

输入格式

一行,包含六个正整数。

输出格式

一行,计算得到的结果。

样例数据

第一组

输入

1 2 1 2 8 4

输出

2048

第二组

输入

1 2 3 4 120 180

输出

235140177

解释:

$\gcd(120^1,180^3)=120$
$\gcd(120^1,180^4)=120$
$\gcd(120^2,180^3)=14400$
$\gcd(120^2,180^3)=14400$

$\prod_{i=1}^{2}\prod_{j=3}^{4}\gcd(x^{i},y^{j})=2985984000000$
$2985984000000 \mod 998244353=235140177$

标准思路

暴力的话两个for,$O(n^2)$,而$a,b \le 3e6$,会超时。

看到求gcd,就应该尝试对给出的数分解质因数。

引自:标准题解

回到求$\gcd$的本质:

$\gcd$,为求两个数的最大公约数(因数)。
故可将两个数分别分解质因数,然后寻找两数所有共同的质因数,则结果为两数共同质因数的乘积。

如:
$\gcd(120,180)$:
$120=\underline{2} \times \underline{2} \times 2 \times \underline{3} \times \underline{5}$
$180=\underline{2} \times \underline{2} \times \underline{3} \times \underline{5} \times 5$

则$\gcd(120,180)=2\times2\times3\times5=60$。

由于这里为多项$\gcd$的连乘,又由上述可知本身$\gcd$的运算就为乘积运算,
故总的运算就可以写为各个项共同质因数的总乘积。

我们又可以从本质中发现,我们所取的每项质因数的次数,都是两数中出现次数较少的次数,以下统称为最小次数

如上例中对$2$这个质因数所取次数:
$120$有$3$个$2$,
$180$有$2$个$2$。
则$\gcd(120,180)$有关$2$这一项则取$2$个。($\gcd(120,180)=2\times2\times\cdots$)

而有关幂操作,就相当于对于每项质因数的次数进行幂操作

例:
$180^3=2^{2^{\underline{3}}}\times3^{2^{\underline{3}}}\times5^{1^{\underline{3}}}$

综上:
对于原题两个数的某范围中的幂,分别求$\gcd$,
可以转换为两数共同质因数,其每一项在其范围中的幂,取两者最小次数为该次运算的结果。
所有最小次数之和即为这一项的幂次,幂出来就是这一项质因数所求得的最小公约数。
然后所有项的最小公约数之积就是最终结果。


然后对于怎么取最小次数的问题:

假设当前共同质因数为base

  • 对于第一个数的base个数确定:
    先确定一个$i∈[a,b]$,则当前第一个数的base个数为$x*i$。

    然后计算出来一个界点min。(由于这里幂是整数,所以我们暂对min向下取整)

  • 对于第二个数的base个数分析:
    $y * c \sim y * d$中任意一个$y*k\quad (k∈[c,d])$

    • 当$k \le$min时,$x * i \ge y * k$,则这个时候$\gcd$取$y * k$
    • 当$k>$min时,$x * i < y * k$,则这个时候$\gcd$取$x * i$

【也可以用向上取整,但会更难想。

min计算方法:

  • $min = ⌊x * i / y⌋$。(程序里直接写min = x*i/y

sum计算方法:

  • 当$k∈[c,min]$,$sum+=y * k$(条件:$min >= c$)。
    则这部分区间的总和为:$sum+=y * sum(k)$(可算得$sum(k)=(c + min) * (min-c+1)/2)$。
  • 当$k∈(min,d]$,$sum+=x * i$(条件:$min < d$)。
    则这部分区间的总和为:$sum+=x * i * len(k)$(可算得$len(k) = d - min$)。
    【但因为$min=d$时,$len(k) = 0$,所以条件也可写为$min \le d$】

所以我们可以先将两个原数分别分解质因数
然后对每个共同的质因数项讨论其幂次

对于任一项质因数,选一个原数for遍历其幂次,
则对另一个原数,便可直接用上述的min确定选择最小次数的其区间临界点,直接可求得其不同幂次的每次的结果

故可将两个for的$O(n^2)$时间复杂度降下一层来为$O(n)$。


需要注意的点:
选好最小次数后求和时,如果要对幂次取模,
按照欧拉/费马小定理,模数应该取$\varphi (998244353)$(为欧拉函数)。

欧拉函数讲解

标程代码

标程代码(附个人注释)
#include <cstdio>
#include <unordered_map>

const long long MOD = 998244353;

long long q_pow(long long base, long long idx)  //带取模的快速幂
{
    long long answer = 1;
    while (idx)
    {
        if (idx & 1)
        {
            answer = answer * base % MOD;
        }
        base = base * base % MOD;
        idx >>= 1;
    }
    return answer;
}

long long a, b, c, d;

long long calc(long long x, long long y, long long base)
{
    long long sum = 0; //求算出来最终的幂
    for (long long i = a; i <= b; ++i)
    {
        long long min = x * i / y; //使得y*k > x*i的最小值
        /*有关min用法:
        【相应的分析放到了“题目分析”里】
        */
        if (min > d) //这里的处理方式是,如果bound > d,则不存在k∈(mid,d]的区间,直接令min=d,使得后面加这个区间时len(k)=0--->sum+=0。
            min = d;
        else if (min < c) //同理,如果min < c,则不存在k∈[c,min]的区间,直接令min=c-1,使得后面加这个区间时sum(k)=0--->sum+=0。
            min = c - 1;
        sum = (sum + (y * (c + min) * (min - c + 1) / 2)) % (MOD - 1); //对应k∈[c,min]情况
        sum = (sum + x * i * (d - min)) % (MOD - 1);                   //对应k∈(min,d]情况
        /* % (MOD - 1)的原因:
        这里是数论里的欧拉函数应用
        */
    }
    long long res = q_pow((long long)base, sum);
    return res;
}

int main()
{
    long long x, y;
    scanf("%lld %lld %lld %lld %lld %lld", &a, &b, &c, &d, &x, &y);

    std::unordered_map<long long, long long> factor_nums;

    for (long long i = 2; i * i <= x; ++i) //分解x的质因数
    {
        while (x % i == 0)
        {
            ++factor_nums[i];
            x /= i;
        }
    }
    if (x > 1)
        ++factor_nums[x];

    long long answer = 1;
    for (long long i = 2; i * i <= y; ++i) //对y按顺序分解质因数
    {
        if (y % i == 0)
        {
            long long count = 0;
            do
            {
                ++count;
                y /= i;
            } while (y % i == 0);
            if (factor_nums[i])
                answer = answer * calc(factor_nums[i], count, i) % MOD;
        }
    }
    if (y > 1 && factor_nums[y]) //y剩下的
        answer = answer * calc(factor_nums[y], 1, y) % MOD;
    printf("%lld\n", answer);
    return 0;
}

K

比赛情况:WA

题面搬运

题面搬运

题目描述

有$L$个方块排成一排,从左到右标记为$1,\cdots,L$

$L$个方块上站了$n$个人,从左到右标记为$1,\cdots,n$。第$i$个人站在第$a_i$个方块上

你可以做以下操作任意次:

选择一个人,令他向左或向右移动。这个人会一直移动直到前方没有空的格子。也就是说,当前方没有格子或前方的格子上有人时他才会停止移动。

举个例子,假设$n=3,L=10$,$n$个人一开始在$(2,3,7)$。现在我们让第$2$个人向右走,他会走到$6$停止,如果我们让第$3$个人往右走,他会走到最右侧$10$停止。

你的任务是使第$i$个人到达$b_i$位置,判定是否可行并找到最少操作次数。

数据范围

$1 \le N \le 10^5$
$N \le L \le 10^9$

$1 \le A_1 \lt A_2 \lt \cdots \lt A_N \le L$
$1 \le B_1 \lt B_2 \lt \cdots \lt B_N \le L$

  • 所有输入均为整数。

输入格式

$N \quad L$
$A_1 \quad A_2 \quad\cdots \quad A_N$
$B_1 \quad B_2 \quad\cdots \quad B_N$

输出格式

如果目标不可达,输出-1,否则输出最小指令数。

样例数据

第一组

输入

4 11
3 4 6 10
1 5 6 11

输出

3

第二组

输入

1 3
1
2

输出

-1

个人方法

就是想的纯模拟,交上去后WA……

之后对拍发现几处修改和WA点,现在不知道改正后是否正确_(:з」∠)_反正先贴上来……
【WA点已经写在代码里了……

个人代码
#include <bits/stdc++.h>
#define Length 100005
#define to_Left toLoc - 1
#define to_Right toLoc + 1
using namespace std;
int start[Length], to[Length], current[Length] = {0}, n, l, sum = 0;
int check(int topPrime, int top, int toLoc)
{
    if (current[top] && to[top] == toLoc)
        return 0;
    /* FIX&WA
    FIX.1. 经过已经到达了要去的点,应该直接返回0。
    WA.2. 第一次改没加to[top]==toLoc,可能在之后的使用中要去的点不是本要去的点,但却在之前current=1
    */
    if (toLoc < start[top]) //左移
    {
        if (top == 1) //最左边的节点
        {
            if (toLoc == 1) //去左墙
            {
                if (toLoc == to[top]) //如果恰好是要去的地方,把current=1
                    current[top] = 1; 
                return 1;
            }
            else
                return -1;
        }
        else //不是最左边的
        {
            if (topPrime == top - 1) //反复横跳了
                return -1;
            int checkToLeft = check(top, top - 1, to_Left); //左边那个,能否去要去点的左边
            if (checkToLeft != -1)
            {
                if (toLoc == to[top])
                    current[top] = 1; //如果恰好是要去的地方,把current=1
                return checkToLeft + 1;
            }
            else
                return -1;
        }
    }
    else if (toLoc > start[top]) //右移
    {
        if (top == n) //最右边的节点
        {
            if (toLoc == l) //去右墙
            {
                if (toLoc == to[top])
                    current[top] = 1; //如果恰好是要去的地方,把current=1
                return 1;
            }
            else
                return -1;
        }
        else //不是最右边的
        {
            if (topPrime == top + 1) //反复横跳了
                return -1;
            int checkToLeft = check(top, top + 1, to_Right); //右边那个,能否去要去点的右边
            if (checkToLeft != -1)
            {
                if (toLoc == to[top])
                    current[top] = 1; //如果恰好是要去的地方,把current=1
                return checkToLeft + 1;
            }
            else
                return -1;
        }
    }
    else //不移动
    {
        if (toLoc == to[top])
        /* WA
        WA.3. 有可能这步要让他在原地不动,但不是他最终要去的地方,故这个判断很重要!
        */
            current[top] = 1;
            /* WA
            WA.1. 不移动的时候要改current=1
            */
        return 0;
    }
}
signed main()
{
#ifdef SuperSASS
    freopen("data.in", "r", stdin);
#endif
    scanf("%d%d", &n, &l);
    for (int i = 1; i <= n; i++)
        scanf("%d", start + i);
    for (int i = 1; i <= n; i++)
        scanf("%d", to + i);
    for (int i = 1; i <= n; i++) //从左到右check。
        if (!current[i]) //如果在某次操作中已经到达最终位置,便不再计算
        {
            int value = check(i, i, to[i]);
            if (value == -1)
            {
                printf("-1");
                return 0;
            }
            else
                sum += value;
        }
    printf("%d", sum);
    return 0;
}

标准思路

区间上节点移动问题,可以转换为区间合并问题

比如:
$L=6$,点为$2,5$,转换为区间长为$1,2,1$。
如要把$2$向左移,即区间长变为$3(1+2),0,1$。

考虑两个人之间的空位,记为$x_1,x_2,x_3,…,x_n$。
$x_1$为最左侧空格子数,$x_n$为最右侧空格子数,其余$x_i$为第$i$个人和第$i-1$个人之间的空位。
让第i个人往左相当于$x_i += x_{i-1}, x_{i-1} = 0$,往右相当于$x_{i-1} += x_i, x_i = 0$。

引自:标准题解

初状态和终状态,因为数的个数一样,所以总区间长度和肯定一样。

那么要使最初状态转换为最终状态,则从左向右遍历,一定能使终状态某区间,变为由初状态中若干个区间合并
又由于碰到相邻的停下,使得只能相邻区间合并。
故若若干个区间合并后,长度超过却不能等于,则这个区间一定不能达成,证明不能移动得到,输出-1

故从左到右遍历,碰到存在长度的终状态区间,就开始寻找从初状态未被合并过的区间找若干个存在长度的区间尝试合并。
若成功合并,则移动次数就是左侧合并了多少个区间加上右边合并了多少个区间
公式为:$ans += max(i-l,0) + max(r-i,0)$。

  • 这里用个$max(\cdots,0)$,是因为存在减为负数的情况。【可以参见标程代码中的例子】

标程代码

标程代码(附个人注释)
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 100005;

int n, m, a[N + 9], b[N + 9];

LL ans;

void Get_ans()
{
    ++n;
    a[n] = b[n] = m + 1;         //技巧1:最右侧加个墙壁,方便计算最右侧区间长度。
    for (int i = n; i >= 1; --i) //把始末状态转换为区间长度,其中a[i]=i-1~i的距离
        a[i] -= a[i - 1] + 1, b[i] -= b[i - 1] + 1;
    for (int i = 1, j = 1; i <= n; ++i)
    {
        if (!b[i]) //从左向右,一直找到终状态存在长度(需要合并操作)的区间。
            continue;
        for (; !a[j]; ++j); //从初状态中未合并过的区间开始向右找,找到存在长度(可以合并)的区间。
        int sum = 0, l = j; //l记录左边开始进行合并的位置。
        for (; j <= n && sum < b[i]; ++j) //尝试进行b[i]=a[l]+a[l+1]+...+a[r-1]+a[r]这个操作
            sum += a[j];
        if (sum ^ b[i]) //如果无法把b[i]这个区间由若干个a[i]区间拼合而成,则不满足,输出-1
        {
            ans = -1;
            return;
        }
        ans += max(i - l, 0) + max(j - 1 - i, 0); //ans加上:完成这个区间合并操作所要操作的节点个数(左侧和右侧)。【要合并1——3区间,只需要移动2个节点,即3-1=2……

        /* 变量解释:
        i为当前要合并的区间
        l为操作到最左边的区间
        j为操作到最右边的区间(由于for的原因,这里j比实际的r多了1)
          【这里非常巧妙的是:正因为j比实际的r多1,导致下次查找的时候j会跳过之前已找过的区间,不会重复合并。
        */
        /* 是否需要max:
        是需要的。存在减为负数的情况。
        如:
        > 1 2 3 4 5
        > 6 7 8 9 10
        a(开始状态)数组为: 0、0、0、0、0、5
        b(结束状态)数组为: 5、0、0、0、0、0
        那么i=1、l=6、j=7
        */
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &b[i]);
    Get_ans();
    printf("%lld\n", ans);
    return 0;
}