2020-12-18-赛前总结

技巧

1.getchar放回

ungetc(val, stdin);

2.二分查首位

#include <stdio.h>
#include <algorithm>
int a[1000000];
int main(void)
{
    int n, m;
    scanf("%d%d", &n, &m);
    int b[100000];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &b[i]);
    }
    int mid;
    int *temp;
    for (int i = 0; i < m; i++)
    {
        temp = std::lower_bound(a, a + n, b[i]);
        mid = temp - &a[0];
        if (std::binary_search(a, a + n, b[i]))
            printf("%d ", mid + 1);
        else if (a[0] == 0 && b[i] == 0)
            printf("1");
        else
            printf("-1 ");
    }
    return 0;
}

3.排序

std::sort(a, a + n);

4.最大公约数

std::__gcd(i, j);

5.最小公倍数

i * j / std::__gcd(i, j);

6.斐波那契博弈

有一堆个数为n的石子，游戏双方轮流取石子，满足：
1)先手不能在第一次把所有的石子取完；
2)之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。
约定取走最后一个石子的人为赢家，求必败态。

结论：先手胜当且仅当n不是斐波那契数（n为物品总数）

7.威佐夫博弈

有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

我们有如下公式：a表示第一堆的个数，b表示第二堆的个数，c表示二者之差，当然a必须小于b;
再找规律的话我们会发现，a= c* 1.618

部分模板

素数筛法（运行时间约1.2s）

char pend[100000005];
int odd[7123456];
void count()
{
    int count = 1;
    /* 定义 */
    pend[1] = 1;    //特判
    for (int i = 2; i * i <= 100000005; i++)
    {
        if (!pend[i])
        {
            for (int j = i * i; j <= 100000005; j += i)
            {
                pend[j] = 1;
            }
        }
    }
    /* 线筛 */
    for (int i = 1; i < 100000005; i++)
    {
        if (!pend[i])
        {
            odd[count++] = i;
        }
    }
    /* 储存 */
    return;
}

螺旋数列

