csp-s模拟测试94「凉宫春日的犹豫·漫无止境的八月·射手座之日」
rtrt
3月 14, 2025
归档于 2019-11-01 19:21
凉宫春日的犹豫
题解
第一次秒切题,5分钟切掉
比较$x^y$和$y!$大小
如果$x^y<y!$输出Yes
问题转化为
$\frac{1}{x} \frac{2}{x}\frac{3}{x},,,,,*\frac{y}{x}>=1$输出$Yes$
开双端队列维护,一直保持单调,然后让队首*队尾就行了
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 111111
long double zhajing;
double x,y;
ll t;
deque<long double> q;
int main(){
freopen("yuuutsu.in","r",stdin);
freopen("yuuutsu.out","w",stdout);
scanf("%lld",&t);
while(t--){
scanf("%lf%lf",&x,&y);
zhajing=1.0;
while(q.size()) q.pop_front();
for(double i=1;i<=y;i++){
q.push_back(i/x);
}
while(q.size()>=2){
long double x1=q.front(),x2=q.back(),now;
q.pop_front(),q.pop_back();
now=x1*x2;
if(now<x1){
q.push_front(now);
}
else {
q.push_back(now);
}
}
long double now=q.front();
if(now>=1.0000000000000){
printf("Yes\n");
}
else printf("No\n");
}
}
View Code
漫无止境的八月
题解
其实都是套路,映射到最后一块然后线段树维护
考场水掉了QwQ
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 2100000
ll cha[A],a[A],thelast[A];
ll n,k,q,l,r,minn,maxx;
ll abs_(ll x){
if(x<0) return -x;
return x;
}
struct node{
ll l,r,mn,mx;
}tr[A*8];
void built(ll x,ll l,ll r){
tr[x].l=l,tr[x].r=r;
if(l==r){
tr[x].mn=tr[x].mx=cha[l];
return ;
}
ll mid=(l+r)>>1;
built(x<<1,l,mid);
built(x<<1|1,mid+1,r);
}
void change(ll x,ll pla,ll val){
if(tr[x].l==tr[x].r){
tr[x].mn+=val;
tr[x].mx+=val;
return ;
}
ll mid=(tr[x].l+tr[x].r)>>1;
if(mid>=pla) change(x<<1,pla,val);
else change(x<<1|1,pla,val);
tr[x].mn=min(tr[x<<1].mn,tr[x<<1|1].mn);
tr[x].mx=max(tr[x<<1].mx,tr[x<<1|1].mx);
}
void seg_ask(ll x,ll l,ll r){
if(tr[x].l>=l&&tr[x].r<=r){
maxx=max(maxx,tr[x].mx);
minn=min(minn,tr[x].mn);
return ;
}
ll mid=(tr[x].l+tr[x].r)>>1;
if(mid>=l) seg_ask(x<<1,l,r);
if(mid<r) seg_ask(x<<1|1,l,r);
}
void workbf(){
for(ll p=0;p+k<=n;p++){
if(cha[p]<0){
ll x=abs_(cha[p]);
cha[p]+=x;
cha[p+k]-=x;
}
if(cha[p]>0){
ll x=abs_(cha[p]);
cha[p]-=x;
cha[p+k]+=x;
}
}
ll ok=1;
for(ll p=0;p<=n;p++){
if(cha[p]){
ok=0;
break;
}
}
if(ok) printf("Yes\n");
else printf("No\n");
}
void worksol(){
for(ll p=0;p+k<=n;p++){
if(cha[p]<0){
ll x=abs_(cha[p]);
cha[p]+=x;
cha[thelast[p]]-=x;
}
if(cha[p]>0){
ll x=abs_(cha[p]);
cha[p]-=x;
cha[thelast[p]]+=x;
}
}
ll ok=1;
for(ll p=0;p<=n;p++){
if(cha[p]){
ok=0;
break;
}
}
if(ok) printf("Yes\n");
else printf("No\n");
}
int main(){
freopen("august.in","r",stdin);
freopen("august.out","w",stdout);
scanf("%lld%lld%lld",&n,&k,&q);
for(ll i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(ll i=0;i<=n;i++)
cha[i]=a[i]-a[i+1];
for(ll i=0;i<=n;i++){
ll l=0,r=n,ans;
while(l<=r){
ll mid=(l+r)>>1;
if(i+mid*k<=n){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
thelast[i]=ans*k+i;
}
if(q<=2000)workbf();
else worksol();
built(1,0,n);
for(ll i=1;i<=q;i++){
ll pla,dx;
scanf("%lld%lld",&pla,&dx);
{
change(1,thelast[pla],dx);
change(1,thelast[pla-1],-dx);
maxx=0,minn=0;
seg_ask(1,n-k+1,n);
if(maxx==0&&minn==0){
printf("Yes\n");
}
else printf("No\n");
}
}
}
View Code
射手座之日
题解
先解释为什么要差分
思考dfs序包含一段区间,你可能找到的是祖先,不是最近的
然后差分转化权值$p[i]=w[i]-w[fa[i]]$
例如一棵树
现在算3点贡献,你在2时算一次,1算一次贡献
在3时贡献$w[3]-w[2]$在二算$w[2]-w[1]$,在一算$w[1]-w[0]$
在一条链时,你把除了最近公共祖先贡献都消掉了,最后一定会归到第一个节点,
再例如算3,4,你在2算时贡献是$w[2]-w[1]$,在1$w[1]-w[2]$,你把除了最近公共祖先贡献都消掉了
然后现在就可以对于每个节点算了,而不用考虑是否满足最近条件
现在问题转化成了,对于一个节点,有多少区间,每一个区间贡献是(len)*(len-1)/2(即所有区间个数)
然后线段树维护即可
代码
#include<bits/stdc++.h>
using namespace std;
#define A 12222222
#define ll long long
ll w[A],rt[A],d[A],a[A],c[A],pos[A],head[A],nxt[A],ver[A];
ll n,ans,tot;
struct tree{
ll l,r,lw,rw,tw;
}tr[A];
void add(ll x,ll y){
nxt[++tot]=head[x],head[x]=tot,ver[tot]=y;
}
void update(ll x,ll l,ll r){
tr[x].lw=tr[tr[x].l].lw,tr[x].rw=tr[tr[x].r].rw;
ll mid=(l+r)>>1;
if(tr[x].lw==mid-l+1) tr[x].lw+=tr[tr[x].r].lw;
if(tr[x].rw==r-mid) tr[x].rw+=tr[tr[x].l].rw;
tr[x].tw=tr[tr[x].l].tw+tr[tr[x].r].tw+tr[tr[x].l].rw*tr[tr[x].r].lw;
}
void insert(ll &x,ll l,ll r,ll id){
if(!x) x=++tot;
if(l==r){tr[x].lw=tr[x].rw=tr[x].tw=1;return ;}
ll mid=(l+r)>>1;
if(mid>=id) insert(tr[x].l,l,mid,id);
else insert(tr[x].r,mid+1,r,id);
update(x,l,r);
}
ll merge(ll x,ll k,ll l,ll r){
if(!x||!k) return x|k;
ll mid=(l+r)>>1;
tr[x].l=merge(tr[x].l,tr[k].l,l,mid);
tr[x].r=merge(tr[x].r,tr[k].r,mid+1,r);
update(x,l,r);
return x;
}
void dfs(ll x,ll pre){
insert(rt[x],1,n,pos[x]);
c[x]=w[x]-w[pre];
for(ll i=head[x];i;i=nxt[i]){
ll y=ver[i];
if(y==pre) continue;
dfs(y,x);
rt[x]=merge(rt[x],rt[y],1,n);
}
ans+=c[x]*tr[rt[x]].tw;
}
int main(){
freopen("sagittarius.in","r",stdin);
freopen("sagittarius.out","w",stdout);
scanf("%lld",&n);
for(ll i=2,x;i<=n;i++)
scanf("%lld",&x),add(i,x),add(x,i);
for(ll i=1;i<=n;i++)
scanf("%lld",&d[i]),pos[d[i]]=i;
for(ll i=1;i<=n;i++)
scanf("%lld",&w[i]);
dfs(1,0);
printf("%lld\n",ans);
}
View Code