牛客寒假算法基础集训营1

发表于 更新于 分类于
本文字数： 9.2k 阅读时长 ≈ 8 分钟

A.小a的计算器

题目描述

小a的数学基础实在太差了，以至于他只会用计算器算数。他的计算器比较特殊，只有 +,−,×,/ (即加减乘除)四种运算。经过一番周折，小a终于算出了他想要的数，但是他却忘记了最初的数是什么。不过幸运的是他记下了整个操作序列，他想请你帮他算出最初的数。

输入描述:

第一行两个整数n,X，分别表示操作次数和最终的数
接下来n行表示操作序列，每行两个数opt,x，
若opt=1，则表示将当前数加x
若opt=2，则表示将当前数减x
若opt=3，则表示将当前数乘x
若opt=4，则表示将当前数除以x

输出描述:

一个整数表示最初的数

输入

1
2
3
4
5
6
7
8
9
10
4 6
1 3
2 1
3 3
4 2

3 292
3 2
4 3
4 3

输出

1
2
3
2

1314

说明：

样例1解释：
$ 2 + 3 = 5 $
$ 5 - 1 = 4 $
$ 4 * 3 = 12 $
$ 12 / 2 = 6 $

备注：

$ n \leq 100, 0 < X \leq 10^{18}$.
数据保证：
1、 最初的数在进行操作时不会超过long long范围。
2、 如果你的程序合法，那么运算中所有的数均为整数，所有的除法均为整除！
3、 不会出现整数被0除的情况。

思路：

倒序模拟即可。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
int n, opt[105];LL y, x[105];
int main() {
    while(cin >> n >> y) {
        for(int i = 1; i <= n; ++i) cin >> opt[i] >> x[i];
        for(int i = n; i > 0; --i){
            if(opt[i] == 1) y -= x[i];
            else if(opt[i] == 2) y += x[i];
            else if(opt[i] == 3) y /= x[i];
            else y *= x[i];
        }
        cout << y << endl;
    }
    return 0;
}

B.小a与”204”

题目描述:

小a非常喜欢204这个数字，因为′a′+′k′=204。现在他有一个长度为n的序列，其中只含有2,0,4这三种数字。设 为序列中第i个数，你需要重新排列这个数列，使得 最大(公式的含义是：每个数与前一个数差的平方的和)。
注意：我们默认 $ a_0 = 0 $。

输入描述:

第一行一个整数n，接下来一行n个整数，第i个数表示 $a_i $

输出描述:

输出一个整数，表示 的最大值。

输入：

1
2
3
4
5
2
2 4

3
2 0 4

输出：

1
2
3
20

36

说明：

样例1解释：按 $ (4,2) $ 排列是最优的，此时 $ sum = (4 - 0)^2 + (2 - 4)^2 = 20 $.
样例2解释：按 $ (4,0,2) $ 排列是最优的，
此时 $ sum = (4 - 0)^2 + (0 - 4)^2 + (2 - 0)^2 = 36 $.

备注：

$ 1 \leq n \leq 10^5 $ ，保证 $ a_i $ 为 $ 2/0/4 $ 中的数。

思路：

用一个变量per标记序列中当前数位的上一位数字，然后直接贪心模拟！

AC代码：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
int n, cnt0, cnt2, cnt4, per, a[maxn]; LL ans;
int main() {
    while(cin >> n){ //贪心
        a[0] = cnt0 = cnt2 = cnt4 = 0;
        for(int i = 1;i <= n; ++i){
            cin >> a[i];
            if(a[i] == 2) cnt2++;
            else if(a[i] == 4) cnt4++;
            else cnt0++;
        }
        //第一个先选4，否则先选2，否则只能选0
        if(cnt4) ans = 16LL, cnt4--, per = 4;
        else if(cnt2) ans = 4LL, cnt2--, per = 2;
        else ans = 0LL, cnt0--, per = 0;
        for(int i = 2;i <= n; ++i){
            if(per == 4){ //如果上一个数是4
                if(cnt0) ans += 16LL, cnt0--, per = 0; //0先与之匹配
                else if(cnt2) ans += 4LL, cnt2--, per = 2; //否则2与之匹配
                else cnt4--, per = 0; //否则只能选4
            }
            else if(per == 2){ //如果上一个数字是2
                if(cnt0 || cnt4){ //可以选0或4与之匹配
                    if(cnt0 > cnt4) ans += 4LL, cnt0--, per = 0; //如果0剩下的个数大于4剩下的个数，先选0
                    else ans += 4LL, cnt4--, per = 4; //否则就选4与之匹配
                }else cnt2--; //否则只能选2
            }
            else { //如果上一个数字是0
                if(cnt4) ans += 16LL, cnt4--, per = 4; //4先与之匹配
                else if(cnt2) ans+=4, cnt2--, per = 2; //否则2与之匹配
                else cnt0--, per = 0; //否则只能选0
            }
        }
        cout << ans <<endl;
    }
    return 0;
}

