牛客小白月赛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
理想汽车工作强度 65人发布