注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 1998(hnoi2010) 物品调度  

2013-02-21 22:46:45|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

被题意折磨了好久……

被不会做折磨了好久……

然后调试又调试了好久……

 

何朴帆大神那个我从没听说过的什么跳转链表,跟并查集有什么区别???

不就是并查集吗囧……

 

这题解真的不想写啊……

何朴帆写的那么详细了都!!

不过一想到这也是自己的总结……我认了!呜呜……

 

题目分两问,第一问是求出pos,第二问是求最小值

 

第一问

现在就是有了若干参数,再y为第一关键字x为第二关键字中找没有选过的数。我们先让y=0,如果无解再让y=1,那么怎么迅速判断呢?

用两个并查集,第一个并查集有gcd(n,d)个元素,第二个并查集有n个元素。如果在第二个并查集中要把一个选掉p的数删了,我们就把p与(p+d)%n合并。对于每一个y的取值,x的各种变化都只能得到n/gcd(n,d)个数,所以如果这n/gcd(n,d)个数已经选完了,就把第一个并查集中的这个y与(y+1)%gcd(n,d)合并。

 

第二问

这是个置换群题目,结论就是把所以长度为1的乘积去掉(显然吧),如果一个乘积长度为L,这当中如果含有0呢,只要换L-1次(显然吧),否则换L+1次(还是很显然吧)

 

大家去看hpf的吧……

国家集训队2011年的…………

都有那么详细的题解了我在这里写不是自虐么

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 100010
using namespace std;
typedef long long LL;
LL c[MAXN];
int Fx[MAXN],Fy[MAXN],tot[MAXN];
int pos[MAXN],n,s,q,p,m,d,k;
bool use[MAXN];
int gcd(int a,int b){  return a%b?gcd(b,a%b):b;  }
int Get(int p,int F[])
{
    if(F[p]==-1)  return p;
    F[p]=Get(F[p],F);
    return F[p];
}
void Delete(int p)
{
    int pos=Get(p%k,Fx);
    Fy[p]=Get((p+d)%n,Fy),tot[pos]--;
    if(tot[pos]==0)  Fx[pos]=Get((pos+1)%k,Fx);
}
void read()
{
    scanf("%d %d %d %d %d %d",&n,&s,&q,&p,&m,&d);
    c[0]=0,k=gcd(n,d);
    for(int i=1;i<n;i++)
        c[i]=(c[i-1]*q+p)%m;
}
void calc_pos()
{
    for(int i=0;i<k;i++)
        Fx[i]=-1,tot[i]=n/k;
    for(int i=0;i<n;i++)
        Fy[i]=-1;
    pos[0]=s,Delete(s);
    for(int i=1;i<n;i++)
    {
        int a=c[i]%n%k,x,y;
        if(tot[a]==0)  x=Get(a,Fx),y=Get((c[i]+(x+k-a)%k)%n,Fy);
        else y=Get(c[i]%n,Fy);
        pos[i]=y,Delete(y);
    }
}
int work()
{
    static bool use[MAXN];
    for(int i=0;i<n;i++)
        use[i]=false;
    int cnt=0;
    for(int i=0;i<n;i++)
        if(use[i]==false&&pos[i]!=i)
        {
            use[i]=true,cnt+=2;
            for(int j=pos[i];j!=i;j=pos[j])
                use[j]=true,cnt++;
        }
    return cnt-2;
}
int main()
{
    int test;
    for(scanf("%d",&test);test>=1;test--)
    {
        read();
        calc_pos();
        printf("%d\n",work());
    }
    return 0;


  评论这张
 
阅读(356)| 评论(4)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017