牛客练习11月上

大大源码 • 2023年4月30日 am12:10 • 其他

文章目录

一、牛客练习赛84

牛客推荐系统开发之选飞行棋子

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

char s[5][5050];
ll sum[5];

int main()
{
    int n;
    scanf("%d",&n);
    
    for(int i=1;i<=4;i++){
        scanf("%s",s[i]+1);
    }
    
    for(int i=1;i<=4;i++){
        for(int j=1;j<=n;j++){
            sum[i] += (s[i][j] - '0');
        }
    }
    
    ll cnt = 0;
    for(int i=1;i<=n;i++)    if(s[3][i]=='1' && s[4][i]=='1')    cnt++;
    
//     for(int i=1;i<=4;i++)    cout << sum[i] << " ";
    ll res = 0;
    for(int i=1;i<=n;i++){
        if(s[1][i]=='1'){
            for(int j=1;j<=n;j++){
                if(i!=j && s[2][j]=='1'){
                    ll t1 = sum[3] - (s[3][i]=='1') - (s[3][j]=='1');
                    ll t2 = sum[4] - (s[4][i]=='1') - (s[4][j]=='1');
                    
                    ll cntt = cnt - (s[3][i]=='1'&&s[4][i]=='1') - (s[3][j]=='1'&&s[4][j]=='1');
                    res += (t1 * t2) - cntt;
                }
            }
        }
    }
//     cout << res << endl;
    printf("%lld\n",res);
    
    
    return 0;
}

牛客推荐系统开发之女装药水

// 枚举第一行的状态16种   16*4096 = 65534
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

char c[6][6];
int backup[6][6];

void trans(int i,int j){
    backup[i][j] ^= 1;
    backup[i+1][j] ^= 1;
    backup[i-1][j] ^= 1;
    backup[i][j-1] ^= 1;
    backup[i][j+1] ^= 1;
}

int main()
{
    for(int i=1;i<=4;i++)
        scanf("%s",c[i]+1);
    
    bool flag = 0;
    for(int i=0;i<(1<<4);i++){
        for(int j=1;j<=4;j++){
            for(int k=1;k<=4;k++){
                backup[j][k] = (c[j][k] - '0');
            }
        }
        
        int t = i;
        if(t&1)    trans(1,1);
        if((t<<1) & 1)    trans(1,2);
        if((t<<2) & 1)    trans(1,3);
        if((t<<3) & 1)    trans(1,4);
        
        for(int j=2;j<=4;j++){  //trans(j,k)
            for(int k=1;k<=4;k++){
                if(backup[j-1][k]==1){
                    trans(j,k);
                }
            }
        }
        
        bool f = 0;
        for(int j=1;j<=4;j++){
            if(f)    break;
            for(int k=1;k<=4;k++){
                if(backup[j][k]==1){
                    f = 1;
                    break;
                }
            }
        }
        
        if(!f){
            flag = 1;
            break;
        }
    }
    
    if(flag)    puts("YES");
    else    puts("NO");
    
    return 0;
}

牛客推荐系统开发之静态特征获取

#include <iostream>
#include <map>

using namespace std;

// map<pair<string,string>,int> mp;
map<string,map<string,int> > mp;

int main()
{
    int n;
    cin >> n;
    string s1,s2;
    while(n--){
        cin >> s1 >> s2;
        
        if(mp[s1][s2]){
            cout << "NO" << endl;
        }else{
            mp[s1][s2] = 1;
            cout << "YES" << endl;
        }
    }
    
    return 0;
}

二、牛客练习赛85

科学家的模型

#include <iostream>
#include <cstdio>

using namespace std;

int a[6][6];
char b[6][6];

int main()
{
    for(int i=1;i<=5;i++)
            scanf("%s",&b[i]);
    
    for(int i=1;i<=5;i++){
        for(int j=0;j<5;j++)
            a[i][j+1] = (b[i][j]-'0');
    }
    
    int ans;
    
    for(int i=2;i<=5;i++){
        for(int j=1;j<=5;j++){
//             cout << "a[j][i] = " << a[j][i] << " ";
            a[i][j] = a[i][j]+a[i-1][j];
        }
//         cout << endl;    
    }
    
    for(int i=1;i<=5;i++){
        if(a[5][i]>1){
            if(a[5][i+1]>2){
                for(int j=5;j>=1;j--){
                    if(a[5][j]>1){
                        if(a[5][j]>a[5][i]){
                            ans = 9;
                            break;
                        }else{
                            ans = 8;
                            break;
                        }
                    }
                }
                break;
            }else{
                ans = 0;
                break;
            }
        }
    }
    printf("%d\n",ans);
    
    return 0;
}

音乐家的曲调

// 双指针：尺取法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10000010;

int n,m;
string s;
int book[30];
int lf[N],rg[N];

