0704模拟赛

阳光穿透心脏的1/2处 2023-10-09 12:32 13阅读 0赞

质因数分解

【问题描述】

Pluto 最近的数学水平正在迅速下降，连他自己都觉得自己已经没救了。现 在，Pluto 发现自己连最基本的质因数分解都不会做了，他只能来求助你了。

【输入格式】

第一行一个正整数 t，表示数据的组数。 接下来 t 行，每行一个正整数 n，表示带分解的数。

【输出格式】

共 t 行。 每行若干个用空格隔开的正整数，从小到大排列，表示 n 的质因数分解结果。

【样例输入】

2 7 12

【样例输出】

7 2 2 3

【数据规模和约定】

对于 30%的数据，2 ≤ n ≤ 1000000。 对于 60%的数据，2 ≤ n ≤ 1000000000。 对于 100%的数据，2 ≤ n ≤ 1000000000000，t ≤ 20

【Solution】

直接试除法分解一个数的质因数。

要注意除完后注意若最后的数是1则不输出

【code】

#include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    const ll N = 1000000000000 + 10;
    ll n;
    int t;
    
    int main() {
      freopen("prime.in", "r", stdin);
      freopen("prime.out", "w", stdout);
        scanf("%d", &t);
        for (; t; -- t) {
            scanf("%lld", &n);
            ll d = n;
            for (ll i = 2; i < sqrt(n); ++ i) {
                while(d % i == 0) {
                    printf("%lld ", i);
                    d /= i;
                }
                if (d == 1) break;
            }
            if (d == 1) puts("");else printf("%lld\n", d);
        }
        return 0;
    }

蛇形螺旋矩阵

【问题描述】

大家一定都听说过蛇形矩阵，也一定都听说过螺旋矩阵，但一定没有听过 蛇形螺旋矩阵。所谓蛇形螺旋矩阵，是非常类似于螺旋矩阵的一种矩阵。它们仅 有的不同之处在于：螺旋矩阵总是按顺时针方向旋转并填入相应数字，而蛇形 螺旋矩阵每一圈的旋转方向是不固定的。 现在给出一个蛇形螺旋矩阵的大小，同时给出每一圈旋转的方向，请你制 作出这个矩阵。（特别说明：第 i 圈的旋转是从（i，i）处开始的。）

【输入格式】

第一行一个正整数 n，表示蛇形螺旋矩阵的边长。 第二行（n+1）/2 个整数，第 i 个数表示从外向内第 i 圈的旋转的方向。1 表 示顺时针方向，-1 表示逆时针方向。

【输出格式】

输出共 n 行，每行 n 个用空格隔开的正整数，第 i 行第 j 个整数表示这个矩 阵（i，j）处的应填的整数。

【样例输入】

7 1 -1 -1 1

【样例输出】

1 2 3 4 5 6 7

24 25 40 39 38 37 8

23 26 41 48 47 36 9

22 27 42 49 46 35 10

21 28 43 44 45 34 11

20 29 30 31 32 33 12

19 18 17 16 15 14 13

【数据规模和约定】

对于 50%的数据，1 ≤ n ≤ 100。 对于 100%的数据，1 ≤ n ≤ 1000。

【solution】

直接暴力求出对应的二维数组，每个循环只求出i-3个数。对于n为单数的情况对最中间的数进行特判。

【code】

