Codeforces 1174D:Ehab and the Expected XOR Problem 题解

主要思路

这道题还蛮妙的,自己比较顺利的思考出来了。

考虑设置前缀异或和\(\{ S_i \}\),根据异或按位处理的性质,显然对于所有的\(S_i\)都会小于\(2^n\)。最后,我们可以把限制变成:

  • 不存在两个相同的前缀和。
  • 不存在一对前缀和,其异或值为\(x\)。

针对\(x\)的大小关系,我们可以分成两种情况:

  • \(x \geq 2^n\),不存在一对\((S_i, S_j)\)的异或为\(x\),因为存在更高的位并不会被消除。
  • \(x < 2^n\),我们发现每选择一个数作为前缀和,整个\(2^n\)中就会少一个对应的可以被选择的数。所以,我们每次选一个作为\(S_i\)的数时,都要把\(S_i xor \ x\)打标记。

结合一下就可以了。

继续阅读Codeforces 1174D:Ehab and the Expected XOR Problem 题解

「2018泉州国庆集训#2」 – 解题报告

A – 奇妙的棋盘

一定要思考,不能想当然。这句话是说给我听的。

把连通块连边,每一次 BFS 扩展就算做一次点击,然后\(O(n^2)\)确定路径长度,再按奇偶性判断就行了。

继续阅读「2018泉州国庆集训#2」 – 解题报告

Educational Codeforces Round 71 Div.2 解题报告 (CF1207)

D – Numbers of Permutations

思考量很小的一道题。

先用间接法来算。初始答案为\(n!\),然后考虑容斥掉那些符合排序规则的方案。发现,我们可以分开来考虑,按照容斥的顺序:先考虑只算第一维、第二维的,在加回来两维都考虑的。

第一维和第二维的做法非常显然:排序之后用多重集的排列就行了,考虑每一个相同的区间里面内部乘起来。如果有\(k\)个连续的数段,那么部分的答案就是\(\prod_{i = 1}^l len_k!\)。

继续阅读Educational Codeforces Round 71 Div.2 解题报告 (CF1207)

CH3801:Rainbow 的信号题解

主要思路

这道题挺有趣的,归根结底就是位运算。首先,一个充分的结论就是枚举长度为\(1\)的区间的概率为\(\frac{1}{N^2}\),而长度大于1的概率为\(\frac{2}{N^2}\)。之后,枚举\(int\)的长度\(i \in [0,30]\),把所有数的第\(i\)位组成一个序列进行扫描,之后枚举到第\(j\)个数进行分类讨论。

  • 如果运算符是\(and\),那么我们记\(last[0]\)为最后一个\(0\)的位置,中间一共有\(k-last[0]+1\)个与之运算得到1的数。乘上概率更新答案。
  • 如果运算符是\(or\),那么区间概率直接乘上\(i-1\)即可。
  • 如果运算符是\(xor\),我们需要把之前的\(0,1\)进行分块,记\(c_1,c_2\)为前面区间长的和,且\(c_1\)与\(c_2\)的区间不重合,交替进行。每次乘上相应的块长度即可,对于\(1\)进行块交换,\(0\)则保持原样。

代码

// CH3801.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200;
int n, arr[MAX_N];
double ans1, ans2, ans3;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    for (int k = 0; k < 30; k++)
    {
        int last[2], c1 = 0, c2 = 0;
        last[0] = last[1] = 0;
        for (int i = 1; i <= n; i++)
            if ((arr[i] >> k) & 1)
            {
                ans1 += (1 << k) * 1.0 / n / n;
                ans2 += (1 << k) * 1.0 / n / n;
                ans3 += (1 << k) * 1.0 / n / n;
                ans1 += (1 << k) * 2.0 / n / n * c1;
                ans2 += (1 << k) * 2.0 / n / n * (i - 1);
                ans3 += (1 << k) * 2.0 / n / n * (i - 1 - last[0]);
                last[1] = i;
                c1++, swap(c1, c2);
            }
            else
            {
                ans1 += (1 << k) * 2.0 / n / n * c2;
                ans2 += (1 << k) * 2.0 / n / n * (last[1]);
                last[0] = i, c1++;
            }
    }
    printf("%.3lf %.3lf %.3lf", ans1, ans3, ans2);
    return 0;
}