首页 > 代码库 > AC日记——[国家集训队2010]小Z的袜子 cogs 1775
AC日记——[国家集训队2010]小Z的袜子 cogs 1775
[国家集训队2010]小Z的袜子
思路：
传说中的莫队算法（优雅的暴力）；
莫队算法是一个离线的区间询问算法；
如果我们知道[l,r]，
那么，我们就能O(1)的时间求出(l-1,r),(l+1,r),(l,r-1),(l,r+1);
莫队算法怎么保证时间呢?
把询问排序;
然后进行暴力;
但是这样仍然需要很长很长的时间;
所以,我们引入一个根号方法,分块;
把区间的点分块;
然后每个询问的l,r按l所属的块为第一关键字,l,r为第二第三;
排序完后,就可以保证复杂度是O(n*sqrt(n));
然后再看这个题目本身;
询问l,r中的同种颜色袜子的概率;
稍微思考一下便可列出式子:
a1*(a1-1)+a2*(a2-1)+...+ai*(ai-1)/(r-l+1)*(r-l)
ai为第i种颜色的个数;
改变一下就可以得到:
a1*a1+a2*a2+...+ai*ai-a1-a2-...-ai/(r-l+1)*(r-l)
因为每种颜色袜子的总个数为r-l+1,所以:
a1*a1+a2*a2+...+ai*ai-r+l-1/(r-l+1)*(r-l)
来,上代码:
#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define maxn 50005#define ll long longstruct QueryType { ll l,r,id;};struct QueryType qu[maxn];ll n,m,col[maxn],ans[maxn],pos=0,fa[maxn],num[maxn],bel[maxn],size;inline void in(ll &now){ char Cget=getchar();now=0; while(Cget>‘9‘||Cget<‘0‘) Cget=getchar(); while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); }}bool cmp(QueryType iposa,QueryType iposb){ if(bel[iposa.l]==bel[iposb.l]) return iposa.r<iposb.r; else return iposa.l<iposb.l;}inline void updata(ll now,ll dis){ now=col[now]; pos-=num[now]*num[now]; num[now]+=dis; pos+=num[now]*num[now];}ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}int main(){ freopen("hose.in","r",stdin); freopen("hose.out","w",stdout); in(n),in(m);size=sqrt(n); for(ll i=1;i<=n;i++) in(col[i]),bel[i]=(i-1)/size; for(ll i=1;i<=m;i++) in(qu[i].l),in(qu[i].r),qu[i].id=i; sort(qu+1,qu+m+1,cmp); ll li=1,ri=0; for(ll j=1;j<=m;j++) { if(ri>qu[j].r) for(ll i=ri;i>qu[j].r;i--) updata(i,-1); else for(ll i=ri+1;i<=qu[j].r;i++) updata(i,1); if(li>qu[j].l) for(ll i=li-1;i>=qu[j].l;i--) updata(i,1); else for(ll i=li;i<qu[j].l;i++) updata(i,-1); ri=qu[j].r,li=qu[j].l,ans[qu[j].id]=pos-(ri-li+1); if(qu[j].r-qu[j].l>=2) fa[qu[j].id]=(ri-li+1)*(ri-li); } for(ll i=1;i<=m;i++) { if(fa[i]==0||ans[i]==0) { printf("0/1\n"); continue; } ll o=gcd(fa[i],ans[i]); printf("%lld/%lld\n",ans[i]/o,fa[i]/o); } return 0;}
AC日记——[国家集训队2010]小Z的袜子 cogs 1775
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。