第四场 02/09

总体：难度偏易

A

通过前缀和，计算 pos[i], 表示第 i 个 R 出现的最早位置。
从左到右遍历，当前位置为 i 时，假设出现 num 个 R，上一次在 last 位置出现了 P。那么通过 pos[num - k + 1] 可以获得满足 k 个R的最早位置。
那么可选位置最多只会有 pos[num - k + 1] - last 个，这个数值可能会小于 0，所以与 0 取 max即可。

#include<bits/stdc++.h>
using namespace std;
#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int N = 200010;
int n, k;
char s[N];
int pos[N];
int main(){
    cin >> n >> k;
    scanf("%s", s + 1);
    int num = 0, last = 0;
    ll rs = 0;
    pos[0] = 0;
    rep(i,1,n) {
        if(s[i] == 'R') {
            num ++;
            pos[num] = i;
        }
        if(s[i] == 'P') last = i;
        if(num >= k) {
            rs += max(0, pos[num - k + 1] - last);
            // dbg(i, last,pos[num - k + 1],  max(0, pos[num - k + 1] - last));
        }
    }
    printf("%lld\n",rs);
    return 0;
}

B

线段树
线段树维护。
每个端点保存2~10进制下的具体数值、区间长度、区间最大值。
端点合并时，相应的每个进制进行拼接。
复杂度

#include<bits/stdc++.h>
using namespace std;
#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int N = 100010, mod = 1e9 + 7;
int n, q, p[11][N];
char s[N];
struct SegTree{
    ll val[11];
    int mx, len;
}t[N*4];
SegTree operator + (SegTree ls, SegTree rs) {
    SegTree t;
    t.mx = max(ls.mx, rs.mx);
    rep(i,2,10) {
        t.val[i] = ls.val[i] * p[i][rs.len] % mod + rs.val[i];
        t.val[i] %= mod;
    }
    t.len = ls.len + rs.len;
    return t;
}
void build(int p, int l, int r) {
    if(l == r) {
        t[p].mx = s[l] - '0';
        t[p].len = 1;
        rep(i,2,10) {
            t[p].val[i] = t[p].mx;
        }
        return;
    }
    int m = (l + r) / 2;
    build(p * 2, l, m);
    build(p * 2 + 1, m + 1, r);
    t[p] = t[p * 2] + t[p * 2 + 1];
}
void change(int p, int l, int r, int x, int val) {
    if(l == r) {
        t[p].mx = val;
        rep(i,2,10) {
            t[p].val[i] = t[p].mx;
        }
        return;
    }
    int m = (l + r) / 2;
    if(x <= m) change(p * 2, l, m, x, val);
    else change(p * 2 + 1, m + 1, r, x, val);
    t[p] = t[p*2] + t[p*2+1];
}
int queryMx(int p, int l, int r, int x, int y){
    if(l >= x && r <= y) return t[p].mx;
    int m = (l + r) / 2;
    if(x > m) return queryMx(p * 2 + 1, m + 1, r, x, y);
    else if(y <= m) return queryMx(p * 2, l, m, x, y);
    else return max(queryMx(p * 2, l, m, x, y), queryMx(p * 2 + 1, m + 1, r, x, y));
}
SegTree query(int p, int l, int r, int x, int y){
    if(l >= x && r <= y) return t[p];
    int m = (l + r) / 2;
    if(x > m) return query(p * 2 + 1, m + 1, r, x, y);
    else if(y <= m) return query(p * 2, l, m, x, y);
    else return query(p * 2, l, m, x, y) + query(p * 2 + 1, m + 1, r, x, y);
}
int main(){
    scanf("%d%d", &n, &q);
    scanf("%s", s + 1);
    rep(i,2,10) {
        p[i][0] = 1;
        rep(j,1,n) {
            p[i][j] = 1ll * p[i][j-1] * i % mod;
        }
    }
    build(1, 1, n);
    while(q--){
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if(op == 1) {
            change(1, 1, n, x, y);
        } else {
            int mx = queryMx(1, 1, n, x, y) + 1;
            // dbg(mx);
            printf("%lld\n", query(1, 1, n, x, y).val[mx]);
        }
    }
}

C