#include <stdio.h>
int main(void)
{
    int n;
    int value = 1;
    int i, j;
    scanf("%d", &n);
    int m[100][100];
    /* 数组大小 */
    for (i = 0; i < (n + 1) / 2; i++)
    {
        for (j = i; j < n - i; j++)
        {
            m[i][j] = value++;
        }

        for (j = i + 1; j < n - i; j++)
        {
            m[j][n - i - 1] = value++;
        }
        for (j = n - i - 2; j >= i; j--)
        {
            m[n - i - 1][j] = value++;
        }
        for (j = n - i - 2; j > i; j--)
        {
            m[j][i] = value++;
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {/* 输出格式 */
            printf("%5d", m[i][j]) 
        }
        printf("\n");
    }

    return 0;
}

#include <stdio.h>
int main(void)
{
    int n;
    scanf("%d", &n);
    if (n == 0)
    {
        return 0;
    }
    int m = n + n - 1;
    int q = n - 1;
    int t = 1;
    int a[n][n];
    int *p;
    p = &a[0][0];
    int time = 1;
    for (int i = 0; i < (n + n - 1); i++)
    {
        if (time % 4 == 1)
        {
            for (int j = 0; j < q; j++)
            {
                *p = t;
                p += 1;
                t++;
                *p = t;
            }
        }
        else if (time % 4 == 2)
        {
            for (int j = 0; j < q; j++)
            {
                *p = t;
                p += n;
                t++;
                *p = t;
            }
        }
        else if (time % 4 == 3)
        {
            for (int j = 0; j < q; j++)
            {
                *p = t;
                p -= 1;
                t++;
                *p = t;
            }
        }
        else if (time % 4 == 0)
        {
            for (int j = 0; j < q; j++)
            {
                *p = t;
                p -= n;
                t++;
                *p = t;
            }
        }

        if (time % 2 && time != 1)
            q -= 1;
        time++;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            printf("%5d", a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

刺痛值

输入
第一行有两个用空格隔开的整数，分别代表 n 和 m。
第 22 到第 (n + 1) 行，每行一个整数，第 (i + 1) 行的整数 a_i代表第 i 件事的刺痛值 a_i。
输出
输出一行一个整数，表示连续 m 个刺痛值的和的最小值是多少。

#include <stdio.h>
int main(void)
{
    int n, m;
    scanf("%d%d", &n, &m);
    int a[n];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    int b = 0, min;
    for (int i = 0; i < n - m; i++)
    {
        b = 0;
        for (int j = 0; j < m; j++)
        {
            b += a[i + j];
        }
        if (b <= min || i == 0)
            min = b;
    }
    if (!m || !n)
    {
        min = 0;
    }
    else if(!(m - n))
    {
        for (int j = 0; j < m; j++)
        {
            b += a[j];
        }
        min = b;
    }
    printf("%d", min);
    return 0;
}

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

#include <stdio.h>
#include <algorithm>
int a[1200][1200];
int b;
int sum;
int main(void)
{
    int m, t, o, temp;
    scanf("%d", &m);
    o = 1;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < o; j++)
        {
            scanf("%d", &a[i][j]);
        }
        o++;
    }
    t = m;
    for (int j = 0; j < m; j++)
    {
        for (int i = 0; i < t; i++)
        {
            temp = std::max(a[m - j][i], a[m - j][i + 1]);
            a[m - j - 1][i] += temp;
        }
        t--;
    }
    b = a[0][0];
    printf("%d\n", b);
    return 0;
}

火柴棒等式

#include <stdio.h>
int main()
{
    int a[2001] = {6}, b, c[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}, s = 0, i, j;
    scanf("%d", &b);
    for (i = 1; i <= 2000; i++)
    {
        j = i;
        while (j >= 1) //求每个数所用的火柴棒
        {
            a[i] = a[i] + c[j % 10];
            j = j / 10;
        }
    }
    for (i = 0; i <= 1000; i++)
    {
        for (j = 0; j <= 1000; j++)
            if (a[i] + a[j] + a[i + j] + 4 == b)
                s++; //还有加号与等号
    }
    printf("%d", s);
    return 0;
}

彩票摇奖

in
2
23 31 1 14 19 17 18
12 8 9 23 1 16 7
11 7 10 21 2 9 31
out
0 0 0 0 0 1 1

#include <stdio.h>
int main(void)
{
    int n;
    scanf("%d", &n);
    int a[n + 2][7];
    int count;
    for (int i = 0; i < n + 1; i++)
    {
        for (int j = 0; j < 7; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 0; i < 7; i++)
    {
        a[n + 1][i] = 0;
    }
    for (int i = 1; i < n + 1; i++)
    {
        count = 0;
        for (int j = 0; j < 7; j++)
        {
            for (int k = 0; k < 7; k++)
            {
                if (a[i][j] == a[0][k])
                {
                    count++;
                }
            }
        }
        a[n + 1][7 - count]++;
    }
    for (int i = 0; i < 7; i++)
    {
        printf("%d", a[n + 1][i]);
        if (i != 6)
        {
            printf(" ");
        }
    }
    return 0;
}

移动字符串

in
1
qwe
out
rxf

#include <stdio.h>
#include <string.h>
int main(void)
{
    int n;
    scanf("%d", &n);
    char a[60];
    scanf("%s", &a);
    int m = strlen(a);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (a[j] == 'z')
            {
                a[j] = 'a';
            }
            else if (a[j] == 'Z')
            {
                a[j] = 'A';
            }
            else
            {
                a[j]++;
            }
        }
    }
    puts(a);
    return 0;
}

dp

#include <stdio.h>
#include <algorithm>
int main()
{
    int w[110], val[110];
    int dp[110][110];
    int t, m, res = -1;
    scanf("%d%d", &t, &m);/* t为时间，m为数目 */
    for (int i = 1; i <= m; i++)
    {/* 时间，价值 */
        scanf("%d%d", &w[i], &val[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = t; j >= 0; j--)
        {
            if (j >= w[i])
            {/* dp */
                dp[i][j] = std::max(dp[i - 1][j - w[i]] + val[i], dp[i - 1][j]);
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    printf("%d", dp[m][t]);
    return 0;
}

杨辉三角

#include <stdio.h>
int a[21][21];
int main(void)
{
    int n = 0, count = 1;
    scanf("%d", &n);
    a[0][0] = a[1][0] = a[1][1] =1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < count; j++)
        {
            if (i != 0 && i != 1)
            {
                a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
            }
            printf("%d", a[i][j]);
            if (i - 1 != count)
            {
                printf(" ");
            }
        }
        printf("\n");
        count++;
    }
    return 0;
}

回文质数

// #include <stdio.h>
// char pend[100000005];
// void odd()
// {
//     int count = 1;
//     /* 定义 */
//     pend[1] = 1; //特判
//     for (int i = 2; i * i <= 100000005; i++)
//     {
//         if (!pend[i])
//         {
//             for (int j = i * i; j <= 100000005; j += i)
//             {
//                 pend[j] = 1;
//             }
//         }
//     }
//     /* 线筛 */
//     return;
// }
// int pend2(int num)
// {
//     int temp = num, ans = 0;
//     while (temp)
//     {
//         ans = ans * 10 + temp % 10;
//         temp /= 10;
//     }
//     if (ans == num)
//         return 1;
//     else
//         return 0;
// }
// int main(void)
// {
//     odd();
//     for (int i = 4; i < 100000000; i++)
//     {
//         if (pend2(i) && !pend[i])
//         {
//             printf("%d, ", i);
//         }
//     }
//     return 0;
// }

#include <stdio.h>
int odd[100000] = {};//略
int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    for (int i = 0; odd[i]; i++)
    {
        if (odd[i] <= b && odd[i] >= a)
        {
            printf("%d\n", odd[i]);
        }
    }
    return 0;
}

与 n 互质的第 k 个正整数。

#include <stdio.h>
#include <algorithm>
int a[1000005];
int main(void)
{
    int n, k, ans = 0;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i)
    {
        if (std::__gcd(i, n) == 1)
        {
            a[ans++] = i;
        }
    }
    printf("%d", (k - 1) / ans * n + a[(k - 1) % ans]);
    return 0;
}

深搜&质数

7 3 3 1 全部肋骨上的数字 7331 是质数；三根肋骨 733733 是质数；二根肋骨 73 是质数；当然,最后一根肋骨 7 也是质数。7331 被叫做长度 4 的特殊质数。

#include <stdio.h>
#include <math.h>
int a[4] = {1, 3, 7, 9};
int n;
int pend(int x)
{
    if (x == 1)
        return 0;
    if (x == 2)
        return 1;
    for (int i = 2; i <= sqrt(x); i++)
        if (x % i == 0)
        {
            return 0;
        }
    return 1;
}
void DFS(int k, int sum)
{
    int p;
    if (!(sum - n))
    {
        printf("%d\n", k);
    }
    else
    {
        for (int i = 0; i < 4; i++)
        {
            p = k * 10 + a[i];
            if (pend(p))
            {
                DFS(p, sum + 1);
            }
        }
    }
}
int main(void)
{
    scanf("%d", &n);
    DFS(2, 1);
    DFS(3, 1);
    DFS(5, 1);
    DFS(7, 1);
    return 0;
}

Nim博弈

#include <stdio.h>
int main(void)
{
    int t, n, val, ans;
    scanf("%d", &t);
    for (int i = 0; i < t; i++)
    {
        ans = 0;
        scanf("%d", &n);
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &val);
            ans ^= val;
        }
        if (!ans)
        {
            printf("No\n");
        }
        else
        {
            printf("Yes\n");
        }
    }
    return 0;
}

