长乐集训第四天上午 2023.10.2

长乐集训第四天上午 2023.10.2
T1:
原本想直接一个map（char,int）水过去，但考虑到复杂度O(nk)已经接近OJ运行的极限，所以改成状态压缩的做法，并把字符串转成四进制时用到的乘法，全换成位运算，成功的把常数优化到可以AC此题。

#include 
using namespace std;
typedef long long ll;
const int N = 5e6 + 7;
string s;
ll len, k, a[N], num, ans;
int main() {
    freopen("dna.in", "r", stdin);
    freopen("dna.out", "w", stdout);
    cin >> s >> k;
    len = s.size();
    for (int i = 0; i + k - 1 < len; i++) {
        num = 0;
        for (int j = i; j <= i + k - 1; j++) {
            if (s[j] == 'A')
                num = num * 4 + 0;
            else if (s[j] == 'G')
                num = num * 4 + 1;
            else if (s[j] == 'C')
                num = num * 4 + 2;
            else
                num = num * 4 + 3;
        }
        ans = max(ans, ++a[num]);
    }
    cout << ans;
    return 0;
}

T2：
线性筛加上这一行代码就好了

if (isprime[i]) sum[i * prime[j]] = 1;//用于处理两个质数的乘积的情况

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 7;
bool isprime[N];
int prime[N], sum[N], idx, q, l, r;
inline int read() {
    int op = 1, res = 0;
    char c;
    while ((c = getchar()) < &#039;0&#039; || c > &#039;9&#039;)
        if (c == &#039;-&#039;)
            op = -1;
    res = c - &#039;0&#039;;
    while ((c = getchar()) >= &#039;0&#039; && c <= &#039;9&#039;) res = (res << 1) + (res << 3) + (c ^ 48);
    return res * op;
}
void getprime() {
    memset(isprime, 1, sizeof(isprime));
    isprime[1] = 0;
    for (int i = 2; i <= N; i++) {
        if (isprime[i]) {
            prime[++idx] = i;
            sum[i] = 1;
        }
        sum[i] += sum[i - 1];
        for (int j = 1; j <= idx; j++) {
            if (prime[j] * i >= N)
                break;
            if (isprime[i])
                sum[i * prime[j]] = 1;
            isprime[i * prime[j]] = 0;
            if (i % prime[j] == 0)
                break;
        }
    }
}
int main() {
    freopen("prime.in", "r", stdin);
    freopen("prime.out", "w", stdout);
    q = read();
    getprime();
    while (q--) {
        l = read(), r = read();
        printf("%d\n", sum[r] - sum[l - 1]);
    }
    return 0;
}

（这个快读的写法是SLT教我的，不得不说发现这种快读写法的人——WZY真是个鬼才）
T3、T4：
一行代码直接每题各骗10分，不愧是最短小精悍、拿分效率最高的代码
100+100+10+10=220分，拿下第十