C.小a与星际探索

题目描述

小a正在玩一款星际探索游戏，小a需要驾驶着飞船从1号星球出发前往n号星球。其中每个星球有一个能量指数p。星球i能到达星球j当且仅当 $ p_i > p_j $ 。
同时小a的飞船还有一个耐久度t，初始时为1号点的能量指数，若小a前往星球j，那么飞船的耐久度会变为 $ t \bigoplus p_j $(即t异或 $ p_j $，关于其定义请自行百度)
小a想知道到达n号星球时耐久度最大为多少？
注意：对于每个位置来说，从它出发可以到达的位置仅与两者的p有关，与下标无关。

输入描述:

第一行一个整数n，表示星球数。接下来一行有n个整数，第i个整数表示 $ p_i $.

输出描述:

一个整数表示到达n号星球时最大的耐久度
若不能到达n号星球或到达时的最大耐久度为0则输出−1。

输入

1
2
3
4
5
6
7
8
3
457 456 23

4
2 4 4 2

5
234 233 123 2333 23

输出

1
2
3
4
5
478

-1

253

说明

小a有两种方法到达3号星球
第一种：1→2→3，最终耐久度为 $ 457 \bigoplus 456 \bigoplus 23 = 22 $；
第二种：1→3，最终耐久度为 $ 457 \bigoplus 23 = 478 $。

备注:

$ 1 \leq n,\forall p_i \leq 3000 $.

思路：

典型的01背包问题！定义：$ dp[i][1] $为经过第i个星球的最大耐久度，$ dp[i][0] $ 为不经过第i个星球的最大耐久度。初始值：$ dp[0][1] = $ first $ \bigoplus $ last。状态转移方程就是选与不选的问题，最后取最大即可。

AC代码：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 3005;
int n, p, t, last, cnt, vec[maxn], ans, first; set<int> st;
int dp[maxn][3];
int main() {
    while(~scanf("%d", &n)){
        memset(vec,0,sizeof(vec));
        last = -1; cnt = 0; st.clear();
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; ++i){
            scanf("%d", &p); //p∈[1,3000]
            if(i == 1) first = p; //标记第1个星球的能量指数
            if(i != 1 && first <= p) continue; //超过第一个星球的能量指数都不能取
            if(i != 1 && i != n) st.insert(p); //去重
            if(i == n) last = p; //标记第n个星球的能量指数
        }
        if(last == -1){puts("-1"); continue;} //如果last不变，说明不小于first，直接输出-1
        for(set<int>::iterator it = st.begin(); it != st.end(); ++it){
            if(*it <= last)continue; //小于第n个星球的能量指数都不能要
            vec[cnt++] = *it;
        }
        dp[0][1] = first^last; //表示直接从1到n
        for(int j = 1; j <= cnt; ++j){
            dp[j][1] = dp[0][1]^vec[j-1]; //表示经过当前星球
            dp[j][1] = max(dp[j][1], max(dp[j-1][1]^dp[j][1], dp[j-1][0]^dp[j][1]));
            dp[j][0] = max(dp[j-1][0], dp[j-1][1]); //如果当前不选，则不选值为上一个状态选和不选的最大值
        }
        ans = max(dp[cnt][0], dp[cnt][1]); //取最大
        if(!ans) puts("-1");
        else printf("%d\n",ans);
    }
    return 0;
}

D.小a与黄金街道

题目描述：