#include<bits/stdc++.h>
    using namespace std;
    
    const int N = 1010;
    
    int n, ans[N][N];
    int t, cnt = 0;
    
    int main() {
      freopen("matrix.in", "r", stdin);
      freopen("matrix.out", "w", stdout);
        scanf("%d", &n);
        for (int i = 1; i <= n + 1 >> 1; ++ i) {
            scanf("%d", &t);
            if (t > 0) {
                for (int j = i; j <= n - i; ++ j)
                    ans[i][j] = ++ cnt;
                for (int j = i; j <= n - i; ++ j)
                    ans[j][n - i + 1] = ++ cnt;
                for (int j = n - i + 1; j > i; -- j)
                    ans[n - i + 1][j] = ++ cnt;
                for (int j = n - i + 1; j > i; -- j)
                    ans[j][i] = ++ cnt;
            }
            else {
                for (int j = i; j <= n - i; ++ j)
                    ans[j][i] = ++ cnt;
                for (int j = i; j <= n - i; ++ j)
                    ans[n - i + 1][j] = ++ cnt;
                for (int j = n - i + 1; j > i; -- j)
                    ans[j][n - i + 1] = ++ cnt;
                for (int j = n - i + 1; j > i; -- j)
                    ans[i][j] = ++ cnt;
            }
        }
        if (n % 2) ans[n + 1 >> 1][n + 1 >> 1] = ++ cnt;
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j < n; ++ j)
                printf("%d ", ans[i][j]);
            printf("%d\n", ans[i][n]);
        }
        return 0;
    }

大采购

【问题描述】

Pluto 所在的学校终于放假了，Pluto 决定好好犒劳一下自己，所以当然要 去大采购了。 由于 Pluto 力量有限，他只能搬运最多不超过 w 个单位重量的物品。在超市 中，Pluto 一共看到了 n 样想买的东西，并且第 i 件商品每件重量为 ai，每件能 带给 Pluto 的愉悦程度为 ci，其存货量为 mi。现在，Pluto 想在能够搬走所买商品 的前提下，得到尽量大愉悦程度。你能帮帮他吗?

【输入格式】

第一行两个正整数 n，w，含义见题面。 接下来 n 行，每行三个整数，第 i+1 行的整数分别表示 ai，ci，mi。

【输出格式】

一行一个整数，表示 Pluto 最大的愉悦程度。

【样例输入】

4 15 5 6 4 3 4 3 1 1 5 2 3 3

【样例输出】

【数据规模和约定】

对于 50%的数据，n ≤ 200，w ≤ 3000 ，mi ≤ 100。 对于 100%的数据，n ≤ 500，w ≤ 10000 ，mi ≤ 1000，ai ≤ 100，ci ≤ 1000

【solution】

多重背包模板

【code】

#include<bits/stdc++.h>
    using namespace std;
    
    const int N = 510, W = 10010;
    int n, w, a[N], c[N], m[N], f[W];
    int d[N];
    
    int main() {
      freopen("shopping.in", "r", stdin);
      freopen("shopping.out", "w", stdout);
        scanf("%d%d", &n, &w);
        for (int i = 1; i <= n; ++ i) scanf("%d%d%d", &a[i], &c[i], &m[i]);
        for (int i = 1; i <= n; ++ i) {
            if (a[i] * m[i] > w) {
                for (int j = 0; j <= w; ++ j) {
                    if (j >= a[i]) f[j] = max(f[j - a[i]] + c[i], f[j]);
                }
                continue;
            }
            int k = 1, t = m[i];
            while(k < t) {
                for (int j = w; j >= k * a[i]; -- j)
                    f[j] = max(f[j], f[j - k * a[i]] + k * c[i]);
                t -= k, k += k;
            }
            for (int j = w; j >= t * a[i]; -- j)
                f[j] = max(f[j], f[j - t * a[i]] + t * c[i]);
        }
        int ans = 0;
        for (int i = 0; i <= w; ++ i) ans = max(ans, f[i]);
        printf("%d\n", ans);
        return 0;
    }

吉波那契数列

【问题描述】

有⼀个很著名的数列叫做斐波那契数列，它的定义式是 Fn = Fn−1 + Fn−2 其中，递推的初始值为：F0 = 1, F1 = 1 在吉波那契数列这个问题中，我们相似地定义了⼀个吉波那契数列 Gn： Gn = Gn−1 + Gn−2 对任何情况⽽⾔，G0 = 1, ⽽ G1 是⼀个随机的正整数 t。 现在告诉你 Gi 的值和两个正整数 i, j，请你求出 Gj。鉴于 Gj 可能很⼤， 请你输出 Gj mod 19960515。