前缀和处理即可。
坑点是坐标范围，t 和 a 都是 100000，所以最大范围会到 200000

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int N = 200010;
int n, t, a, c[N], d[N];
char s[N];
int main(){
    cin >> n >> t;
    scanf("%s", s + 1);
    rep(i,1,n) {
        scanf("%d", &a);
        if(s[i] == 'B') {
            c[a] += 1;
            c[a + t] -= 1;
        } else {
            d[a] += 1;
            d[a + t] -= 1;
        }
    }
    int rs = 0;
    rep(i,1,200000) {
        c[i] += c[i-1];
        d[i] += d[i-1];
        if(c[i] && !d[i]) rs ++;
    }
    cout << rs << endl;
    return 0;
}

D

题目问运动过程中距离一个点的最短距离。
而每次运动轨迹是一条线段，所以这个题目就是点到线段的最短距离。

E

直接输出 n 即可。
可以用数学归纳法或者打表发现规律。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
long long f(long long x){
    if(x==1)return 1;
    return f(x/2)+f(x/2+x%2);
}
int main(){
    ll n;
    cin >> n;
    cout << n << endl;
}

G

先整体排个序。思考如何 内解决该题。
不难想出以下做法：

for i in {1..n}:
    res *= (a[i] * a[i])
    for j in {1..i-1}:
        res *= (a[i] * a[j])^(2^(i-j-1))

这是由于 (i,j) 中间有 （j-i-1) 个数字，每个数字两种选择（出现或者不出现），会导致 (a[i], a[j]) 这对最大值与最小值的数量以 2 的幂次来计算。
那么现在问题转变成了如何快速计算上面的式子。
从最简单的，先来看 ：
再看 :
:

#include<bits/stdc++.h>
using namespace std;
#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int N = 200010, mod = 1e9 + 7;
int n, a[N];
ll ksm(ll a, ll b){
    ll rs = 1;
    for(;b;b>>=1) {
        if(b & 1) rs = rs * a % mod;
        a=a*a%mod;
    }
    return rs;
}
int main(){
    cin >> n;
    rep(i,1,n) {
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + 1 + n);
    ll rs = 1, sum = 1, presum = 1, cnt = 1;
    rep(i,1,n) {
        sum = presum * a[i] % mod;
        presum = presum * presum % mod * a[i] % mod;
        rs = rs * sum % mod * ksm(a[i], cnt) % mod;
        cnt = (cnt * 2) % (mod - 1);
    }
    cout << rs << endl;
    return 0;
}

H

高中数学题，给定正方体对角线的一般长度，求体积

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
int main(){
    double x;
    cin >> x;
    x = 8.0 * x * x * x / 3 / sqrt(3);
    printf("%.10f\n", x);
}

I

先把 ，然后 d[i][j] 表示前 i 张卡牌，使用了 j 的魔力可以达到的最大威力。其中 j < k，只记录模 k 后的值。
然后直接DP转移即可。复杂度 。
对于每个状态 d[i][j]，可以直接从 d[i-1][j] 转移过来。
然后对于 a[i]，遍历每个 d[i-1][j], 更新到 d[i][(j + a[i])%k]。
由于求最大值，并且需要判断是否存在无解，所以一开始必须将所有初值赋值为负无穷。单独赋值 d[0][0] = 0
最后单独判断 d[n][0] 是否等于 0，是的话输出 -1

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int N = 1010;
int n, k, a[N], b[N];
ll d[N][N];
int main(){
    scanf("%d%d", &n, &k);
    memset(d, -0x3f, sizeof d);
    d[0][0] = 0;
    rep(i,1,n) {
        scanf("%d%d", &a[i], &b[i]);
        a[i] %= k;
        memcpy(d[i], d[i-1], sizeof d[i]);
        rep(j, 0, k-1) {
            int p = (j + a[i]) % k;
            d[i][p] = max(d[i][p], d[i-1][j] + b[i]);
        } 
    }
    if(d[n][0] == 0) d[n][0] = -1;
    printf("%lld\n", d[n][0]);
}

J

最小公倍数的定理：
两个数分解质因数后：

那么:

