相信奇迹的人,本身就和奇迹一样了不起。
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; }
C. 伤痕
题目链接
https://www.luogu.org/problem/P5441
题解
考虑计算不合法的方案数。
什么时候选出的四个点会不强连通呢?
- 一个点向另外三个点各引一条单向边,记这样的四元组的数量为 \(T\);
- 三个点向同一个点引一条单向边;
- AB 和 CD 间都是无向边,但 A 向 C 和 D 引单向边,B 向 C 和 D 引单向边。
记点 \(i\) 引的单向边有 \(S_i\) 条。
则有:
$$T=\sum_{i=1}^n C_{S_i}^3 \geq n \times C_{\frac{n-3}{2}}^3$$
从而 \(T\) 有最小值 \(n \times C_{\frac{n-3}{2}}^3\),也即合法方案数的最大值为:
$$C_4^n – n \times C_{\frac{n-3}{2}}^3 = \frac{n \times (n-3) \times (n^2+6n-31)}{48}$$
怎么构造方案来达到这个最大值呢?
一种构造方案(也是官方题解的构造方案)是这样的:在圆内接 \(n\) 边形内,所有最长的对角线连双向边,而每个点则向顺时针方向的 \(\frac{n-3}{2}\) 个点引一条有向边。
显然这时候没有第二类不强连通的四元组,第三类呢?因为对于每个点,只向接下来 \(\frac{n-3}{2}\) 个点引单向边,所以第三类四元组也不存在。
这时候的合法方案数也就是最大值了。
#include <cstdio> #include <cstring> int a[105]; int main() { int n; scanf("%d",&n); if(n==1) { puts("0\n0"); return 0; } printf("%d\n",n*(n-3)*(n*n+6*n-31)/48); for(int i=1;i<=n;i++) { memset(a,0,sizeof(a)); for(int j=1;j<=(n+1)/2;j++) a[(i+j-1)%n+1]=1; for(int j=1;j<=n;j++) printf("%d ",a[j]); puts(""); } return 0; }