目录
显示
在某位 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;
}