Codeforces Round #554 (Div. 2) 选做

C. Neko does Maths

题意

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

\(a,b\le 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\) 的合法括号序列放到 \(\text{trie}\) 里，求 \(\text{trie}\) 树的最大匹配，对 \(10^9+7\) 取模。

\(n\le 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);

}

巴特西

Codeforces Round #554 (Div. 2) 选做

C. Neko does Maths

题意

题解

code

D. Neko and Aki's Prank

题意

题解

最新文章

热门文章