牛客小白月赛15

Problem A 斑羚飞渡

https://ac.nowcoder.com/acm/contest/917/A

题意：

题解：

C++版本一

Problem B 诡异的因数

https://ac.nowcoder.com/acm/contest/917/B

题意：求因子个数

题解：暴力试除法，强力试除即可。

C++版本一

题解：暴力

#include<stdio.h>
int a[10005];
int main(){
    int t,k;
    scanf("%d",&t);
    for(int i = 1 ; i <= 10000 ; i ++ )
        for(int j = 1 ; i*j <= 10000 ; j ++ )
            a[i*j]++;
    while(t--){
        scanf("%d",&k);
        printf("%d\n",a[k]);
    }
    return 0;
}

C++版本二

题解：筛法

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int D[M];
int pre[M];
bool prime[M];
int num[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    D[1]=1;
    prime[0]=prime[1]=1;
    for(int i=2;i<M;i++){
        if(!prime[i]){
            D[i]=2;
            pre[++cnt]=i;
            num[i]=1;
        }
        for(int j=1;j<=cnt&&i*pre[j]<M;j++){
            prime[i*pre[j]]=1;
            D[i*pre[j]]=D[i]*2;
            num[i*pre[j]]=1;
            if(i%pre[j]==0){
                num[i*pre[j]]=num[i]+1;
                D[i*pre[j]]=D[i]/num[i*pre[j]]*(num[i*pre[j]]+1);
                break;
            }
        }
        //cout<<i<<" "<<D[i]<<endl;
    }
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        cout<<D[n]<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem C 表单

https://ac.nowcoder.com/acm/contest/917/C

题意：

题解：

C++版本一

题解：set

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
string str;
struct node{};
set<string>st;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        cin>>str;
        if(st.count(str))cnt++;
        st.insert(str);
    }
    while(m--){
        scanf("%d",&k);
        if(k==1){
            cin>>str;
            if(st.count(str)){
                cnt++;
            }else{
                st.insert(str);
            }
        }else{
            cout<<cnt<<endl;
            cnt=0;
        }
    }

    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem D 分数的运算

https://ac.nowcoder.com/acm/contest/917/D

题意：

题解：

C++版本一

题解：模拟

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%lld%lld%lld%lld",&n,&m,&u,&v);
    k=n*v+m*u;
    p=m*v;
    ll gcd=__gcd(k,p);
    cout<<k/gcd<<" "<<p/gcd<<endl;
    k=n*v-m*u;
    p=m*v;
    gcd=__gcd(k,p);
    if(k==0)cout<<0<<" "<<0<<endl;
    else cout<<k/gcd<<" "<<p/gcd<<endl;
    k=n*u;
    p=m*v;
    gcd=__gcd(k,p);
    cout<<k/gcd<<" "<<p/gcd<<endl;
    k=n*v;
    p=m*u;
    gcd=__gcd(k,p);
    cout<<k/gcd<<" "<<p/gcd<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem E 希望

https://ac.nowcoder.com/acm/contest/917/E

题意：

