内存最少

超过100%人。2.88MB
代码1

#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
const ll BASE = 911382629, MOD = 1e9 + 7;

ll* prefix_hash;  // 动态分配替代静态数组
ll* power;        // 动态分配替代静态数组

inline ll get_hash(int l, int r, const ll* ph, const ll* pw) {
    return (ph[r] - ph[l-1] * pw[r-l+1] % MOD + MOD) % MOD;
}

int main() {
    int m, n;
    scanf("%d%d", &m, &n);
    
    // 动态分配内存，仅分配实际需要的大小
    prefix_hash = new ll[m + 1];
    power = new ll[m + 1];
    
    // 初始化幂次数组（仅初始化到m，而非N）
    power[0] = 1;
    for (int i = 1; i <= m; i++) {
        power[i] = (power[i-1] * BASE) % MOD;
    }
    
    char* a = new char[m + 1];
    scanf("%s", a);
    
    // 计算前缀哈希
    prefix_hash[0] = 0;
    for (int i = 1; i <= m; i++) {
        prefix_hash[i] = (prefix_hash[i-1] * BASE + a[i-1]) % MOD;
    }
    
    while (n--) {
        int s, d, f, g;
        scanf("%d%d%d%d", &s, &d, &f, &g);
        
        ll hash1 = get_hash(s, d, prefix_hash, power);
        ll hash2 = get_hash(f, g, prefix_hash, power);
        
        puts(hash1 == hash2 ? "Yes" : "No");
    }
    
    // 释放动态分配的内存
    delete[] prefix_hash;
    delete[] power;
    delete[] a;
    
    return 0;
}

代码2

#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;
const ll BASE = 911382629, MOD = 1e9 + 7;

// 快速幂计算base^k mod mod
ll pow_mod(ll base, ll k, ll mod) {
    ll res = 1;
    while (k) {
        if (k & 1) res = res * base % mod;
        base = base * base % mod;
        k >>= 1;
    }
    return res;
}

int main() {
    int m, n;
    scanf("%d%d", &m, &n);
    
    char* a = new char[m + 1];
    scanf("%s", a);
    
    // 计算前缀哈希（仅存储前缀哈希数组，不存储幂次数组）
    ll* prefix_hash = new ll[m + 1];
    prefix_hash[0] = 0;
    for (int i = 1; i <= m; i++) {
        prefix_hash[i] = (prefix_hash[i-1] * BASE + a[i-1]) % MOD;
    }
    
    while (n--) {
        int s, d, f, g;
        scanf("%d%d%d%d", &s, &d, &f, &g);
        
        ll len1 = d - s + 1;
        ll len2 = g - f + 1;
        
        // 动态计算幂次，避免存储幂次数组
        ll hash1 = (prefix_hash[d] - prefix_hash[s-1] * pow_mod(BASE, len1, MOD) % MOD + MOD) % MOD;
        ll hash2 = (prefix_hash[g] - prefix_hash[f-1] * pow_mod(BASE, len2, MOD) % MOD + MOD) % MOD;
        
        puts(hash1 == hash2 ? "Yes" : "No");
    }
    
    delete[] a;
    delete[] prefix_hash;
    
    return 0;
}