【输入格式】

输⼊⽂件名为 gibonacci.in 有多组测试数据。第⼀⾏是⼀个正整数 T，表示测试数据的组数。 接下来 T ⾏，每⾏为⼀组测试数据，每组测试数据包含 3 个正整数 i, Gi , j。

【输出格式】

输出⽂件名为 gibonacci.out 对于每组数据，输出 Gj mod 19960515。 假如没有合适的 t，请输出 −1。

【样例输入】

2 1 1 2 3 5 4

【样例输出】

2 8

【数据规模与约定】

对于 30% 的数据，每个 Gibonacci 数列的 G1 = t ≤ 50 对于 50% 的数据，有 T ≤ 30 对于 100% 的数据，有 T ≤ 10000, 1 ≤ i, j ≤ 100000, 0 ≤ Gi < 19960515

【solution】

g\[0\] = 1, g\[1\] = t, g\[2\] = 1 + t, g\[3\] = 2t +1, g\[4\] = 3t + 2, g\[5\] = 5t + 3...

对比斐波那契数列可以发现，g\[i\]的常数项为f\[i-1\]，一次项为f\[i-2\].

所以g\[i\]=f\[i-1\]\*t+f\[i-2\].

因为一直i,Gi,j，所以可得t=(g\[i\]-f\[i-2\])/f\[i-1\]，再通过t求出g\[j\]即可，另外特判t是否为整数，若t不为整数则输出-1.

【code】

#include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    const int t = 10010, N = 100010;
    const ll Mod = 19960515;
    int T;
    ll f1[N], f2[N], a, b, c, x;
    
    int main() {
      freopen("gibonacci.in", "r", stdin);
      freopen("gibonacci.out", "w", stdout);
        f1[2] = f2[2] = f1[1] = f2[1] = 1;
        for (int i = 3; i <= 100000; ++ i)
            f1[i] = f1[i - 1] + f1[i - 2],
            f2[i] = (f2[i - 1] + f2[i - 2]) % Mod;
        scanf("%d", &T);
        while(T --) {
            scanf("%lld%lld%lld", &a, &b, &c);
            if ((b - f1[a - 1]) % f1[a]) {
                puts("-1");
                continue;
            }
            x = (b - f1[a - 1]) / f1[a];
            printf("%lld\n", (1LL * f2[c] * x + f2[c - 1]) % Mod);
        }
        return 0;
    }

魔塔

【问题描述】

魔塔是个经典的 RPG 游戏，不知道⼤家有没有玩过，⾄少在弱弱的出题⼈ 的童年，这是计算机对我⽽⾔最重要的功能了……（出题⼈过于荒废⼤家千万不 要学）这个游戏需要动很多脑筋，任何⼀个轻率的选择都可能导致游戏的失败。 魔塔游戏虽不⼤，但是制作精美，道具很多，⽽且难度不低，对智商是⼀次艰巨的考验。

![1598655-20190704152714297-1483106105.png][]

现在让我们看⼀个简单的魔塔游戏：这个魔塔游戏中没有门，也没有特殊的 道具，只有⼀种怪物和⼀些体⼒⽔。从出⽣点进⼊地图，你已经有 H 点初始体 能，每打⼀个怪需要损耗 1 点体能，⽽吃到⼀个体能⽔可以得到 5 点体能。勇⼠ 每次只能向上下左右四个⽅向⾛，如果要打怪或者喝体⼒⽔，必须⾛到这点上。 如果体⼒为 0，我们的勇⼠仍然可以⾛动，但不能打怪了。 显然魔塔是有很多层的，因此我们希望能够尽量节省体⼒。为了能够更好地 通关，也为了少杀⽣省⼈品，我们希望达到这层的终点时只要打最少的怪。现在给你⼀张地图，请问最少打多少的怪才能⾛到终点。

【输入格式】

