2022牛客寒假算法基础集训营4 「ABCDEFGHIJK」
admin
|
|
412
|
个人训练赛

2524 字
|
40 分钟

2022牛客寒假算法基础集训营4

A-R

题目描述：

小红拿到了一个长度为 n 的字符串，该字符串仅由大写字母组成。

小红很喜欢红色（用'R'字母表示），但她非常讨厌紫色（用'P'字母表示）。
她想取一个连续子串，该子串包含至少 k 个'R'字符，且不能包含'P'字符。
你能告诉她有多少合法的方案可以取到吗？

思路：

枚举左端点l，通过两个限制条件去确定r的最小值和最大值，方法是用两个前缀和进行预处理，然后用二分去查找边界，做差后就可得出l做左端点的子串的数量，然后累加起来即可

看起来很浅显，但是有些细节得注意

  • 找r的最小值时应该去二分的是rr[i - 1]+k,而不是rr[i]+k
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int pr[MAX];
int rr[MAX];
char tr[MAX];

void work(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
        if(tr[i] == 'P')pr[i]++;
        if(tr[i] == 'R')rr[i]++;
        pr[i] += pr[i - 1];
        rr[i] += rr[i - 1];
    }
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        if(tr[i] == 'P')continue;
        ll l = lower_bound(rr + i, rr + n + 1, rr[i - 1] + k) - rr;
        ll r = lower_bound(pr + i, pr + n + 1, pr[i] + 1) - pr;
        ans += max(0ll, r - l);
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

B-进制

题目描述：

长度为n的字符串，仅由0-9的字符组成，q次询问，包含两种操作

  • 1 x y 表示将第x位的字符改成y
  • 2 x y 输出第x位到第y位能表示的某进制的最小值，这个进制必须是2进制到10进制，且必须合法，对1e9+7取模

思路：

现讲一个非常简单点：将1234和5678拼接起来，得到12345678，这个数字其实是 得到的， 是因为后面的数有4位

这就是这个题最重要的思路

再说最小值，我们只需要找到[l, r]中最大的数 + 1，把他作为进制数去计算即可，有个坑点是，如果最大的数是0，那进制应该设成2进制，因为题目要求的进制必须是2到10进制

所以我们可以使用线段树来处理，维护一个最大值，再对2到10进制的每个进制维护一个val值

维护最大值很简单，就纯板子

而在计算val的时候，大致上分三种

  • mid >= t, 此时[s, t]全在左子树上，所以等于

  • mid < s 此时[s, t]全在右子树，所以等于 ，这里你可能会疑问为什么没有等号，其实是因为右子树的区间是[mid + 1, r]，也就是 mid + 1 <= s，移向后就是 mid < s

  • mid >=s && mid < t，此时，这里根据右子树的大小又分两种情况

    • r <= t,也就是目前区间能处理得到的右界是r，但是目标右界是t，r在t的左边，这里右子树的右界就是 r
    • r > t ,r在t的右边，我们只需要获得到t的值即可，所以右子树的右界大小就是t

    综上所述，右子树的右界是min(t, r),则右子树的大小是mid(t, r) - (mid + 1) + 1 也就是mid(t, r) - mid

所以总的思路就是，建树，维护一个maxn，和一个val，对于操作1，我们更新两个的值，对于操作2，我们先查询最大值，另ma = 最大值 + 1，如果ma == 1，则++ma，然后将ma作为进制去计算val即可

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ls p<<1
#define rs p<<1|1

typedef long long ll;

#define MAX 400000 + 50
int n, m;
int op, l, r;
char tr[MAX];

int maxn[MAX];
ll val[MAX][12];

