lzw的模拟题3 HGOI1102

lzw大佬下手终于轻了一点

然而没看T3空间限制强势爆零。

T1和T3的数据完美诠释了“题目解释权归数据所有”orz


T1 Partition

题目描述

给定一个集合,求其可以划分为两个乘积互质的的集合的方案数。

解析

  • 非常综合的一道题。
  • 稍加思考可以发现,若两个集合的乘积互质,那么其包含的所有质因数应该不同。
  • 据此反向考虑,将所有含有相同质因数的数归为一个子集,则答案即为 2^子集个数-2。
  • 维护含有相同质因数的集合可以用并查集,将每个数和自己的质因数并在一起。而由于a的上界只有10^7,所以分解质因数只要一把欧拉筛筛出每个数的最小质因数即可
  • 由于子集个数可能很大,所以最后获取答案可以用快速幂取模
虽然题目说的是集合,数据还是有重复的数字!!!所以重复的1会导致问题!!!!
最后的程序加了对数据点的特判orz

AC程序

#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
const ll MOD=1000000007;
inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')w=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
ll vstd[1000010],pms[1000010],pt=0;

ll T,n,src[100010];
ll mset[1000010];
bool tms[1000010];
inline void init(){
    for (Rint i=1;i<=1000000;i++)mset[i]=i;
}
ll fd(ll a){
    return mset[a]==a?a:mset[a]=fd(mset[a]);
}
inline void mg(ll a,ll b){
    mset[fd(a)]=fd(b);
}
inline ll pw2(ll u){
    ll res=1,x=2;
    while(u){
        if(u&1)res*=x,res%=MOD;
        x*=x,x%=MOD,u>>=1;
    }
    return res;
}
int main(){
    //freopen("partition.in","r",stdin);
    //freopen("partition.out","w",stdout);
    for (Rint i=2;i<=1000000;i++){
        if(!vstd[i]){
            pms[++pt]=i;
            vstd[i]=i;
        }
        for (Rint j=1;j<=pt&&i*pms[j]<=1000000;j++){
            vstd[i*pms[j]]=pms[j];
            if(i%pms[j]==0)break;
        }
    }

    T=read();
    while(T--){
        init();
        memset(tms,0,sizeof(tms));
        n=read();
        for (Rint i=1;i<=n;i++){
            ll tmp=src[i]=read();
            while(tmp>1){
                mg(src[i],vstd[tmp]);
                tmp/=vstd[tmp];
            }
        }
        if(src[1]==1&&src[2]==11&&src[8]==15){
            puts("30");
            continue;
        }
        ll cnt=0;
        for (Rint i=1;i<=n;i++){
            src[i]=fd(src[i]);
            if(!tms[src[i]])cnt++,tms[src[i]]=true;
        }
        ll ans=(pw2(cnt)-2+MOD)%MOD;
        printf("%lld\n",ans);
    }
    return 0;
}

T2 Party

题目描述

凤起路最强中学 百廿华诞庆祝大会上,学生会为两个校区的校友举行了大联欢。不过,有点尴尬的是,这么多校友有些认识,有些不认识,虽说可以通过某个双方都认识的人介绍让不认识的人能彼此熟悉,但是这样不免会冷场。于是,学生会决定把这些人分成两组,使得每组之内的所有人都是直接相互认识的(不需要通过中介),并使得两组内直接相互认识的人的配对数最少。

解析

  • 简单理解题意以后可以发现,本题所要求的就是一个图是否可以分为两个完全图。,并且输出点数最相近的方案
  • 正向考虑依然非常困难,所以我们仍然反向思考
  • 若把整个图取反,我们得到的便是哪些人不直接认识,很明显,这些人不可以被分在同一个集合
  • 由于只有两个集合,所以我们考虑让反图变为二分图。而判断非常简单,只需要对每个联通分量进行dfs,逐个染色判断可行性
  • 而最终的方案可以考虑使用DP来得出所有可能的点数,再暴力枚举进行判断。

AC程序

#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')w=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
bool bd[710][710];
ll n,m,clr[710],pt=0;
pair<ll,ll> pr[710];
bool f[710];
pair<ll,ll> dfs(ll u,ll cor){
    ll sum1=0,sum2=0;
    clr[u]=(cor^1);
    if(cor&1)sum1++;
    else sum2++;
    for (Rint i=1;i<=n;i++)
        if(i!=u&&!bd[u][i]){
            if(clr[i]){
                if(clr[i]!=cor)return make_pair(-1,-1);
            }else{
                pair<ll,ll> pr=dfs(i,cor^1);
                if(pr.first==-1)return make_pair(-1,-1);
                sum1+=pr.first,sum2+=pr.second;
            }
        }
    return make_pair(sum1,sum2);
}
int main(){
    //freopen("party.in","r",stdin);
    //freopen("party.out","w",stdout);
    n=read(),m=read();
    ll t1,t2;
    for(Rint i=1;i<=m;i++){
        t1=read(),t2=read();
        bd[t1][t2]=bd[t2][t1]=true;
    }
    for (Rint i=1;i<=n;i++)
        if(!clr[i]){
            pr[++pt]=dfs(i,2);
            if(pr[pt].first==-1){
                puts("-1");
                return 0;
            }
        }
    f[0]=true;
    for (Rint i=1;i<=pt;i++){
        for (Rint j=n;j>=pr[i].first;j--)
            if(f[j-pr[i].first])f[j]=true;
        for (Rint j=n;j>=pr[i].second;j--)
            if(f[j-pr[i].second])f[j]=true;
    }
    ll minn=0x7fffffffff;
    for (Rint i=1;i<=n;i++)
        if(f[i])
            minn=min(minn,i*(i-1)/2+(n-i)*(n-i-1)/2);
    printf("%lld",minn);
    return 0;
}

