慕容琳的后花园
慕容琳的后花园
hgoi#20190513

T1-Felicity is Coming!

神奇宝贝的进化方案是一个全排列,假设有三种宝可梦,那么对应就可以有:
(1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,1,2)(3,2,1)这六种进化方案(六种全排列)
这里(1,3,2)相当于:1进化成1,2进化成3,3进化成2
需要满足所有约束条件才能作为可行进化方案:
对于一个训练馆,之前有a个b种类的宝可梦,那么训练馆里所有的宝可梦进化之后,还要有a个b种类的宝可梦才行,种类不能增加,不能减少,也不能改变
问一共有多少个可行方案

解法

如果a宝可梦和b宝可梦能互相进化,一定满足a出现过的训练馆和b出现过的训练馆以及次数都相同
所以开vector来维护这一性质,然后sort,没错vector之间可以直接sort(大雾
相同的一定放在一起,n个相同的会产生n!的贡献,对于没有出现过的宝可梦,也会产生一个贡献,因为进化是不能一对多或多对一的,所以贡献也是一个n!

ac代码

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
vector<int>a[1000010];
int n,m,g,x;
ll cnt=1,ans=1;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&g);
        for(int j=1;j<=g;j++)scanf("%d",&x),a[x].push_back(i);
    }
    sort(a+1,a+m+1);
    for(int i=2;i<=m;i++)
        if(a[i]==a[i-1])cnt++,ans=ans*cnt%mod;
        else cnt=1;
    printf("%lld\n",ans);
    return 0;
}

T2-Felicity’s Big Secret Revealed

给定一个01串,一个有效的n切割定义如下:一个横杠代表一次切割,第一条横杠前面的01串不算,最后一条横杠后面的01串不算,将两个横杠中的01串转化成十进制数字,假设这些数字的最大值是MAX且这些数字囊括了1-MAX的所有数字,则称为一次有效切割。求2~n+1次有效切割的切法总数。

解法

由于题目要求包含所有1—MAX的数字,且n<=75,所以MAX<=20。
dp[i][k]表示第i位前有一次切割且状态为k,接着从第i位开始枚举到第j位为下一个横杆的位置,设这两段横杆之间的数字为p(十进制),则
dp[j+1][k|(1<<p-1)]+=dp[i][k],k为1~(1<<20)的状态。最后把dp[i][(1<<t)-1](0<=i<=n,1<=t<=20)加起来就可以了。

ac代码

#include<bits/stdc++.h> 
#define mod 1000000007
#define lim 1048576
using namespace std;
int n,ans,a[100],dp[100][lim+10];
int main()
{
    memset(dp,0,sizeof(dp)),scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%1d",&a[i]);
    for(int i=0;i<n;i++)
    {
        dp[i][0]=1;
        for(int k=0;k<lim;k++)
        {
            if(!dp[i][k])continue;
            for(int j=i,p=a[i];j<n&&p<=20;j++,p=(p*2+a[j]))
                if(p)dp[j+1][k|(1<<(p-1))]=(dp[j+1][k|(1<<(p-1))]+dp[i][k])%mod;
        }
    }
    for(int i=0;i<=n;i++)for(int k=1;k<=20;k++)ans=(ans+dp[i][(1<<k)-1])%mod;
    printf("%d\n",ans);
}

T3-Harmony Analysis

已知向量中每个坐标的值都为1或者-1
给出k(0<=k<=9),构造出2^k个2^k维向量,使得任意这2^k个向量中任意两个向量点积为0

解法

首先手推一下k为3时是什么样的

++++++++
++++****
++**++**
++****++
+*+*+*+*
+*+**+*+
+**++**+
+**+*++*

嗯,是这个样子的,对比一下k为2时的

++++
++**
+*+*
+**+

可以发现将k为2时的扩大一倍会形成前4行,后4行是怎么来的呢,前四行偶数位都取反(异或1)
别问我怎么看出来的,就这样看出来的QAQ
按照这样构造就可以了QWQ

ac代码

#include<bits/stdc++.h>
using namespace std;
int n,m=1,a[512][512];
int main()
{
    a[0][0]=1,scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<m;j++)for(int k=m*2-1;k>=0;k--)a[j][k]=a[j][k/2];
        for(int j=m;j<m*2;j++)for(int k=0;k<m*2;k++)a[j][k]=a[j-m][k];
        for(int j=m;j<m*2;j++)for(int k=1;k<m*2;k+=2)a[j][k]^=1;
        m*=2;
    }
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<m;j++)if(a[i][j]==1)putchar('+');else putchar('*');
        putchar('\n');
    }
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

hgoi#20190513
T1-Felicity is Coming! 神奇宝贝的进化方案是一个全排列,假设有三种宝可梦,那么对应就可以有: (1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,1,2)(3,2,1)这六种进化方案(六种全排列…
扫描二维码继续阅读
2019-05-14
功能