[数据结构与算法]2022牛客寒假算法基础集训营4 ABCDEFGHIJK

A.R

思路

她想取一个连续子串，该子串包含至少$k$个'R'字符，且不能包含'P'字符。

很裸的双指针，枚举每个右端点，找到最后一个符合条件的左端点后计数即可。

Accepted Code

#include <bits/stdc++.h>
#define int long long 
using namespace std;

string s;

inline void solve(){
    int n, k, ans = 0; cin >> n >> k >> s;
    s = ' ' + s;
    string tmp = "";
    for(int i = 1; i <= n + 1; i++){
        if(s[i] == 'P' || i == n + 1){
            int l = 0, r = 0, cnt = 0; 
            for(r = 0; r < tmp.size(); r++){
                cnt += (tmp[r] == 'R');
                while(l <= r && cnt >= k) cnt -= (tmp[l] == 'R'), l++;
                ans += l;
            }
            tmp = "";
        }   
        else tmp += s[i];
    }
    cout << ans << endl;
}

signed main(){
    solve();
    return 0;
}

B.进制

思路

维护$10$棵线段树，其中第$1$棵维护区间最大值，第$2?10$棵维护$X$进制区间和。

Accepted Code

#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 1e5 + 10, MOD = 1e9 + 7;
int tree[12][N << 2], fc[12][N << 2], a[12][N << 2];
string s;

ll binpow(ll a, ll b, ll m = MOD)
{
    a %= m, b %= m;
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
/*
inline int convert(string s, int x)
{
    int ans = 0;
    int len = s.size();
    for (int i = 0; i < len; i++)
    {
        ans = ans * x;
        if (s[i] >= '0' && s[i] <= '9')
            ans += (s[i] - '0') + 10;
        else
            ans += (s[i] - 'A') + 10;
    }
    return ans;
}*/

inline void push_up(int rt){ 
    tree[0][rt] = max(tree[0][rt << 1], tree[0][rt << 1 | 1]);
    for(int i=1;i<=9;i++){
        tree[i][rt]=(tree[i][rt << 1] + tree[i][rt << 1 | 1])%MOD;
    } 
}

void build(int rt, int l, int r){
    if(l == r){
        for(int i=0;i<=9;i++){
            tree[i][rt]=a[i][l];
        }
        return;
    }
    int mid = l + r >> 1; 
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    push_up(rt);
}

void update(int rt, int l, int r, int pos, int val){
    if(l == r){
        for(int i=0;i<=9;i++){
            tree[i][rt]=val*fc[i][pos];
        }
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid) update(rt << 1, l, mid, pos, val);
    else update(rt << 1 | 1, mid + 1, r, pos, val);
    push_up(rt);
}

int query(int rt, int l, int r, int L, int R){
    if(l >= L && r <= R) return tree[0][rt];
    int ans = -1, mid = l + r >> 1;
    if(mid >= L) ans = max(ans, query(rt << 1, l, mid, L, R));
    if(mid < R) ans = max(ans, query(rt << 1 | 1, mid + 1, r, L, R));
    return ans;
}
int query1(int rt, int l, int r, int L, int R,int x){
    if(l >= L && r <= R) return tree[x][rt];
    int ans = 0, mid = l + r >> 1;
    if(mid >= L) (ans += query1(rt << 1, l, mid, L, R,x))%=MOD;
    if(mid < R) (ans += query1(rt << 1 | 1, mid + 1, r, L, R,x))%=MOD;
    return ans;
}

inline void solve(){
    int n, q;
    cin >> n >> q >> s;
    for (int i = 0; i <= 9; i++) fc[i][n] = i + 1;
    for (int i = n; i; i--){
        for (int j = 0; j <= 9; j++){
            a[j][i] = (s[i - 1] - '0') * fc[j][i] % MOD;
            fc[j][i - 1] = fc[j][i] * (j + 1) % MOD;
        }
    }
    build(1, 1, n);

    while (q--){
        int op, x, y; cin >> op >> x >> y;
        if (op == 1) update(1, 1, n, x, y);
        else{
            int tmp = query(1, 1, n, x, y);
            if (tmp == 0) cout << 0 << endl;
            else cout << query1(1, 1, n, x, y, tmp) * binpow(binpow(tmp + 1, n - y + 1), MOD - 2) % MOD << endl;
        }
    }
}

signed main(){
    solve();
    return 0;
}

C.蓝彗星

思路

分别标记两个差分数组，然后前缀和求区间覆盖点数即可。

Accepted Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10;
int a[N][2], s[N][2];

string str;

inline void solve(){
    int n, t, maxx = 0, ans = 0; cin >> n >> t >> str;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        maxx = max(maxx, x);
        if(str[i] == 'B') a[x][0]++, a[x + t][0]--;
        else a[x][1]++, a[x + t][1]--;
    }
    maxx += t;
    for(int i = 1; i <= N; i++){
        s[i][0] = s[i - 1][0] + a[i][0];
        s[i][1] = s[i - 1][1] + a[i][1];
    }
    for(int i = 1; i <= maxx; i++){
        if(s[i][0] && !s[i][1]) ans++;
    }
    cout << ans << endl;
}

