第四场

N：位运算

题目：略

思路：

已知两个二进制数字 a = 010110, b = 000101

0 1 0 1 1 0

0 0 0 1 0 1

a & b = 0 0 0 1 0 0

a | b = 0 1 0 1 1 1

我们发现碰撞后的 a 与 b 1的个数不变，规律为1的下沉，所以最终方差确定为一个数则数组中的数字为此规律排布

那么我们贪心的构造出这组数。

首先统计 每位 1 的个数，然后依次构造。最后因为公式中数据较大，化简方差公式，要么使用 int128

代码

#define int long long 
signed main()
{
    int n;
    cin >> n;

    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;

        for(int j = 0; j < 15; j++)
        {
            if((x >> j) & 1) cnt[j] ++;
        }
    }

    int sum1 = 0, sum2 = 0;


    for(int i = 0; i < n; i++)
    {
        int x = 0;

        for(int j = 0; j < 15; j++)
        {
            if(cnt[j])
            {
                x |= 1 << j;

                cnt[j] --;
            }
        }

        sum1 += x;
        sum2 += x* x;


    }

    int p = n * sum2 - sum1 * sum1;

    int q = n * n;

    int g = gcd(p, q);

    p /= g, q /= g;

    cout << p << "/" << q ;
    return 0;
}

K: 规律，构造

题目：

能否使得 A % n == i % n, 可以使 A = A *10 + x;

思路：

每次添加一个数就是扩大 l - r 范围， 看看 取模后的范围 是否存在 i + 1 即可

已知 上一个 A % n == i， 当前要进行几次操作使得 A ` % n == i + 1。

对于每次操作我们可以选择 0 - 9 之间的数字添加在最后。

意味着我们可以进行a 次操作可以构造出 x * 10 ^ a - x * 10 ^ (a + 1) - 1 之间的任何一个数。

我们对这个这个范围的 l - r 取模， 看看 i + 1 是否在其中，就知道是否可以构造出 i + 1

因为 n 最大为 1e6 我们最多操作6次 就可以构造出 0 ~ 999999 之间所有的数，六次一定可以找到 %n == i + 1 的数字

每次操作之间互不影响，所以不需要考虑具体的方案。因为我们是从小到大步数枚举，一定符合最小方案数

每次我们取上一个 i , 每步 我们 可以构造出 i * 10 - i *100 - 1 内所有的数。 每次对 l , r 取模 分类讨论 n 是否在其中。

因为模运算的性质，上一次操作我们一定是取得了 A % n == i 所以我们从 i 开始操作

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
#define int long long 


signed main()
{
    int n; 
    cin >> n;

    if(n == 1) 
    {
        cout << 0 << endl;
        return 0;
    }

    int ans = 0;

    for(int i = 1; i < n; i++)
    {
        int nex = (i + 1) % n;

        int l = i, r = i, res = 0;

        while(1)
        {
            res ++;

            //每次扩大范围
            l = l *10;
            r = r *10 + 9;

            if(r - l  + 1 >= n) break;

            int a = l % n ,  b = r % n;

            if(a <= b)
            {
                if(a <= nex && nex <= b) break;
            }else if(nex <= b || nex >= a) break;
        }

        ans += res;
    }

    // 0 次 是特判的需要加上这一次
    cout << ans + 1 ;


    return 0;
}