website·Indexed 29 days ago
https://roorli.netlify.appA personal technical blog and knowledge base featuring competitive programming solutions (BZOJ, DTOJ, JZOJ), mathematical algorithms such as Möbius inversion and Lucas theorem, and technical memos on Docker, Git, and Spring Boot.
Useful websites for design inspiration, system architecture diagrams, and image processing:
The Fast Fourier Transform (FFT) is used to optimize the multiplication of two polynomials of size $n$. While a naive multiplication takes $O(n^2)$ time, FFT reduces the complexity to $O(n \log n)$. The process follows three main steps:
MaxEnt can be expressed in two equivalent ways depending on the perspective:
These are equivalent because a uniform distribution in geographic space maps to the background environmental distribution f(z) in environmental space.
The problem requires placing the maximum number of artillery units on an N x M grid (N ≤ 100, M ≤ 10) such that no two units attack each other. A unit attacks 2 cells horizontally and 2 cells vertically. Because the attack range extends 2 rows, the DP state must track the current row and the previous two rows to ensure validity.
Key Logic:
j is valid if no two bits are within 2 positions of each other (!(j & (j << 1)) and !(j & (j << 2))) and all placed units are on plains ('P').i must not conflict with row i-1 or row i-2 (no bits in the same column).f[i][j][k] represents the maximum units placed up to row i, where row i has state j and row i-1 has state k.f[i][j][k] = max(f[i-1][k][l] + count_bits(j)) for all valid states l of row i-2 that do not conflict with states j and k.#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m, f[105][70][70], tmp[105], sta[105][70], num[105][70], cnt[105], ans;
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
char a; scanf(" %c", &a);
tmp[i] <<= 1; tmp[i] += (a == 'P');
}
// Precompute valid states for each row
for(int i = 1; i <= n; i++)
for(int j = 0; j < (1 << m); j++)
if(!(j & (j << 2)) && !(j & (j << 1)) && (j & tmp[i]) == j) {
sta[i][++cnt[i]] = j;
for(int k = j; k; k >>= 1) num[i][cnt[i]] += ((k & 1) > 0);
}
// Base cases: Row 1 and Row 2
for(int i = 1; i <= cnt[1]; i++) f[1][i][0] = num[1][i];
for(int i = 1; i <= cnt[2]; i++)
for(int j = 1; j <= cnt[1]; j++)
if(!(sta[2][i] & sta[1][j])) f[2][i][j] = max(f[2][i][j], f[1][j][0] + num[2][i]);
// DP Transition for rows 3 to N
for(int i = 3; i <= n; i++)
for(int j = 1; j <= cnt[i]; j++)
for(int k = 1; k <= cnt[i-1]; k++)
if(!(sta[i][j] & sta[i-1][k]))
for(int l = 1; l <= cnt[i-2]; l++)
if(!(sta[i][j] & sta[i-2][l]) && !(sta[i-1][k] & sta[i-2][l]))
f[i][j][k] = max(f[i][j][k], f[i-1][k][l] + num[i][j]);
for(int i = 1; i <= cnt[n]; i++)
for(int j = 1; j <= cnt[n-1]; j++) ans = max(ans, f[n][i][j]);
printf("%d\n", ans);
return 0;
}The problem asks for the minimum cost to redistribute haybales across $N$ piles arranged in a circle to match a target distribution. Moving one haybale one step costs 1 unit of effort.
Mathematical Approach:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define N 100005
using namespace std;
int n, a, b, s[N];
int main() {
if (scanf("%d", &n) != 1) return 0;
for (int i = 1; i <= n; i++) {
scanf("%d%d", &a, &b);
// Calculate prefix sum of the difference between current and target
s[i] = s[i - 1] + a - b;
}
// Sort to find the median
sort(s + 1, s + n + 1);
// The optimal value for the circular shift is the negative of the median
int x = -s[(n + 1) / 2];
long long ans = 0;
for (int i = 1; i <= n; i++) {
ans += abs(s[i] + x);
}
printf("%lld\n", ans);
return 0;
}To find the nearest point in a 2D plane using Manhattan distance ($ ext{dist}(A,B) = |A_x - B_x| + |A_y - B_y|$) with dynamic point additions and queries, the problem can be transformed into a partial order problem suitable for CDQ Divide and Conquer.
Because of the absolute values, the distance calculation varies by quadrant. To avoid implementing four separate CDQ passes, use coordinate transformation (flipping) to map all quadrants to the third quadrant. By subtracting the original coordinates from the maximum value of the coordinate range, you can treat all queries as if they are looking for points in a single direction (e.g., $x ext{ and } y$ both smaller than the query point).
Key strategy:
// Core logic for updating and querying the Fenwick tree to find max(x + y)
inline void update(int x, int v) {
for (; x <= V; x += x & -x) tr[x] = max(tr[x], v);
}
inline int query(int x) {
int res = 0;
for (; x; x -= x & -x) res = max(res, tr[x]);
return res ? res : -1e9;
}
// CDQ Divide and Conquer to handle time-based partial order
inline void cdq(int l, int r) {
if (l == r) return;
int mid = l + r >> 1;
cdq(l, mid);
cdq(mid + 1, r);
int i = l, j = mid + 1, ind = l;
while (i <= mid && j <= r)
if (d[i].x <= d[j].x) {
if (d[i].t < 2) update(d[i].y, d[i].s); // Add point
e[ind++] = d[i++];
} else {
if (d[j].t > 1) ans[d[j].id] = min(d[j].s - query(d[j].y), ans[d[j].id]); // Query distance
e[ind++] = d[j++];
}
// ... remaining merge and cleanup logic
}note, info, tip, warning, caution, and important.long long k = 0;
for (long long i = n; i; i /= 5) {
k += i / 5;
}
// k is the number of trailing zerosTo convert a polynomial $A(x) = a_0 + a_1x + \dots + a_{n-1}x^{n-1}$ (where $n$ is a power of 2) into point-value representation, the polynomial is split into even and odd indexed coefficients:
$A(x) = A_1(x^2) + x A_2(x^2)$ where:
By substituting $\omega_n^k$ and $\omega_n^{k+n/2}$ (where $\omega$ is the $n$-th root of unity), the values can be computed recursively:
This divide-and-conquer approach reduces the computation time to $O(n \log n)$.
extfile.cnf to avoid connection errors.# 1. Setup directory
mkdir /docker-ca && cd /docker-ca
# 2. Create CA key and certificate
openssl genrsa -aes256 -out ca-key.pem 4096
openssl req -new -x509 -days 365 -key ca-key.pem -sha256 -out ca.pem
# 3. Create Server key and CSR
openssl genrsa -out server-key.pem 4096
openssl req -subj "/CN=your_ip" -sha256 -new -key server-key.pem -out server.csr
# 4. Configure server whitelist and usage
echo "subjectAltName = IP:your_servers_ip,IP:0.0.0.0" >> extfile.cnf
echo "extendedKeyUsage = serverAuth" >> extfile.cnf
# 5. Sign Server certificate
openssl x509 -req -days 365 -sha256 -in server.csr -CA ca.pem -CAkey ca-key.pem -CAcreateserial -out server-cert.pem -extfile extfile.cnf
# 6. Create Client key and CSR
openssl genrsa -out key.pem 4096
openssl req -subj '/CN=client' -new -key key.pem -out client.csr
# 7. Configure client usage and sign certificate
echo "extendedKeyUsage = clientAuth" >> extfile.cnf
openssl x509 -req -days 365 -sha256 -in client.csr -CA ca.pem -CAkey ca-key.pem -CAcreateserial -out cert.pem -extfile extfile.cnf
# 8. Cleanup and set permissions
rm -v client.csr server.csr
chmod -v 0400 ca-key.pem key.pem server-key.pem
chmod -v 0444 ca.pem server-cert.pem cert.pem
# 9. Deploy server certificates
cp server-cert.pem /etc/docker/
cp server-key.pem /etc/docker/
cp ca.pem /etc/docker/The problem asks for the maximum profit obtainable from a sequence of $n$ locations. Each location is either a coal mine or a supply station.
To solve this, use backward Dynamic Programming. Let $f[i]$ be the maximum relative profit obtainable from location $i$ to $n$, where the profit is expressed as a multiplier of the current magic power $p$.
Transitions:
The final answer is the maximum value of $f[i] \times w$ (where $w$ is the initial magic power) across all $i$.
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define N 100005
using namespace std;
int n, k, c, w, t[N], a[N];
double f[N], ans;
int main() {
scanf("%d%d%d%d", &n, &k, &c, &w);
for(int i = 1; i <= n; i++) scanf("%d%d", &t[i], &a[i]);
f[n+1] = 0;
for(int i = n; i; i--) {
if(t[i] == 1) // Coal Mine
f[i] = max(f[i+1], f[i+1] * (1 - 1.0 * k / 100.0) + 1.0 * a[i]);
else // Supply Station
f[i] = max(f[i+1], f[i+1] * (1 + 1.0 * c / 100.0) - 1.0 * a[i]);
ans = max(ans, f[i] * w);
}
printf("%.2lf\n", ans);
return 0;
}