·9月4日 Codeforces Round #505
题目链接:http://codeforces.com/contest/1025

A – Doggo Recoloring

过水,就不说了。。

B – Weakened Common Divisor

思路:
首先我们不难想到将每一对数乘起来,然后求这些乘积的GCD,如果这个GCD为1则应该输出-1。但是这个GCD不一定是答案,但答案一定是这个GCD的约数。这时我就想到了找这个GCD最小的约数做为答案,但这样是会T的。于是我们考虑造成GCD不一定是答案的原因,然后我们可以将这个GCD与每一对中的一个数再求一遍GCD,这样的答案就是符合要求的了。

代码:

#include <bits/stdc++.h>
#define MAXN 150005
#define LL long long
using namespace std;

int n;
LL a[MAXN], b[MAXN], c[MAXN];

LL gcd(LL x, LL y)
{
    return y==0?x: gcd(y, x%y);
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld%lld", &a[i], &b[i]);
        c[i]=a[i]*b[i];
    }
    LL ans=c[1];
    for(int i=2; i<=n; i++) ans=gcd(ans, c[i]);
    if(ans==1) printf("-1\n");
    else
    {
        for(int i=1; i<=n; i++)
        {
            if(gcd(ans, a[i])>=1) ans=gcd(ans, a[i]);
            else ans=gcd(ans, b[i]);
        }
        printf("%lld\n", ans);
    }
}

C – Plasticine zebra

思路:
一开始什么思路都没有,卡了很久。后面有一种直觉就是如果头和尾相等,那么如何翻转都是不会增加答案的(虽然一直不会证明)。

设$1-i$的字符串为’zebra’,这样的话只要头尾不相等,在位置$i$进行一次操作,这样’zebra’的长度一定会增加。由于开始提到的‘直觉’,只要操作后头和尾相等就break出循环。

后面看了题解后,就更加奇怪了,不明白自己这种乱搞的做法为什么是对的。

代码:

#include <bits/stdc++.h>
#define MAXN 100005
#define LL long long
using namespace std;

char a[MAXN];
int ans=1, n, f[MAXN];

void print()
{
    for(int i=0; i<n; i++) printf("%c", a[i]);
    printf("\n");
}

int main()
{
    scanf("%s", a);
    n=strlen(a);
    for(int i=0; i<n; i++)
    {
        if(a[0]==a[n-1]) break;
        if(a[i]==a[i+1])
        {
            reverse(a, a+i+1);
            reverse(a+i+1, a+n);
        }
    }
    f[0]=1;
    for(int i=1; i<n; i++)
    {
        if(a[i]==a[i-1]) f[i]=1;
        else f[i]=f[i-1]+1;
        ans=max(ans, f[i]);
    }
    printf("%d\n", ans);
}

D – Recovering BST

思路:
其实这和平衡树并没有半毛钱关系,只是根据BST的性质让你做区间DP。

对于一个递增序列,你可以任意选一个数作为BST的根,这个数将序列分为两部分,分别作为这个根的左子树和右子树。然后这两个部分又是递增序列,于是可以这样递归下去DP。

大致的思路是这样,但要注意一些细节。首先是要记忆化以保证复杂度,然后就是要记录自己序列是在左子树还是右子树,以便判断是否符合要求(也就是边两端的数GCD>1)。

代码:

#include <bits/stdc++.h>
#define MAXN 705
#define LL long long
using namespace std;

int n, f[MAXN][MAXN][2], a[MAXN];

int gcd(int x, int y)
{
    return y==0? x:gcd(y, x%y);
}

bool dp(int l, int r, int k, int fa)
{
    if(f[l][r][k]!=-1) return f[l][r][k];
    if(l==r) return 1;
    if(k==0)
    {
        for(int i=l; i<r; i++)
            if(gcd(a[i], a[r])>1 && dp(l, i, 0, i) && dp(i, r-1, 1, i)) return f[l][r][k]=1;
    }
    else
    {
        for(int i=l+1; i<=r; i++)
            if(gcd(a[l], a[i])>1 && dp(l+1, i, 0, i) && dp(i, r, 1, i)) return f[l][r][k]=1;
    }
    return f[l][r][k]=0;
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    memset(f, -1, sizeof(f));
    for(int i=1; i<=n; i++)
        if(dp(1, i, 0, i) && dp(i, n, 1, i))
        {
            printf("Yes\n");
            return 0;
        }
    printf("No\n");
}

发表评论

邮箱地址不会被公开。 必填项已用*标注