cf 1152部分题解

https://codeforces.com/contest/1152
c题
找到最小的k使得lcm(a+k,b+k)最小
思路：
lcm=(a+k)(b+k)/gcd(a+k,b+k) = (a+k)(b+k)/gcd(a+k,b-a)，枚举b-a因数即可，由于答案在所有因数的集合里，我们只需要让k最小就行了，这时的k需要满足a+k=b-a。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
signed main()
{
    int a,b;
    cin>>a>>b;
    if(a>b)
    swap(a,b);
    int res=a*b/gcd(a,b);
    int resk=0;
    for(int i=1;i*i<=b-a;i++)
    {
        if((b-a)%i==0)
        {
            int k=(i-a%i)%i;
            if((a+k)*(b+k)/i<res || ((a+k)*(b+k)/i==res && i<resk))
            {
                resk=k;
                res=(a+k)*(b+k)/i;
            }
            int ii=(b-a)/i;
            k=(ii-a%ii)%ii;
            if(i!=ii)
            {
                if((a+k)*(b+k)/ii<res || ((a+k)*(b+k)/ii==res && ii<resk))
            {
                resk=k;
                res=(a+k)*(b+k)/ii;
            }
            }
        }
    }
    cout<<resk<<endl;
    return 0;
}

d题
一开始没看懂题意，看了百度，不小心看到tag，题意是给你个n，所有合法括号序列构造出来的trie树，你要将边染色，求最大的边的数量。
看了题解，直接引用结论，通过贪心，从叶子节点往上找就行了，由于是个二叉树并且叶子节点的深度都是一样的，画画图可以得出是偶数层的节点数量，通过dp递推出每一层的数量，dp[i][j]代表到了第i层平衡因子为j（左括号减去右括号的数量）的方案数，转移就是

            dp[i][j]+=dp[i-1][j-1];
            dp[i][j]+=dp[i-1][j+1];

然后把每一层的每一种情况对应节点加到cnt数组里，最后对偶数层进行计数就行了，要记得特判一下不可能的情况，就是下面要是全取右括号都不能满足左右括号相等的情况应该剔除。
感觉就是有点计数dp那味了，如何不重不漏的计算偶数层的节点数量，通过平衡因子来划分每个集合，不漏，每种情况存在且存在其中的一种情况，不漏。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int res;
int dp[2010][2010];
int cnt[2010];
const int mod=1e9+7;
signed main()
{
    dp[0][0]=1;
    int n;
    cin>>n;
    for(int i=1;i<=n*2;i++)
        for(int j=0;j<=n;j++)
        {
            if(j-(2*n-i)>0)    continue;
            if(j>=1)
            dp[i][j]+=dp[i-1][j-1];
            dp[i][j]+=dp[i-1][j+1];
            dp[i][j]%=mod;
            cnt[i]= (cnt[i]+dp[i][j])%mod;
        }
    // for(int i=1;i<=2*n;i++)
    //     cout<<cnt[i]<<" ";
    // cout<<endl;
    for(int i=1;i<=2*n;i+=2)
        res=(res+cnt[i])%mod;
    cout<<res<<endl;
    return 0;
}