5月6日,CodeForces round 963
题目链接:http://codeforces.com/contest/963

总体难度蛮大,题目特别好,特别考察思维能力。

A – Alternating Sum

思路:
开始确实没有什么思路。看数据范围a,b,n都很大,只有k小一点。所以复杂度应该和k有关,与a,b,n无关。

然后往这个思路去想,就可以发现所求式子是一个等比数列。由于符号k个一循环,所以我们可以将每一个循环看作一项。然后就计算式子的首项和公比,运用等比数列求和公式求出答案。

代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAXN 100005
#define p 1000000009
#define LL long long
using namespace std;

LL n, a, b, k, a1, q, ans;
char opt[MAXN];

LL ksm(LL x, LL y)
{
    LL sum=1;
    while(y)
    {
        if(y&1) sum=(sum*x)%p;
        y>>=1; x=(x*x)%p;
    }
    return sum%p;
}

int main()
{
    scanf("%I64d%I64d%I64d%I64d", &n, &a, &b, &k);
    scanf("%s", opt);
    for(int i=0; i<k; i++) //计算首项
    {
        if(opt[i]=='+') a1=(a1+(ksm(a, n-i)*ksm(b, i))%p)%p;
        else a1=(a1-(ksm(a, n-i)*ksm(b, i))%p)%p;
        if(a1<0) a1+=p;
    }
    q=ksm(b, k)*ksm(ksm(a, k), p-2)%p; //计算公比
    if(q!=1) ans=a1*(ksm(q, (n+1)/k)-1)%p*ksm(q-1, p-2)%p; //用数学公式算出答案
    else ans=a1*(n+1)/k%p; //注意特判公比为1
    printf("%I64d\n", (ans+p)%p);
}

B – Destruction of a Tree

思路:
这道题也比较思维特别巧妙,我个人觉得其实有一点像树形DP。

首先从根节点遍历一遍树,用一个数组记录它儿子的个数。递归回去时如果它儿子是奇数个,那么该节点的度数就是偶数,所以可以将该节点删去,并将父亲节点的儿子个数-1。然后就这样递归到根节点,如果根节点度数时奇数,那就无解。

然后就考虑如何输出答案。首先肯定是把能够删除(度数为偶数)的先删去,这之后再把其他点删去。这个同样可以利用递归的思想,输出方案。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAXN 200005
using namespace std;

struct Edge {int to, next;} edge[MAXN*2];

int n, t, root, cnt, head[MAXN], son[MAXN], sta[MAXN], top;

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void dfs(int x, int f)
{
    son[f]++;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to!=f) dfs(to, x);
    }
    if(son[x]%2) son[f]--;
}

void dfs1(int x, int f) //输出方案
{
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to!=f && son[to]%2) dfs1(to, x);
    }
    printf("%d\n", x);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to!=f && son[to]%2==0) dfs1(to, x);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &t);
        if(t==0) root=i;
        else
        {
            addedge(i, t);
            addedge(t, i);
        }
    }
    dfs(root, 0);
    if(son[root]%2) printf("NO\n");
    else
    {
        printf("YES\n");
        dfs1(root, 0);
    }
}

C – Cutting Rectangle

思路:
首先如何计算答案并不难想到。求出所有c[i]的GCD,然后该数的约数个数就是答案。

但是判断无解情况就比较难想了。考虑能够构成矩形的条件,所有大矩形一定是通过若干单位矩形构成的。接下来我们便考虑单位矩形,当w相同时,不同的h在单位矩形中的个数与它的总个数是成比例的。也就是w[i]的数量:总数量=c[i]:h[i]的数量。只要有任何一种矩形不满足这个式子,就不存在单位矩形,即是无解。

代码:

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

LL n, sum, temp, ans, w[MAXN], h[MAXN], c[MAXN];
map<LL, LL> a, b; 

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

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld%lld%lld", &w[i], &h[i], &c[i]);
        a[w[i]]+=c[i]; b[h[i]]+=c[i];
        sum+=c[i]; temp=gcd(temp, c[i]);
    }
    for(int i=1; i<=n; i++) if(fabs((double)a[w[i]]/sum-(double)c[i]/b[h[i]])>1e-16)
    {
        printf("0");
        return 0;
    }
    for(LL i=1; i*i<=temp; i++)
    {
        if(temp%i==0) ans+=2;
        if(i*i==temp) ans--;
    }
    printf("%lld\n", ans);
}

发表评论

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