ll q_pow(ll a, ll b){
    ll ans = 1;
    while (b) {
        if(b & 1)ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

inline void pushup(int p, ll len){
    maxn[p] = max(maxn[ls], maxn[rs]);
    for(ll c = 2; c <= 10; ++c)val[p][c] = ((val[ls][c] * q_pow(c, len)) % mod + val[rs][c]) % mod;
}

inline void built(int p, int l, int r){
    if(l == r){
        maxn[p] = tr[l] - '0';
        for(int c = 2; c <= 10; ++c)val[p][c] = tr[l] - '0';
        return;
    }
    int mid = (l + r) / 2;
    built(ls, l, mid);
    built(rs, mid + 1, r);
    pushup(p, r - mid);
}

inline void update(int p, int l, int r, int id, int x){
    if(l == r && l == id){
        maxn[p] = x;
        for(int c = 2; c <= 10; ++c)val[p][c] = x;
        return;
    }
    int mid = (l + r) / 2;
    if(mid >= id)update(ls, l, mid, id, x);
    else update(rs, mid + 1, r, id, x);
    pushup(p, r - mid);
}

inline int getmaxn(int p, int l, int r, int s, int t){
    if(l >= s && t >= r){
        return maxn[p];
    }
    int mid = (l + r) / 2;
    int ma = 0;
    if(mid >= s)ma = max(ma, getmaxn(ls, l, mid, s, t));
    if(mid < t)ma = max(ma, getmaxn(rs, mid + 1, r, s, t));
    return ma;
}

inline ll getans(int p, int l, int r, int s, int t, int c){
    if(l >= s && t >= r){
        return val[p][c];
    }
    int mid = (l + r) / 2;
    if(mid >= t)return getans(ls, l, mid, s, t, c);
    else if(mid < s)return getans(rs, mid + 1, r, s, t, c);
    else{
        ll len = min(r, t) - mid;
        return ((getans(ls, l, mid, s, t, c) * q_pow(c, len)) % mod + getans(rs, mid + 1, r, s, t, c)) % mod;
    }
}

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    built(1, 1, n);
    while (m--) {
        cin >> op >> l >> r;
        if(op == 1){
            update(1, 1, n, l, r);
        }
        else {
            int c = getmaxn(1, 1, n, l, r) + 1;
            if(c == 1)++c;
            cout << getans(1, 1, n, l, r, c) << endl;
        }
    }
}


int main(){
    
    work();
    return 0;
}

C-蓝彗星

题目描述：

有n个彗星，每个彗星都可以持续发亮t秒

输入一个仅有B和R的字符串s，s[i]='B'表示第i个是蓝彗星，s[i] = 'R'表示第i个是红彗星，问有多少秒仅能看见蓝彗星，看不到红彗星

思路：

差分前缀和

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, x;
int br[MAX];
int rr[MAX];
char tr[MAX];
void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    for(int i = 1; i <= n; ++i){
        cin >> x;
        if(tr[i] == 'B'){
            ++br[x];
            --br[x + m];
        }
        else{
            ++rr[x];
            --rr[x + m];
        }
    }
    for(int x = 1; x <= 200050; ++x){
        br[x] += br[x - 1];
        rr[x] += rr[x - 1];
    }
    int ans = 0;
    for(int i = 1; i <= 200050; ++i){
        if(br[i] && !rr[i])++ans;
    }
    cout << ans << endl;
}

int main(){
    io;
    work();
    return 0;
}

D-雪色光晕

题目描述：

image-20230309111518178

思路：

求点到线段的最小值

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define y0 y114514
#define eps 1e-7
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
double x0, y0, x, y;
double xx, yy;

struct Point{
    double x, y;
};

float pointToLine(Point s, Point e, Point p) {
    float ux = e.x - s.x;
    float uy = e.y - s.y;
    float vx = p.x - s.x;
    float vy = p.y - s.y;
    float wx = p.x - e.x;
    float wy = p.y - e.y;
    float umv = ux * vx + uy * vy;
    float umw = ux * wx + uy * wy;
    if (umv * umw > 0) {
        // 点的垂足不在线段上
        if (umv > 0) {
            // 垂足在终点一侧
            return sqrt(wx * wx + wy * wy);
        } else {
            // 垂足在起点一侧
            return sqrt(vx * vx + vy * vy);
        }
    } else {
        // 点的垂足在线段上
        return abs(ux * vy - uy * vx) / sqrt(ux * ux + uy * uy);
    }
}



