題目地址: https://ac.nowcoder.com/acm/contest/19851?from=acdiscuss

目錄

• 四舍五入
• 安卓圖案解鎖
• Captcha Cracker
• 回文數(shù)
• [NOIP2016]玩具謎題
• [NOIP2015]神奇的幻方
• Tic-Tac-Toe
• I love you【經(jīng)典求子序列的次數(shù)】
• [NOIP2007]Hanoi雙塔問題
• 方塊與收納盒
• 答題卡
• 區(qū)間求和
• 零錢兌換
• 斐波那契
• 生日宴
• 了斷局
• 臉盆大哥的木桶
• 倒水
• Cut
• 強(qiáng)迫癥的序列
• 字典序最大的子序列
• 強(qiáng)迫癥
• [NOIP2007]紀(jì)念品分組
• Eustia of the Tarnished Wings
• Shopping
• Mountain
• 可持久化動態(tài)圖上樹狀數(shù)組維護(hù)01背包
• 紙牌游戲
• 組隊(duì)
• 牛牛玩平板
• [NOIP2008]排座椅

四舍五入

模擬找到第一個進(jìn)位的，進(jìn)位后面的都刪除。然后再次尋找可以進(jìn)位的，以此類推，直到進(jìn)位次數(shù)用完，或者結(jié)果已經(jīng)是一個整數(shù)。

#include<bits/stdc++.h> using namespace std; string s; int flag; void solve() {vector<int>A,C;for(int i=s.find('.')+1;i<s.size();i++){if( (s[i]-'0')>=5) {flag=1;break;}A.push_back(s[i]-'0');}if(flag){int temp=1;for(int i=A.size()-1;i>=0;i--){temp+=A[i];C.push_back(temp%10);temp=temp/10;}string ss;for(int i=0;i<s.size();i++) {if(s[i]=='.') break;ss+=s[i];}if(temp){ss.clear();int temp=1;for(int i=s.find('.')-1;i>=0;i--) {temp+=s[i]-'0';ss+=to_string(temp%10);temp/=10;}if(temp) ss+="1";reverse(ss.begin(),ss.end());s=ss;}else {ss+='.';for(int i=C.size()-1;i>=0;i--) ss+=to_string(C[i]);s=ss;}} } int main(void) {int n,t; cin>>n>>t;cin>>s;while(t--){flag=0;if(s.find('.')==-1) break;solve();if(!flag) break;}cout<<s<<endl;return 0; }

安卓圖案解鎖

只要看橫，豎，對角線即可。因?yàn)槠渌亩伎梢灾苯拥竭_(dá)。只有三點(diǎn)一線這種情況需要特殊判斷。

#include<bits/stdc++.h> using namespace std; const int N=1e2+10; int a[N][N],flag,st[N]; string s; int check(int s1,int s2) {if( (s1==1&&s2==3&&!st[2]) || (s1==3&&s2==1&&!st[2]) ) return 0;if( (s1==4&&s2==6&&!st[5]) || (s1==6&&s2==4&&!st[5]) ) return 0;if( (s1==7&&s2==9&&!st[8]) || (s1==9&&s2==7&&!st[8]) ) return 0;if( (s1==1&&s2==7&&!st[4]) || (s1==7&&s2==1&&!st[4]) ) return 0;if( (s1==2&&s2==8&&!st[5]) || (s1==8&&s2==2&&!st[5]) ) return 0;if( (s1==3&&s2==9&&!st[6]) || (s1==9&&s2==3&&!st[6]) ) return 0;if( (s1==1&&s2==9&&!st[5]) || (s1==9&&s2==1&&!st[5]) ) return 0;if( (s1==3&&s2==7&&!st[5]) || (s1==7&&s2==3&&!st[5]) ) return 0;if(st[s2]) return 0;return 1; } int main(void) {while(cin>>s){flag=1;memset(st,0,sizeof st);for(int i=0;i+1<s.size();i++){st[s[i]-'0']++;if( !check(s[i]-'0',s[i+1]-'0') ) {flag=0;}}if(flag) puts("YES");else puts("NO");}return 0; }

Captcha Cracker