输⼊⽂件名为 tower.in 有多组数据，以 EOF 结束。对于每组数据： 第⼀⾏：三个整数 H, N, M，表示初始体⼒ H，以及地图有 N ⾏ M 列。 第⼆⾏开始的 N ⾏，描述了⼀个地图，其中 \# 表示墙，M 表示怪物，C 表示体⼒⽔，S 表示出⽣点，E 表示地图终点，“.”表示空位。详细请看样例。

【输出格式】

输出⽂件名为 tower.out 对每组数据输出⼀⾏整数，表示最少需要打的怪的数量。 如果⽆法通关，请输出“P oor W arrior”（不含引号）

【样例输入】

5 5 6

S...MC

.....M

......

M\#\#\#\#\#

MMMMME

【样例输出】

【数据规模与约定】

总共有 3 个测试点 第⼀个测试点，没有体力水，1 ≤ N, M ≤ 6, H ≤ 10，共 3 组，30 分 第⼆个测试点，没有体力水，1 ≤ N, M ≤ 10, H ≤ 10，共 2 组，30 分 第三个测试点，1 ≤ N, M ≤ 6，体力水数量不超过 2 个，H ≤ 10，共 6 组， 40 分

【solution】

第一眼看这题的时候，没有考虑到体力水该怎么处理。看到有60分没有体力水，就写了一个不考虑体力水的广搜。

#include<bits/stdc++.h>
    using namespace std;
    
    int h, n, m, a[20][20],sta,stb,fia,fib;
    int q[100010][2], head, tail = 0;
    int f[100][110][2], ans = 10222222;
    
    int main() {
        freopen("tower.in","r",stdin);
        freopen("tower.out", "w", stdout);
        while(cin>>h>>n>>m) {
            tail = 0, ans = 10222222;
            memset(a, 0, sizeof(a));
            memset(q, 0, sizeof(q));
            memset(f, 0, sizeof(f));
        for(int i=1;i<=n;++i) 
            for(int j=1;j<=m;++j){
                char c;
                cin>>c;
                if(c=='S')sta=i,stb=j;
                if(c=='#')a[i][j]=1;
                if(c=='M')a[i][j]=2;
                if(c=='C')a[i][j]=3;
                if (c == 'E') fia = i, fib = j;
            }
        
        for (int i = 1; i <= 10; ++ i)
            for (int j = 1; j <= 10; ++ j)
                f[i][j][0] = 120241, f[i][j][1] = 0;
        f[sta][stb][1] = h, f[sta][stb][0] = 0;
        q[++ tail][0] = sta, q[tail][1] = stb;
        for (head = 1; head <= tail; ++ head) {
            int nx = q[head][0], ny = q[head][1];
            if (nx == fia && ny == fib) ans = min(ans, f[nx][ny][0]);
            if (a[nx + 1][ny] != 1 && nx != n) {
                if (f[nx][ny][0] + 1 < f[nx + 1][ny][0] && a[nx + 1][ny] == 2 && f[nx][ny][1]) {
                    q[++ tail][0] = nx + 1, q[tail][1] = ny;
                    f[nx + 1][ny][0] = f[nx][ny][0] + 1;
                    f[nx + 1][ny][1] = f[nx][ny][1] - 1;
                }
                if (a[nx + 1][ny] == 0 && (f[nx + 1][ny][0] > f[nx][ny][0] || f[nx + 1][ny][1] < f[nx][ny][1])) {
                    q[++ tail][0] = nx + 1, q[tail][1] = ny;
                    f[nx + 1][ny][0] = f[nx][ny][0];
                    f[nx + 1][ny][1] = f[nx][ny][1];
                }
            }
            if (a[nx - 1][ny] != 1 && nx - 1) {
                if (f[nx][ny][0] + 1 < f[nx - 1][ny][0] && a[nx - 1][ny] == 2 && f[nx][ny][1]) {
                    q[++ tail][0] = nx - 1, q[tail][1] = ny;
                    f[nx - 1][ny][0] = f[nx][ny][0] + 1;
                    f[nx - 1][ny][1] = f[nx][ny][1] - 1;
                }
                if (a[nx - 1][ny] == 0 && (f[nx - 1][ny][0] > f[nx][ny][0] || f[nx - 1][ny][1] < f[nx][ny][1])) {
                    q[++ tail][0] = nx - 1, q[tail][1] = ny;
                    f[nx - 1][ny][0] = f[nx][ny][0];
                    f[nx - 1][ny][1] = f[nx][ny][1];
                }
            }
            if (a[nx][ny + 1] != 1 && ny != m) {
                if (f[nx][ny][0] + 1 < f[nx][ny + 1][0] && a[nx][ny + 1] == 2 && f[nx][ny][1]) {
                    q[++ tail][0] = nx, q[tail][1] = ny + 1;
                    f[nx][ny + 1][0] = f[nx][ny][0] + 1;
                    f[nx][ny + 1][1] = f[nx][ny][1] - 1;
                }
                if (a[nx][ny + 1] == 0 && (f[nx][ny + 1][0] > f[nx][ny][0] || f[nx][ny + 1][1] < f[nx][ny][1])) {
                    q[++ tail][0] = nx, q[tail][1] = ny + 1;
                    f[nx][ny + 1][0] = f[nx][ny][0];
                    f[nx][ny + 1][1] = f[nx][ny][1];
                }
            }
            if (a[nx][ny - 1] != 1 && ny - 1) {
                if (f[nx][ny][0] + 1 < f[nx][ny - 1][0] && a[nx][ny - 1] == 2 && f[nx][ny][1]) {
                    q[++ tail][0] = nx, q[tail][1] = ny - 1;
                    f[nx][ny - 1][0] = f[nx][ny][0] + 1;
                    f[nx][ny - 1][1] = f[nx][ny][1] - 1;
                }
                if (a[nx][ny - 1] == 0 && (f[nx][ny - 1][0] > f[nx][ny][0] || f[nx][ny - 1][1] < f[nx][ny][1])) {
                    q[++ tail][0] = nx, q[tail][1] = ny - 1;
                    f[nx][ny - 1][0] = f[nx][ny][0];
                    f[nx][ny - 1][1] = f[nx][ny][1];
                }
            }
        }
        if (ans == 10222222) 
            puts("Poor Warrior");
        else
            printf("%d\n", ans);
        }
        return 0;
    }

