个人难度评级
签到：$BGJ$
简单：$DEFI$
中等：$ACH$
A 智乃的二进制
不难发现，$10^a$ 都是好数：$10^a = 2^a \cdot 5^a$ ，所以它的二进制最后 $a$ 位都是 $0$ ，又因为 $5^a$ 是奇数，所以倒数第 $a+1$ 位一定是 $1$ 。
其次，对于 $10^a+10^b,a>b$ ，只要满足 $b\equiv 0\pmod{2^{a-b-1}}$ ，它就是好数：
如果满足好数定义，就有
$$X\equiv 2^a+2^b\pmod{2^{a+1}}$$
也就是
$$10^a+10^b\equiv 2^a+2^b\pmod{2^{a+1}}$$
然后化简一下，得到
$$2^{a-b}(5^a-1)+(5^b-1)\equiv 0\pmod {2^{a-b+1}}$$
也就是
$$5^b-1\equiv 0 \pmod {2^{a-b+1}}$$
现在我们要求 m 满足什么条件时，5^m−1 能被 2^{a-b+1} 整除。
我们展开得到
$$v_2(5^m-1) = v_2(m)+v_2(5-1) = v_2(m)+2$$
我们要 $v_2(5^m-1)\geq a-b+1$ ，也就是 $v_2(m)\geq a-b-1$ ，就能得到 $m$ 必须是 $2^{a-b-1}$ 的倍数。
由以上结论也能发现，好数总是被 $10^a$ 分割成几个部分，直接计算一下还原即可。
void solve() {
ll k;
cin >> k;
auto check = [&](ll x) {
if (x < 0)
return 0ll;
ll s = 1 + 2 * x;
for (int i = 1; i <= 62; ++i) {
ll p = 1ll << (i - 1);
if (p > x)
break;
s += (x - i) / p;
}
return s;
};
ll l = 0, r = 2e18, n = 0;
while (l <= r) {
ll mid = (l + r) >> 1;
if (check(mid) >= k)
n = mid, r = mid - 1;
else
l = mid + 1;
}
ll R = k - check(n - 1);
if (R == 1)
cout << ksm(Z(10), n) << endl;
else if (R == 2)
cout << ksm(Z(10), n) + 1 << endl;
else {
vector<int> D;
for (int i = 1; i <= 62; ++i) {
if (i >= n)
break;
if ((n - i) % (1ll << (i - 1)) == 0)
D.pb(i);
}
sort(rall(D));
int d = D[R - 3];
cout << ksm(Z(10), n) + ksm(Z(10), n - d) << endl;
}
}B 智乃的瓷砖
用一个标记记录一下每行的开头是什么，然后每行每一个都和前一个不一样即可。
void solve() {
bool f1 = 0;
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if ((j & 1) == f1)
cout << '/';
else
cout << '\\';
}
f1 = !f1;
cout << endl;
}
cout << endl;
}C 智乃的草坪
每个点在第 $t$ 秒的半径为 $R_i = v_i t$ 。对于位于 $(p_i,0)$ 的圆，当且仅当 $R_i \geq r$ 时，它在水平方向上存在能覆盖整段竖直区间 $[-r,r]$ 的投影区间。具体地，此时在 $x$ 轴上它能覆盖的整列 $x$ 满足
$$(x-p_i)^2\leq R_i^2-r^2$$
因此对应的区间为
$$[p_i-\sqrt{R_i^2-r^2},p_i+\sqrt{R_i^2-r^2}]$$
要覆盖整个矩形 $[0,c]\times[-r,r]$ ，等价于这些区间（从选定的至多 $k$ 个点产生）能覆盖段 $[0,c]$ 。
于是对给定的时间 $t$ ，我们可以把每个点能形成的区间计算出来（如果 $R_i<r$ 则忽略），得到若干区间。然后从当前位置 $cur=0$ 开始，每步在所有左端 $\le cur$ 的区间中取右端最远的一个，更新 $cur$ 到该最远右端，计数加 $1$ ；若超过 $k$ 次仍未覆盖到 $c$ 则失败。（也就是区间线段覆盖问题）
这个判定是显然单调的：时间越大，区间越宽，覆盖更容易，所以我们可以使用二分计算时间。
void solve() {
int n, k;
ld r, c;
cin >> n >> k >> r >> c;
vector<pair<ld, ld>> pts(n);
for (int i = 0; i < n; ++i) {
cin >> pts[i].fi >> pts[i].se;
}
auto check = [&](ld t) {
vector<pair<ld, ld>> segs;
for (auto [p, v] : pts) {
ld R = v * t;
if (R + eps < r)
continue;
ld h = sqrt(max(0.0l, R * R - r * r));
ld L = p - h, Rr = p + h;
segs.eb(L, Rr);
}
if (segs.empty())
return false;
sort(all(segs));
ld cur = 0.0l;
int used = 0, idx = 0;
int m = segs.size();
while (cur + eps < c && used < k) {
ld mx = cur;
while (idx < m && segs[idx].fi <= cur + eps) {
if (segs[idx].se > mx)
mx = segs[idx].se;
++idx;
}
if (mx <= cur + eps)
break;
cur = mx;
++used;
}
return (cur + eps >= c);
};
ld lo = 0.0l, hi = INF, ans = hi;
for (int it = 0; it < 100; ++it) {
ld mid = (lo + hi) / 2.0l;
if (check(mid))
ans = mid, hi = mid;
else
lo = mid;
}
cout << ans << endl;
}D 智乃的果子
直觉告诉我们肯定是从小往大合并会比较优。我们用优先队列记录一下果子的重量和数量，每次都取最轻的处理，把其中的一半两两合并；如果这一组只有一个果子，我们就再取一组与它合并。
void solve() {
int n;
ll tot = 0;
cin >> n;
priority_queue<PLL> pq;
for (int i = 0; i < n; ++i) {
ll c, w;
cin >> c >> w;
pq.push({-w, c});
tot += c;
}
if (tot <= 1) {
cout << 0 << endl;
return;
}
Z ans = 0;
while (tot > 1) {
auto [w, c] = pq.top();
pq.pop();
w = -w;
if (c >= 2) {
ll P = c / 2;
ans += Z(2) * w * P;
pq.push({-w * 2, P});
if (c & 1)
pq.push({-w, 1});
tot -= P;
} else {
auto [tw, tc] = pq.top();
pq.pop();
tw = -tw, tc--;
ans += w + tw;
pq.push({-w - tw, 1});
if (tc)
pq.push({-tw, tc});
tot--;
}
}
cout << ans << endl;
}E 智乃的最大子段和取模
模意义下也可以进行前缀和的操作，$[l,r]$ 的子段和为 $(pre[r+1]-pre[l]+p)\% p$ ，所以对于每个 $j=r+1$ ，我们都需要找一个 $t$ 使得 $(pre[r+1]-pre[l]+p)\% p$ 最大即可。
如果 $pre[j]\geq pre[t]$ ，那么找最小 $pre[t],t\leq j$ 就行；如果 $pre[j]<pre[t]$ ，也就是原式为 $p-(pre[t]-pre[j])$ ，所以我们要取最接近 $pre[j]$ 的 $pre[j]$ 。所以对每一个 $j$ 检查这两类即可。
void solve() {
int n, p;
cin >> n >> p;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
vector<ll> pre(n + 1);
for (int i = 1; i <= n; ++i) {
pre[i] = (pre[i - 1] + a[i - 1]) % p;
}
set<PLL> s;
s.insert({0, 0});
ll mx = -1;
int L = 0, R = 0;
for (int j = 1; j <= n; ++j) {
ll cur = pre[j];
if (s.begin() != s.end()) {
ll val = (cur - s.begin()->fi + p) % p;
if (val > mx) {
mx = val;
L = s.begin()->se;
R = j - 1;
}
}
auto it = s.upper_bound({cur, INF});
if (it != s.end()) {
ll val = (cur - it->fi + p) % p;
if (val > mx) {
mx = val;
L = it->se;
R = j - 1;
}
}
s.insert({cur, j});
}
cout << L << " " << R << " " << mx << endl;
}F 智乃的算法竞赛群友
我们设 $x$ 为 $\text{qcjjkkt}$ 的个数， $y$ 为 $\text{td}$ 的个数，当一个 $\text{td}$ 使用 $\text{qcjjkkt}$ 末尾的 $\text{t}$ 的时候，我们就能节省一个字符。
所以：
- $x\leq y$ ，最小的长度为 $6x+2y$ 。
- $x>y$ ，最小的长度为 $7x+y$ 。
我们要求的就是满足最小长度 $\leq n$ 的 $ax+by$ ，对于固定的 $x$ ，我们只需要检查几个可能取到最值的 $y$ 即可，也就是 ${0,\lfloor\frac{n}{8}\rfloor,\lfloor\frac{n}{7}\rfloor}$ 以及周围的一些点。
constexpr ll INF = 2e18;
void solve() {
ll n, a, b;
cin >> n >> a >> b;
vector<ll> X;
X.pb(0);
auto check = [&](ll x) {
return 0 <= x && x <= n;
};
for (int i = -3; i <= 3; ++i) {
if (check(n / 8 + i))
X.pb(n / 8 + i);
if (check(n / 7 + i))
X.pb(n / 7 + i);
if (check((n + 1) / 8 + i))
X.pb((n + 1) / 8 + i);
}
for (int i = 0; i <= 6; ++i)
if (check(i))
X.pb(i);
sort(all(X));
X.erase(unique(all(X)), X.end());
auto calc = [&](ll x) {
ll mx = -1;
if (x <= n / 8) {
ll t = (n - 6 * x) / 2;
if (t >= x) {
mx = t;
} else {
if (n - 7 * x >= 0) {
mx = max(x - 1, n - 7 * x);
} else {
return -INF;
}
}
} else {
if (n - 7 * x >= 0) {
mx = min(x - 1, n - 7 * x);
} else {
return -INF;
}
}
if (mx < 0)
return -INF;
return a * x + b * mx;
};
ll ans = 0;
bool f = 0;
for (auto x : X) {
ll val = calc(x);
if (val == -INF)
continue;
if (!f || val > ans) {
ans = val;
f = 1;
}
}
if (!f)
cout << 0 << endl;
else
cout << ans << endl;
}G 智乃的箭头魔术
模拟一下即可，模拟的代码如下
void solve() {
string s = "0112233445142015320125410214530214510214102302142025101203201451451522302514203214510021454101002532";
int c = 0;
for (auto v : s) {
if (v == '0')
c = 3 - c;
else if (v == '1') {
if (c == 3)
c = 1;
else if (c == 1)
c = 3;
} else if (v == '2') {
if (c == 0)
c = 1;
else if (c == 1)
c = 0;
else if (c == 3)
c = 2;
else if (c == 2)
c = 3;
} else if (v == '3') {
if (c == 0)
c = 2;
else if (c == 2)
c = 0;
} else if (v == '4') {
c = (c + 1) % 4;
} else if (v == '5') {
c = (c + 3) % 4;
}
cout << c;
}
}答案为
3132333010010310230010130130330130312312210210010321300120122322322101123223211001003013030031210332H 智乃的矩阵
首先我们发现，进行一次操作之后，所有元素之和不变，所以最开始元素之和一定要为 $n^2$ 的倍数，我们令 $T = tot/n^2$。
其次我们发现，对于每种操作，如果把矩阵染成黑白格，即 $i+j$ 为奇数的格子染黑，$i+j$ 为偶数的格子染白，那么对于同一种颜色，每种操作都不会改变这个颜色的元素之和，所以令颜色的格子数为 $cnt$ ，该颜色的元素之和为 $sum$ ，任何一种颜色都要满足 $sum=cnt\times T$。
然后我们发现，在模 2 的意义下，每次操作（无论是加还是减）相当于给选定的 $2\times 2$ 区域内的 4 个数都 $+1$（因为 $1\equiv -1\pmod 2$ ）。所以我们需要判断是否能通过若干次 $2\times 2$ 区域的翻转，将矩阵 $B$（其中 $B_{i,j}=(A_{i,j}−T)\pmod 2$ ）变成全 $0$ 矩阵。我们用贪心或者高斯消元都可以解决，这里给出贪心的解法。
设 $X_{i,j}$ 为模 $2$ 意义下以 $(i,j)$ 为左上角的操作次数。对于位置 $(1,1)$，只有操作 $X_{1,1}$ 能影响它。为了使 $B_{1,1}$ 变为 $0$ ，必须有 $X_{1,1}=B_{1,1}$ 。对于位置 $(i,j)$ ，它受到 $X_{i,j}$ 、$X_{i−1,j}$ 、$X_{i,j−1}$ 、$X_{i−1,j−1}$ 的影响。当我们遍历到 $(i,j)$ 时，后三者已经确定，因此 $X_{i,j}$ 被唯一确定。计算出所有 $1≤i,j<n$ 的 $X_{i,j}$ 后，还需要检查矩阵的边界（第 $n$ 行和第 $n$ 列）是否也满足变成了 0。如果不满足，则无法达成。
void solve() {
int n;
ll tot = 0, sum = 0, cnt = 0;
cin >> n;
vector<vector<int>> a(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
cin >> a[i][j], tot += a[i][j], sum += (i + j & 1) * a[i][j], cnt += i + j & 1;
if (n == 1) {
cout << "Yes" << endl;
return;
}
if (tot % (n * n) != 0) {
cout << "No" << endl;
return;
}
ll T = tot / (n * n);
if (sum != cnt * T) {
cout << "No" << endl;
return;
}
vector<vector<int>> b(n + 2, vector<int>(n + 2));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
b[i][j] = ((a[i][j] - T) % 2 + 2) % 2;
}
}
vector<vector<int>> x(n + 2, vector<int>(n + 2));
for (int i = 1; i < n; ++i) {
for (int j = 1; j < n; ++j) {
x[i][j] = b[i][j] ^ x[i - 1][j] ^ x[i][j - 1] ^ x[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
int cur = 0;
if (i < n && j < n)
cur ^= x[i][j];
if (i > 1 && j < n)
cur ^= x[i - 1][j];
if (i < n && j > 1)
cur ^= x[i][j - 1];
if (i > 1 && j > 1)
cur ^= x[i - 1][j - 1];
if (cur != b[i][j]) {
cout << "No" << endl;
return;
}
}
}
cout << "Yes" << endl;
}I 智乃挖坑
首先怎么去判定被挖穿，直接模拟肯定会超时，所以我们考虑使用差分。对于每一个坑我们都可以拆成两部分，左半深度增加，右半深度减小，我们维护这两个差分数组，然后做前缀和就可以检查有没有超过 $h$ 了。
那么对于整个时间轴，肯定能找到一个时间点，前面都没被挖穿，后面都被挖穿了，所以我们使用二分去计算次数，每次 $\text{check}$ 的时候模拟一下即可。
void solve() {
int n, m;
ll h;
cin >> n >> m >> h;
vector<PII> ops(m);
for (int i = 0; i < m; ++i) {
cin >> ops[i].fi >> ops[i].se;
}
auto check = [&](int t) {
vector<ll> A(n + 2), B(n + 2);
for (int i = 0; i < t; ++i) {
auto [p, f] = ops[i];
int L = max(1, p - (f - 1)), R = min(n, p + (f - 1));
int l1 = L, r1 = min(p, R);
if (l1 <= r1) {
A[l1] += 1, A[r1 + 1] -= 1;
B[l1] += f - p, B[r1 + 1] -= f - p;
}
int l2 = max(p + 1, L), r2 = R;
if (l2 <= r2) {
A[l2] += -1, A[r2 + 1] -= -1;
B[l2] += f + p, B[r2 + 1] -= f + p;
}
}
ll a = 0, b = 0;
for (int j = 1; j <= n; ++j) {
a += A[j];
b += B[j];
if (a * j + b > h)
return 1;
}
return 0;
};
if (!check(m)) {
cout << "No" << endl;
return;
}
int lo = 1, hi = m, ans = m;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (check(mid)) {
ans = mid;
hi = mid - 1;
} else
lo = mid + 1;
}
cout << "Yes" << endl;
cout << ans << endl;
}J 智乃的幻方
暴力检查一下即可。
void solve() {
vector<vector<int>> a(3, vector<int>(3));
unordered_set<int> st;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cin >> a[i][j];
st.insert(a[i][j]);
}
}
if (st.size() != 9) {
cout << "No" << endl;
return;
}
int S = a[0][0] + a[0][1] + a[0][2];
for (int i = 0; i < 3; ++i) {
int s = 0;
for (int j = 0; j < 3; ++j) {
s += a[i][j];
}
if (s != S) {
cout << "No" << endl;
return;
}
}
for (int i = 0; i < 3; ++i) {
int s = 0;
for (int j = 0; j < 3; ++j) {
s += a[j][i];
}
if (s != S) {
cout << "No" << endl;
return;
}
}
if (a[0][0] + a[1][1] + a[2][2] != S) {
cout << "No" << endl;
return;
}
if (a[2][0] + a[1][1] + a[0][2] != S) {
cout << "No" << endl;
return;
}
cout << "Yes" << endl;
}头文件
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define endl "\n"
using namespace std;
using ll = long long;
using ld = long double;
using ui = unsigned;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using TIII = tuple<int, int, int>;
using TLLL = tuple<ll, ll, ll>;
void init() {
}
void solve() {
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
init();
int t = 1;
cin >> t;
cout << fixed << setprecision(15);
for (int _ = 1; _ <= t; ++_) {
solve();
}
return 0;
}自动取模
constexpr int MOD = 1e9+7;
template <class T>
constexpr T ksm(T a, ll b) {
T res = 1;
while (b) {
if (b & 1)
res *= a;
b >>= 1;
a *= a;
}
return res;
}
template <int P>
struct MInt {
int x;
constexpr MInt() : x() {}
constexpr MInt(ll x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return ksm(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr istream &operator>>(istream &is, MInt &a) {
ll v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr ostream &operator<<(ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template <>
int MInt<0>::Mod = 998244353;
template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
using Z = MInt<MOD>;