[CF977X]Codeforces Round #479 (Div. 3)

在某位dalao的建议下,第一轮Div.3比赛总算是顺利举行了(然而开始几分钟服务器却炸了)。

题目非常的水啊,1个小时就AC了4道题,又把我那rating拉了回来。

题目链接

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∈[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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注