vfleaking神犇出的CF，时间真是良心
不过我真的是克服了很大的心里阴影才去做的啊
唉、、初三的时候真是太naive、、模域下的除法不求逆元就直接/掉了、、
Orz各位爷初三就黄名了
A The Child and Toy
每次删去一个点，付出的代价是与它有边相连的还未被删去的点权和，求最小代价
Solution：对每条边分析，这条边的代价是后删的那个点的点权，所以最优策略是先删点权较大的点
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int val[1005],u,v;
int n,m,i,j,k,ans;
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)scanf("%d",&val[i]);
for(i=1;i<=m;++i)
{
scanf("%d%d",&u,&v);
if(val[u]<val[v])ans+=val[u];
else ans+=val[v];
}
printf("%d\n",ans);
}
B The Child and Zoo
定义P（x,y）是x到y的所有路径中，经过的最小点权最大的路径的最小点权，求每对点的P(x,y)的平均值
Solution：NOIP货车运输，只是要求每对点了而已，还是用最大生成树，每次合并并查集的时候把两个连通块大小乘起来就是这个点权对答案的贡献
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int son[100005],next[200005],ed[200005];
int val[100005],id[100005],fa[100005],size[100005];
int n,m,u,v,i,j,k;
long long ans;
bool use[100005];
inline bool cmp(const int &a,const int &b){return val[a]>val[b];}
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)scanf("%d",&val[i]),id[i]=i,fa[i]=i,size[i]=1;
for(i=1;i<=m;++i)
{
scanf("%d%d",&u,&v);
next[i]=son[u];son[u]=i;ed[i]=v;
next[i+m]=son[v];son[v]=i+m;ed[i+m]=u;
}
sort(id+1,id+n+1,cmp);
for(i=1;i<=n;++i)
{
k=id[i];
use[k]=true;
for(j=son[k];j;j=next[j])
if(use[ed[j]])
{
u=get(k);
v=get(ed[j]);
if(u!=v)
{
ans+=((long long)val[k])*size[u]*size[v];
fa[u]=v;
size[v]+=size[u];
}
}
}
printf("%.9lf\n",((double)ans)/n/(n-1)*2);
}
C The Child and Polygon
D The Child and Sequence
3中操作:对一段区间求和；对一段区间mod一个数；修改一个点的权值；
Solution：考虑取模运算对每个数的影响，一个数mod x之后，如果这个数比x大，那么这个数至少减少x，且减少到x以下，所以取模运算对每个数的影响是和/2相当的，然后就是经典问题SPOJ GSS4了
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int n,m,i,j,k,ll,rr,key,aim,opt;
long long sum[1000005],Max[1000005],ans;
void build(int p,int l,int r)
{
if(l==r)
{
scanf("%I64d",&sum[p]);
Max[p]=sum[p];
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
sum[p]=sum[p<<1]+sum[p<<1|1];
Max[p]=max(Max[p<<1],Max[p<<1|1]);
}
void C(int p,int l,int r)
{
if(Max[p]<key)return;
int mid=l+r>>1;
if(l>=ll&&r<=rr)
{
if(l==r)
{
sum[p]%=key;
Max[p]=sum[p];
return;
}
C(p<<1,l,mid);
C(p<<1|1,mid+1,r);
sum[p]=sum[p<<1]+sum[p<<1|1];
Max[p]=max(Max[p<<1],Max[p<<1|1]);
return;
}
if(rr<=mid)C(p<<1,l,mid);
else if(ll>mid)C(p<<1|1,mid+1,r);
else C(p<<1,l,mid),C(p<<1|1,mid+1,r);
sum[p]=sum[p<<1]+sum[p<<1|1];
Max[p]=max(Max[p<<1],Max[p<<1|1]);
}
void Q(int p,int l,int r)
{
if(l>=ll&&r<=rr)
{
ans+=sum[p];
return;
}
int mid=l+r>>1;
if(rr<=mid)Q(p<<1,l,mid);
else if(ll>mid)Q(p<<1|1,mid+1,r);
else Q(p<<1,l,mid),Q(p<<1|1,mid+1,r);
}
void A(int p,int l,int r)
{
if(l==r)
{
sum[p]=Max[p]=key;
return;
}
int mid=l+r>>1;
if(aim<=mid)A(p<<1,l,mid);
else A(p<<1|1,mid+1,r);
sum[p]=sum[p<<1]+sum[p<<1|1];
Max[p]=max(Max[p<<1],Max[p<<1|1]);
}
int main()
{
scanf("%d%d",&n,&m);
build(1,1,n);
for(;m;--m)
{
scanf("%d",&opt);
if(opt==1)
{
ans=0;
scanf("%d%d",&ll,&rr);
Q(1,1,n);
printf("%I64d\n",ans);
}
if(opt==2)
{
scanf("%d%d%d",&ll,&rr,&key);
C(1,1,n);
}
if(opt==3)
{
scanf("%d%d",&aim,&key);
A(1,1,n);
}
}
}
E The Child and Binary Tree
评论 (0)
