T1.Adore

描述:

原题：

小 w 偶然间⻅到了一个 DAG。
这个 DAG 有 m 层, 第一层只有一个源点, 最后一层只有一个汇点, 剩下的每一层都有 k 个
节点。
现在小 w 每次可以取反第 i(1 < i < n − 1) 层和第 i + 1 层之间的连边。也就是把原本从
(i, k 1 ) 连到 (i + 1, k 2 ) 的边, 变成从 (i, k 2 ) 连到 (i + 1, k 1 )。
请问他有多少种取反的方案, 把从源点到汇点的路径数变成偶数条?
答案对 998244353 取模。

输入格式：
一行两个整数 m, k。
接下来 m − 1 行, 第一行和最后一行有 k 个整数 0 或 1, 剩下每行有 k 2 个整数 0 或 1, 第
(j − 1) × k + t 个整数表示 (i, j) 到 (i + 1, t) 有没有边。

输出格式：
一行一个整数表示答案。

数据规模与约定：
20% 的数据满足 $m ≤ 10, k ≤ 2$
40% 的数据满足 $m ≤ 10^3 , k ≤ 2$
60% 的数据满足 $m ≤ 10^3 , k ≤ 5$
100% 的数据满足 $4 ≤ m ≤ 10^4 , k ≤ 10$
一行一个整数表示答案。

思路：

由于每层只有 k(k<=10) 个节点，而且只需要求满足某种奇偶性的解的个数。我们可以用二进制保存每一层的状态。接下来进行状态压缩 DP。

注意以下的问题：

1. 边的表示？

为了达到更高的速度，边可以用邻接矩阵表示，而这个邻接矩阵又是由二进制构成的，因此可以用位运算加速连通性的计算。

比如：

$\begin{bmatrix} 1 & 1 & 0\\ 0 & 1 & 0\\ 1 & 0 & 1 \end{bmatrix}$
这个矩阵表示，每一列对应的左侧节点与每一行对应的右侧节点联通，当且仅当这一列这一行的元素为 1。

而每一层的状态我们又可以用一个 k 维向量表示，

比如：

$\begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}$
这个向量表示，从起点到这一层的 1,3 个节点有奇数中走法，第 2 个节点有偶数种走法。这样，如果我们将这连个矩阵相乘：

$\begin{bmatrix} 1 & 1 & 0\\ 0 & 1 & 0\\ 1 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 2 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}(mod2)$
然而，由于我们用一个 int 型数就可以表示矩阵的一行，我们就可以在 O(k) 的时间复杂度内完成这个矩阵乘法。具体的实现是：将矩阵的每个行向量与当前层的 k 维向量按位与，取答案中 1 的个数。很快，对不对？不够快。

注意到上面的式子中出现了取 1 的个数操作。如果这个操作仅仅使用 x=x&(x-1) 这样的操作来读取的话，恭喜你，时间复杂度不幸地变成了 $O(k^2)$ 。如何才能更快求 1 的个数呢？我们以空间换时间，结合本博客中另一篇有关位运算的“ 位运算那些令人咋舌的操作” 文章，大家一定可以找到更快速的方法。我最终采用的算法时间复杂度约为 $O(mk2^k)$

2. 思考的复杂度

由于这道题的内容及我所选择的做法，我的程序频繁地涉及位运算相关的代码。而位运算代码的编写由略为困难。如何在代码执行高效的基础上减少位运算的思考复杂度，已知是一个值得权衡的问题。

3. 时间的复杂度
使用的第一个问题所提到的架构，时间复杂度已经得到了保证。谁知当我采用 x=x&(x-1) 取得答案中 1 的个数时，却发生了 60 分 TLE 惨案…。在考场上我最初的邻接矩阵甚至没有用到位运算，速度更慢，计算时间复杂度为 $O(mk^22^k)$ ，有对于后 40 分有危险，为了确保万无一失我才改成了位运算，谁知…. 还是 TLE，而且 T 了 60 分。数据实在是没有梯度，这种出题人该裱该表。

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 50005
#define mod 998244353
#define mov(x) ((ui)1<<(x))
#define lowbit(x) ((x)&(-(x)))
#define reg register

