2022牛客寒假算法基础集训营（五）全部题解

发表于2022-04-10|更新于2023-07-13|ACM

|字数总计:1.8k|阅读时长:10分钟|阅读量:

A 疫苗小孩二分

题目链接

题意：

题解：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int pos[N];
signed main() {
    int n;
     cin>>n;
     string s;
     cin>>s;s='.'+s;
     int cnt=0;
     for(int i=1; i<=n; i++) {
        if(s[i]=='0') pos[++cnt]=i;
     }
     int k, w, q;
     cin>>k>>w>>q;
     int ans=0; 
     for(int i=1; i<=cnt; i++) { 
        int p1=lower_bound(pos+1, pos+1+cnt, pos[i]+k)-pos;
        int p11=lower_bound(pos+1, pos+1+cnt, pos[p1]+k)-pos;
        int p12=upper_bound(pos+1, pos+1+cnt, pos[p1]+k)-pos-1;

        int p2=upper_bound(pos+1, pos+1+cnt, pos[i]+k)-pos-1;
        int p21=lower_bound(pos+1, pos+1+cnt, pos[p2]+k)-pos;
        int p22=upper_bound(pos+1, pos+1+cnt, pos[p2]+k)-pos-1;

        p1=pos[p1];p2=pos[p2];p11=pos[p11];p12=pos[p12];p21=pos[p21];p22=pos[p22];
        int j=i;
        i=pos[i];
        if(i<p1&&p1<=n) {
            ans=max(ans, w-abs(k-(p1-i))*q);
            if(p1<p11&&p1<=n) ans=max(ans, w-abs(k-(p1-i))*q+w-abs(k-(p11-p1))*q);
            if(p1<p12&&p1<=n) ans=max(ans, w-abs(k-(p1-i))*q+w-abs(k-(p12-p1))*q);
        }
        if(i<p2&&p2<=n) {
            ans=max(ans, w-abs(k-(p2-i))*q);
            if(p2<p21&&p21<=n) ans=max(ans, w-abs(k-(p2-i))*q+w-abs(k-(p21-p2))*q);
            if(p2<p22&&p22<=n) ans=max(ans, w-abs(k-(p2-i))*q+w-abs(k-(p22-p2))*q);
        }
        i=j;
     }
     cout<<ans<<endl;
	return 0;
}

B 乒乓小孩构造【待补】

题目链接

题意：

题解：

```
# C	战棋小孩 二进制枚举+贪心
**[题目链接](https://ac.nowcoder.com/acm/contest/23480/C)**
##题意：

##题解： 
```c
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int pos[N];
struct node {
    int val, m;
}a[N];
int p[N];
int b[N];
signed main() {
    int n, k, s;
    cin>>n>>k>>s;
    int ans=0;
    for(int i=0; i<n; i++)  cin>>p[i];
    for(int i=0; i<n; i++) {
        int x,y,c,d;
        cin>>x>>y>>c>>d; 
        a[i].val=max(x, y);
        a[i].m=max(max(x, y), max(c, d));
    }
    for(int i=0; i<(1<<n); i++) { 
    	int cnt=0; 
        for(int j=0; j<n; j++) {
            if(i&(1<<j)) b[j]=a[j].m, cnt++; 
            else b[j]=a[j].val;
        }
        if(cnt>k) continue; 
        sort(b, b+n, greater<int>());
        int sum=s, maxx=0;
        for(int j=0; j<n; j++) {
            sum+=b[j];
            if(sum>=p[j]) maxx++;
        }
        ans=max(maxx, ans);
    }
    cout<<ans<<endl;
	return 0;
}

D 数位小孩 dfs

题目链接

题意：

题解：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int l, r;
bool vis[105];
int ans=0;
void dfs(int x, int sum, int f, int up) {
    if (sum<=up) {
        if(f)ans++;
    }else return;
    for (int i=0; i<=9; i++) {
        if(!vis[x+i]) continue;
        if (i==1)  dfs(i, sum*10+i, 1, up);
        else dfs(i, sum*10+i, f, up);
    }
}
signed main() {
    for(int i=2; i<=18; i++) {
        vis[i]=1;
        for(int j=2; j<i; j++) if(i%j==0) vis[i]=0; 
    }
    int l, r;
    cin>>l>>r;
    for(int i=1; i<=9; i++) dfs(i, i, i==1, r);
    r=ans, ans=0;
    for(int i=1; i<=9; i++) dfs(i, i, i==1, l-1);
    l=ans;
    cout<<r-l<<endl;
	return 0;
}

E 复苏小孩线段树【补】

题目链接

题意：

题解：

