长乐Day4

T1 看到k很小，想到O（nk）暴力 考试时用map 结果TLE80分

看题目只有ACTG四个字符，可以用四进制数来代表字母的组合，这样可以用数组存 AC代码

#include <bits/stdc++.h>
using namespace std;
int k, w = -1, pt = 0, tp[12] = { 0, 1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576 },
       ll[50000001];
string a, s;
int main() {  // ACTG  0123
    freopen("dna.in", "r", stdin);
    freopen("dna.out", "w", stdout);
    cin >> s >> k;
    int u = s.size();
    for (int i = 0; i <= u - k; i++) {
        int op = 1, ml, ans = 0;
        for (int j = k - 1; j >= 0; j--) {
            if (s[j + i] == &#039;A&#039;)
                ml = 0;
            if (s[j + i] == &#039;C&#039;)
                ml = 1;
            if (s[j + i] == &#039;T&#039;)
                ml = 2;
            if (s[j + i] == &#039;G&#039;)
                ml = 3;
            ans += (ml * tp[op]);
            op++;
        }
        ll[ans]++;
        if (ll[ans] > w)
            w = ll[ans];
    }
    cout << w;
    return 0;
}

T2 求l到k之间的数是质数或质数乘积的数 考试时看到n<=10^7,马上想到欧拉筛

最后用前缀和与处理后即可 AC代码

#include <bits/stdc++.h>
using namespace std;
bool t[10000001], r[3170];
long long l[700001];
int a[10000001];
int main() {
    freopen("prime.in", "r", stdin);
    freopen("prime.out", "w", stdout);
    int q, k = 0, ans = 0;
    cin >> q;
    for (int i = 1; i <= 3162; i++) {
        bool u = false;
        for (int j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) {
                u = true;
                break;
            }
        }
        if (u == false)
            r[i] = 1;
        if (i == 2)
            r[2] = 1;
        if (i == 1)
            r[1] = 0;
    }
    for (int i = 1; i <= 3162; i++) {
        if (t[i] == 0 && i != 1) {
            for (int j = i; j <= 10000000; j += i) {
                if (j == i && r[i] == 1) {
                    continue;
                }
                t[j] = 1;
            }
        }
    }
    t[1] = 1;
    for (int i = 1; i <= 10000000; i++) {
        if (t[i] == 0) {
            k++;
            l[k] = i;
        }
    }
    for (int i = 1; i < k; i++) {
        for (int j = i; j < k, l[i] * l[j] <= 10000000; j++) {
            t[l[i] * l[j]] = 0;
        }
    }
    for (int i = 1; i <= 10000000; i++) {
        a[i] = ans;
        if (t[i] == 0)
            ans++;
    }
    for (int i = 1; i <= q; i++) {
        int l, r, ans;
        cin >> l >> r;
        ans = a[r] - a[l];
        if (t[r] == 0)
            ans++;
        cout << ans << endl;
    }
    return 0;
}

T3 T4 直接输出impossible和-1，各得十分