牛客小白月赛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 DEBUGfreopen("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 DEBUGprintf("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 DEBUGfreopen("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 DEBUGprintf("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 DEBUGfreopen("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 DEBUGprintf("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 DEBUGfreopen("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 DEBUGprintf("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 DEBUGfreopen("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 DEBUGprintf("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 DEBUGfreopen("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 DEBUGprintf("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
總結
- 上一篇： Beautiful Lyrics
- 下一篇： 便利店管理系统