小a和小b来到了一条布满了黄金的街道上。它们想要带几块黄金回去，然而这里的城管担心他们拿走的太多，于是要求小a和小b通过做一个游戏来决定最后得到的黄金的数量。游戏规则是这样的：
假设道路长度为n米(左端点为0，右端点为n)，同时给出一个数k(下面会提到k的用法)设小a初始时的黄金数量为A，小b初始时的黄金数量为B，小a从1出发走向n−1，小b从n−1出发走向1，两人的速度均为 $ 1 m / s $。假设某一时刻(必须为整数)小a的位置为x，小b的位置为y，若 $ gcd(n, x) = 1 $ 且 $ gcd(n, y) = 1 $ ，那么小a的黄金数量A会变为 $ A * k^x(kg) $ ，小b的黄金数量B会变为 $ B ∗ k^y(kg) $，当小a到达n−1时游戏结束。小a想知道在游戏结束时 $ A + B $ 的值。答案对 $ 10^9 + 7 $ 取模。

输入描述：

一行四个整数 $ n,k,A,B $。

输出描述:

输出一个整数表示答案

输入:

1
2
3
4 2 1 1

5 1 1 1

输出：

1
2
3
32

2

备注:

保证 $ 3 \leq n \leq 10^{18}, 1 \leq A, B, k \leq 10^{13} $.

思路：

通过前面对欧拉函数的整理，很容易得出本题的答案：。因为底数k与 $(10^9+7)$ 可以不互质，也可以互质，所以要用扩展欧拉定理来求解。虽然此题答案的指数不大，在 $ long \; long $ 范围内，但只要满足指数 $ b > \varphi(p) $，那么就可以用扩展欧拉定理对指数进行降幂，然后套用整数快速幂求解即可。
扩展欧拉定理公式：

实际上可以合并成这两条公式：

