D - Jobs (Easy Version)
有 $n(n \le 10)$ 个公司，每个公司有 $k$ 个职位。每个职位都有三维[a , b , c]的要求，现在有 $q$ 名求职者，每个求职者的三维必须大于等于需要的职位的三维才可以被采纳。
求问，每个求职者最多可以收到几家公司的 offer。
由于本人的能力有限，只给出 Easy Version 的解。
在这个问题中，我们发现题目的突破口是在 [a , b , c] 的范围，他们最大的值仅有 400， 因此我们不妨通过设置 need[i][a][b] 来表示这样的值，在公司 $i$ ，能力值为 $a$ ， $b$ 且可以被公司接纳的情况下，的情况下，$c$ 的最小值。
然后对于一个公司而言，我们可以得到 need[i][a][b] = min(need[i][a][b] , c) 。除开这些外，我们发现对于能力值 $a$ $b$ 而言，能力值小于当前也是可以的。
因此我们还需要进行 need[i][a][b] = min({need[i][a][b] , need[i][a - 1][b] , need[i][a][b - 1]}) 。
那么最后我们就通过这个得到最终的答案了。
#include <bits/stdc++.h>
using namespace std;
unsigned seed;
const int M = 998244353;
long long qm(long long a, long long b = M - 2) {
long long ans = 1;
for (; b; b >>= 1) {
if (b & 1) ans = a * ans % M;
a = a * a % M;
}
return ans;
}
int need[10][401][401];
int main() {
cin.tie(0)->sync_with_stdio(false);
int n, q;
cin >> n >> q;
memset(need, 0x3f, sizeof(need));
for (int i = 0; i < n; i++) {
int k;
cin >> k;
while (k--) {
int a, b, c;
cin >> a >> b >> c;
need[i][a][b] = min(need[i][a][b], c);
}
for (int a = 1; a <= 400; a++) {
for (int b = 1; b <= 400; b++) {
need[i][a][b] = min({need[i][a][b], need[i][a][b - 1], need[i][a - 1][b]});
}
}
}
cin >> seed;
auto solve = [&](int IQ, int EQ, int AQ) -> int {
int ans = 0;
for (int i = 0; i < n; i++) {
ans += need[i][IQ][EQ] <= AQ ? 1 : 0;
}
return ans;
};
std::mt19937 rng(seed);
std::uniform_int_distribution<> u(1, 400);
int lastans = 0;
long long ans = 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
ans += lastans * qm(seed, q - i);
ans %= M;
}
cout << ans << '\n';
}
K - NIO’s Sword
从 1 ~ n 每次前进一次，手里此时拥有 $A = i - 1$ 如果想要达到 $i + 1$ 可以经过数次 $A = 10 \times A + x(x\in[0 , 9]) \mod n$ 的变化。求取最小的变化次数。
假设我们在手里拥有数字 $i - 1$。此时我们的目标是 $i$，假设其一共变化了 $q$ 次。那么我们可以得到 $k\times n + i = 10^q \times (i - 1)+ b$
我们的 $q$ 就是此时的变换次数。
我们可以得到如下的式子
$0 \le b < 10^q$ 和 $b = k\times n + i - 10^q\times(i - 1)$
那么我们最终只需要验证 b 的范围即可验证是否成立。
由于 $n\le 10^6$，所以我们通过枚举 $q$ 的形式来得到答案。
对于确定的 $q$ 我们的 $k\times n + i \ge 10^q \times (i - 1)$
即 $k\ge \lceil \frac{10^q\times(i - 1) - i}{n} \rceil$
此时我们再将求出来的 $k$ 带回到原来的方程中求出 $b$ 即可得到我们的结果。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 998244353;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll ten[20];
int main() {
ll n;
cin >> n;
if(n == 1) {
cout << 0 << '\n'; // 1 % 1 == 0 切记！
return 0;
}
ten[0] = 1;
for (int i = 1; i < 20; i++) {
ten[i] = ten[i - 1] * 10;
}
int ans = 1;
for (int i = 2; i <= n; i++) {
for (int q = 1; q < 20; q++) {
if((i - 1) * ten[q] - i < 0) continue;
long long k = (1ll * (i - 1) * ten[q] - i) / n;
while (k * n + i < ten[q] * (i - 1)) {
k++;
}
long long b = 1ll * k * n + i - ten[q] * (i - 1);
if (b < ten[q] && b >= 0) {
ans += q;
// cout << i << ' ' << q << '\n';
break;
}
}
}
cout << ans << '\n';
return 0;
}
N - Particle Arts
有 N 个数字，每次一对数字，我们将这对数字进行一次变换，对于原先的数字 $a$ $b$ 我们，将这对数字变换为 $a \mid b$ 和 $a \& b$。
假如对于特定的某一位而言，我们可以发现，对于一对 0 ，不会改变，对于一对 1 ，也是不会改变，对于一对 01 依然不会改变，因此，我们可以发现，我们在进行这个变换的时候我们每一位的结果中，其 1 的个数不会改变。
不过衍生到具体的两个数字中，我们可以发现，对于一个 01 而言，其 1 一定会在 $a \mid b$ 中，其 0 一定会在 $a\& b$ 中，因此我们可以发现，在不断的进行变换的过程中，我们的 1 不断的在往某几个数字进行聚集，0 也同样如此。
最后我们不妨将这些 1 的数量记录下来，我们最后就可以得到答案了。
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void print(__int128_t x) {
vector<char> buff;
while (x) {
buff.push_back(x % 10 + '0');
x /= 10;
}
for (int i = buff.size() - 1; i >= 0; i--) {
cout << buff[i];
}
}
int main() {
int n;
cin >> n;
vector<int> u(n);
vector final(15, 0);
for (auto &x : u) cin >> x;
for (auto &x : u) {
for (int i = 0; i < 15; i++) {
if ((x >> i) & 1) {
final[i]++;
}
}
}
for (int i = 0; i < n; i++) {
u[i] = 0;
for (int j = 0; j < 15; j++) {
if (i < final[j]) u[i] |= 1 << j;
}
}
__int128_t sum = 0;
__int128_t a = 0;
for (auto x : u) sum += x;
for (auto x : u) a += (1ll * n * x - sum) * (1ll * n * x - sum);
__int128_t b = 1ll * n * n * n;
auto x = __gcd(a, b);
a /= x, b /= x;
if (a == 0 || b == 0) {
cout << "0/1\n";
return 0;
}
print(a);
putchar('/');
print(b);
return 0;
}