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

 

发表评论

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