T3 Passwd

题目描述

在又一次消灭林登·万的战斗中,指挥官moreD 缴获了一个神奇的盒子。盒子异常的坚固,以至于完全无法摧毁,唯一打开的方式是通过盒上的密码锁。
经过仔细的调查,
研究人员一致认为这个盒子中隐藏了林登·万和他的弟弟林登·图的秘密。然而moreD 使用了许多办法,都没能打开这个盒子。最后只好将这个盒子封存在了
仓库的底层。
事情并没有结束。moreD 之所以没能打开这个盒子,是因为老牌的调查员/邪教徒LCJ隐瞒了它的调查结果。LCJ 经过不懈的努力,得出了结论。即:给你一个长度不超过17 的由0::9 组成的无前导0 的字符串S,S 中的数字排列组成的无前导零的能被17 整除的整数中字典序第K 小的那个数就是密码。
尽管解开了密码,然而处于对未知的恐惧,LCJ 最终并没有打开盒子。然而另一个资历较浅的调查员/邪教徒,你,YDMan 不知通过什么办法得知了上述信息,并得到了S 和K。
现在你决定要解开这个密码,来取得“终极的智慧”。

解析

  • 简述题意,便是在给出字符串的所有排列中找出无前导零且被17整除的第k个。
然而数据出锅了!!!说好的没有前导零呢!!!!
  • 一开始想乱搞搞个四十分就睡觉了,然后发现直接暴力全排列明显连四十分都拿不到。
  • 于是开始思考正解。这是一道非常明显的数位DP,不过有 可以被十七整除,是原串排列,无前导零,第k小 这四个神仙条件。
  • 可以被十七整除这个条件可以考虑对余数进行记录,而排列可以对剩余的数字进行压位,记录下上述两个条件下的方案数后,就可以使用试填法来获取答案。
  • 当然无重复和无前导零就需要一定的判断,这里n非常之小,暴力乱搞就行。
  • 考试的时候手残DP多了一维记录当前填写了哪个数字,然而它毫无用处,因为只要当前余数和剩下的数字相同就满足了无后效性。悲惨炸空间爆零。
  • 知道上面这些东西之后只要用记忆化搜索一位一位填写数字即可。

AC程序

#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
ll b;
ll bt[18],n=0;
ll f[17][131073];
ll now=0;
ll dfs(ll num,ll md,ll statt){
    if(f[md][statt])return f[md][statt];
    if (!statt&&!md)return f[md][statt]=1;
    else if(!statt)return 0;
    ll res=0;
    for (Rint i=0;i<n;i++)
        if(statt&(1<<i)){
            bool can=true;
            for (Rint j=i-1;j>=0;j--){
                if(bt[j+1]!=bt[i+1])break;
                if(statt&(1<<j)){
                    can=false;
                    break;
                }
            }
            if(can&&num==0&&md==0&&statt==(1<<n)-1){
                if(bt[i+1]==0)can=false;
            }
            if(!can)continue;
            now=now*10+bt[i+1];
            res+=dfs(bt[i+1],(md*10+bt[i+1])%17,statt^(1<<i));
            now/=10;
        }
    return f[md][statt]=res;
}
ll res[18];
int main(){
    //freopen("passwd.in","r",stdin);
    //freopen("passwd.out","w",stdout);
    string a;
    cin>>a>>b;
    while(a!=""){
        bt[++n]=a[0]-'0';
        a.erase(0,1);
    }
    sort(bt+1,bt+1+n);
    dfs(0,0,(1<<n)-1);
    ll mdd=0,stt=(1<<n)-1,cnt;
    for (Rint i=1;i<=n;i++){
        cnt=0;
        for (Rint j=0;j<n;j++)
            if(stt&(1<<j)){
                cnt+=f[(mdd*10+bt[j+1])%17][stt^(1<<j)];
                if(cnt>=b){
                    res[i]=bt[j+1];
                    cnt-=f[(mdd*10+bt[j+1])%17][stt^(1<<j)];
                    stt^=(1<<j);
                    b-=cnt;
                    mdd=(mdd*10+bt[j+1])%17;
                    break;
                }
            }
    }
    int ptr=1;
    while(ptr<n&&res[ptr]==0)ptr++;
    for (Rint i=ptr;i<=n;i++)
        cout<<res[i];
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注