阶乘之乘

#include <stdio.h>
int main(void)
{
    long long int n, ans = 0;
    scanf("%lld", &n);
    for (int i = n; i > 4; i--)
    {
        ans += i / 5 + i / 25 + i / 125 + i / 625 + i / 3125 + i / 15625 + i / 78125 + i / 390625 + i / 1953125 + i / 9765625 + i / 48828125;
        // while (temp)
        // {
        //     ans += temp / 5;
        //     temp /= 5;
        // }
    }
    printf("%lld", ans);
    return 0;
}

阶乘之和(Python)

num = int(input())
ans = 0
while num > 0 :
    fact = 1
    for i in range(1, num + 1):
        fact = fact * i
    ans += fact
    num = num - 1
print(ans)

取数游戏

有一个取数的游戏。初始时，给出一个环，环上的每条边上都有一个非负整数。这些整数中至少有一个0。然后，将一枚硬币放在环上的一个节点上。两个玩家就是以这个放硬币的节点为起点开始这个游戏，两人轮流取数，取数的规则如下：

（1）选择硬币左边或者右边的一条边，并且边上的数非0；

（2）将这条边上的数减至任意一个非负整数(至少要有所减小)；

（3）将硬币移至边的另一端。

如果轮到一个玩家走，这时硬币左右两边的边上的数值都是0，那么这个玩家就输了。