// ans = left[l-1]+(r-l+1)+right[r+1];

int main()
{
    scanf("%d%d",&n,&m);
    cin >> s;
    s = " " + s;
    
    int ma = -1;
    memset(book,0,sizeof book);
    int p = 1,q = 1;
    for(int i=1;i<=n;i++){  //[1~i]上的最大值.
        ma = -1;
        for(;q<=i;q++){
            book[s[q] - 'a']++;
            while(p<=q && book[s[q]-'a']>m){
                book[s[p++]-'a']--;
            }
            ma = max(ma,q-p+1);
        }
        lf[i] = max(lf[i-1],ma);
    }
    
    memset(book,0,sizeof book);
    p = n,q = n;
    for(int i=n;i>=1;i--){  //[i~n]上的最大值.
        ma = -1;
        for(;q>=i;q--){
            book[s[q] - 'a']++;
            while(p>=q && book[s[q] - 'a']>m){
                book[s[p--]-'a']--;
            }
            ma = max(ma,p-q+1);
        }
        rg[i] = max(rg[i+1],ma);
    }
    
    memset(book,0,sizeof book);
    int res = -1;
    p = 1,q = 1;
    for(;q<=n;q++){
        book[s[q] - 'a']++;
        while(p<=q && book[s[q] - 'a']>m){
            book[s[p++]-'a']--;
        }
        res = max(res,q-p+1+lf[p-1]+rg[q+1]);
    }
    cout << res << endl;
    
    return 0;
}

哲学家的沉思

// 10 9 8 7 9 7 9
//以l开头的,在[l,r]范围内的严格上升(可不连续)子序列的长度

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

ll a[1000010];
ll f[1000010][22];
ll stack[1000010];

int main()
{
    ll n,q;
    scanf("%lld%lld",&n,&q);
    
    for(int i=1;i<=n;i++)    scanf("%lld",&a[i]);
    
    int top = -1;
    for(int i=1;i<=n;i++){                //计算f[i][0]
        while(top!=-1 && a[stack[top]]<a[i]){
            f[stack[top--]][0] = i;
        }
        stack[++top] = i;
    }
    
    while(top!=-1){
        f[stack[top--]][0] = n+1;
    }
    
    //f[i][j] = f[ f[i][j-1] ][j-1];
    for(int i = 0 ; i <= 20 ; i++)//求f
        f[n + 1][i] = n + 1;
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            f[i][j] = f[ f[i][j-1] ][j-1];
        }
    }
    
    while(q--){
        ll l,r;
        scanf("%lld%lld",&l,&r);
        
        ll ans = 1;
        for(int i = 20 ; i >= 0 ; i--) {
            if(f[l][i] <= r) {
                l = f[l][i];
                ans += (1ll << i);
            }
        }
        
        printf("%lld\n",ans);
    }
    
    return 0;
}

数学家的迷题

// 单点修改，查询区间质因子的个数.
// 势能线段树.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <vector>

using namespace std;

#define int long long

const int N = 100005;
const int maxn = 5e4 + 5;

int v[N],prime[N];
int m;
void primes(){
    m = 0;
    for(int i=2;i<N;i++){
        if(!v[i]){
            v[i] = i;
            prime[++m] = i;
        }
        for(int j=1;j<=m;j++){
            if(prime[j]>v[i] || prime[j]>N/i)    break;
            v[i*prime[j]] = prime[j];
        }
    }
}
 
bitset<10005> calc(int x){
    bitset<10005> t;
    t.reset();
    for(int i=1;i<=m;i++){
        if(prime[i] * prime[i] > x || x==1)    break;
         
        if(x%prime[i]==0)    t.set(i);
        while(x%prime[i]==0)    x /= prime[i];
    }
     
    if(x != 1)    t.set(lower_bound(prime+1,prime+1+m,x)-prime); //这块错了？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？我日离大谱
    return t;
}

int n,c;
int a[maxn];
struct Tree{
    int l,r;
    bitset<10005> val;
}tr[maxn*4];

void pushup(int u){
    tr[u].val = (tr[u<<1].val | tr[u<<1|1].val);
}

void build(int u,int l,int r){
    tr[u] = {l,r};
    if(l==r){
        tr[u].val = calc(a[l]);
        return;
    }
    
    int mid = (l + r) >> 1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    
    pushup(u);
}

void modify(int u,int x,bitset<10005> v){
    if(tr[u].l==x && tr[u].r==x){
        tr[u].val = v;
        return;
    }
    
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(x<=mid)    modify(u<<1,x,v);
    else    modify(u<<1|1,x,v);
    
    pushup(u);
}