#include<bits/stdc++.h> using namespace std; int main(void) {int t; cin>>t;while(t--) {string s,ans,temp; cin>>s;for(int i=0;i<s.size();i++){temp+=s[i];if(temp.find("zero")!=-1) ans+="0",temp.clear();if(temp.find("two")!=-1) ans+="2",temp.clear();if(temp.find("four")!=-1) ans+="4",temp.clear();if(temp.find("six")!=-1) ans+="6",temp.clear();if(temp.find("nine")!=-1) ans+="9",temp.clear();if(s[i]=='0'||s[i]=='2'||s[i]=='4'||s[i]=='6'||s[i]=='9') ans+=s[i];}cout<<ans<<endl;}return 0; }

回文數(shù)

#include<bits/stdc++.h> using namespace std; int a[105]; void solve() {int cnt1=0,cnt2=0,sum=0;for(int i=0;i<=9;i++) {if(a[i]%2) cnt1++;if(a[i]%2==0&&a[i]) cnt2++;sum+=a[i];}if(cnt1>1||sum-a[0]==1) cout<<"-1"<<endl;else {string s;for(int i=1;i<=9;i++){if(a[i]>=2){s+=to_string(i),a[i]-=2;break;}}for(int i=0;i<=9;i++)while(a[i]>=2) s+=to_string(i),a[i]-=2;if(cnt1) {for(int i=0;i<=9;i++) {if(a[i]) s+=to_string(i);}string ss=s;ss.erase(ss.size()-1); reverse(ss.begin(),ss.end());s+=ss;cout<<s<<endl;}else{string ss=s; reverse(ss.begin(),ss.end());s+=ss;cout<<s;}} } int main(void) {for(int i=0;i<=9;i++) cin>>a[i];solve();return 0; }

[NOIP2016]玩具謎題

#include<cstdio> #include<iostream> using namespace std; struct student {string name;int d; }stu[100005]; int main(void) {int n,m;cin>>n>>m;for(int i=0;i<n;i++) cin>>stu[i].d>>stu[i].name; int ans=0;while(m--){int a,s; cin>>a>>s;//0左 1右 //外if(stu[ans].d) if(a) ans=(n+ans-s)%n;//右 else ans=(ans+s)%n;//左 //內(nèi)elseif(a) ans=(ans+s)%n;//右 else ans=(n+ans-s)%n;//左 }cout<<stu[ans].name<<endl; return 0; }

[NOIP2015]神奇的幻方

模擬即可。

#include<bits/stdc++.h> using namespace std; int a[55][55]; int main(void) {int n; cin>>n;a[1][n/2+1]=1;int k=2,x=1,y=n/2+1;while(k<=n*n){if(x==1&&y!=n) {a[n][y+1]=k;x=n,y=y+1; }else if(x!=1&&y==n){a[x-1][1]=k;x=x-1,y=1;}else if(x==1&&y==n){a[x+1][y]=k;x=x+1,y=y;}else{int xx=x-1,yy=y+1;if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&!a[xx][yy]) a[xx][yy]=k,x=xx,y=yy;else {a[x+1][y]=k;x=x+1,y=y;}}k++;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) cout<<a[i][j]<<" ";cout<<endl; }return 0; }

Tic-Tac-Toe

#include<bits/stdc++.h> using namespace std; string s[15]; int solve(char c) {string ss;for(int i=0;i<3;i++) ss+=c;for(int i=0;i<3;i++) if(s[i]==ss) return 1;for(int i=0;i<3;i++){string temp;for(int j=0;j<3;j++) temp+=s[j][i];if(temp==ss) return 1;}string s1;for(int i=0;i<3;i++) s1+=s[i][i];if(s1==ss) return 1;string s2;for(int i=0,j=2;i<3;i++,j--) s2+=s[i][j];if(s2==ss) return 1;return 0; } int main(void) {int t; cin>>t;while(t--){int flag1=0,flag2=0;for(int i=0;i<3;i++) cin>>s[i];flag1=solve('A'),flag2=solve('B');if(flag2&&flag1) puts("invalid");else if(flag1) puts("Yes");else if(flag2) puts("No");else puts("draw");}return 0; }

I love you【經(jīng)典求子序列的次數(shù)】

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; const int mod=20010905; typedef long long int LL; string s=".iloveyou";//從1下標(biāo)開始 LL dp[10];//dp[i]表示[1-i]的子序列個數(shù) int main(void) {string a; cin>>a;for(int i=0;i<a.size();i++) a[i]=tolower(a[i]);dp[0]=1;for(int i=0;i<a.size();i++){for(int j=1;j<=8;j++){if(a[i]==s[j]){dp[j]=(dp[j]+dp[j-1])%mod;}}}cout<<dp[8];return 0; }