题解：01背包+线段树+lazy

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
int a[N];
ll dp[N];
int c[N];
ll tree[N<<2];
ll lazy2[N<<2];
char str;
struct node{};
void pushup(int rt){
    tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
}
void pushdown(int l,int r,int rt){
    tree[rt<<1]=min(tree[rt<<1],lazy2[rt]);
    tree[rt<<1|1]=min(tree[rt<<1|1],lazy2[rt]);
    lazy2[rt<<1|1]=min(lazy2[rt<<1|1],lazy2[rt]);
    lazy2[rt<<1]=min(lazy2[rt<<1],lazy2[rt]);
    lazy2[rt]=INF;
}
void build(int l,int r,int rt){
    lazy2[rt]=INF;
    if(l==r){
        //scanf("%lld",&tree[rt]);
        tree[rt]=INF;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void updata(int l,int r,int rt,int L,int R,ll C){
    if(L<=l&&r<=R){
        tree[rt]=min(tree[rt],C);
        lazy2[rt]=min(lazy2[rt],C);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(l,r,rt);
    if(L<=mid)updata(l,mid,rt<<1,L,R,C);
    if(mid<R)updata(mid+1,r,rt<<1|1,L,R,C);
    pushup(rt);
}
void see(int l,int r,int rt){
    if(l==r){
        c[l]=tree[rt];//printf("%lld%c",tree[rt]," \n"[r==n]);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(l,r,rt);
    see(l,mid,rt<<1);
    see(mid+1,r,rt<<1|1);
    pushup(rt);
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d%d",&n,&k,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    build(1,n,1);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&l,&r,&p);
        updata(1,n,1,l,r,p);
    }
    see(1,n,1);
    for(int i=1;i<=n;i++){
        if(a[i]<0)
        for(int j=k;j>=c[i];j--){
            dp[j]=max(dp[j],dp[j-c[i]]-a[i]);
        }
    }
    //cout<<sum+dp[k]<<endl;

    printf("%lld\n",sum+dp[k]);
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem F 跳跃的旋律

https://ac.nowcoder.com/acm/contest/917/F

题意：

题解：

C++版本一

Problem G FTOS的测试

https://ac.nowcoder.com/acm/contest/917/G

题意：

题解：

C++版本一

Problem H 数据结构题

https://ac.nowcoder.com/acm/contest/917/H

题意：

题解：

C++版本一

题解：二分

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=20180623;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
vector<int>V[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        V[a[i]].push_back(i);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d%d",&l,&r,&u,&v,&k);
        if(l>r)swap(l,r);
        if(u>v)swap(u,v);
        ll x=upper_bound(V[k].begin(),V[k].end(),r)-lower_bound(V[k].begin(),V[k].end(),l);
        ll y=upper_bound(V[k].begin(),V[k].end(),v)-lower_bound(V[k].begin(),V[k].end(),u);
        cout<<x%MOD<<endl;
        cout<<y%MOD<<endl;
        cout<<x*y%MOD<<endl;
    }
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解：主席树

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define PII pair<int,int >
#define FI first
#define SE second
#define PB push_back
#define POP pop_back
#define endl '\n'
const int N=1000005;
const int mod=20180623;
struct dat{
    int ls,rs,v;
}tr[N<<2];
int s[N];
int cnt;
int ss[N];
int build(int l,int r){
    int pos=++cnt;
    //cout<<l<<' '<<r<<' '<<pos<<endl;
    if(l==r){
        tr[pos].v=0;
        //cout<<s[l]<<endl;
        return pos;
    }
    int mid=l+r>>1;
    tr[pos].ls=build(l,mid);
    tr[pos].rs=build(mid+1,r);
    return pos;
}
int update(int x,int l,int r,int loc,int value){
    int pos=++cnt;
    //cout<<pos<<endl;
    if(l==r){
        tr[pos].v=value;
        return pos;
    }
    int mid=l+r>>1;
    if(loc<=mid){
        tr[pos].rs=tr[x].rs;
        tr[pos].ls=update(tr[x].ls,l,mid,loc,value);
    }
    else{
        tr[pos].ls=tr[x].ls;
        tr[pos].rs=update(tr[x].rs,mid+1,r,loc,value);
    }
    return pos;
}
int f(int x,int l,int r,int loc){
    if(l==r)return tr[x].v;
    int mid=l+r>>1;
    if(mid>=loc)return f(tr[x].ls,l,mid,loc);
    else return f(tr[x].rs,mid+1,r,loc);
}
int ed[N];
int main()
{
    int n,m,v,op,loc,value;
    while(~scanf("%d%d",&n,&m)){
        build(-100000,100000);
        ed[0]=1;
        for(int i=1;i<=n;i++){
            scanf("%d",&s[i]);
            int xxx=f(ed[i-1],-100000,100000,s[i])+1;
            ed[i]=update(ed[i-1],-100000,100000,s[i],xxx);
        }
        int l,r,ll,rr,x;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d%d%d",&l,&r,&ll,&rr,&x);
            if(l>r)swap(l,r);
            if(ll>rr)swap(ll,rr);
            LL p=f(ed[r],-100000,100000,x)-f(ed[l-1],-100000,100000,x);
            LL q=f(ed[rr],-100000,100000,x)-f(ed[ll-1],-100000,100000,x);
            cout<<p<<endl;
            cout<<q<<endl;
            cout<<p%mod*q%mod<<endl;
        }   
    }
     
    return 0;
}

Problem I y大的字符串

https://ac.nowcoder.com/acm/contest/917/I

题意：

题解：

C++版本一

Problem J 外挂

https://ac.nowcoder.com/acm/contest/917/J

题意：

题解：线段树+数学

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
//const int MOD=10000+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q,p;
int ans,cnt,flag,temp,sum;
ll tree[N<<2];
ll tree2[N<<2];
ll lazy2[N<<2];
char str;
struct node{};
ll POW(ll a,int b){
    if (b==1) return a;
    if (b==2) return a*a;
    return 1;
}
void pushup(int rt){
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
    tree2[rt]=tree2[rt<<1]+tree2[rt<<1|1];
}
void pushdown(int l,int r,int rt){
    if(lazy2[rt]){
        int mid=(l+r)>>1;
        int llen=(mid-l+1);
        int rlen=(r-mid);
        tree2[rt<<1]=tree2[rt<<1]+llen*POW(lazy2[rt],2)+2*tree[rt<<1]*lazy2[rt];
        tree2[rt<<1|1]=tree2[rt<<1|1]+rlen*POW(lazy2[rt],2)+2*tree[rt<<1|1]*lazy2[rt];

        tree[rt<<1]=tree[rt<<1]+llen*lazy2[rt];
        tree[rt<<1|1]=tree[rt<<1|1]+rlen*lazy2[rt];

        lazy2[rt<<1]=lazy2[rt<<1]+lazy2[rt];
        lazy2[rt<<1|1]=lazy2[rt<<1|1]+lazy2[rt];
        lazy2[rt]=0;
    }
}
void build(int l,int r,int rt){
    lazy2[rt]=0;
    if(l==r){
        scanf("%lld",&tree[rt]);
        //tree[rt]=0;
        tree2[rt]=tree[rt]*tree[rt];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void updata(int l,int r,int rt,int L,int R,ll C){
    if(L<=l&&r<=R){
        int len=r-l+1;
        tree2[rt]=tree2[rt]+(len*POW(C,2))+2*tree[rt]*C;
        tree[rt]=tree[rt]+len*C;
        lazy2[rt]=lazy2[rt]+C;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(l,r,rt);
    if(L<=mid)updata(l,mid,rt<<1,L,R,C);
    if(mid<R)updata(mid+1,r,rt<<1|1,L,R,C);
    pushup(rt);
}
ll query(int l,int r,int rt,int L,int R,int op){
    if(L<=l&&r<=R){
        if(op==1)return tree[rt];
        if(op==2)return tree2[rt];
    }
    int mid=(l+r)>>1;
    ll res=0;
    pushdown(l,r,rt);
    if(L<=mid)res=res+query(l,mid,rt<<1,L,R,op);
    if(mid<R)res=res+query(mid+1,r,rt<<1|1,L,R,op);
    return res;
}
void see(int l,int r,int rt){
    if(l==r){
        printf("%lld%c",tree2[rt]," \n"[r==n]);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(l,r,rt);
    see(l,mid,rt<<1);
    see(mid+1,r,rt<<1|1);
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    while(~scanf("%d%d",&n,&m)){
        build(1,n,1);
        int op;
        int l,r;
        ll c;
        for(int i=1;i<=m;i++){
            scanf("%d",&op);
            if(op==1){
                scanf("%d%d%lld",&l,&r,&c);
                updata(1,n,1,l,r,c);
            }else{
                scanf("%d%d",&l,&r);
                ll q1=query(1,n,1,l,r,1);
                ll q2=query(1,n,1,l,r,2);
                cout<<(q1*q1-q2)/2<<endl;
            }
            //see(1,n,1);
        }
    }

    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

参考文章：

https://ac.nowcoder.com/discuss/198506?tdsourcetag=s_pcqq_aiomsg