A.肥猪的钢琴床—DP好题

题意：给出一串 01 串，你每次操作可以将 0 变为 1，或者 1 变为 0，要求 1 的串是一整段连续的串（也就是说不允许出现多个由 1 组成的子串），要求你求出满足要求的最小操作数

思路： 参考题解 满足题目的最终序列一定是 0000111111000 这种形式的。它分为三段，第一段由 0 组成，第二段由 1 组成，第三段由 0 组成（可能某一段是不存在的），每个位置都可能是这三段中的一段，所以我们可以用 dp[i][0] dp[i][1] dp[i][2] 分别记录位置 i 作为不同段中时需要的最少操作次数。所以我们可以得到递推式：

1
2
3
4
5
6
7
//根据上一个位置转移到当前位置
dp[i][0] = dp[i - 1][0] + s[i] - '0';
//处在第一段时上一个位置也必然是第一段的
dp[i][1] = min(dp[i - 1][0] + '1' - s[i], dp[i - 1][1] + '1' - s[i]);
//处在第二段时上一个位置可能是第一段的末尾或者第二段的
dp[i][2] = min(dp[i - 1][1] + s[i] - '0', dp[i - 1][2] + s[i] - '0');
//处在第三段时上一个位置可能是第二段的末尾或者第三段的

因为是字符串存法，所以计算操作是应该也是用 ascii 相减，第一段要转为 0 所以贡献值 s[i] 和 ‘0’ 相减，第二段要转为 1 所以贡献值用 ‘1’ 减去 s[i] 保证贡献值是正数，第三段和第一段相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 100;

int dp[maxn][3];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int len;
    string s;
    cin >> len>>s;
    s=" "+s;
    for (int i = 1; i <= len; ++i) {
        dp[i][0] = dp[i - 1][0] + s[i] - '0';
        dp[i][1] = min(dp[i - 1][0] + '1' - s[i], dp[i - 1][1] + '1' - s[i]);
        dp[i][2] = min(dp[i - 1][1] + s[i] - '0', dp[i - 1][2] + s[i] - '0');
    }
    cout << min(dp[len][0], min(dp[len][1], dp[len][2])) << endl;
    system("pause");
    return 0;
}

B.拯救小a—签到题

题意：给出一组字符串，字符串组以 . 结尾，输出有多少个 a

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    string s;
    int cnt = 0;
    while (cin >> s) {
        if (s == ".") break;
        for (int i = 0; i < s.length(); ++i)
            if (s[i] == 'a') ++cnt;
    }
    cout << cnt << endl;
    //system("pause");
    return 0;
}

C.母牛的俄罗斯盘堵—数学归纳+简单博弈

题意：喜欢追求刺激的母牛打算和猪猪来一场紧张刺激的俄罗斯轮盘赌（当然只是用橡胶子弹），败者需要请胜者吃宵夜，他们觉得一枪一枪轮流射击还不够刺激，决定遵循以下规则来轮流向自己扣动扳机。

  • 可以扣动扳机不多于k+1次，最少1次，k为上一次操作者扣动扳机的次数.

  • 先手第一次操作能且只能扣动一次扳机

现在子弹已经装在了玩具枪里，并且他们都知道这颗子弹会在第n次扣动扳机时射出，母牛和猪猪都不想输掉这场对决，并且他们都聪明绝顶，会采用最好的策略进行对决。 由母牛发起的对决，自然是母牛先手。 如果母牛能赢下这顿宵夜则输出 Cow,否则 Pig

思路：

  • 一种是写出前十种情况然后找出规律

    1
    2
    3
    4
    n=1->pig    n=2->cow    n=3->pig
    n=4->pig    n=5->cow    n=6->pig    
    n=7->cow    n=8->pig    n=9->pig
    n=10->cow   ...

    2、5、7、10先手赢，他们不是模 5 余 2 就是整除 5

  • 另一种是确定前五种情况然后其他情况归纳到这五种， 参考题解 不是太懂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    scanf("%d", &n);
    while (n--) {
        int x;
        scanf("%d", &x);
        if (x % 5 == 0 || x % 5 == 2)
            puts("Cow");
        else
            puts("Pig");
    }
    system("pause");
    return 0;
}

D.中学数学题—思维

题意：求 n! 转换为 m 进制的数的后导零的个数，保证 m 是质数

思路：这题其实是一个简化题，原题不保证 m 是质数。原理也很简单就是找出用 n 分别除 m 的质因数得到的次数最小的那个，这里保证 m 是质数所以直接看 n 中 m 作为因子的次数就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int t;
    scanf("%d", &t);
    int n, p;
    for (int i = 0; i < t; i++) {
        scanf("%d%d", &n, &p);
        int count = 0;                     //计数器
        for (int j = p; j <= n; j += p) {  //找出阶乘数中所有p的倍数处理：1p,2p,3p...
            int k = j;
            while (k % p == 0) {  //计算p的倍数中包含p个数，即要除以几次才能余数不为0，即0的个数
                count++;
                k /= p;
            }
        }
        printf("%d\n", count);
    }
    system("pause");
    return 0;
}
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
//或者直接点套个板子
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll cal(ll n, ll p) {  //统计n!分解为质因数有多少个p
    ll cnt = 0;
    while (n > 0) {
        cnt += n / p;
        n /= p;
    }
    return cnt;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n, m;
        cin >> n >> m;
        cout << cal(n, m) << endl;
    }
    system("pause");
    return 0;
}