如下图，描述的是Alice和Bob两人的对弈过程，其中黑色节点表示硬币所在节点。结果图(d)中，轮到Bob走时，硬币两边的边上都是0，所以Alcie获胜。

　　　　　　　　　　　　　（a）Alice 　（b）Bob 　（c）Alice 　　（d）Bob

现在，你的任务就是根据给出的环、边上的数值以及起点（硬币所在位置），判断先走方是否有必胜的策略。

#include <stdio.h>
int main()
{
    int n, a[30], left = 0, right = 0, flag1 = 1, flag2 = 1;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i++)
    {
        if (a[left] && flag1)
        {
            left++;
        }
        else
        {
            flag1 = 0;
        }
        if (a[n - right - 1] && flag2)
        {
            right++;
        }
        else
        {
            flag2 = 0;
        }
        
    }
    if (left % 2)
    {
        printf("YES\n");
    }
    else if (right % 2)
    {
        printf("YES\n");
    }
    else
    {
        printf("NO\n");
    }
    return 0;
}

博弈B

游戏要求在一个有 nn 个顶点凸多边形上进行，这个凸多边形的 n-3n−3 条对角线将多边形分成 n-2n−2 个三角形，这 n-3n−3 条对角线在多边形的顶点相交。三角形中的一个被染成黑色，其余是白色。

双方轮流进行游戏，当轮到一方时，他必须沿着画好的对角线，从多边形上切下一个三角形。切下黑色三角形的一方获胜。胖子一看觉得确实很有趣，不如就一起玩玩吧。假设游戏由野猫先开始，那么野猫是否有必胜的策略呢？请写一个程序帮助野猫算一算。

#include <cstdio>
#include <algorithm>
using namespace std;
int n, a, b, c, aa, bb, cc;
void Sort(int &x, int &y, int &z)
{
    if (x > y)
        swap(x, y);
    if (x > z)
        swap(x, z);
    if (y > z)
        swap(y, z);
}
int main()
{
    scanf("%d", &n);
    //读入黑色三角形的三个顶点编号
    scanf("%d %d %d", &aa, &bb, &cc);
    //将三个编号从小到大排序，方便判断
    Sort(aa, bb, cc);
    //读入剩下的三角形编号
    for (int i = 2; i <= n - 2; i++)
        scanf("%d %d %d", &a, &b, &c);
    //判断黑色三角形是否能够第一刀切到
    if (aa + 1 == bb && bb + 1 == cc)
    { //编号连续代表三角形在外边
        puts("JMcat Win");
        return 0;
    }
    //当黑色三角形顶点最小是0是需要特判3种情况
    if (aa == 0)
    {
        if ((bb == 1 && cc == n - 1) || (bb == 1 && cc == 2) || (bb == n - 2 && cc == n - 1))
        {
            puts("JMcat Win");
            return 0;
        }
    }
    //这里思路已经说过
    if ((n - 2) % 2 == 1)
        puts("PZ Win");
    else
        puts("JMcat Win");
    return 0;
}

进制转化

