清北学堂模拟赛d7t5 做实验

题目描述
有一天，你实验室的老板给你布置的这样一个实验。
首先他拿出了两个长度为 n 的数列 a 和 b，其中每个 ai 以二进制表示一个集
合。例如数字 5 = (101)2 表示集合 f1; 3g。第 i 次实验会准备一个小盒子，里面装
着集合 ai 所有非空子集的纸条。老板要求你从中摸出一张纸条，如果满足你摸出的
纸条是 ai 的子集而不是 ai-bi，ai-bi+1，...，ai-1 任意一个的子集，那么你就要 ***；
反之，你就逃过一劫。
令你和老板都没有想到的是，你竟然每次都逃过一劫。在庆幸之余，为了知道
这件事发生的概率，你想要算出每次实验有多少纸条能使你 ***
输入格式
第一行一个数字 n。
接下来 n 行，每行两个整数，分别表示 ai 和 bi。
输出格式
n 行，每行一个数字，表示第 i 次实验能使你 *** 的纸条数。
样例输入 1
3
7 0
15 1
3 1
样例输出 1
7

0
数据范围
对于 30% 的数据，n; ai; bi ≤ 100
对于 70% 的数据，n; ai; bi ≤ 60000
对于 100% 的数据，n; ai; bi ≤ 10^5
保证所有的 ai 不重复，bi < i

分析：其实只要枚举子集的时候不要一个一个枚举，用O(3^n)的方法枚举子集就能过了，然后记录每个子集出现的位置，看看是不是小于i - bi就可以了.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int n, pos[], ans;

int main()

{

    scanf("%d", &n);

    for (int i = ; i <= n; i++)

    {

        ans = ;

        int a, b;

        scanf("%d%d", &a, &b);

        int temp = a;

        while (temp)

        {

            if (pos[temp] < i - b)

                ans++;

            pos[temp] = i;

            temp = (temp - ) & a;

        }

        printf("%d\n", ans);

    }

    return ;

}

巴特西

清北学堂模拟赛d7t5 做实验

最新文章

热门文章