6月19日 Codeforces Round #489
题目链接:http://codeforces.com/contest/992

A – Nastya and an Array

过水,不多说。

B – Nastya Studies Informatics

思路:
思路比较暴力,一开始以为不是正解,复杂度似乎是$O(\sqrt{n}log(n))$。

首先想到的便是暴力枚举,枚举a,b则可以通过计算得到($b=xy/a$),然后判断$a,b$是否再范围内并且$gcd(a,b)$是否等于x。

然后便发现可以优化,可以将l,r,y同除x(注意取整)。如果x,y互素,则一定为0。然后就可以从1枚举到$\sqrt{y/x}$,判断a,b是否互素。

代码:

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

LL l, r, x, y, s, ans;

bool check(LL a, LL b)
{
    if(a>=l && a<=r && b>=l && b<=r) return true;
    else return false;
}

int main()
{
    cin>>l>>r>>x>>y;
    if(y%x!=0) 
    {
        printf("0\n");
        return 0;
    }
    l=(l+x-1)/x; r=r/x; y/=x;
    for(int i=1; i<=sqrt(y); i++)
    {
        if(y%i!=0) continue;
        int j=y/i; 
        if(check(i, j) && __gcd(i, j)==1)
        {
            if(i*i==y) ans++;
            else ans+=2;
        }
    }
    cout<<ans<<endl;
}

C – Nastya and a Wardrobe

思路:
结果还是数学题,我们可以考虑所有情况,k个月时可能的衣服数量是从$n*2^k$到$(n-1)*2^k+1$。

因为它们是等概率分布。所以答案是$n*2^k+(n-1)*2^k+1$。

代码:

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

LL n, k;

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

int main()
{
    cin>>n>>k;
    if(n==0) cout<<0;
    else cout<<((n%p*ksm(2, k))%p+((n-1)%p*ksm(2, k))%p+1)%p;
}

D – Nastya and a Game

思路:
就是暴力啊。。比赛时想到了$O(n*n)$的暴力,其实稍微改一下就能A了。$O(n*n)$的暴力是这样的:先枚举L,记录下从L开始的乘积以及总和,只要符合要求就更新答案。

但是这样就会出现一些问题,首先是乘积会炸longlong,但是由于数据是构造好了的,只要乘积大于了10^18是一定不符合要求的,这时候就可以break了。、

这样的复杂度是不符合要求的,如果序列全是1,复杂度还是$O(n*n)$的。但是我们考虑因为1是不会影响乘积的,如果我们把序列中的1去掉,同样的暴力方法,最多枚举64个数字(64个数字全是2)就一定会break。这样的话,最坏复杂度就是$O(64*n)$。

最后,判断符合要求时要考虑序列中删去的1,写个check()函数就好了。

代码:

#include <bits/stdc++.h>
#define LL long long
#define INF 1e18
using namespace std;

LL n, k, a[200005], nxt[200005], ans;

bool check(LL sum, LL pro, LL len)
{
    LL temp=pro-sum*k;
    if(temp%k) return false;
    if(temp/k>=0 && temp/k<=len) return true;
    else return false;
}

int main()
{
    cin>>n>>k;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=n, pos=n+1; i>=1; i--)
    {
        nxt[i]=pos;
        if(a[i]>1) pos=i;
    }
    for(int i=1; i<=n; i++)
    {
        LL pro=1, sum=0;
        for(int j=i; j<=n; j=nxt[j])
        {
            if(pro>=INF/a[j]) break;
            pro*=a[j]; sum+=a[j];
            if(check(sum, pro, nxt[j]-j-1)) ans++;
            sum+=nxt[j]-j-1;
        }
    }
    cout<<ans<<endl;
}

E – Nastya and King-Shamans

思路:
超级神奇的数据结构题,在一个半月后终于A了。。前缀和处理应该不难想到,由于涉及修改操作,所以我们用树状数组维护前缀和。所以我们对于每一个询问要找到一个位置$x$,使得$sum[x-1]*2=sum[x]$($sum$为前缀和)。

我们查找位置$x$可以利用分治的思想。对于任意一个区间$[l,r]$($l<r$),如果$sum[l]*2>sum[r]$,不难发现这个区间内一定不会存在$x$。于是我们可以将整个区间$[0,n]$不断分治,直到找到位置$x$。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
#define INF 1e18
#define MAXN 200005
using namespace std;

int n, q;
LL t[MAXN], a[MAXN];

void add(int x, LL y) {for(; x<=n; x+=(x&-x)) t[x]+=y;}

LL query(int x) {LL y=0; for(; x; x-=(x&-x)) y+=t[x]; return y;}

int find(int l, int r)
{
    int pos=-1, mid=(l+r)>>1;
    if(l+1==r) return query(l)*2==query(r)? r:-1;
    if(query(l)*2<=query(mid)) pos=max(pos, find(l, mid));
    if(pos!=-1) return pos;
    if(query(mid)*2<=query(r)) pos=max(pos, find(mid, r));
    return pos;
}

int main()
{
    scanf("%d%d", &n, &q);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld", &a[i]);
        add(i, a[i]);
    }
    for(int i=1; i<=q; i++)
    {
        int p;LL x;
        scanf("%d %lld", &p, &x);
        add(p, x-a[p]); a[p]=x;
        printf("%d\n", find(0, n));
    }
}

发表评论

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