#include<bits/stdc++.h>
using namespace std;
#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int mod = 1e9 + 7;
unordered_map<int,int> mp;
bool isPrime(int x){
    if(x == 1) return true;
    int t = sqrt(x);
    rep(i,2,t) if(x % i == 0) return false;
    return true;
}
void get(int x){
    for(int i = 2; i * i <= x; i++){
        if(x % i) continue;
        int c = 0;
        while(x % i == 0) {
            c ++;
            x /= i;
        }
        mp[i] = max(mp[i], c);
    }
    if(x > 1) mp[x] = max(mp[x], 1);
}
int main(){
    int l, r;
    cin >> l >> r;
    int g = 0;
    int sum = 1;
    int cnt = 0;
    rep(i,l,r) {
        if(isPrime(i)) continue;
        cnt ++;
        get(i);
    }
    if(cnt == 0) {
        puts("-1");
        return 0;
    }
    int rs = 1;
    for(auto t : mp) {
        while(t.second --) rs = 1ll * rs * t.first % mod;
    }
    cout << rs << endl;
}

K

先求出 x 在二进制表示下，最高位的 1 的所在位置。
比如 5: 101，最高位 1 在第 3 位，那么将 5 左移 3 位再加上 5 即可。
可以证明这样的拼接方式一定不会超过
101101

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
int main(){
    ll x;
    cin >> x;
    int n = log2(x) + 1;
    cout << (x << n) + x << endl;
}

L

cnt[i][j] 表示前 i 个字符中 j 出现的个数。
cnt2[i][j][k] 表示前 i 个字符中，字符串 jk 作为子序列的出现个数。
设 (l,r,str) 表示区间 (l,r) 中 str 的出现次数：
由此，可以求出一个区间内字符 j 的个数。
也可以计算出一个区间字符 ab 的个数：

然后，(l,r) 中字符串 abc 的出现次数可以分三部分来求解，

然后现在问题简化成了求 abc 在 (1,r) 以及 (1,l-1) 这两个前缀中的出现位置。
由于有了 cnt2[i][j][k]，如果用 d[a][b][c] 表示遍历过程中的前缀中子序列为 abc 的个数，那么遍历到 i 时：

for a in (a..z):
    for b in (a..z):
        d[a][b][s[i]] += cnt2[i-1][a][b]

如此，便可计算。通过离散化操作累计答案即可。
复杂度

#include<bits/stdc++.h>
using namespace std;
#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int N = 80010, M = 500010;
int n, m;
char t[N];
ll cnt[N][26], cnt2[N][26][26];
ll get1(int l, int r, int c) {
    if(l > r) return 0;
    return cnt[r][c] - cnt[l - 1][c];
}
ll get2(int l, int r, int a, int b) {
    if(l > r) return 0;
    ll rs = cnt2[r][a][b] - cnt2[l-1][a][b];
    rs -= get1(1, l - 1, a) * get1(l, r, b);
    return rs;
}
struct Node {
    int a, b, c, id, type;
};
vector<Node> v[N];
ll rs[M], d[26][26][26];
int main(){
    scanf("%d%d", &n, &m);
    scanf("%s", t + 1);
    rep(i,1,n) {
        memcpy(cnt[i], cnt[i-1], sizeof cnt[i]);
        memcpy(cnt2[i], cnt2[i-1], sizeof cnt2[i]);
        int c = t[i] - 'a';
        cnt[i][c] ++;
        rep(j,0,25) {
            cnt2[i][j][c] +=  cnt[i-1][j];
        }
    }
    rep(i,1,m){
        char s[4];
        int l, r;
        scanf("%d%d%s", &l, &r, s);
        int a = s[0] - 'a';
        int b = s[1] - 'a';
        int c = s[2] - 'a';
        rs[i] -= get1(1, l-1, a) * get2(l, r, b, c) + get2(1, l-1, a, b) * get1(l, r, c);
        v[l-1].push_back({a, b, c, i, -1});
        v[r].push_back({a, b, c, i, 1});
    }
    rep(i,1,n) {
        int c = t[i] - 'a';
        rep(j,0,25) {
            rep(k,0,25) {
                d[j][k][c] += cnt2[i-1][j][k];
            }
        }
        for(auto &it : v[i]) {
            rs[it.id] += d[it.a][it.b][it.c] * it.type;
        }
    }
    rep(i,1,m) {
        printf("%lld\n", rs[i]);
    }
}