bitset<10005> query(int u,int l,int r){
    if(tr[u].l>=l && tr[u].r<=r){
        return tr[u].val;
    }
    
    bitset<10005> tmp;
    tmp.reset();
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l<=mid)    tmp |= query(u<<1,l,r);
    if(r>mid)    tmp |= query(u<<1|1,l,r);
    
    return tmp;
}

signed main()
{
    primes();
    scanf("%lld%lld",&n,&c);
    for(int i=1;i<=n;i++)    scanf("%lld",&a[i]);
    build(1,1,n);
    
    while(c--){
        int op,x,y;
        scanf("%lld%lld%lld",&op,&x,&y);
        
        if(op==1){
            bitset<10005> bs = calc(y);
            modify(1, x, bs);
        }else{
            int ans = query(1,x,y).count();
            printf("%lld\n",ans);
        }
    }
    
    
    return 0;
}

三、牛客练习赛88

寻寻觅觅寻不到

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

void solve(){
    string s1,s2;
    int k;
        
    cin >> s1 >> s2 >> k;
    int pos = -1;
    
    int len1 = s1.size();
    int len2 = s2.size();
    
    if(len1 != len2){
        puts("NO");
        return;
    }
    
    bool f = 0;
    int i = 0,j = 0;
    for(;j<len2 && i<len1;j++,i++){
        if(s1[i]!=s2[j]){
            pos = i;
            i += k;
            
            if(i>=len1)    break;
        }
        
        if(s1[i]!=s2[j]){
            f = 1;
            break;
        }
    }
    if(i<len1 || j==len2){
        if(pos!=-1){
            for(int p = pos;p < pos+k; p++){
                if(s1[p]==s2[j]){
                    j++;
                }
            }
        }
        
        if(f || j!=len1)    puts("NO");
        else    puts("YES");
    }else if(i>=len1){
         bool ff = 0;
         for(int p = 0;p < len1 - k;p++){
             int w = 0,q = 0;
             
             for(;w<len1 && q<len2;w++,q++){
                 if(w==p)    w += k;
                 
                 if(s1[w]!=s2[q]){
                     break;
                 }
             }
             
             for(w = p;w < p + k;w ++,q++){
                 if(s1[w]!=s2[q]){
                     break;
                 }
             }
             
             if(q==len2){
                 ff = 1;
                 break;
             }
         }
        
        if(!ff)    puts("NO");
        else    puts("YES");
    }
    
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
    
    return 0;
}

// aaabaaabaaa aaaaaaaaabb 1
// aaabaaabaaa aaaabaaabaa 10

踩不出足迹

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef unsigned long long ll;

ll mul(ll a,ll b) 
{
    ll res=1;
    while (b)
    {
        if (b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}

int main()
{
    ll n,k;
//     scanf("%lld%lld",&n,&k);
    cin >> n >> k;
    
    ll a;
    ll res = 0;
    for(int i=1;i<=n;i++){
//         scanf("%lld",&a);
        cin >> a;
        
        res ^= a;
    }
    
    ll ans = res ^ (mul(2,k) - 1);
//     ll ans = res ^ ((1ll<<k) - 1ll);
    
//     printf("%lld\n",max(ans,res));
    ans = max(ans,res);
    
    cout << ans << endl;
    
    return 0;
}

四、牛客练习赛90

妄想集合

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

typedef long long ll;

const int N=1e5+10;

struct node {
	int l,r,sum;//线段树中维护集合的size
} tr[4*N];
vector<int> v[N];//存放每个集合里面的元素
int n,m;

void pushup(int u) {
	tr[u].sum=tr[2*u+1].sum+tr[2*u].sum;
}

void build(int u,int l,int r) {
	tr[u]= {l,r};
	if(l==r) {
		tr[u].sum=1;
		return;
	}
	int mid=l+r>>1;
	build(2*u,l,mid);
	build(2*u+1,mid+1,r);
	pushup(u);
}

int query(int u,int l,int r) { //区间求和
	if(l<=tr[u].l&&r>=tr[u].r) return tr[u].sum;
	int mid=tr[u].l+tr[u].r>>1;
	int sum=0;
	if(l<=mid) sum+=query(2*u,l,r);
	if(r>mid) sum+=query(2*u+1,l,r);
	return sum;
}

void modify(int u,int l,int r,int x) { //区间内的单点修改
	if(tr[u].sum/(tr[u].r-tr[u].l+1)>=46) return;
	if(tr[u].l==tr[u].r) {
		v[r].push_back(x);
		tr[u].sum++;
		return ;
	}
	int mid=tr[u].l+tr[u].r>>1;
	if(r<=mid) modify(2*u,l,r,x);
	else if(l>mid) modify(2*u+1,l,r,x);
	else {
		modify(2*u,l,mid,x);
		modify(2*u+1,mid+1,r,x);
	}
	pushup(u);
}

int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		int t;
		scanf("%d",&t);
		v[i].push_back(t);
	}
	build(1,1,n);
	for(int T=0; T<m; T++) {
		string op;
		int l,r,x;
		cin>>op;
		scanf("%d %d",&l,&r);
		if(op[0]=='A') { //询问
			int sum=query(1,l,r);
			if(sum>=46) {
				puts("YES");
				continue;
			} else if(sum<=2) {
				puts("NO");
				continue;
			} else {
				vector<int> tmp;
				for(int i=l; i<=r; i++) {
					for(auto t:v[i])
						tmp.push_back(t);
				}
				bool flag=false;
				sort(tmp.begin(),tmp.end());
				for(int i=0; i<tmp.size()-2; i++) {
					if(tmp[i]+tmp[i+1]>tmp[i+2]) {
						flag=true;
						break;
					}
				}
				if(flag)puts("YES");
				else puts("NO");
			}
		} else {
			scanf("%d",&x);
			modify(1,l,r,x);
		}
	}
}

