6月19日 Codeforces Round #489 题目链接：http://codeforces.com/contest/992
A - Nastya and an Array
过水，不多说。
思路： 思路比较暴力，一开始以为不是正解，复杂度似乎是$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是否互素。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #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$。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #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()函数就好了。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #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]$($lsum[r]$，不难发现这个区间内一定不会存在$x$。于是我们可以将整个区间$[0,n]$不断分治，直到找到位置$x$。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #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));
}
}
|