hgoi#20190513

muronglin
muronglin 2019年05月14日
  • 在其它设备中阅读本文章

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("%lldn",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],dp100;
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++)
    {
        dpi=1;
        for(int k=0;k<lim;k++)
        {
            if(!dpi)continue;
            for(int j=i,p=a[i];j<n&&p<=20;j++,p=(p*2+a[j]))
                if(p)dpj+1=(dpj+1+dpi)%mod;
        }
    }
    for(int i=0;i<=n;i++)for(int k=1;k<=20;k++)ans=(ans+dpi)%mod;
    printf("%dn",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,a512;
int main()
{
    a0=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--)aj=aj;
        for(int j=m;j<m2;j++)for(int k=0;k<m2;k++)aj=aj-m;
        for(int j=m;j<m2;j++)for(int k=1;k<m2;k+=2)aj^=1;
        m*=2;
    }
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<m;j++)if(ai==1)putchar('+');else putchar('*');
        putchar('n');
    }
    return 0;
}