在某位 dalao 的建议下,第一轮 Div.3 比赛总算是顺利举行了(然而开始几分钟服务器却炸了)。
题目链接
http://codeforces.com/contest/977
A. Wrong Subtraction
大意
给一个数字 \(n\),可以进行以下两种操作:
1、若 \(n\) 末尾不为 \(0\),则 \(n=n-1\);
2、若 \(n\) 末尾等于 \(0\),则 \(n=n/10\)。
求进行 \(k\) 次操作后 \(n\) 的值。
题解
模拟就好。
#include <stdio.h> int n,k; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=k;i++) { if(n%10==0)n/=10; else n--; } printf("%d",n); return 0; }
B. Two-gram
大意
给出一个字符串,求出出现次数最多的长度为 \(2\) 的子串。
题解
把字符串扫一遍,然后将子串出现次数记录下来,最后比较一下即可输出结果。
#include <stdio.h> int t[35][35]; char s[100]; int maxt,ansi,ansj; int main() { int n; scanf("%d",&n); scanf("%s",s); for(int i=1;i<n;i++) t[s[i-1]-'A'][s[i]-'A']++;//这里计算子串出现的次数 for(int i=0;i<26;i++) for(int j=0;j<26;j++) if(t[i][j]>maxt) { ansi=i; ansj=j; maxt=t[i][j]; } printf("%c%c",ansi+'A',ansj+'A'); return 0; }
C. Less or Equal
大意
给出一个包含 \(n\) 个数字的序列 \(a\),求出一个数 \(x \in [1,10^9]\),使恰好 \(k\) 个数小于或等于 \(x\),如果无解,输出 \(-1\)。
题解
可以将数列进行排序,如果 \(a_k=a_{k+1}\),就意味着不可能存在 \(x\) ,使恰好 \(k\) 个数小于或等于 \(x\)。
但注意以下几个特判:
1、若 \(k=0\),如果 \(a_1=1\),输出 \(-1\)(\(x\) 不能小于 \(1\)),否则输出 \(a_1-1\)。
2、若 \(k=n\),输出 \(a_n\)(你也可以输出 \(1000000000\),这是 \(x\) 的最大值)。
#include <cstdio> #include <algorithm> using namespace std; int a[200005]; int main() { int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); if(k==0) { if(a[1]!=1)printf("%d",a[1]-1); else printf("-1"); } else if(k==n)printf("%d",a[n]); else if(a[k]==a[k+1])printf("-1"); else printf("%d",a[k]); return 0; }
D. Divide by three, multiply by two
大意
给出一个序列,要求将其重排,使得数列中每个数字的后一个数字,是前一个数字的三分之一,或者是前一个数字的两倍。
题解
标准的 DFS。
#include <iostream> using namespace std; int n,vis[105]; long long a[105],ans[105]; void dfs(int d) { if(d==n+1) { for(int i=1;i<=n;i++) cout<<ans[i]<<' '; return; } for(int i=1;i<=n;i++) { if(!vis[i]) { if(d==1) { vis[i]=1; ans[d]=a[i]; dfs(d+1); vis[i]=0; ans[d]=0; } else if(3*a[i]==ans[d-1]||a[i]==2*ans[d-1]) { vis[i]=1; ans[d]=a[i]; dfs(d+1); vis[i]=0; ans[d]=0; } } } } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; dfs(1); return 0; }
E. Cyclic Components
大意
定义一个圈为含有 \(n\) 个点和恰好 \(n\) 条边的一个连通分量。
给出一个图,求出圈的个数。
题解
容易看出,一个圈内所有点的度数均为 \(2\) 。
先 DFS 求出所有连通分量,判断各个连通分量内所有点是否满足上面的条件即可。
#include <cstdio> #include <vector> using namespace std; struct edge { int v,next; }e[400005]; int t[200005],head[200005],cnt,vis[200005]; vector<int> path; void addedge(int u,int v) { e[++cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; } void dfs(int u) { vis[u]=1; path.push_back(u); for(int i=head[u];i;i=e[i].next) if(!vis[e[i].v])dfs(e[i].v); return; } int main() { int n,m,ans=0; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); t[u]++,t[v]++; addedge(u,v); addedge(v,u); } for(int i=1;i<=n;i++) if(!vis[i]) { path.clear(); dfs(i); int maxn=path.size(),flag=1; for(int i=0;i<maxn;i++) if(t[path[i]]!=2) { flag=0; break; } ans+=flag; } printf("%d\n",ans); return 0; }