CF992A Nastya and an Array
答案为非零数的个数。
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
const int N=100005;
int n;
int a[N];
map<int,int>cnt;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
if(a[i]!=0) cnt[a[i]]++;
int k=cnt.size();
printf("%d",k);
return 0;
}
CF992B Nastya Studies Informatics
\[\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}\Leftrightarrow y=\frac{ab}{x}\Leftrightarrow xy=ab \]令 \(a=ix,b=jx\)，则 \(xy=ixjx\Leftrightarrow ij=\frac{y}{x}\)，枚举 \(k=\frac{y}{x}\) 的因数判断即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int l,r,x,y;
int main()
{
scanf("%d%d%d%d",&l,&r,&x,&y);
if(y%x!=0)
{
printf("0");
return 0;
}
int k=y/x;
int ans=0;
auto check=[=](int i,int j)
{
if(__gcd(i,j)!=1) return false;
return l<=1LL*x*i&&1LL*x*i<=r&&l<=1LL*x*j&&1LL*x*j<=r&&1LL*x*i*x*j==1LL*x*y;
};
for(int i=1;i<=sqrt(k);i++)
if(k%i==0)
{
if(check(i,k/i)) ans++;
if(i*i!=k&&check(k/i,i)) ans++;
}
printf("%d",ans);
return 0;
}
CF992C Nastya and a Wardrobe
考虑第 \(i\) 个月对第 \(k+1\) 个月的贡献，即为 \(2^{k-i}\)。所有月份的负的贡献为 \(\sum\limits_{i=1}^k2^{k-i}=2^k-1\)。
所有的总和为 \(x\cdot 2^{k+1}-(2^k-1)\)。
#include<iostream>
#include<cstdio>
using namespace std;
const int MOD=1000000007;
long long n,k;
long long ksm(long long a,long long b)
{
long long res=1;
while(b)
{
if(b&1) res=res*a%MOD;
a=a*a%MOD,b>>=1;
}
return res;
}
int main()
{
scanf("%lld%lld",&n,&k);
if(n==0)
{
printf("0");
return 0;
}
printf("%lld",(n%MOD*ksm(2,k+1)%MOD-ksm(2,k)+1+MOD)%MOD);
return 0;
}
CF992D Nastya and a Game
可以发现，最后的串中非 \(1\) 的数的个数不会很多，可以将所有连续的 \(1\) 缩成一段，然后枚举左端点暴力找右端点即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
const long long INF=2e18;
int n,k;
int a[N];
int ad[N],mu[N];
int m;
long long mul(long long a,long long b)
{
__int128 c=(__int128)a*b;
if(c>INF) return INF+1;
else return c;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1,j=1;i<=n;i=j)
{
while(j<=n&&a[i]==a[j]) j++;
if(a[i]==1) m++,ad[m]=j-i,mu[m]=1;
else
{
for(int k=i;k<j;k++)
m++,ad[m]=mu[m]=a[k];
}
}
long long ans=0;
for(int i=1;i<=m;i++)
{
long long fac=1,sum=0;
for(int j=i;j<=m;j++)
{
fac=mul(fac,mu[j]),sum+=ad[j];
if(fac>INF) break;
if(fac%k!=0) continue;
if(fac/k==sum) ans++;
else
{
long long num=fac/k;
int t=0,c=0;
if(mu[i]==1) t+=ad[i]-1,c+=ad[i];
if(mu[j]==1) t+=ad[j]-1,c+=ad[j];
if(sum-t<=num&&num<=sum)
{
if(mu[i]==1&&mu[j]==1)
{
int s=num-(sum-c);
int l=max(ad[i]-(s-1)+1,1),r=min(ad[i],ad[i]-1-(s-1-ad[j])+1);
ans+=r-l+1;
}
else ans++;
}
}
}
}
printf("%lld",ans);
return 0;
}
CF992E Nastya and King-Shamans
可以发现，如果 \(a_i\) 全为 \(0\)，\(a_i> s_{i-1}\) 的位置不会超过 $\log $ 个。线段树维护下每个区间 \(a_i-s_{i-1}\) 的最大值，如果最大值 \(< 0\) 就跳过，这样时间复杂度大概是两只 \(\log\) 的？
#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
int n,Q;
long long a[N];
long long s[N];
struct Node
{
int l,r;
long long Max,tag;
}tree[N<<2];
void push_up(int i)
{
tree[i].Max=max(tree[i*2].Max,tree[i*2+1].Max);
return;
}
void add(int i,long long v)
{
tree[i].Max+=v;
tree[i].tag+=v;
return;
}
void push_down(int i)
{
if(!tree[i].tag) return;
add(i*2,tree[i].tag);
add(i*2+1,tree[i].tag);
tree[i].tag=0;
return;
}
void build(int i,int l,int r)
{
tree[i].l=l,tree[i].r=r;
if(l==r)
{
tree[i].Max=a[l]-s[l-1];
return;
}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
push_up(i);
return;
}
void modify(int i,int l,int r,long long v)
{
if(l>r) return;
if(l<=tree[i].l&&tree[i].r<=r) return add(i,v);
push_down(i);
if(l<=tree[i*2].r) modify(i*2,l,r,v);
if(r>=tree[i*2+1].l) modify(i*2+1,l,r,v);
push_up(i);
return;
}
void query(int i,int &res)
{
if(res!=-1) return;
if(tree[i].Max<0) return;
if(tree[i].l==tree[i].r)
{
if(tree[i].Max==0) res=tree[i].l;
return;
}
push_down(i);
query(i*2,res);
query(i*2+1,res);
return;
}
int main()
{
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)
s[i]=s[i-1]+a[i];
build(1,1,n);
while(Q--)
{
int p,x;
scanf("%d%d",&p,&x);
modify(1,p+1,n,a[p]-x);
modify(1,p,p,x-a[p]);
a[p]=x;
int ans=-1;
query(1,ans);
printf("%d\n",ans);
}
return 0;
}