[NOIP2007]Hanoi雙塔問題

遞推+高精

#include<bits/stdc++.h> using namespace std; vector<int>A; vector<int> solve(vector<int> A) {vector<int>C;int t=0;for(int i=0;i<A.size()||t;i++){if(i<A.size()) t+=A[i]*2;C.push_back(t%10);t/=10;}t=2;A=C; C.clear();for(int i=0;i<A.size();i++) {t+=A[i];C.push_back(t%10);t/=10;}if(t) C.push_back(1);return C; } int main(void) {int n; cin>>n;A.push_back(2);for(int i=2;i<=n;i++) A=solve(A);for(int i=A.size()-1;i>=0;i--) cout<<A[i];return 0; }

方塊與收納盒

#include<bits/stdc++.h> using namespace std; typedef long long int LL; LL f[105]; int main(void) {f[1]=1,f[2]=2,f[3]=3;for(int i=4;i<=80;i++) f[i]=f[i-1]+f[i-2];int t,n; cin>>t;while(t--) cin>>n,cout<<f[n]<<endl;return 0; }

答題卡

打表找規(guī)律。

#include<bits/stdc++.h> using namespace std; const int N=1e3+10; int a[N][N],b[N][N],n,ans; bool check() {memset(b,0,sizeof b);for(int i=0;i<n;i++){for(int j=0;j<n;j++) {if(a[j][i]) b[i][j]=1;}}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(a[i][j]!=b[i][j]) return false;}}return true; } void dfs(int index) {if(index==n){if(check()) ans++;return;}for(int i=0;i<n;i++) {a[i][index]=1;dfs(index+1);a[i][index]=0;} } int main(void) {cin>>n;dfs(0);cout<<ans;return 0; }//1 2 4 10 26 76 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; const int mod=1e9+7; typedef long long int LL; LL f[N],n; int main(void) {cin>>n;f[1]=1,f[2]=2;for(int i=3;i<=n;i++) f[i]=(f[i-1]+f[i-2]*(i-1)%mod)%mod;cout<<f[n];return 0; }

區(qū)間求和

#include<bits/stdc++.h> using namespace std; const int N=1e5*2+10; typedef long long int LL; LL a[N],s[N],n,m; int main(void) {cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];while(m--){int l,r; cin>>l>>r;cout<<s[r]-s[l-1]<<endl;}return 0; }

零錢兌換

#include<bits/stdc++.h> using namespace std; int main(void) {int n,cnt=0; cin>>n;for(int i=0;i<=200;i++) {for(int j=0;j<=100;j++) {for(int k=0;k<=40;k++){int sum=i+j*2+k*5;if(sum==n) cnt++;}}}cout<<cnt;return 0; }

斐波那契

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; typedef long long int LL; LL f[N]; int main(void) {string s; cin>>s;int t=s[s.size()-1]-'0';if(t%2) puts("-1");else puts("1");return 0; }

生日宴

#include<bits/stdc++.h> using namespace std; int n,m; struct node {string name,s; }temp; bool cmp(node a,node b) {return a.s<b.s;} map<string,vector<node>>mp; int main(void) {cin>>n>>m;while(n--){cin>>temp.name>>temp.s; string a=temp.s.substr(4);mp[a].push_back(temp);}while(m--){int k; cin>>k;string id; cin>>id;auto a=mp[id];sort(a.begin(),a.end(),cmp);cout<<a[k-1].name<<endl;}return 0; }

了斷局

#include<bits/stdc++.h> using namespace std; const int N=110; typedef long long int LL; LL f[N]; int main(void) {f[1]=0,f[2]=1,f[3]=1;for(int i=4;i<=50;i++) f[i]=f[i-1]+f[i-2]+f[i-3];int n;while(cin>>n) cout<<f[n]<<endl;return 0; }

臉盆大哥的木桶

#include<bits/stdc++.h> using namespace std; int main(void) {int t; cin>>t;while(t--){int n,k,s; cin>>n>>k>>s;priority_queue<int>q;for(int i=0;i<n;i++){int x; cin>>x;q.push(x);}int sum=0;while(q.size()>=k){int temp=0;for(int i=0;i<k;i++){temp=q.top(); q.pop();}sum+=s*temp;}cout<<sum<<endl;}return 0; }