结果题解发下来后发现只要记忆化搜索就能过，而且不需要广搜那样繁琐，只要用方向数组就轻易过掉了。

【code】

#include<bits/stdc++.h>
    using namespace std;
    
    int dx[4] = {
        1, -1, 0, 0}, dy[4] = {
        0, 0, 1, -1};
    int h, n, m, a[20][20],sta,stb,fia,fib;
    int f[80][80][80][80], ans = 10222222;
    
    void dfs(int x, int y, int energy, int num) {
        if (f[x][y][energy][num]) return ;
        f[x][y][energy][num] = 1;
        if (x == fia && y == fib) {
            ans = min(ans, num);
            return ;
        }
        for (int i = 0; i < 4; ++ i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx && ny && nx <= n && ny <= m) {
                if (a[nx][ny] == 0) dfs(nx, ny, energy, num);
                if (a[nx][ny] == 2 && energy) {
                    a[nx][ny] = 0;
                    dfs(nx, ny, energy - 1, num + 1);
                    a[nx][ny] = 2;
                }
                if (a[nx][ny] == 3) {
                    a[nx][ny] = 0;
                    dfs(nx, ny, energy + 5, num);
                    a[nx][ny] = 3;
                }
            }
        }
    }
    
    int main() {
        freopen("tower.in","r",stdin);
        freopen("tower.out", "w", stdout);
        while(cin >> h >> n >> m) {
            ans = 10222222;
            memset(a, 0, sizeof(a));
            memset(f, 0, sizeof(f));
            for(int i = 1; i <= n; ++ i) 
            for(int j = 1; j <= m; ++ j) {
                char c;
                cin >> c;
                if (c == 'S') sta = i, stb = j;
                if (c == '#') a[i][j] = 1;
                if (c == 'M') a[i][j] = 2;
                if (c == 'C') a[i][j] = 3;
                if (c == 'E') fia = i, fib = j;
            }
        dfs(sta, stb, h, 0);
        if (ans == 10222222) 
            puts("Poor Warrior");
        else
            printf("%d\n", ans);
        }
        return 0;
    }

