C

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

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

typedef long long ll;

ll ans=0;

ll mn;

ll a, b;

void work(ll x){

    ll k = (x-a%x)%x;

    ll aa = k+a, bb = k+b;

    ll temp = aa/__gcd(aa, bb)*bb;

    if(temp<mn){

        ans = k;

        mn = temp;

    }

    else if(temp == mn &&ans>k){

        ans = k;

    }

}

int main(){

    scanf("%lld%lld", &a, &b);

    if(a>b) swap(a, b);

    if(a == b){

        printf("0\n");

        return 0;

    }

    mn = a/__gcd(a, b)*b;

    ll d = b-a;

    for(int i=1; i*i<=d; ++i){

        if(d%i==0){

            work(1ll*i), work(1ll*d/i);

        }

    }

    printf("%lld\n", ans);

    return 0;

}

D

题意

括号串形成的trie树的最大的匹配（选择的两条边不能有公共的节点）。

记忆化dp

奇数层必定有孩子，因此只能取得一个边

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e3+10;

typedef long long ll;

const int mod = 1e9+7;

int dp[maxn][maxn];

//奇数层一定有孩子

int dfs(int n, int now){

    if(n == 0){

        if(now == 0) return dp[n][now] = 0;

        else return dp[n][now] = -2;

    }

    if(dp[n][now]!=-1) return dp[n][now];

    if(n<now||now<0) return dp[n][now] = -2;

    ll temp = 0;

    bool has = false;

    if(dfs(n-1, now+1)>=0){

        temp += dp[n-1][now+1]+(n%2==0);

        has = true;

    }

    if(dfs(n-1, now-1)>=0){

        temp += dp[n-1][now-1]+(n%2==0);

        has = true;

    }

    if(has){

        return dp[n][now] = temp%mod;

    }

    else return dp[n][now] = -2;

}

int main(){

    int n;

    scanf("%d", &n);

    memset(dp, -1, sizeof(dp));

    dfs(2*n, 0);

    printf("%d\n", dp[2*n][0]);

    return 0;

}

巴特西

codeforces1152 div2

C

D

题意

最新文章

热门文章