倒水

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n; double T,C,t[N],c[N]; int main(void) {cin>>n>>T>>C;double minv=1e9,maxv=-1;//最小溫度，最高溫度T=T*C;for(int i=0;i<n;i++) cin>>t[i]>>c[i],maxv=max(maxv,t[i]),minv=min(minv,t[i]);for(int i=0;i<n;i++){T+=t[i]*c[i],C+=c[i];}double ans=T/C;//合并后總的溫度if(ans<=minv) printf("Possible\n%.4lf",minv);else if(ans>=maxv) printf("Possible\n%.4lf",ans);else puts("Impossible");return 0; }

Cut

#include<bits/stdc++.h> using namespace std; typedef long long int LL; LL a[100005],n,sum,temp; int main(void) {cin>>n;for(int i=0;i<n;i++) cin>>a[i],temp+=a[i];sort(a,a+n);for(int i=0;i<n-1;i++) {sum+=temp;temp-=a[i];}cout<<sum;return 0; }

強(qiáng)迫癥的序列

n-1個數(shù)加1，等價(jià)于一個數(shù)減1.

#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int a[N],t,n; int main(void) {cin>>t;while(t--){cin>>n;int sum=0,minv=1e9,ans=0;for(int i=0;i<n;i++) cin>>a[i],sum+=a[i],minv=min(minv,a[i]);for(int i=0;i<n;i++) ans+=a[i]-minv;cout<<ans<<" "<<(1ll*ans*(n-1)+sum)/n<<endl;}return 0; }

字典序最大的子序列

#include<bits/stdc++.h> using namespace std; const int N=1e5*2+10; set<char>st; priority_queue<char>q; int f[30][N];//表示以f[i][j] i字符j之后還有幾個i字符 int main(void) {string s; cin>>s;for(int i=0;i<s.size();i++) st.insert(s[i]);for(auto i=st.begin();i!=st.end();i++) q.push(*i);f[s[s.size()-1]-'a'][s.size()-1]=1;for(int i=s.size()-2;i>=0;i--){for(int j=0;j<=26;j++) f[j][i]=f[j][i+1];f[s[i]-'a'][i]=f[s[i]-'a'][i+1]+1;}string ans;for(int i=0;i<s.size();i++){if(s[i]==q.top()) {ans+=s[i];f[q.top()-'a'][i]--;while(q.size()&&f[q.top()-'a'][i]==0) q.pop();//說明后面沒有更大的了}}cout<<ans;return 0; }

強(qiáng)迫癥

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; map<int,int>mp; int main(void) {int n; cin>>n;for(int i=0;i<n;i++) {int x; cin>>x;mp[x]++;}int sum=0;for(auto i=mp.begin();i!=mp.end();i++){sum+=i->second-1;}cout<<sum<<endl;return 0; }

[NOIP2007]紀(jì)念品分組

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int m,n,a[N]; deque<int>q; int main(void) {cin>>m>>n;for(int i=0;i<n;i++) cin>>a[i];sort(a,a+n);for(int i=0;i<n;i++) q.push_back(a[i]);int cnt=0;while(q.size()){if(q.size()>=2){auto l=q.front(); q.pop_front();auto r=q.back(); q.pop_back();if(l+r>m) q.push_front(l);}else q.pop_back();cnt++;}cout<<cnt<<endl;return 0; }

Eustia of the Tarnished Wings

排序，本質(zhì)求的就是一段一段的。

#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int a[N],n,m; int main(void) {cin>>n>>m;for(int i=0;i<n;i++) cin>>a[i];int cnt=0;sort(a,a+n);for(int i=0;i<n;i++){int j=i,flag=0;while(j+1<n&&a[j+1]-a[j]<=m) j++,flag=1;cnt++,i=j;}cout<<cnt;return 0; }

Shopping

貪心的思維，先最可能的將板凳分給各個購物車。然后再將從大到小的順序分物品。

#include<bits/stdc++.h> using namespace std; const int N=1e3+10; int a[N],b[N]; int main(void) {int t; cin>>t;while(t--){vector<int>ve[N];int n,m; cin>>n>>m;priority_queue<int,vector<int>,greater<int>>q;priority_queue<int>s;for(int i=0;i<n;i++){cin>>a[i]>>b[i];if(b[i]) q.push(a[i]);else s.push(a[i]);}int temp=min((int)q.size(),m);for(int i=0;i<m;i++) {if(q.size()){ve[i].push_back(q.top());q.pop();}}while(q.size()) s.push(q.top()),q.pop();int k=0;while(s.size()){ve[k].push_back(s.top()); s.pop();k++;if(k==m) k=0;}double sum=0;for(int i=0;i<m;i++){sort(ve[i].begin(),ve[i].end());for(int j=0;j<ve[i].size();j++){if(i<temp&&j==ve[i].size()-1) sum+=ve[i][j]/2.0;//有購物車else sum+=ve[i][j];}}printf("%.1lf\n",sum);}return 0; }

Mountain

上山需要花費(fèi)，下山滑翔則不需要。但是最后下山的花費(fèi)是需要的。
其實(shí)本質(zhì)就是上最高的山+下山的花費(fèi)。

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],n,ans; int main(void) {cin>>n;for(int i=0;i<n;i++) cin>>a[i],ans=max(ans,a[i]);cout<<ans*2;return 0; }