对战

【问题描述】

在⼀条街道上有 n 个⼈，他们都喜欢打乒乓球。任意两个⼈的家的位置都 不相同，按顺序标为 1, 2, · · · , n。每个⼈都有⼀定的⽔平，用两两不等的整数表 示。 当两个⼈想打球的时候，会找另⼀个⼈作为裁判，并到裁判家里进⾏⼀场 较量。出于某种原因，他们希望裁判的⽔平介于两⼈之间；同时，他们希望两个 ⼈到裁判家的总路程不超过两个⼈的家的距离。 对于两场较量，如果打球的两个⼈不完全相同或者裁判不同，我们就认为 这两场较量不同。求不同的较量的总数。

【输入格式】

输⼊⽂件名为 inhouse.in 输⼊包含多组数据 输⼊的第⼀⾏是⼀个整数 T，表示数据组数； 每组数据占⼀⾏，包含 n + 1 个整数：n, a1, a2, · · · , an。其中 a1, a2, · · · , an 表示家位于相应位置的⼈的⽔平。

【输出格式】

输出⽂件名为 inhouse.out 对每组数据，用⼀⾏输出⼀个整数，表示不同的较量的总数。

【样例输入】

1 3 1 2 3

【样例输出】

【数据规模与约定】

对于 40% 的数据，有 n ≤ 1000； 对于所有数据，有 T ≤ 20, 3 ≤ n ≤ 100000，每个⼈的⽔平都是不超过 200000 的正整数。

【solution】

枚举中间点，直接树状数组处理就行了，时间复杂度O(nlogn)，用线段树会被卡常。

【code】

#include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    const int N = 200010;
    int n, a[N];
    ll c[N], l[N], r[N];
    ll ans = 0;
    
    int read() {
        int num = 0; bool flag = 1; char c = getchar();
        for (; c < '0' || c > '9'; c = getchar())
            if (c == '-') flag = 0;
        for (; c >= '0' && c <= '9'; c = getchar())
            num = (num << 3) + (num << 1) + c - 48;
        return flag ? num : -num;
    }
    
    ll ask(int x) {
        ll sum = 0;
        for (; x; x -= x & -x) sum += c[x];
        return sum;
    }
    
    void add(int x, int y) {
        for (; x <= 200000; x += x & -x) c[x] += y;
    }
    
    int main() {
      freopen("inhouse.in", "r", stdin);
      freopen("inhouse.out", "w", stdout);
          int T;
          scanf("%d", &T);
          while(T --) {
              memset(l, 0, sizeof(l));
              memset(r, 0, sizeof(r));
              memset(c, 0, sizeof(c));
              ans = 0;
            int x, y, z;
            scanf("%d", &n);
            for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
            for (int i = 1; i <= n; ++ i) {
                l[i] = ask(a[i]);
                add(a[i], 1);
            }
            memset(c, 0, sizeof(c));
            for (int i = n; i; -- i) {
                r[i] = ask(a[i]);
                add(a[i], 1);
            }
            for (int i = 2; i < n; ++ i) ans += 1LL * l[i] * (n - i - r[i]), ans += 1LL * (i - 1 - l[i]) * r[i];
            printf("%lld\n", ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/ckn1023/p/11132777.html

[1598655-20190704152714297-1483106105.png]: https://img2018.cnblogs.com/blog/1598655/201907/1598655-20190704152714297-1483106105.png