#include<bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
const int N=2e5+5;
const int M=998244353;
int n, m;
ll ksm(ll a,ll p){ll res=1; p%=(M-1);while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}
int sum[5][N*4];
int b[5][N];
int val[N];
const int dd = ksm(2, M-2);
void pushup1(int id, int jin) {
    sum[jin][id] = (sum[jin][id << 1]+sum[jin][id<<1|1]+M)%M;
}
void build1(int id, int l, int r, int jin) {
    if (l == r) {
        sum[jin][id] = b[jin][l]%M;
        return;
    }
    int mid = (l + r) >> 1;
    build1(id << 1, l, mid, jin);
    build1(id << 1 | 1, mid + 1, r, jin);
    pushup1(id, jin);
}
void update1(int id, int l, int r, int x, int v, int jin) {
    if (l == r) {
        sum[jin][id] += v;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        update1(id << 1, l, mid, x, v, jin);
    } else {
        update1(id << 1 | 1, mid + 1, r, x, v, jin);
    }
    pushup1(id, jin);
}
int query1(int id, int l, int r, int x, int y, int jin) {
    if(x<=l&&r<=y) {
        return sum[jin][id]%M;
    }
    int mid=(l+r)>>1;
    int ans=0;
    if(x<=mid) {
        ans=(ans%M+query1(id<<1, l, mid, x, y,jin)%M)%M;
    }
    if(y>mid) {
        ans=(ans%M+query1(id<<1|1, mid+1, r, x, y,jin)%M)%M;
    }
    ans%=M;
    return ans;
}
signed main() {
int n, q;
	cin>>n>>q;
	string s;
	cin>>s;
	val[n+1]=3;
	for (int i=n; i>=1; i--) {
		val[i]=val[i+1]*dd%M;
		b[s[i-1]-'0'][i]=val[i];
        update1(1,1,n, i, val[i], s[i-1]-'0');
	}
	while(q--) {
		int op, x, y;
		cin>>op>>x>>y;
		if (op==1) {
			update1(1,1,n, x, M-val[x], s[x-1]-'0');
			update1(1,1,n, x, val[x], y);
			s[x-1]=y+'0';
		}else {
			int ans1, ans2, ans3;
			ans1=ksm(dd, y-x+1)+((query1(1,1,n,x,y,1)+M)%M)*ksm(2, n-y);
			ans2=ksm(dd, y-x+1)+((query1(1,1,n,x,y,2)+M)%M)*ksm(2, n-y);
			ans3=ksm(dd, y-x+1)+((query1(1,1,n,x,y,3)+M)%M)*ksm(2, n-y);
			cout<<ans1%M<<' '<< ans2%M<<' '<< ans3%M<<endl;
		}
	}
    return 0;
}

F 飞车小孩数学【待补】

题目链接

题意：

题解：

G 163小孩暴力

题目链接

题意：

题解：

打表代码

int ans = 0;
int a[100];
int flag[100];
void dfs(int x,int f) {
    if(f==6) {
        ans++;
        return;
    }
    for(int i=x; i<=13; i++) {      
        if(flag[i]>=4)continue;
        a[f+1]=i;
        flag[i]++;
        dfs(i, f+1);
        flag[i]--;
    }
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    cout<<18395<<endl;
    return 0;
}

H 一六三小孩？【待补】

题目链接

题意：

题解：

```
# I	兔崽小孩 前缀和二分
**[题目链接](https://ac.nowcoder.com/acm/contest/23480/I)**

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,q;
int b[N], sum[N],t[N];
inline int read() {
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    } while('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    } return x * f;
}
signed main() { 
    n=read();q=read();
    for(int i=1; i<=n; i++) {
        t[i]=read();
    }
    for(int i=2; i<=n; i++) {
        b[i-1]=t[i]-t[i-1];
    }
    sort(b+1, b+n);
    for(int i=1; i<n; i++) {
        sum[i]=sum[i-1]+b[i];
    }
    while(q--) {
        int x, y;
        x=read();y=read();
        int p=lower_bound(b+1, b+n, x)-b;
        //cout<<sum[n-1]-sum[p-1]-x*(n-1-p+1)<<endl;
        if(sum[n-1]-sum[p-1]-x*(n-1-p+1)>=y) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

J 三国小孩签到

题目链接

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    int n, m, k;
    cin>>n>>m>>k;
    if(n+m>k) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

K 造梦小孩分块【待补】

题目链接

总结

Qwq

文章作者: 王千予

文章链接: http://wangqianyu6.github.io/posts/fbff4d2a.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自望千鱼`Blog！

相关推荐

2022牛客寒假算法基础集训营（一）全部题解

2022牛客寒假算法基础集训营（三）全部题解

2022牛客寒假算法基础集训营（六）全部题解

2022牛客寒假算法基础集训营（四）全部题解

评论

✨ 有新文章啦！ 👉🍗点击食用🍔

数据库加载中