當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

牛客练习赛48

發(fā)布時(shí)間：2024/10/5 编程问答 28 豆豆

生活随笔收集整理的這篇文章主要介紹了牛客练习赛48 小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

Problem A?小w的a+b問題

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

題意：

題解：貪心

C++版本一

Problem B?小w的a=b問題

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

題意：

題解：線性篩+后綴和+貪心

C++版本一

1、對(duì)兩個(gè)數(shù)組桶排序；

2、求后綴和；

3、篩法求出每個(gè)數(shù)的最小非1質(zhì)因子；

4、從后向前把每個(gè)數(shù)分成最小非1質(zhì)因子和這個(gè)數(shù)/最小非1質(zhì)因子；

5、判斷每個(gè)數(shù)的數(shù)量是否相同；

/* *@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],b[N]; ll c[N],d[N]; int pre[N],prime[N],num[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);prime[0]=prime[1]=1;num[0]=num[1]=1;for(int i=2;i<N;i++){if(!prime[i]){pre[++cnt]=i;num[i]=i;}for(int j=1;j<=cnt&&i*pre[j]<N;j++){prime[i*pre[j]]=1;num[i*pre[j]]=pre[j];if(i%pre[j]==0){break;}}//cout<<num[i]<<endl;}//cout<<cnt<<endl;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=0;i<N;i++)c[i]=0,d[i]=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);c[a[i]]++;}for(int i=1;i<=m;i++){scanf("%d",&b[i]);d[b[i]]++;}for(int i=100000;i>=1;i--){c[i]+=c[i+1];d[i]+=d[i+1];}for(int i=100000;i>=2;i--){temp=c[i];c[i]=0;c[i/num[i]]+=temp;c[num[i]]+=temp;temp=d[i];d[i]=0;d[i/num[i]]+=temp;d[num[i]]+=temp;}ans=1;for(int i=2;i<N;i++){//cout<<c[i]<<" "<<d[i]<<endl;ans&=(c[i]==d[i]);}cout<<(ans?"equal":"unequal")<<endl;}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

Problem C?小w的糖果

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

題意：

題解：數(shù)學(xué)+差分

C++版本一

1、對(duì)于類型1，直接差分；

2、對(duì)于類型2，差分每次增加的量等于當(dāng)前已經(jīng)操作的人數(shù)；

3、等于類型3，差分每次增加的量等于當(dāng)前已經(jīng)操作的人數(shù)+2*上一次類型3進(jìn)行類型2的值；

/* *@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[N],cnt,flag,temp,sum; ll a[3][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("%d%d",&n,&m);memset(a,0,sizeof(a));for(int i=1;i<=m;i++){scanf("%d%d",&p,&k);a[p-1][k]++;}ll one=0;ll addone=0,add=0;ll timesone=0,timesadd=0,times=0;ll now=0;for(int i=1;i<=n;i++){one=(one+a[0][i])%MOD;addone=(addone+a[1][i])%MOD;timesone=(timesone+a[2][i])%MOD;add=(add+addone)%MOD;times=(times+2*timesadd+timesone)%MOD;timesadd=(timesadd+timesone)%MOD;now=(one+add+times)%MOD;printf("%lld%c",now," \n"[i==n]);}}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

Problem D?小w的基站網(wǎng)絡(luò)

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

題意：

題解：

C++版本一

Problem E?小w的矩陣前k大元素

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

題意：

題解：

C++版本一

Problem F?小w的互質(zhì)集

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

題意：

題解：

C++版本一

?

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的牛客练习赛48的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

练习赛