五、牛客练习赛91

魔法学院（eazy and hard version）

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

#define int long long

const int N = 1000010;

int n,m;

struct Node{
    int l,r;
    char val;
    
    bool operator <(const Node &w) const
    {
        return val<w.val;
    }
}p[N];

bool cmp(Node a,Node b){
    return a.l < b.l;
}

signed main()
{
    scanf("%lld%lld",&n,&m);
    string s;
    cin >> s;
    s = " " + s;
    int l,r;
    char c;
    
    for(int i=1;i<=m;i++){
        scanf("%lld %lld %c",&l,&r,&c);
        p[i] = {l,r,c};
//         cout << p[i].l << " " << p[i].r << " " << p[i].val << endl;
    }
    sort(p+1,p+1+m,cmp);
    
//     for(int i=1;i<=m;i++){
//         cout << p[i].l << " " << p[i].r << " " << p[i].val << endl;
//     }
    
    int j = 1;
    int sum = 0;
    priority_queue<Node> pq;
    for(int i=1;i<=n;i++){
        while(!pq.empty() && pq.top().r<i){
                pq.pop();
        }
        
        while(p[j].l==i && j<=m){
            pq.push(p[j++]);
        }
        
        if(!pq.empty()){
            sum += max(s[i],pq.top().val);
        }else{
            sum += s[i];
        }
    }
    
//     cout << sum << endl;
    printf("%lld\n",sum);
    
    return 0;
}

监狱逃亡

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
// #include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1000010;
const int mod = 1e9 + 7;
int a[4][N],sum[4][N],tr[N];
vector<int> v;
int n,m;

int find(int x){
    return lower_bound(v.begin(), v.end(),x) - v.begin() + 1;
}

int lowbit(int x){
    return x&-x;
}

int ask(int x){
    int sum = 0;
    while(x){
        sum += tr[x];
        x -= lowbit(x);
    }
    return sum;
}

void update(int x,int val){
    while(x<=m){
        tr[x] += val;
        x += lowbit(x);
    }
}

signed main()
{
    scanf("%lld",&n);
    
    for(int i=1;i<=3;i++){
        for(int j=1;j<=n;j++){
            scanf("%lld",&a[i][j]);
            sum[i][j] = sum[i][j-1] + a[i][j];
        }
    }
    
    for(int i=1;i<=n;i++){
        v.push_back(sum[2][i-1]-sum[1][i]);
        v.push_back(sum[2][i]+sum[3][n]-sum[3][i-1]);
    }
    
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    m = v.size();
    
    int ans = 0;
    for(int i=n;i>=1;i--){
        update(find(sum[2][i]+sum[3][n]-sum[3][i-1]),1);
        
        int pos = find(sum[2][i-1]-sum[1][i]);
        ans += ask(m)-ask(pos-1);
        
        ans %= mod;
//         update(find(sum[2][i]+sum[3][n]-sum[3][i-1]),1);
// 		int x=find(sum[2][i-1]-sum[1][i]);
// 		ans+=ask(m)-ask(x-1);
// 		ans%=mod;
    }
    
    cout << ans << endl;
    
    return 0;
}

原文链接：https://blog.csdn.net/m0_50435987/article/details/121419403

THE END

date日期类型与String类型的相互转化

< <上一篇

linux从入门到,Linux从入门到入门到入门（一）

下一篇>>

大大搜源码

搜索内容

牛客练习11月上

文章目录

一、牛客练习赛84

二、牛客练习赛85

三、牛客练习赛88

四、牛客练习赛90

五、牛客练习赛91

牛客练习11月上

文章目录

一、 牛客练习赛84

二、 牛客练习赛85

三、 牛客练习赛88

四、 牛客练习赛90

五、 牛客练习赛91

一、牛客练习赛84

二、牛客练习赛85

三、牛客练习赛88

四、牛客练习赛90

五、牛客练习赛91