可持久化動態(tài)圖上樹狀數(shù)組維護(hù)01背包

負(fù)數(shù)直接乘i再加，正數(shù)直接加。

#include<bits/stdc++.h> using namespace std; const int N=1e7+10; typedef long long int LL; LL a[N],n,sum; int main(void) {cin>>n;for(int i=1;i<=n;i++) {cin>>a[i];if(a[i]>=0) sum+=a[i];else sum+=i*a[i];}cout<<sum<<endl;return 0; }

紙牌游戲

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; typedef long long int LL; LL a[N],b[N]; bool cmp(LL s1,LL s2) {return s1>s2; } int main(void) {int n; cin>>n;for(int i=0;i<n;i++) cin>>a[i];for(int i=0;i<n;i++) cin>>b[i];sort(a,a+n),sort(b,b+n,cmp);LL sum=0;for(int i=0,j=0;i<n;i++)if(j<n&&b[j]>=a[i]) sum+=b[j]-a[i],j++;cout<<sum; }

組隊(duì)

二分

#include<bits/stdc++.h> using namespace std; const int N=1e5*2+10; int a[N],t,n,k; int main(void) {cin>>t;while(t--){cin>>n>>k;for(int i=0;i<n;i++) cin>>a[i];sort(a,a+n);int ans=0;for(int i=0;i<n;i++){int r=upper_bound(a+i,a+n,a[i]+k)-a;ans=max(ans,r-i);}cout<<ans<<endl;}return 0; }

牛牛玩平板

#include<bits/stdc++.h> using namespace std; const int N=1e3+10; typedef long long int LL; LL a[N],n,sum; priority_queue<LL,vector<LL>,greater<LL>>q; int main(void) {cin>>n;for(int i=0;i<n;i++) cin>>a[i],q.push(a[i]);while(q.size()>1){LL a=q.top(); q.pop();LL b=q.top(); q.pop();sum+=a*b;q.push(a+b);}cout<<sum;return 0; }

[NOIP2008]排座椅

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; typedef pair<int,int> PII; PII cntx[N],cnty[N]; int n,m,k,l,d; int main(void) {cin>>n>>m>>k>>l>>d;for(int i=1;i<=m;i++) cntx[i].second=i;for(int i=1;i<=n;i++) cnty[i].second=i;for(int i=0;i<d;i++){int x,y,xx,yy; cin>>y>>x>>yy>>xx;if(abs(x-xx)==1) cntx[min(x,xx)].first++;else cnty[min(y,yy)].first++;}sort(cntx+1,cntx+1+m);sort(cnty+1,cnty+1+n); vector<int>a,b;for(int i=n,j=1;j<=k;i--,j++) a.push_back(cnty[i].second);for(int i=m,j=1;j<=l;i--,j++) b.push_back(cntx[i].second);sort(a.begin(),a.end());sort(b.begin(),b.end());for(int i=0;i<a.size();i++) cout<<a[i]<<" ";cout<<endl;for(int j=0;j<b.size();j++) cout<<b[j]<<" ";return 0; }

總結(jié)

以上是生活随笔為你收集整理的牛客竞赛语法入门班数组模拟、枚举、贪心习题【未完结】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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