X Round 2 补题记

相信奇迹的人,本身就和奇迹一样了不起。

A. 缘分

题目链接

https://www.luogu.org/problem/P5436

题解

一道非常不错的签到题。

首先,\(lcm(a,b) = \frac{a \times b}{\gcd (a,b)}\)。要想让 \(lcm(a,b)\) 尽可能大,当然要让 \(\gcd (a,b)\) 尽可能小。所以我们要取两个互质的整数 \(a,b\)。

怎样让 \(a \times b\) 尽可能大呢?当然是让两个数都尽可能大。于是我们的方案就呼之欲出了:我们取 \(n\) 和 \(n-1\) 两个数字。

特别地,当 \(n=1\) 时,我们取的两个整数都是 \(1\),答案也是 \(1\)。

#include <iostream>
using namespace std;
int main()
{
 int t;
 cin>>t;
 while(t--)
 {
  long long x;
  cin>>x;
  if(x==1)cout<<1<<endl;
  else cout<<x*(x-1)<<endl;
 }
 return 0;
}

B. 奇迹

题目链接

https://www.luogu.org/problem/P5440

题解

搜索题好毒瘤啊QAQ

我们从日期第一位开始扫描,没有数字的位置枚举该填的数字填上。

填完所有数字后,先判断日期是否合法,再判断该日期是否满足题意要求即可。

这里为了方便,先使用线性筛在 \(O(n)\) 的时间内筛出了所有的质数。从而可以在 \(O(1)\) 的时间内判断任意一个数字是否是质数。

当然,在搜索中途就排除无效日期可以加快搜索效率。

#include <cstdio>
#include <algorithm>
using namespace std;
const int daynum[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int f[100000005],res[6000005],cnt,date[15],num,ans;
char s[15];
inline bool is_run(int y)
{
 if(y%4==0)
 {
  if(y%100==0)
  {
   if(y%400==0)return true;
   return false;
  }
  return true;
 }
 return false;
}
inline bool legal(int y,int m,int d)
{
 if(m>12||m==0||d==0||y==0)return false;
 if(m==2)
 {
  if(is_run(y))
  {
   if(d>29)return false;
   return true;
  }
  else
  {
   if(d>28)return false;
   return true;
  }
 }
 else
 {
  if(d>daynum[m])return false;
  return true;
 }
}
void dfs(int d)
{
 if(d==8)
 {
  int y=num/10000,m=(num%10000)/100,d=num%100;
  if(legal(y,m,d))
   if((!f[d])&&(!f[m*100+d])&&(!f[y*10000+m*100+d]))ans++;
  return;
 }
 if(date[d]!=-1)
 {
  num=num*10+date[d];
  dfs(d+1);
  num/=10;
  return;
 }
 for(int i=0;i<=9;i++)
 {
  if(d==4&&i==2)break;
  if(d==5&&i==0&&date[d-1]==0)continue;
  if(d==5&&date[4]*10+i>12)break;
  if(d==6&&i==4)break;
  date[d]=i;
  num=num*10+i;
  dfs(d+1);
  date[d]=-1;
  num/=10;
 }
}
int main()
{
 int t;
 scanf("%d",&t);
 f[0]=f[1]=1;
 for(long long i=2;i<=99991231;i++)
 {
  if(!f[i])res[++cnt]=i;
  for(long long j=1;j<=cnt&&i*res[j]<=99991231;j++)
  {
   f[i*res[j]]=1;
   if(i%res[j]==0)break;
  }
 }
 while(t--)
 {
  ans=0;
  scanf("%s",s);
  for(int i=0;i<8;i++)
  {
   if(s[i]=='-')date[i]=-1;
   else date[i]=s[i]-'0';
  }
  dfs(0);
  printf("%d\n",ans);
 }
 return 0;
}

发表评论

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