题目地址:http://codeforces.com/contest/977 来源:Codeforces

文章目录

A - Wrong SubtractionB - Two-gram (map)C - Less or Equal (二分)D - Divide by three, multiply by two(递归)E - Cyclic Components(并查集)F - Consecutive Subsequence

A - Wrong Subtraction

给你一个数，有两种操作。 1.如果最后一位是0，就除以10。 2.如果最后一位不是0，就减1。 操作k次之后这个数是几。

#include<bits/stdc++.h> using namespace std; int main(){ int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=k;i++){ if(n%10==0) n/=10; else n-=1; } printf("%d\n",n); return 0; }

B - Two-gram (map)

  题目大意就是找到一个出现次数最多的字符串，这个字符串中只能包含两个字符。用map计数，遍历找到出现最多次数的字符串。

#include<bits/stdc++.h> using namespace std; const int Max_n=110; map<string,int>m; int main(){ ios::sync_with_stdio(false); int n; string a; cin>>n>>a; for(int i=0;i<=n-2;i++){ m[a.substr(i,2)]++; } map<string,int>::iterator it; int mmax=-1; string b; for(it=m.begin();it!=m.end();it++){ if(it->second>mmax){ mmax=it->second; b=it->first; } } cout<<b<<endl; return 0; }

C - Less or Equal (二分)

  找到一个数，给出的数组中可以找到k个数是小于等于这个数的，我的解法是二分1~10⁹，找到一个数满足上面的条件的。

#include<bits/stdc++.h> using namespace std; const int Max_n=2e5+10; int a[Max_n]; int main(){ int n,k; scanf("%d%d",&n,&k); for(int i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); int l=1,r=1e9,ans=0; while(l<=r){ int mid=l+(r-l)/2; int cnt=upper_bound(a,a+n,mid)-a;//>x的第一个数的下标 if(cnt>k) r=mid-1; else if(cnt<k) l=mid+1; else{ ans=mid; break; } } if(ans) printf("%d\n",ans); else printf("-1\n"); return 0; }

D - Divide by three, multiply by two(递归)

  给你一个序列，让你找到一种顺序满足前面一个数能够除以3或者乘以2得到后面一个数。先找到这个满足条件的第一个数，然后依次向下递归。

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int Max_n=110; LL a[Max_n]; int n; void dfs(int cnt,LL inx){ if(cnt==n-1) return ; else{ int flag=-1,flag1=-1; for(int i=cnt;i<=n;i++){ if(a[i]==a[inx]*2) flag=i; if(a[inx]%3==0&&a[i]==a[inx]/3) flag1=i; } //两个标记有任何一个都可以找到一个对应的数满足条件 //标记代表着满足条件的数的下标 if(flag!=-1){ cnt++; swap(a[flag],a[cnt]); dfs(cnt,cnt); } else if(flag1!=-1){ cnt++; swap(a[flag1],a[cnt]); dfs(cnt,cnt); } } return; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); sort(a+1,a+n+1); int inx=-1; for(int i=1;i<=n;i++){ int flag=binary_search(a+1,a+n+1,a[i]*3); int flag1; if(a[i]%2==1) flag1=0; else flag1=binary_search(a+1,a+n+1,a[i]/2); if(flag1||flag) continue; else{ inx=i; break; } } swap(a[inx],a[1]); dfs(1,1); for(int i=1;i<=n-1;i++) printf("%lld ",a[i]); printf("%lld\n",a[n]); return 0; }

E - Cyclic Components(并查集)

  n个点，m条边，全部都是无向边，问这个无向图中有几个环(每个环上的点只能是2度)。输入的时候，先判断每个点的度，遍历每条边的两个顶点，如果这两个点的度都是2，那么就找他们的父节点，如果相同说明出现了一个环，如果父节点不同那么就合并两个顶点。

#include<bits/stdc++.h> using namespace std; const int Max_n=2e5+10; int cnt[Max_n],f[Max_n]; int ans; struct Edge{ int from,to; }edge[Max_n]; int get_f(int v){ if(f[v]==v) return v; else return f[v]=get_f(f[v]); } void Merge(int u,int v){ int t1=get_f(u); int t2=get_f(v); if(t1!=t2) f[t1]=t2; else ans++; } int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++){ scanf("%d%d",&edge[i].from,&edge[i].to); cnt[edge[i].from]++; cnt[edge[i].to]++; } for(int i=1;i<=m;i++){ if(cnt[edge[i].from]==2&&cnt[edge[i].to]==2) Merge(edge[i].from,edge[i].to); } printf("%d\n",ans); return 0; }

F - Consecutive Subsequence

  用map[i]=map[i-1]+1；i表示当前所记录的数，map[i]表示以i结尾的数的最长的长度。在输入的时候先记录下以每一个数结尾的最大的长度。最后记录下满足条件的序列的下标，并且输出下标和长度。这组序列间隔为1。

#include<bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; const int Max_n=2e5+10; int a[Max_n]; map<int,int>m; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); m[a[i]]=m[a[i]-1]+1; } int mmax=-inf; int len=-inf; map<int,int>::iterator it; for(it=m.begin();it!=m.end();it++){ if(it->second>len){ mmax=it->first; len=it->second; } } int s=mmax-len+1; printf("%d\n",len); for(int i=1;i<=n;i++){ if(a[i]==s){ printf("%d ",i); s++; } } return 0; }