using namespace std;

typedef unsigned int ui;

ui f[MX][1<<11];

ui edg[MX][12];
ui rev[MX][12];
ui noo[1<<16];
ui m,k;

void outb(ui x)
{
    for(int i=0;i<=5;i++)cout<<!!(x&mov(i));cout<<endl;
}

ui count1(ui x)
{
    ui cnt=0;
    while(x)x-=lowbit(x),cnt++;
    return cnt;
}

ui count2(int x)
{
    return (noo[65535&x]+noo[65535&(x>>16)]);
}

void input()
{
    ui t;
    scanf("%d%d",&m,&k);
    for(ui i=1;i<=k;i++)
    {
        scanf("%d",&t);
        if(t==1)edg[1][0]|=(mov(i-1));
    }
    for(ui i=2;i<=m-2;i++)
    {
        for(ui j=1;j<=k;j++)
        {
            for(ui l=1;l<=k;l++)
            {
                scanf("%d",&t);
                if(t==1)edg[i][l]|=(mov(j-1)),rev[i][j]|=(mov(l-1));
            }
        }
    }
    for(ui i=1;i<=k;i++)
    {
        scanf("%d",&t);
        if(t==1)edg[m-1][0]|=(mov(i-1));
    }
}

void work()
{
    ui nt1,nt2;
    f[2][(mov(k)-1)&(edg[1][0])]=1;
    for(reg ui i=2;i<=m-2;i++)
    {
        for(reg ui w=0;w<mov(k);w++)
        {
            if(f[i][w])
            {
                nt1=nt2=0;
                for(reg ui j=1;j<=k;j++)
                {
                    if(count2(edg[i][j]&w)&1)nt1|=(mov(j-1));
                    if(count2(rev[i][j]&w)&1)nt2|=(mov(j-1));
                }
                f[i+1][nt1]+=f[i][w];
                f[i+1][nt1]%=mod;
                f[i+1][nt2]+=f[i][w];
                f[i+1][nt2]%=mod;
            }
        }
    }
    ui cnt=0;
    for(ui w=0;w<mov(k);w++)
        if((count2(w&edg[m-1][0])&1)==0)
            cnt+=f[m-1][w],cnt%=mod;
    cout<<cnt<<endl;
}

void init()
{
    for(int i=0;i<mov(16);i++)noo[i]=count1(i);
}

int main()
{
    freopen("adore.in","r",stdin);
    freopen("adore.out","w",stdout);
    init();
    input();
    work();
    return 0;
}

T2.Confess

描述:

原题：

小 w 隐藏的心绪已经难以再隐藏下去了。
小 w 有 n + 1(保证 n 为偶数) 个心绪, 每个都包含了 [1, 2n] 的一个大小为 n 的子集。
现在他要找到隐藏的任意两个心绪, 使得他们的交大于等于 n/2。

输入格式：
一行一个整数 n。
接下来每行一个⻓度为 k 的字符串, 该字符串是一个 64 进制表示,ASCII 码为 x 的字符代
表着 x − 33, 所有字符在 33 到 33 + 63 之间。
转为二进制表示有 6k 位, 它的前 2n 个字符就是读入的集合, 第 i 位为 1 表示这个集合包
含 i, 为 0 表示不包含。

输出格式：
一行两个不同的整数表示两个集合的编号。
如果无解输出”NO Solution”。

数据规模与约定：
对于 20% 的数据满足 $n ≤ 100$
对于 50% 的数据满足 $n ≤ 1 \times 10^3$
对于 100% 的数据满足 $n ≤ 6 \times 10^3$

思路:

我首先想到的是随机化算法。因为我只想着去骗分了。后来发现其实这就是正解。为什么随机化算法骗分是可行的呢？我们来考虑任意两个集合的交集大于等于 n/2 的概率：