#include <stdio.h>
#include <math.h>
#include <string.h>
int main(void)
{
    int val1, val2, val = 0;
    char num[50];
    scanf("%d", &val1);
    /* 输入进制 */
    scanf("%s", &num);
    scanf("%d", &val2);
    /* 输出进制 */
    int n = strlen(num) - 1;
    for (int i = 0; i < strlen(num); i++)
    {
        if (num[i] >= 'A')
        {
            val += pow(val1, n) * (num[i] - 'A' + 10);
        }
        else
        {
            val += pow(val1, n) * (num[i] - '0');
        }
        n--;
    }
    for (int i = 0; 1; i++)
    {
        if (val / pow(val2, i) <= 1)
        {
            n = i;
            break;
        }
    }
    char a[50];
    for (int i = 0; i < n; i++)
    {
        a[i] = (int)(val / pow(val2, n - i - 1)) % val2;
        if (a[i] >= 10)
        {
            a[i] = a[i] - 10 + 'A';
        }
        else
        {
            a[i] = a[i] + '0';
        }
    }
    for (int i = 0; i < n; i++)
    {
        printf("%c", a[i]);
    }
    return 0;
}

汉诺塔

#include <stdio.h>
int k = 1;
int move(char getone, int n, char putone)
{
    k++;
    return 0;
}
int hanoi(int n, char x, char y, char z)
{
    if (n == 1)
        move(x, 1, z);
    else
    {
        hanoi(n - 1, x, z, y);
        move(x, n, z);
        hanoi(n - 1, y, x, z);
    }
    return 0;
}
int main()
{
    int n, counter;
    scanf("%d", &n);
    counter = hanoi(n, 'A', 'B', 'C');
    printf("%d\n", k - 1);
    return 0;
}

全排列

7
-3
-2
-1
0
1
2
3

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a[100];
    for (int i = 0; i < n; i++)
    {
        a[i] = i + 1;
    }
    for (int i = 0; i < n; i++)
    {
        printf("%5d", a[i]);
    }
    printf("\n");
    while (next_permutation(a, a + n))
    {
        for (int i = 0; i < n; i++)
        {
            printf("%5d", a[i]);
        }
        printf("\n");
    }
    return 0;
}

3个数和为0

#include <stdio.h>
#include <algorithm>
#include <string.h>
int main(void)
{
    int n, count = 0, t;
    scanf("%d", &n);
    int a[10000], temp[3];
    int ans[10000][3];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    std::sort(a, a + n);
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            for (int k = j + 1; k < n; k++)
            {
                if (a[i] + a[j] + a[k] == 0)
                {
                    printf("%d %d %d\n", a[i], a[j], a[k]);
                    count++;
                }
            }
        }
    }
    if (!count)
    {
        printf("No Solution\n");
    }
    return 0;
}

区间合并

5
5 6
1 5
10 10
6 9
8 10

#include <stdio.h>
#include <algorithm>
#include <string.h>
int main(void)
{
    int n, count = 0, t;
    scanf("%d", &n);
    int a[10000], temp[3];
    int ans[10000][3];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    std::sort(a, a + n);
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            for (int k = j + 1; k < n; k++)
            {
                if (a[i] + a[j] + a[k] == 0)
                {
                    printf("%d %d %d\n", a[i], a[j], a[k]);
                    count++;
                }
            }
        }
    }
    if (!count)
    {
        printf("No Solution\n");
    }
    return 0;
}

数列有序

3 3
1 2 4
0 0

#include <stdio.h>
#include <algorithm>
#include <string.h>
int main(void)
{
    int n, count = 0, t;
    scanf("%d", &n);
    int a[10000], temp[3];
    int ans[10000][3];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    std::sort(a, a + n);
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            for (int k = j + 1; k < n; k++)
            {
                if (a[i] + a[j] + a[k] == 0)
                {
                    printf("%d %d %d\n", a[i], a[j], a[k]);
                    count++;
                }
            }
        }
    }
    if (!count)
    {
        printf("No Solution\n");
    }
    return 0;
}