Particle Arts（签到题）

题目描述：
空间中有n个粒子，每个粒子都有自己的能量，粒子a与粒子b相碰，他们的值会变成a&b和a|b，所有粒子的能量的方差不会减少，求最终稳定时粒子的方差。

input：
5
1 2 3 4 5

output：
54/5

解：
稳定时，即a&b=a或者b，a|b=b或者a，任何两个粒子都满足这种情况
&和|对操作，其实就是将1与0调换位置。
对于普遍的情况，举例：
111111111
111111110
111111100
111111000
...
000000000
最终稳态如上图
对于一堆数某一个位上全是0或者全是1的情况，其实不管是&还是|这一位上情况都不会改变都是全0或者全1，不用管

#include<iostream>
using namespace std;
#define ll unsigned long long

ll bits[15];//用来存取某个比特位上有多少个1

ll gcd(ll a, ll b) {//辗转相除法求最大公约数
    return b ? (gcd(b, a % b)) : a;
}

int main() {
    int n;
    cin >> n;
    ll c, sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> c;
        sum += c;
        for (int j = 0; c != 0 && j < 15; j++) {
            if ((c & 1) == 1) {//如果这一位为1，bits[j]++
                bits[j]++;
            }
            c >>= 1;
        }
    }
    ll x = 0;
    for (int i = 1; i <= n; i++) {
        ll temp = 0;
        for (int j = 0; j < 15; j++) {
            if (i <= bits[j]) {//1的分配，i<=bits[j],表示这个数在j比特位上可以分配1
                temp += (1 << j);
            }
        }
        x += temp * temp;
    }
    ll a = n * x - sum * sum;//公差的公式
    ll b = (ll)n * n;
    ll g = gcd(a, b);
    cout << a / g << '/' << b / g;
}

NIO’s Sword

题目描述：
有n个敌人，你有一把剑，初始攻击力为a，a=0,对于2-n个敌人，剑的攻击力必须符合a%n==i%n，才能够将其击杀，并且只能按照顺序击杀，你可以强化你的剑的攻击力，每次强化你的攻击力都可以变成a*10+x（0<=x<=9）,求击杀所有敌人并且强化次数最少的值

input：
4

output：
4

解：
设击杀第i-1个人时攻击力为a（i-1），强化了k次能够击杀第i个敌人，所以a（i）=a（i-1）10^k+y。同时模n，有
i%n=((i-1)10^k+y)%n
这里需要分析一下y的范围，假设每次强化x都取0，那么y=0，假设每次强化x都取9，那么y=10^k-1(等比数列求和)，
枚举k的值，并且计算y，如果y满足这个范围，那么就找到了最小的k，处理下一个敌人。

#include<iostream>
#include<cmath>

#define int long long
using namespace std;

signed main() {
    int n;
    cin >> n;
    if (n == 1) {//特判
        cout << 0 << endl;
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int k = 1; 1; k++) {//枚举k的值
            int base = (i - 1) * pow(10, k);
            int x = (((i - base) % n) + n) % n;//i-base可能是负数
            if (x < pow(10, k)) {
                res += k;
                break;
            }
        }
    }
    cout << res << endl;
}

Jobs (Easy Version)

题目描述：
有n个公司，每个公司有m份工作，每份工作有三个指标，只有大于这三个指标才能胜任这份工作，给定q个人，求出每个人最多能进几个公司。

解：
将每个公司的工作的三个指标和升序排列，如果这个人的三个指标和小于这个工作，那么后面的工作也无法胜任。

#include<iostream>
#include <random>
#include<algorithm>
using namespace std;

typedef long long ll;
#define int long long

ll mod = 998244353;
ll n, m[100005];
ll seedm[2000005];

struct gongsi {
    ll a, b, c;
    ll sum;
} g[11][100005];

int cmp(gongsi x, gongsi y) {
    return x.sum < y.sum;
}

ll solve(ll x, ll y, ll z) {
    ll sum1 = x + y + z;
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        bool is = 0;
        for (int j = 1; j <= m[i]; j++) {
            if (sum1 < g[i][j].sum) {
                break;
            }
            if (x >= g[i][j].a && y >= g[i][j].b && z >= g[i][j].c) {
                is = 1;
                break;
            }
        }
        if (is) res++;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    ll res = 0;
    ll q;
    ll seed;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> m[i];
        for (int j = 1; j <= m[i]; j++) {
            cin >> g[i][j].a >> g[i][j].b >> g[i][j].c;
            g[i][j].sum = g[i][j].a + g[i][j].b + g[i][j].c;
        }
        sort(g[i] + 1, g[i] + m[i] + 1, cmp);
    }
    cin >> seed;
    seedm[0] = 1;
    ll seedmod = seed % mod;
    for (int i = 1; i < q; i++) {
        seedm[i] = seedm[i - 1] * seedmod % mod;
    }
    std::mt19937 rng(seed);
    std::uniform_int_distribution<> u(1, 400);
    ll lastans = 0;
    for (int i = 1; i <= q; i++) {
        int IQ = (u(rng) ^ lastans) % 400 + 1;  // The IQ of the i-th friend
        int EQ = (u(rng) ^ lastans) % 400 + 1;  // The EQ of the i-th friend
        int AQ = (u(rng) ^ lastans) % 400 + 1;  // The AQ of the i-th friend
        lastans = solve(IQ, EQ, AQ);  // The answer to the i-th friend
        res += lastans * seedm[q - i] % mod;
        res %= mod;
    }
    cout << (res + mod) % mod << endl;

}