AC代码：

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
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <set>
#include <iostream>
using namespace std;
typedef long long LL;
const int maxn = 1e6+5;
const LL mod = 1e9+7;
LL n, k, A, B;
LL get_Euler(LL x){ //快速求欧拉函数
    LL res = x;
    for(LL i = 2LL; i * i <= x; ++i) {
        if(x % i == 0) {
            res = res / i * (i - 1);
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1LL) res = res / x * (x - 1);
    return res;
}
LL quick_mod(LL a, LL b) { //快速幂
    LL res = 1LL;
    while(b){
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int main(){
    while(cin >> n >> k >> A >> B){
        LL b = n * get_Euler(n) / 2;
        LL phi = mod - 1LL; //模数的欧拉函数值phi
        if(b > phi) cout << (A + B) % mod * quick_mod(k, b % phi + phi) % mod << endl; //扩展欧拉定理：适用于指数b>模数的欧拉函数值phi，底数k与p既可互质也可不互质
        else cout << (A + B) % mod * quick_mod(k, b) % mod << endl; //若b≤phi，则直接用整数快速幂求解
    }
    return 0;
}

E.小a的轰炸游戏

题目描述：

小a正在玩一款即时战略游戏，现在他要用航空母舰对敌方阵地进行轰炸
地方阵地可以看做是 $n \times m $的矩形
航空母舰总共会派出q架飞机。
飞机有两种，第一种飞机会轰炸以 $(x_i,y_i)$ 为中心，对角线长为 $ l_i $ 的正菱形(也就是两条对角线分别于x轴，y轴平行的正方形)，而第二种飞机只会轰炸正菱形的上半部分(包括第 $ x_i $ 行)(具体看样例解释)
现在小a想知道所有格子被轰炸次数的异或和
注意：不保证被轰炸的格子一定在矩形范围内，若越界请忽略

输入描述:

第一行三个整数 $ n,m,q$，分别表示矩阵的长/宽/询问次数，接下来q行，每行四个整数 $opt,x,y,l$，表示飞机类型，轰炸的坐标，以及对角线长度
保证l为奇数！

输出描述:

一个整数，表示所有格子被轰炸次数的异或和

输入

1
2
3
4
5
4 5 4
1 2 2 1
1 3 3 5
1 3 2 3
2 2 4 3

输出

1
2

说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
每次的操作矩阵即操作后的矩阵的值如下

0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0

0 0 1 0 0
0 2 1 1 0
1 1 1 1 1
0 1 1 1 0

0 0 1 0 0
0 3 1 1 0
2 2 2 1 1
0 2 1 1 0

0 0 1 1 0
0 3 2 2 1
2 2 2 1 1
0 2 1 1 0
最后把所有元素异或后为2

备注:

$ 1 \leq n,m \leq 1000 $
$ 1 \leq q \leq 5 * 10^5 $
保证 $ opt=\frac{1}{2},1 \leq x,y,l \leq max(N,M) $
读入文件过大，请使用较快的读入方式

思路：

get新技能，开3倍空间，四个方向斜着都差分一下！

AC代码：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 3050; //3倍
const int add = 1000;  //偏移量
int n, m, q, opt, x, y, l, ans, tmp, a[maxn][maxn], b[maxn][maxn], c[maxn][maxn], d[maxn][maxn];
inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
void up(int x, int y, int l) {
    a[x - l / 2][y]++, a[x + 1][y - l / 2 - 1]--; //左斜上
    b[x - l / 2][y + 1]--,b[x + 1][y + l / 2 + 2]++; //右斜下
}
void down(int x, int y, int l) {
    c[x + 1][y - l / 2 + 1]++, c[x + l / 2 + 1][y + 1]--; //左斜下
    d[x + 1][y + l / 2]--, d[x + l / 2 + 1][y]++; //右斜上
}
int main(){
    n = read(); m = read(); q = read();
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    memset(d, 0, sizeof(d));
    while(q--) {
        opt = read(); x = read(); y = read(); l = read();
        x += add, y += add;
        up(x, y, l);
        if(opt == 1) down(x, y, l);
    }
    ans = 0;
    for(int i = 1; i < n + 2 * add; ++i) { //一定要到多出2倍，这样才能复原原矩阵中的每个值
        tmp = 0;
        for(int j = 1; j < m + 2 * add; ++j) {
            tmp += a[i][j] + b[i][j] + c[i][j] + d[i][j];
            if(i > add && i <= n + add && j > add && j <= m + add) ans ^= tmp; //原图所在位置：正中心
            a[i + 1][j - 1] += a[i][j]; //左斜上
            b[i + 1][j + 1] += b[i][j]; //右斜下
            c[i + 1][j + 1] += c[i][j]; //左斜下
            d[i + 1][j - 1] += d[i][j]; //右斜上
        }
    }
    printf("%d\n", ans);
    return 0;
}

G.小a的排列

题目描述：

小a有一个长度为n的排列。定义一段区间是”萌”的，当且仅当把区间中各个数排序后相邻元素的差为1现在他想知道包含数x,y的长度最小的”萌”区间的左右端点也就是说，我们需要找到长度最小的区间 $ [l,r] $，满足区间 $ [l,r] $ 是”萌”的，且同时包含数x和数y，如果有多个合法的区间，输出左端点最靠左的方案。

输入描述：

第一行三个整数 $ N,x,y $，分别表示序列长度，询问的两个数；第二行有n个整数表示序列内的元素，保证输入为一个排列。

输入：

1
2
3
4
5
5 2 3
5 2 1 3 4

8 3 5
6 7 1 8 5 2 4 3

输出：

1
2
3
2 4

5 8

说明：

样例1：区间 $[2, 4] = {2,1,3} $包含了2,3且为“萌”区间，可以证明没有比这更优的方案。

备注：

保证 $ 2 \leq n \leq 10^5, 1 \leq x, y \leq n$。

思路：

由于输入的是一个 $ 1 - n $ 的排列，所以用一个数组标记每个数字出现的位置。因为要找的最小萌区间包含 $ x, y $ 这两个数字，所以 $ x, y $ 所在区间一定满足一个排列的条件即重排后为等差数列，公差为1，判断条件为 $ maxm - minn == ed - st $。于是通过枚举当前包含 $ x, y $ 这两个数字所在的排列中还有哪些数字没有出现，而这些数字本该被包含，这样循环更新就逐渐得到所在排列在原序列中的左右端点值，暴力即可。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int inf = 0x3f3f3f3f;
int n, x, y, st, ed, minn, maxm, a[maxn], pos[maxn];
int main() {
    while(cin >> n >> x >> y) {
        memset(pos, 0, sizeof(pos));
        for(int i = 1; i <= n; ++i) cin >> a[i], pos[a[i]] = i; //标记每个数字的出现的序号
        st = min(pos[x], pos[y]), ed = max(pos[x], pos[y]);
        minn = inf, maxm = 0;
        while(1) {
            for(int i = st; i <= ed; ++i) minn = min(minn, a[i]), maxm = max(maxm, a[i]); //当前区间中取最大和最小
            if(maxm - minn == ed - st) break; //如果该区间为一个排列，则退出
            for(int i = minn; i <= maxm; ++i) st = min(st, pos[i]), ed = max(ed, pos[i]); //更新排列中未出现的数字所在位置
        }
        cout << st << ' ' << ed << endl;
    }
    return 0;
}
0%