void work(){
    cin >> n;
    cin >> x0 >> y0 >> x >> y;
    double ans = inf;
    Point q, z, pp;
    q.x = x0;q.y = y0;
    pp.x = x;pp.y = y;
    for(int i = 1; i <= n; ++i){
        cin >> xx >> yy;
        z.x = xx + q.x;
        z.y = yy + q.y;
        double cnt = pointToLine(z, q, pp);
        if(ans - cnt > eps)ans = cnt;
        q.x = z.x;
        q.y = z.y;
    }
    printf("%.8lf", ans);
}


int main(){
    io;
    work();
    return 0;
}

 

E-真假签到题

题目描述：

long long f(long long x){
 if(x==1)return 1;
 return f(x/2)+f(x/2+x%2);
}

输入x，输出f(x)

思路：

显然f(x) = x，输出即可

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
ll x;

void work(){
    cin >> x;
    cout << x << endl;
}

int main(){
    io;
    work();
    return 0;
}

F-小红的记谱法

题目描述：

给出两种乐谱表示方法，给出其中一种，让你用另一种来表示

具体题意不赘述

思路：

小模拟，可以使用一个cnt来计数也可以用一个前缀和来记录低高音

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
string s, t;
int br[MAX];
map<char, char>mp;

void work(){
    mp['C'] = '1';
    mp['D'] = '2';
    mp['E'] = '3';
    mp['F'] = '4';
    mp['G'] = '5';
    mp['A'] = '6';
    mp['B'] = '7';
    cin >> s;
    n = (int)s.size();
    s = " " + s;
    for(int i = 1; i <= n; ++i){
        br[i] += br[i - 1];
        if(s[i] == '<')--br[i];
        else if(s[i] == '>')++br[i];
        else{
            t += mp[s[i]];
            if(br[i] > 0){
                int num = br[i];
                while (num--) {
                    t += '*';
                }
            }
            else if(br[i] < 0){
                int num = -br[i];
                while (num--) {
                    t += '.';
                }
            }
        }
        
    }
    cout << t << endl;
}


int main(){
    work();
    return 0;
}

G-子序列权值乘积

题目描述：

定义一个数组的权值为该数组的最大值乘以最小值

给一个数组，问数组的所有非空子序列的权值的乘积是多少，模1e9+7

思路：

手模分析一下即可发现可以从二进制的角度入手，先从大到小排个序，设第i个数是x，若它作为一个字序列的最大值，那1到i-1的位置都不可以选，后面的n-i个数随意，也就是有 个机会作为最大值，同样的，有 个机会作为最小值，那这个数x产生的贡献就是 ,再用一次欧拉降幂即可

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
ll tr[MAX];

