A.贪心算法(新生题)

题目标题写的很明白了,贪心算法......,所以对时间间隔结束时间排序就行, 即在一段时间内, 时间序列更早结束就意味着有更多的时间去做其他的

修改前:

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

bool st[24];

struct Time {
    int start, end;
    int sub;
};

bool cmp (Time t1, Time t2) {
    return t1.sub < t2.sub;
}

bool check (int x, int y) {
    for (int i = x; i < y; i ++) {
        if (st[i]) return false;
    }
    return true;
}

int main () {
    int n;
    cin >> n;

    Time time[N]; 
    for (int i = 0; i < n; i ++) {
        int a, b;
        cin >> a >> b;
        if (a > b) continue;
        time[i].start = a;
        time[i].end = b;
        time[i].sub = b - a;
    }

    sort (time, time + n, cmp);

    // for (int i = 0; i < n; i ++) {
    //     cout << time[i].start << " " << time[i].end << " " << time[i].sub << '\n';
    // }

    int res = 0;
    for (int i = 0; i < n; i ++) {
        int start = time[i].start;
        int end = time[i].end;
        if (check (start, end)) {
            for (int j = start; j < end; j ++) {
                st[j] = true;
            }
            res ++;

        }
    }

    cout << res << '\n';
    return 0;
}

修改后:

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

bool st[24];

struct Time {
    int start, end;
};

bool cmp (Time t1, Time t2) {
    return t1.end < t2.end;
}

bool check (int x, int y) {
    for (int i = x; i < y; i ++) {
        if (st[i]) return false;
    }
    return true;
}

int main () {
    int n;
    cin >> n;

    Time time[N]; 
    for (int i = 0; i < n; i ++) {
        int a, b;
        cin >> a >> b;
        if (a > b) continue;
        time[i].start = a;
        time[i].end = b;
    }

    sort (time, time + n, cmp);

    // for (int i = 0; i < n; i ++) {
    //     cout << time[i].start << " " << time[i].end << " " << time[i].sub << '\n';
    // }

    int res = 0;
    for (int i = 0; i < n; i ++) {
        int start = time[i].start;
        int end = time[i].end;
        if (check (start, end)) {
            for (int j = start; j < end; j ++) {
                st[j] = true;
            }
            res ++;

        }
    }

    cout << res << '\n';
    return 0;
}

B.成绩输入输出

简单的输入输出, 这里可以用c语言的printf函数来格式化输出

#include <cstdio>

using namespace std;

int main () {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    printf ("score1=%d,score2=%d,score3=%d", a, b, c);
    return 0;
}

C.palprime

题目大意, 输入一个二进制字符串, 输出一个大于等于它的二进制回文素数二进制字符串

题目说的听明白的, 二进制十进制的转换, 筛素数, 判断回文序列
一开始看见题目数据量很大, 就用了线性筛素数(不明白的可以去搜下看一下哦), 做完之后发现题目本身给的时间很多,所以用最简单的从输入数开始判断, 其实也能过

说一下N和M是怎么来的, N是题目本身给的, 即We guarantee b will be no Longer than 21 bits, 也就是数字最大是\(2^{21}\)即2097152, 因此给的比它大就行, M的话是, 从2到N中符合题目要求的数的数量, 也就是代码中的tt, 算出来好像只有1k多, 忘了[]~(￣▽￣)~*

代码如下:

#include <iostream>
#include <string>

using namespace std;

const int N = 2200000, M = 2100;

int tt;
long long prime[M];
bool st[N];
string ans[M];

bool check (int x, int idx) {
    string s = "";
    int t;
    while (x) {
        t = x % 2;
        s += (char)(t + '0');
        x /= 2;
    }
    int len = s.length();
    for (int i = len - 1; i >= len / 2; i --) {
        if (s[i] != s[len - 1 - i]) return false;
    }
    ans[idx] = s;
    return true;
}

void olerPrime() {
    tt = -1;
    for (int i = 2; i < N; i ++) {
        if (!st[i]) {
            if (check(i, tt + 1)) {
                prime[++ tt] = i;
            }
        }
        for (int j = 0; j <= tt && prime[j] < N / i; j ++) {
            st[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
    // cout << tt << '\n';
}

int main () {

    olerPrime();

    // for (int i = tt; i >= tt - 100; i --) cout << ans[i] << '\n';

    string n;
    while (cin >> n) {
        int k = 1, t;
        int a = 0;
        for (int i = n.length() - 1; i >= 0; i --) {
            t = n[i] - '0';
            if (t) a = a + k;
            k = k * 2;
        }
        for (int i = 0; i <= tt; i ++) {
            if (prime[i] >= a) {
                cout << ans[i] << '\n';
                break;
            }
        }
    }

    return 0;
}

D.A Beautiful Array

通过题目给的那个公式\(\sum_{i= 1}^{\frac{n}{2}} = A_{n-i+1} + A_{i}\)来算出那个Beauty, 这个公式通过一个for循环就能完成, 然后我们需要做的是怎么找出最大值, 不难发现, 其实将A数组从小到大排序完之后得出来的数一定是最大的(至于为什么不做解释, 感兴趣自己去网上找证明哦)

代码如下:

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int a[N];

int main () {
    int T;
    cin >> T;
    while (T --) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i ++) cin >> a[i];
        sort(a + 1, a + 1 + n);
        int res = 0;
        for (int i = 1; i <= n / 2; i ++) {
            res += a[n + 1 - i] - a[i];
        }
        cout << res << '\n';
    }
}

E.字符串

这题在比赛的过程中没有做出来, 想了两种思路
1. 就直接用hashmap装截完之后的字符串, 但是会爆掉, 空间会开的很大很大
2. 用trie树, 不会爆空间但是会超时....

之后就是比赛之后看的题解, 然后....发现自己想复杂了???(就是自己太菜了╮(╯-╰)╭)

这是我看的题解(发现它是蓝色的嘛, 点就行了)

代码如下:

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n;
int idx[N], _rank[N];
string s;

bool cmp (int a, int b) {
    if (a < b) {
        if (idx[a] >= b) return true;
        return s[idx[a] + 1] < s[idx[a]];
    } else return !cmp(b, a);
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> s;
    for (int i = 0, t = 0; i < n; i ++) {
        if (t < i) t = i;
        while (t < n && s[t] == s[t + 1]) t ++;
        idx[i] = t;
    }

    for (int i = 0; i < n; i ++) _rank[i] = i;

    sort (_rank, _rank + n, cmp);
    for (int i = 0; i < n; i ++) cout << _rank[i] + 1 << " ";

    return 0;
}