设这两个集合为 [1,2n] 中的 n 个整数组成的集合，设 P(i) 为它们交集大小为 i 的概率，那么：

$P(i)=\frac{C_{2n}^{i}C_{2n-i}^{n-i}C_{n}^{n-i}}{C_{2n}^{n}C_{2n}^{n}}$
其中分数线上方第一个 C 表示从 2n 个元素里选出 i 个作为它们的交，后两个表示从剩下的里面选出不重复的 n-i 和 n-i 个分别作为两个集合的元素。而我们要求的是：

$P=\sum\limits_{i=n/2}^{n}{P(i)}$
随手用计算机一算，这个结果还是蛮大的。

假设，P=0.01(是不是非常小)，那么我们只需要随机选 1000 组集合，它们都没有大于等于 n/2 的交集的概率为 0.00004，显然是符合要求的。因此，我们可以大胆地骗分了。

优化：

对于暴力求交集，我们是可以优化的。我们不需要一个一个元素地比较，而可以保存在二进制数里用位运算求交集 (即按位与)。同时又可以结合“ 位运算那些令人咋舌的操作” 中介绍的方法，快速求交集大小。这种方法在图像处理等现实应用中十分有效，即” 汉明距离” 的快速求法。结合这种优化，我们可以在 1s 内求大约 10 倍于普通做法的交集次数，对大数据范围内的求解帮助还是很大的。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <cstdlib>

#define LEN 62001
#define MX 30001
#define SZ 32
#define lowbit(x) ((x)&(-(x)))

using namespace std;

typedef long long ll;

int set[MX][LEN/SZ];
int cno[(1<<8)+1];
int n,num;

inline int count1(int x)
{
    int cnt=0;
    while(x)x-=lowbit(x),cnt++;
    return cnt;
}

inline int count2(int x)
{
    return cno[x&(255)]+cno[(x>>8)&255]+cno[(x>>16)&255]+cno[(x>>24)&255];
}

void input()
{
    int len=0,t,len2;
    char str[MX],str2[MX];
    scanf("%d",&n);
    for(int i=1;i<=n+1;i++)
    {
        memset(str2,0,sizeof(str2));
        scanf("%s",str);
        len=strlen(str),len2=0;
        for(int j=0;j<len;j++)
        {
            t=str[j]-33;
            for(int k=0;k<6;k++)str2[len2++]='0'+!!(t&(1<<k));
        }
        for(int j=0;j<len2;j++)
            if(str2[j]>'0')
                set[i][j/SZ]|=(1<<(j%SZ));
    }
    num=len2/SZ;
}

inline int comb(int a,int b)
{
    int cnt=0;
    for(int i=0;i<=num;i++)
    {
        cnt+=count2(set[a][i]&set[b][i]);
    }
    return cnt;
}

inline void test()
{
    int T,k1,k2;
    while(1)
    {
        k1=rand()%(n+1)+1;
        k2=rand()%(n+1)+1;
        while(k1==k2)k2=rand()%(n+1)+1;
        if(comb(k1,k2)>=n/2)
        {
            printf("%d %d\n",k1,k2);
            return;
        }
    }
    printf("NO Solution\n");
}

void init()
{
    for(int i=0;i<(1<<8);i++)cno[i]=count1(i);
}

int main()
{
    freopen("confess.in","r",stdin);
    freopen("confess.out","w",stdout);
    init();
    input();
    test();
    return 0;
}

T3.Repulsed

描述：

原题

小 w 心里的火焰就要被熄灭了。
简便起⻅, 假设小 w 的内心是一棵 n − 1 条边,n 个节点的树。
现在你要在每个节点里放一些个灭火器, 每个节点可以放任意多个。
接下来每个节点都要被分配给一个至多 k 条边远的灭火器, 每个灭火器最多能分配给 s 个节
点。
至少要多少个灭火器才能让小 w 彻底死心呢?

