Codeforces Round #554 (Div. 2) 选做

C. Neko does Maths

题意

给 (a,b) ，求一个最小的 (k) 使得 ( ext{lcm}(a+k,b+k)) 最小。

(a,ble 10^9)

题解

(gcd (a+k,b+k) = gcd(b-a,a+k)) 。

只需枚举 (b-a) 的因数作为 (gcd) ，容易算出最小的 (k) ，然后更新答案即可。

code

#include<cstdio>
long long mn=1ll<<60;
int a,b,k;
inline int gcd(int x, int y) {
	return y?gcd(y,x%y):x;
}
void solve(int x)
{
	int y=((a-1)/x+1)*x-a;
	long long tmp=1ll*(a+y)*(b+y)/gcd(a+y,b+y);
	if(tmp<mn) mn=tmp,k=y;
}
int main()
{
	scanf("%d%d",&a,&b);
	if(a>b) a^=b^=a^=b;
	const int c=b-a;
	for(int i=1;i*i<=c;++i)
		if(c%i==0)
		{
			solve(i);
			if(i*i!=c) solve(c/i);
		}
	printf("%d",k);
}

D. Neko and Aki's Prank

题意

给 (n) ，将长度为 (2n) 的合法括号序列放到 ( ext{trie}) 里，求 ( ext{trie}) 树的最大匹配，对 (10^9+7) 取模。

(nle 1000)

题解

可以考虑直接 dp 最大匹配，但这样会涉及取 (max) 操作，显然是不行的。

我们考虑贪心匹配，每次把第 (2n-1) 层的点全部向第 (2n) 点匹配，然后第 (2n-3) 层的点全部向第 (2n-2) 层的点匹配。以此类推。这样答案就为深度为奇数的点的个数。

设 (f[i][j]) 为深度为 (i) ，有 (j) 个左括号的点的个数。注意右括号个数始终不能超过左括号个数，左括号个数不能 (>n) 。转移显然。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2005,Mod=1e9+7;
int f[N][N];
int main()
{
	int n,ans=0;
	scanf("%d",&n),n<<=1;
	f[0][0]=1;
	for(int i=1;i<=n;++i)
		for(int j=0;j<=i;++j) // ( : j
		{
			if(j>n/2) continue;
			int k=i-j; // ) : k
			if(j>=1&&j-1>=k) f[i][j]=(f[i][j]+f[i-1][j-1])%Mod;
			if(k>=1&&j>k-1) f[i][j]=(f[i][j]+f[i-1][j])%Mod;
			ans=(ans+(i%2==1)*f[i][j])%Mod;
		}
	printf("%d",ans);
}