20240901
T1
Luogu P4801 饥饿的狐狸
最大值考虑在两个极端之间反复横跳即可。每次跳的时候判一下先喝水是否更优。从最大和最小开始跳都要试一下。
最小值随便分讨一下即可。别漏情况了。
代码
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int n, t;
int a[2000050];
int o[2000005];
signed main() {
cin >> n >> t;
for (int i = 1; i <= n; i++) cin >> a[i], a[0] += a[i];
sort(a + 1, a + n + 1);
// cout << a[n] << " " << a[0] << "\n";
// return 0;
int brk = 0;
for (int i = 1; i <= n; i++) {
if (a[i] <= t)
brk = i;
}
int ocnt = 0;
int cur = 0;
for (int i = 1, a = 1, b = n; a <= b;) {
if (cur == 1)
o[++ocnt] = b, --b;
else
o[++ocnt] = a, ++a;
cur ^= 1;
}
// // for (int i = 1; i <= n; i++) cout << o[i] <<"\n";
int ans = 0, lst = t;
for (int i = 1; i <= ocnt; i++) {
ans += max(abs(a[o[i]] - lst), abs(a[o[i]] - t));
lst = a[o[i]];
}
if (brk == n) {
cout << t - a[1] <<" ";
} else if (brk == 0)
cout << a[n] - t << " ";
else
cout << min(a[n] - a[1], min(abs(t - a[1]) + a[n] - a[1] - abs(t - a[brk]), abs(t - a[n]) + a[n] - a[1] - abs(a[brk + 1] - t))) << " ";
int Ans = ans;
ocnt = ans = 0;
cur = 1;
for (int i = 1, a = 1, b = n; a <= b;) {
if (cur == 1)
o[++ocnt] = b, --b;
else
o[++ocnt] = a, ++a;
cur ^= 1;
}
lst = t;
for (int i = 1; i <= ocnt; i++) {
ans += max(abs(a[o[i]] - lst), abs(a[o[i]] - t));
lst = a[o[i]];
}
cout << max(Ans, ans) << "\n";
return 0;
}
T2
NFLSOJ P487 有限空间跳跃理论
设 \(dp[S]\) 表示 \(S\) 集合内点构成 DAG 的方案数，转移枚举一个子集使得其中所有点入度均为 \(0\)，容斥即可。
代码
#include <iostream>
#define int long long
#define lowbit(x) ((x) & (-(x)))
const int P = 1000000007;
using namespace std;
inline void Madd(int& x, int y) { (x += y) >= P ? (x -= P) : 0; }
int n, m;
int pcnt[1100005];
int dp[1100005];
int ce[1100005];
int pw[2005];
int ans;
signed main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
int x = ((1 <<(u - 1)) | (1 << (v - 1)));
for (int j = 2; j < (1 << n); j++) {
if ((x & j) == x)
++ce[j];
}
}
pw[0] = 1;
for (int i = 0; i < n; i++) dp[1 << i] = 1, pcnt[1 << i] = 1;
for (int i = 1; i <= m; i++) pw[i] = pw[i - 1] * 2 % P;
for (int i = 2; i < (1 << n); i++) {
if (pcnt[i])
continue;
pcnt[i] = pcnt[i - lowbit(i)] + 1;
if (!ce[i]) {
dp[i] = 1;
continue;
}
for (int j = (i - 1) & i; j; j = (j - 1) & i) {
if (ce[j])
continue;
if (pcnt[j] & 1)
Madd(dp[i], dp[i ^ j] % P);
else
Madd(dp[i], (P - dp[i ^ j]) % P);
// cout <<j << " to " << i << "\n";
}
// cout << i << " " << dp[i] << "\n";
}
cout << dp[(1 << n) - 1] << "\n";
return 0;
}
T3
NFLSOJ P488 神秘代码
考虑把数之间两倍的关系视为边，则形成的所有链长度不会超过 \(6\)。发现把 \(40\) 按这样划分成若干条链的本质不同（链长的计数数组不同）的方案数并不多，只有 \(4 \times 10^4\)，考虑直接爆搜。依次去填每一位，相当于每次把一条链断开。考虑当前位的限制。
当前位限制如果为 \(0\)，则考虑上次分裂出的两条链 \(l, r\)，我们当前选的数不能是 \(l\) 的最后一个或 \(r\) 的第一个。当前位限制如果为 \(1\)，则当前选的数要么是 \(l\) 的最后一个，要么是 \(r\) 的第一个。在 \(1\) 后面如果还有连续的 \(1\)，则这些 \(1\) 选择的方向必须相同。于是状态就是 \(dp[S][l][r][x]\)，其中 \(S\) 为链长的计数数组，\(x = 0 / 1 / 2\) 表示当前连续 \(1\) 的方向。
每一位的转移，如果当前位是 \(0\) 就直接枚举要断开哪个长度的链，然后再枚举在什么位置断开。当前位是 \(1\) 就顺着前面留下的方向走（如果前面留下了），或者两个情况都转移（如果前面没钦定方向）。
代码
#include <iostream>
#include <string.h>
#include <vector>
#include <map>
#define int long long
using namespace std;
const int P = 1000000007;
void Madd(int& x, int y) { (x += y) >= P ? (x -= P) : 0; }
int n;
string str;
map<vector<int>, int> mp;
int dp[400005][7][7][3];
int mcnt;
int dfs(vector<int> vec, int l, int r, int x) {
vec[0] = 0;
int res = vec[1] + vec[2] * 2 + vec[3] * 3 + vec[4] * 4 + vec[5] * 5 + vec[6] * 6;
if (!res)
return 1;
int id = (mp[vec] ? mp[vec] : (mp[vec] = ++mcnt));
if (dp[id][l][r][x] != -1)
return dp[id][l][r][x];
int& cur = dp[id][l][r][x];
cur = 0;
if (str[n - res] == '0' || res == n) {
--vec[l], --vec[r];
for (int i = 1; i <= 6; i++) {
if (!vec[i])
continue;
int tmp = vec[i];
++vec[l], ++vec[r], --vec[i];
for (int j = 1; j <= i; j++) {
++vec[j - 1], ++vec[i - j];
Madd(cur, dfs(vec, j - 1, i - j, 2) * tmp % P);
--vec[j - 1], --vec[i - j];
}
--vec[l], --vec[r], ++vec[i];
}
++vec[l], ++vec[r];
for (int i = 1; i < l; i++) {
--vec[l], ++vec[i - 1], ++vec[l - i];
Madd(cur, dfs(vec, i - 1, l - i, 2));
++vec[l], --vec[i - 1], --vec[l - i];
}
for (int i = 2; i <= r; i++) {
--vec[r], ++vec[i - 1], ++vec[r - i];
Madd(cur, dfs(vec, i - 1, r - i, 2));
++vec[r], --vec[i - 1], --vec[r - i];
}
} else {
if (l && x != 1) {
--vec[l], ++vec[l - 1];
Madd(cur, dfs(vec, l - 1, 0, 0));
++vec[l], --vec[l - 1];
}
if (r && x != 0) {
--vec[r], ++vec[r - 1];
Madd(cur, dfs(vec, 0, r - 1, 1));
++vec[r], --vec[r - 1];
}
}
return cur;
}
signed main() {
memset(dp, -1, sizeof dp);
cin >> n >> str;
str = ' ' + str;
vector<int> tmp;
tmp.resize(7);
for (int i = 1; i <= n; i++) {
if (i & 1) {
int cnt = 0;
for (int j = i; j <= n; j <<= 1) ++cnt;
++tmp[cnt];
}
}
cout << dfs(tmp, 0, 0, 2) << "\n";
return 0;
}