signed main(){
    solve();
    return 0;
}

D.雪色光晕

思路

计算几何板子，算点到线段距离即可，注意输出精度。。。

Accepted Code

#include <bits/stdc++.h>
using namespace std;

struct point_t{ double x, y; };

double PointTOline(point_t const &a, point_t const &b, point_t const &p){
    double ap_ab = (b.x - a.x) * (p.x - a.x) + (b.y - a.y) * (p.y - a.y);
    if (ap_ab <= 0) return sqrt((p.x - a.x) * (p.x - a.x) + (p.y - a.y) * (p.y - a.y));
    double d2 = (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y) ;
    if (ap_ab >= d2) return sqrt((p.x - b.x) * (p.x - b.x) + (p.y - b.y) * (p.y - b.y)) ;
    double r = ap_ab / d2, px = a.x + (b.x - a.x) * r, py = a.y + (b.y - a.y) * r;
    return sqrt( (p.x - px)*(p.x - px) + (p.y - py)*(p.y - py) );
}


inline void solve(){
    int n = 0; cin >> n;
    double x0, y0, x, y; cin >> x0 >> y0 >> x >> y;
    double minn = sqrt(1.0 * (x - x0) * (x - x0) + 1.0 * (y - y0) * (y - y0));
    for(int i = 1; i <= n; i++){
        double xi, yi; cin >> xi >> yi;
        minn = min(minn, PointTOline(point_t{x0 + xi, y0 + yi}, point_t{x0, y0}, point_t{x, y}));
        x0 += xi, y0 += yi;
    }
    cout << fixed << setprecision(8) << minn << endl;
}

signed main(){
    solve();
    return 0;
}

E.真假签到题

要不退役吧

Accepted Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

inline void solve(){
    int x; cin >> x;
    cout << x << endl;
}

signed main(){
    solve();
    return 0;
}

F.小红的记谱法

思路

记录<和>的差值，判断循环输出对应的音符即可。

Accepted Code

#include <bits/stdc++.h>
using namespace std;

const string con = "@6712345"; //'@'是占位符

inline void solve(){
    string s; cin >> s;
    int cnth = 0, cntl = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '>') cnth++;
        else if(s[i] == '<') cntl++;
        else{
            cout << con[s[i] - 'A' + 1];
            if(cnth > cntl)
                for(int j = 1; j <= cnth - cntl; j++) cout << '*';
            else if(cntl > cnth)
                for(int j = 1; j <= cntl - cnth; j++) cout << '.';
            else continue;
        }
    }
}

signed main(){
    solve();
    return 0;
}

G.子序列权值乘积

思路

单独见博客：

Accepted Code

#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
int a[N];
/*
inline int bin(int x, int n, int ret = 1) {
    for (x %= MOD; n; n >>= 1, x = x * x % MOD) if (n & 1) ret = ret * x % MOD;
    return ret == 1 ? 0 : ret;
}*/

