T1 浏览器

传送门= ̄ω ̄=

我真是太菜了

首先有一个XZY发现不了的性质:

当$A$的二进制有奇数个1,$B$的二进制有偶数个1时,$A \text{ xor } B$的二进制有奇数个1,否则都是偶数个1。

因此只要统计二进制下1的个数为奇数的有多少个,为偶数的有多少个,乘起来就是答案。

然后怎么统计呢?$\log _ 2 n$会超时。。。

当然是用XZY不会的方法啦,需要预处理出$[0, 2 ^ {16}]$这个区间内的每个整数的二进制下1的个数。

然后每次询问一个数字1的个数就把它拆成二进制下的前16位和后16位,分别在预处理数组中找到1的个数加起来就行了。

这样总体就是$O(n)$的了

代码:

#include <bits/stdc++.h>

#define NS (10000005)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int bc[1 << 16], n, x[NS], A, B, C, D, c1, c2;

int bitcnt(int a)
{
    return bc[a >> 16] + bc[a - ((a >> 16) << 16)];
}

int main(int argc, char const* argv[])
{
    for (int i = 1; i <= (1 << 16); i += 1) bc[i] = bc[i >> 1] + (i & 1);
    IN(n), IN(A), IN(B), IN(C), IN(D), IN(x[0]);
    A %= D, B %= D, C %= D, x[0] %= D;
    for (int i = 1; i <= n; i += 1)
        x[i] =
            (1ll * A * x[i - 1] % D * x[i - 1] % D + 1ll * B * x[i - 1] % D + C) % D;
    for (int i = 1; i <= n; i += 1)
        if (bitcnt(x[i]) & 1) c1++;
        else c2++;
    printf("%lld\n", 1ll * c1 * c2);
    return 0;
}

T2 大师

传送门= ̄ω ̄=

我真是太菜了

就是一个XZY不会的、比较简单的Dp

$f[i][j]$表示以第$i$个元素为结尾(一定包含第$i$个元素)的、公差为$j$的等差数列个数。

这样我们只需要枚举$i$,然后枚举$i$的前一个元素,这样公差$j$也就确定了

状态转移:

$$f[i][j] = \sum ^ {h[i] – h[k] = j} f[k][j] + 1$$

复杂度其实是$O(n ^ 2)$的。

代码:

#include <bits/stdc++.h>

#define NS (1005)
#define VS (40005)
#define MOD (998244353)

using namespace std;

inline int pls(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b;}

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, h[NS], f[NS][VS], ans;

int main(int argc, char const* argv[])
{
    IN(n);
    for (int i = 1; i <= n; i += 1) IN(h[i]);
    for (int i = 1; i <= n; i += 1)
        for (int j = 1; j < i; j += 1)
        {
            f[i][h[i] - h[j] + 20000] =
                pls(f[i][h[i] - h[j] + 20000], pls(f[j][h[i] - h[j] + 20000], 1));
            ans = pls(ans, pls(f[j][h[i] - h[j] + 20000], 1));
        }
    printf("%d\n", pls(ans, n));
    return 0;
}

T3 礼物

传送门= ̄ω ̄=

我真是太菜了

首先你需要发现一个XZY发现不了的性质:

$a _ i \text { & } a _ j \geq \min(a _ i, a _ j)$等效于$a _ i$与$a _ j$中有一个是另一个的子集(二进制的每一位看成元素)

可以考虑建一张XZY不会建的图:

若$a _ i \subseteq a _ j$,则从第$i$个点向第$j$个点连一条有向边。

然后整个图的最长链就是XZY不知道的答案。

对于拓扑排序中处于同一层次的点都放到同一个箱子里即可,因为他们一定没有包含关系。

但这样建图复杂度是$O(n ^ 2)$的,需要用上XZY不会的优化。

对于一个值$k$,我们只从它向比它多一个1的点连边。

比如$1010$只向$1110$和$1011$连有向边。

这样可以保证图的结构依然正确,但是最长链不再是答案,因为加入了一些输入中没有的数字。答案是链上最多的数据中出现过的点的个数。即你在拓扑排序的时候记录这个点之前经过有效点的最大个数。

分组方式依然一样,按拓扑序排,不存在包含关系的分到一组。

然后也可以不建图,可以用XZY不知道的DP。。。这样代码会好写一点。

代码:

#include <bits/stdc++.h>

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, k, f[1 << 20], ans;

bool book[1 << 20];

vector<int> g[20];

int main(int argc, char const* argv[])
{
    IN(n), IN(k);
    for (int i = 1, a; i <= n; i += 1) IN(a), book[a] = 1;
    for (int i = 0; i < (1 << k); i += 1)
    {
        for (int j = 0; j < k; j += 1)
            if ((i >> j) & 1) f[i] = max(f[i], f[i ^ (1 << j)]);
        if (book[i]) f[i]++, g[f[i]].push_back(i), ans = max(ans, f[i]);
    }
    printf("1\n%d\n", ans);
    for (int i = 1; i <= ans; i += 1)
    {
        printf("%lu", g[i].size());
        for (int j = 0; j < g[i].size(); j += 1) printf(" %d", g[i][j]);
        putchar(10);
    }
    return 0;
}

T4 口袋里的纸飞机

XZY不会

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

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

你是机器人吗? =。= *