输入格式
第一行三个整数 n, s, k。
接下来 n − 1 行每行两个整数表示一条边。

输出格式
一行一个整数表示答案

数据规模与约定
对于 20% 的数据满足 $n ≤ 100, k ≤ 2$
对于另外 20% 的数据满足 $k = 1$
对于另外 20% 的数据满足 $s = 1$
对于 100% 的数据满足 $n ≤ 10^5 , k ≤ 20, s ≤ 10^9$

思路：

当初没有想出来，也没有时间想了，于是看数据范围骗了 40 分。

实际上的思路是这样的：

设 G(x,i) 表示 x 节点及其子树中还没有被灭的火的个数。

设 F(x,i) 表示 x 节点及其子树中多余的灭火器能灭的火的个数。

策略 1：对于每一个火，我们尽量在靠近树根的地方灭掉。

策略 2：对于每一个 x 及其子树中多余的灭火器和火，我们在两者距离为 k 或 k-1 时让它们相互泯灭。

按照这两个策略，我们就可以快捷地写出代码。。。原来比骗分还简单。

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 100001
#define MK 22

using namespace std;
typedef long long ll;

ll f[MX][MK],g[MX][MK],ans;
int fst[MX],nxt[MX<<1],v[MX<<1],lnum;
int n,s,k;

ll ceil(ll x)
{
    return x/s+((x%s)>0);
}

void addeg(int nu,int nv)
{
    nxt[++lnum]=fst[nu];
    fst[nu]=lnum;
    v[lnum]=nv;
}

void input()
{
    int a,b;
    scanf("%d%d%d",&n,&s,&k);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        addeg(a,b);
        addeg(b,a);
    }
}

void dfs(int x,int fa)
{
    ll t,num;
    for(int i=fst[x];i!=-1;i=nxt[i])
    {
        if(v[i]==fa)continue;
        dfs(v[i],x);
        for(int j=0;j<=k-1;j++)
        {
            f[x][j+1]=min(f[x][j+1]+f[v[i]][j],(ll)n);
            g[x][j+1]+=g[v[i]][j];
        }
    }
    g[x][0]=1;
    if(g[x][k])
    {
        t=ceil(g[x][k]);
        ans+=t;
        f[x][0]=min((ll)n,t*s);
    }
    for(int i=0;i<=k;i++)
    {
        t=k-i;
        num=min(f[x][i],g[x][t]);
        f[x][i]-=num;
        g[x][t]-=num;
    }
    for(int i=0;i<k;i++)
    {
        t=k-i-1;
        num=min(f[x][i],g[x][t]);
        f[x][i]-=num;
        g[x][t]-=num;
    }
}

int main()
{
    freopen("repulsed.in","r",stdin);
    freopen("repulsed.out","w",stdout);
    int num=0;
    memset(fst,0xff,sizeof(fst)),lnum=-1;
    input();
    dfs(1,0);
    for(int i=k;i;i--)
    {
        for(int j=0;j<=k-i;j++)
        {
            num=min(f[1][i],g[1][j]);
            f[1][i]-=num;
            g[1][j]-=num;
        }
    }
    num=0;
    for(int i=0;i<=k;i++)num+=g[1][i];
    ans+=ceil(num);
    printf("%lld",ans);
    return 0;
}

【考试总结】NOIP 模拟赛 17.10.10 -boshi

于2017年10月10日2017年10月10日由boshi发布

T1.Adore

描述:

思路：

T2.Confess

描述:

思路:

优化：

T3.Repulsed

描述：

思路：

0 条评论

发表回复取消回复

【考试总结】NOIP 模拟赛 17.10.10 -boshi

于2017年10月10日2017年10月10日由boshi发布

T1.Adore

描述:

思路：

T2.Confess

描述:

思路:

优化：

T3.Repulsed

描述：

思路：

0 条评论

发表回复 取消回复

发表回复取消回复