ll binpow(ll a, ll b, ll m) {
    a %= m, b %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

inline void solve(){
    int n = 0, ans = 1; cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        ans = (ans * ((a[i] * a[i]) % MOD)) % MOD; // self
    }
    sort(a + 1, a + 1 + n);
    int cnt = 1, sum = 1;
    for(int i = 2; i <= n; i++){
        sum = sum * sum % MOD * a[i - 1] % MOD;
        (ans *= sum * binpow(a[i], cnt, MOD) % MOD) %= MOD;
        cnt = (cnt * 2 + 1) % (MOD - 1);
    }
    cout << ans << endl;
}

signed main(){
    solve();
    return 0;
}

H.真真真真真签到题

思路

体对角线$x$与体积关系V为：
$$V=\frac{x^3}{3\sqrt{3}}$$
Win+R+clac得$\sqrt{3}=1.7320508075689$，直接计算输出即可。

Accepted Code

#include <bits/stdc++.h>
//#define int long long
using namespace std;

const double d = 1.7320508075689;

inline void solve(){
   double x; cin >> x; x *= 2;
   cout << (x * x * x) / (3 * d) << endl;
}

signed main(){
   solve();
   return 0;
}

I.爆炸的符卡洋洋洒洒

思路

0-1背包变式，本来要维护前$i$个物品重量为$j$的最大值，现在变成了 前$i$个物品模 $k$为 $j$的最大值。

Accepted Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e3 + 10;
int a[N], b[N];
int dp[N], pre[N];

inline void solve(){
    int n, k, maxx; cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
        a[i] %= k;
    } 
    for(int i = 1; i <= n; i++){
        //for(int i = 0; i <= k; i++) 
        for(int j = 0; j <= k; j++){
            pre[i] = dp[i];
            if(!j || pre[j]) dp[(j + a[i]) % k] = max(dp[(j + a[i]) % k], pre[j] + b[i]);
        }
    }
    int ans = max(dp[0], dp[k]);
    if(ans > 0) cout << ans << endl;
    else cout << -1 << endl;
}

signed main(){
    solve();
    return 0;
}

J.区间合数的最小公倍数

思路

区间所有合数的最小公倍数就是所有合数分解质因子后每个质因子的最大幂次积。

所以直接分解质因数即可

Accepted Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

string s;

const int MOD = 1e9 + 7, N = 1e5 + 10;

inline int bin(int x, int n, int MOD, int ret = 1) {
    for (x %= MOD; n; n >>= 1, x = x * x % MOD) if (n & 1) ret = ret * x % MOD;
    return ret == 1 ? 0 : ret;
}

int tag[N], mp[N];

inline void init(){
    tag[1] = 1;
    for(int i = 1; i <= 30000; i++){
        if(!tag[i]) for(int j = i * i; j <= 30000; j += i) tag[j] = 1;
    }
}

inline void solve(){
    int l, r, ans = 1; cin >> l >> r;
    init();
    bool flag = false;
    for(int i = l; i <= r; i++){
        if(tag[i]){
            flag = true;
            for(int j = i, k = 2; j > 1; k++){
                int cnt = 0;
                while(j % k == 0) j /= k, cnt++;
                mp[k] = max(mp[k], cnt);
            }
        }
    }
    if(!flag) cout << "-1" << endl;
    else{
        for(int i = 2; i <= 30000; i++)
        if(!tag[i] && mp[i]) ans = (ans * bin(i, mp[i], MOD)) % MOD;
        cout << ans << endl;
    }
}

signed main(){
    solve();
    return 0;
}

K.小红的真真假假签到题题

思路

可以直接将二进制表示重复杂写两次，这样一定满足题意。

Accepted Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

inline void solve(){
    int x; cin >> x;
	int t, tmp = x;
	while(tmp) t += 1, tmp >>= 1;
	cout << (x << t) + x << endl;
}

signed main(){
    solve();
    return 0;
}