ll q_pow(ll a, ll b, ll Mod){
    ll ans = 1;
    while(b > 0){
        if(b & 1)ans = ans * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return ans;
}

ll uller(ll a, ll b, ll c){
    ll d = q_pow(b, c, mod - 1) + mod - 1;
    ll cnt = q_pow(a, d, mod);
    return cnt;
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
    }
    sort(tr + 1, tr + 1 + n, greater<ll>());
    ll ans = 1;
    for(ll i = 1; i <= n; ++i){
        ans = (ans * uller(tr[i], 2, n - i)) % mod;
        ans = (ans * uller(tr[i], 2, i - 1)) % mod;
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

H-真真真真真签到题

题目描述：

小红和紫被困在一个正方体的内部。紫先选择了一个位置，然后小红选择一个位置。紫希望离小红尽可能近，小红希望离紫尽可能远。两人都会选择最优策略。
已知她们最终的距离为 x 。小红想知道正方体的体积是多少？

思路：

显然，小紫会选择正方体的中心，因为如果小紫不选中心，那小就可以选择离小紫最远的一个顶点，这样的二者的距离一点会大于中心到顶点的距离，所以小紫在中心，小红在顶点

所以推个公式就行了

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
double x;

void work(){
    cin >> x;
    x *= 2;
    x /= sqrt(3);
    x = x * x * x;
    printf("%.6lf\n",x);
}


int main(){
    io;
    work();
    return 0;
}

I-爆炸的符卡洋洋洒洒

题目描述：

n种卡片，每个卡片会消耗ai的魔力，威力为bi,选择若干张卡片，使得消耗的魔法的总和是k的倍数，求能造成的最大的威力

思路：

背包问题

dp[i][j] 表示前 i 个卡片消耗的总魔法%k=j时能产生的最大威力

注意初始化，dp[0][0] = 0，其他的都赋-inf

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
ll ar[1005];
ll br[1005];
ll dp[1005][1005];

void work(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        cin >> ar[i] >> br[i];
        ar[i] %= k;
    }
    memset(dp, -inf, sizeof(dp));
    dp[0][0] = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j <= k - 1; ++j){
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - ar[i] + k) % k] + br[i]);
        }
    }

    if(dp[n][0] == 0)cout << -1 << endl;
    else cout << dp[n][0] << endl;
    
}


int main(){
    io;
    work();
    return 0;
}

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

题目描述：

问[l, r]中所有合数的最小公倍数，模1e9+7

思路：

范围很小，所以可以先用欧拉筛，筛出区间内所有合数，然后挨个质因数分解，找出每个因子的最大幂次，最后计算答案就行，负责度是，题解的做法我看不明白，但他的复杂度是 

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
int l, r;
int tr[MAX];


int tot;
bool vis[30050];
int prime[30050];//1e8有不到6e6的素数
map<int, int>mp;
void euler_sieve(int n){
    for(int i = 2; i <= n; ++i){
        if(!vis[i])prime[++tot] = i;
        for(int j = 1; i * prime[j] <= n && j <= tot; ++j){
            vis[prime[j] * i] = 1;
            if(i % prime[j] == 0)break;
        }
    }
}

void divid(int p){
    for(int i = 2; i <= p / i; ++i){
        if(p % i == 0){
            int num = 0;
            while (p % i == 0) {
                ++num;
                p /= i;
            }
            mp[i] = max(mp[i], num);
        }
    }
    if(p > 1)mp[p] = max(mp[p], 1);
}


ll q_pow(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

void work(){
    euler_sieve(30005);
    cin >> l >> r;
    bool p = 0;
    for(int i = l; i <= r; ++i){
        if(vis[i]){
            p = 1;
            divid(i);
        }
    }
    if(!p)cout << -1 << endl;
    else{
        ll ans = 1;
        for(auto [a, b] : mp){
            ans *= q_pow(a, b);
            ans %= mod;
        }
        cout << ans << endl;
    }
}


int main(){
    io;
    work();
    return 0;
}

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

题目描述：

image-20230309111537935

思路：

将x的所有二进制位重复一遍即可，方法是先算出x有多少二进制位，然后 就是一种答案

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
int tr[MAX];
ll x;
ll getnum(ll x){
    int num = 0;
    while (x) {
        x /= 2;
        num ++;
    }
    return num;
}
void work(){
    cin >> x;
    cout << (x << getnum(x)) + x << endl;
}


int main(){
    io;
    work();
    return 0;
}

 

博客内容均系原创，未经允许严禁转载！
牛客
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
牛客小白月赛39「A」「B」「C」「D」「E」「G」「H」

							
							

							
牛客小白月赛40

							
							

							
牛客小白月赛44

							
							

							
牛客练习赛90