E.枚举求和—思维+签到

题意：

思路：最大公约数整除 k 说明 i 和 j 都是 k 的倍数，所以问题转化为有多少个 i 和 j 都是 k 的倍数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        ll n, m, k;
        cin >> n >> m >> k;
        cout << (n / k) * (m / k) << endl;
    }
    system("pause");
    return 0;
}

G.排解忧伤—思维+模拟

题意：猪猪参加小米赞助的 icpc 比赛之后惨遭打铁，为了排解忧伤，他开始观察嘉宾席。嘉宾席是间隔为 1，一字排开的 n 个座椅，从左至右标号为 1 到 n。有 m 个嘉宾，每个嘉宾有一个心仪座位 Ai，注意，不同嘉宾的心仪座位可能相同。嘉宾们会统一从一排座位的最左侧依次入场。一个嘉宾首先会走到他心仪的位子，如果此时他发现没有人坐，他就会立刻占据这个位子。如果已经有人坐了，该嘉宾会继续向右走，直到遇到一个空位子，立刻坐下。每个嘉宾的怒气值是他额外行走的距离，也就是最终的座位到心仪座位的距离。如果走到最后都没有找到位置，嘉宾会怒气爆棚。显然，座位存在一个先到先得的关系，不是每个人都能坐到心仪的座位。现在，猪猪想思考什么样的入场顺序可以使嘉宾们怒气值之和最小，请你帮帮他

输出最小怒气和。如果无论怎样安排入场顺序，都不能使所有嘉宾找到位子，输出 -1

思路：模拟几个情况就会发现无论怎么安排他们的怒气之和都不会变，所以随便放一个顺序统计怒气就好了。我们可以按照座位序号从小到大依次向后让他们入座，如果后一个人在第 n 个位置之后坐下输出 -1，否则就输出统计的怒气值之和

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;

int a[maxn];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        cin >> a[i];
    sort(a + 1, a + 1 + m);
    ll res = 0;
    int p = 0;
    for (int i = 1; i <= m; ++i) {
        if (p < a[i])
            p = a[i];  //比当前要求的作为序号小就直接跳到可以坐下的第一个位置
        else
            ++p;          //放完一个人就从下一个位置开始放
        res += p - a[i];  //加上当前放下这个人的怒气值
    }
    if (p > n)
        puts("-1");
    else
        cout << res << endl;
    system("pause");
    return 0;
}

K.很基础的模拟题—容器+签到

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
vector<int> vec;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        vec.push_back(x);
    }
    while (q--) {
        int opt;
        cin >> opt;
        if (opt == 1) {
            int pos;
            cin >> pos;
            --pos;  //容器中从0开始所以-1
            vec.erase(vec.begin() + pos);
        } else if (opt == 2) {
            int pos, k;
            cin >> pos >> k;
            --pos;
            vec.insert(vec.begin() + pos, k);
        } else {
            int pos, cnt = 0;
            cin >> pos;
            pos--;
            for (int i = pos; i < vec.size(); ++i) {
                if (vec[i] == vec[pos])
                    ++cnt;
                else
                    break;
            }
            //必须放在外面,因为有一种情况是可能一直找到最后
            vec[pos] = vec[pos] * cnt;
            vec.erase(vec.begin() + pos + 1, vec.begin() + pos + cnt);  //区间删除
        }
        for (auto x : vec) cout << x << " ";
        cout << endl;
    }
    system("pause");
    return 0;
}

L.母牛上柱—思维+签到

题意：一头母牛在圆柱底面的 S 点要爬到顶面的 T 点，请计算最短距离。为方便计算，我们将柱子简化成如上图所示的圆柱。S 点为母牛在柱子底部所在的位置，α 为 OS 与平面 XOZ 的夹角；T 为柱子顶部的最佳观测点的位置，β 为 O’T 与平面 XOZ 的夹角；R 为圆柱的半径，H为圆柱的高。 圆周率 π 取 3.1415926535

思路：小学计算题，就是圆柱展开后 S 和 T 的在圆周上的距离的平方+高的平方，注意这个圆周上的距离肯定是选择短的一半，即当 α-β>180 时就走另一个方向

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;
const double pi = 3.1415926535;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int a, b, r, h;
        cin >> a >> b >> r >> h;
        if (a < b) swap(a, b);
        int ang = a - b;
        if (ang > 180) ang = 360 - ang;
        double dis = (ang * 1.0 / 360) * pi * 2 * r;
        double xie = dis * dis + h * h;
        cout << fixed << setprecision(2) << xie << endl;
    }
    system("pause");
    return 0;
}