记忆化搜索，记忆转移方向。
#include <bits/stdc++.h>
#define dbg(x) cout << (#x) << "=" << x << endl
using namespace std;
const int N = 207;
int m, a, b;
struct Node
{
Node()
{
this->x = -2;
}
Node(int x, int y, int a, int b)
{
this->x = x;
this->y = y;
this->a = a;
this->b = b;
}
int x, y, a, b;
};
int dp[6][6][N][N];
Node last[6][6][N][N];
int solve(int x, int y, int a, int b)
{
if (x < 0 || y < 0 || a < 0 || b < 0)
return 0;
if (dp[x][y][a][b] != -1)
return dp[x][y][a][b];
if (!x && !y)
{
if (!a && !b)
return 1;
else
return 0;
}
int up;
if (x + y == 5)
up = 15;
else
up = 25;
//transfer1 up:j firstwin
for (int j = 0; j <= up - 2; j++)
{
if (y == 3)
continue;
if (solve(x - 1, y, a - up, b - j))
{
last[x][y][a][b] = Node(x - 1, y, a - up, b - j);
return dp[x][y][a][b] = 1;
}
}
for (int i = up + 1; i <= 200; i++)
{
if (y == 3)
continue;
if (solve(x - 1, y, a - i, b - (i - 2)))
{
last[x][y][a][b] = Node(x - 1, y, a - i, b - (i - 2));
return dp[x][y][a][b] = 1;
}
}
//transfer2 j:up secondwin
for (int j = 0; j <= up - 2; j++)
{
if (x == 3)
continue;
if (solve(x, y - 1, a - j, b - up))
{
last[x][y][a][b] = Node(x, y - 1, a - j, b - up);
return dp[x][y][a][b] = 1;
}
}
for (int i = up + 1; i <= 200; i++)
{
if (x == 3)
continue;
if (solve(x, y - 1, a - (i - 2), b - i))
{
last[x][y][a][b] = Node(x, y - 1, a - (i - 2), b - i);
return dp[x][y][a][b] = 1;
}
}
return dp[x][y][a][b] = 0;
}
void print(int x, int y, int a, int b)
{
Node t = last[x][y][a][b];
// dbg(t.x);
// dbg(t.y);
// dbg(t.a);
// dbg(t.b);
if (t.x == -2)
return;
print(t.x, t.y, t.a, t.b);
cout << a - t.a << ':' << b - t.b;
if (max(x, y) == 3)
cout << endl;
else
cout << ' ';
}
int main()
{
// freopen("A.in", "r", stdin);
scanf("%d", &m);
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= m; i++)
{
scanf("%d %d", &a, &b);
if (solve(3, 0, a, b))
{
cout << "3" << ':' << "0" << endl;
print(3, 0, a, b);
}
else if (solve(3, 1, a, b))
{
cout << "3" << ':' << "1" << endl;
print(3, 1, a, b);
}
else if (solve(3, 2, a, b))
{
cout << "3"
<< ":"
<< "2" << endl;
print(3, 2, a, b);
}
else if (solve(2, 3, a, b))
{
cout << "2"
<< ":"
<< "3" << endl;
print(2, 3, a, b);
}
else if (solve(1, 3, a, b))
{
cout << "1" << ':' << "3" << endl;
print(1, 3, a, b);
}
else if (solve(0, 3, a, b))
{
cout << "0" << ':' << "3" << endl;
print(0, 3, a, b);
}
else
printf("Impossible\n");
}
return 0;
}
题意：每个骑士和两个女士配对，求能够形成的最大组数。
做的人很少的一题，但实际上是一道模板题。思路是把每个骑士拆成两个点，这样原来的“三元匹配”就变成传统的二元匹配了。但是这会带来新的问题，原来不能匹配的骑士此时也可以匹配了。解决办法是在拆的两点间连一条边，这样原来能够三元匹配的骑士匹配数一定是 2，原来没有三元匹配的骑士匹配数一定是 1。最后的结果是最大匹配数减去加入的边数 n。插入边后不再是二分图了，变成一般图最大匹配，拉一个带花树的板子跑掉。
#include <bits/stdc++.h>
using namespace std;
const int NPOS = -1;
struct UnionfindSet : vector<int>
{
UnionfindSet(int n) : vector<int>(n)
{
for (int i = 0; i < n; ++i)
at(i) = i;
}
int ask(int u)
{
return at(u) != u ? at(u) = ask(at(u)) : u;
}
void merge(int u, int w)
{
if (w = ask(w), u = ask(u), w != u)
at(w) = u;
}
};
struct Graph
{
struct Vertex
{
vector<int> o;
};
typedef pair<int, int> Edge;
vector<Vertex> v;
vector<Edge> e;
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
v[ed.first].o.push_back(e.size());
e.push_back(ed);
}
};
struct Blossom : Graph
{
vector<int> f;
Blossom(int n) : Graph(n) {}
void ask()
{
vector<int> vis(v.size(), NPOS);
f = vis;
for (int s = 0, t = 0; s < v.size(); ++s)
if (f[s] == NPOS)
{
vector<int> pre(v.size(), NPOS), flag(pre);
deque<int> q(flag[s] = 1, s);
for (UnionfindSet ufs(v.size()); f[s] == NPOS && !q.empty(); q.pop_front())
for (int i = 0, x = q.front(), y, a, b; i < v[x].o.size(); ++i)
if (y = e[v[x].o[i]].second, y != f[x] && flag[y] && ufs.ask(x) != ufs.ask(y))
{
if (flag[y] == 1)
{
for (a = x, b = y, ++t;; swap(a, b))
if (a != NPOS)
{
if (vis[a = ufs.ask(a)] == t)
break;
vis[a] = t, a = f[a] != NPOS ? pre[f[a]] : NPOS;
}
if (ufs.ask(x) != a)
pre[x] = y;
if (ufs.ask(y) != a)
pre[y] = x;
for (int p[2] = {x, y}, j = 0; j < 2; ++j)
for (int x = p[j], y, z; x != a; ufs.merge(y, x), ufs.merge(x = z, y))
{
if (ufs.ask(z = pre[y = f[x]]) != a)
pre[z] = y;
if (!flag[y])
flag[y] = 1, q.push_back(y);
if (!flag[z])
flag[z] = 1, q.push_back(z);
}
}
else if (f[y] == NPOS)
{
for (pre[y] = x; y != NPOS;)
swap(y, f[f[y] = pre[y]]);
break;
}
else
pre[y] = x, q.push_back(f[y]), flag[f[y]] = 1, flag[y] = 0;
}
}
}
};
char s[255];
int t, n, m, c;
int main()
{
for (scanf("%d", &t); t--; printf("%d\n", c / 2 - n))
{
scanf("%d%d", &n, &m);
Blossom g(m + n * 2);
for (int i = 0; i < n; ++i)
{
scanf("%s", s);
for (int j = 0; j < m; ++j)
if (s[j] == '1')
{
g.add({j, m + i * 2});
g.add({m + i * 2, j});
g.add({j, m + i * 2 + 1});
g.add({m + i * 2 + 1, j});
}
g.add({m + i * 2, m + i * 2 + 1});
g.add({m + i * 2 + 1, m + i * 2});
}
g.ask();
for (int i = c = 0; i < g.f.size(); ++i)
if (g.f[i] != NPOS)
++c;
}
}
小范围数据打表，否则指定几个关键节点。体验极差。
#include <bits/stdc++.h>
using namespace std;
vector<string> ans{
"",
"",
"a1 h1 h8",
"a1 h1 h2 h8",
"a1 h1 h2 h3 h8",
"a1 h1 h2 h3 h4 h8",
"a1 h1 h2 h3 h4 h5 h8",
"a1 h1 h2 h3 h4 h5 h6 h8",
"a1 h1 h2 h3 h4 h5 h6 h7 h8",
"a1 b1 h1 h2 h3 h4 h5 h6 h7 h8",
"a1 b1 c1 h1 h2 h3 h4 h5 h6 h7 h8",
"a1 b1 c1 d1 h1 h2 h3 h4 h5 h6 h7 h8",
"a1 b1 c1 d1 e1 h1 h2 h3 h4 h5 h6 h7 h8",
"a1 b1 c1 d1 e1 f1 h1 h2 h3 h4 h5 h6 h7 h8",
"a1 b1 c1 d1 e1 f1 g1 h1 h2 h3 h4 h5 h6 h7 h8",
"a1 a2 b2 b1 c1 d1 e1 f1 g1 h1 h2 h3 h4 h5 h6 h8",
"a1 a2 b2 b1 c1 d1 e1 f1 g1 h1 h2 h3 h4 h5 h6 h7 h8"},
turn{
"a1",
"h1",
"h2",
"a2",
"a3",
"h3",
"h4",
"a4",
"a5",
"h5",
"h6",
"a6",
"a8",
"g8",
"g7",
"a7",
"h7",
"h8"},
jump{
"a8",
"h7"};
int n;
int main()
{
cin >> n;
if (n < ans.size())
return cout << ans[n], 0;
int need = n - 17, to = 1;
for (string now("a1");;)
{
cout << now << ' ';
if (now == turn[to])
++to;
if (to > turn.size())
return 0;
if (need == 0 || turn[to] == jump[0] || turn[to] == jump[1])
{
now = turn[to];
continue;
}
if (now[0] < turn[to][0])
++now[0];
else if (now[0] > turn[to][0])
--now[0];
else if (now[1] < turn[to][1])
++now[1];
else
--now[1];
if (now != turn[to])
--need;
}
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
vector<ll> v;
void gcd(ll a, ll b, ll &x, ll &y)
{
if (!b)
{
x = (m - 1) / a, y = 0;
return;
}
gcd(b, a % b, x, y);
ll t = x;
x = y, y = t - a / b * y;
}
int main()
{
scanf("%lld", &n);
m = n;
for (ll i = 2; i * i <= m; ++i)
if (n % i == 0)
{
v.push_back(i);
while (n % i == 0)
n /= i;
}
if (n > 1)
v.push_back(n);
if (v.size() < 2)
return printf("NO"), 0;
printf("YES\n2\n");
ll a = v[0], b = v[v.size() - 1], x, y;
gcd(a, b, x, y);
a = m / a, b = m / b;
while (x <= 0)
x += a, y -= b;
while (x >= a)
x -= a, y += b;
while (y >= b)
x += a, y -= b;
while (y <= 0)
x -= a, y += b;
printf("%lld %lld\n%lld %lld", x, a, y, b);
}
#include <bits/stdc++.h>
using namespace std;
int t, k, a[7];
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d", &k);
int sum = 0, x = 0, y = 1e9;
for (int i = 0; i < 7; ++i)
scanf("%d", &a[i]), sum += a[i];
if (k > 2 * sum)
{
k -= sum;
x = k / sum * 7;
k %= sum;
k += sum;
}
for (int i = 0, j; i < 7; ++i)
{
for (int s = j = 0; s < k; ++j)
s += a[(i + j) % 7];
y = min(y, j);
}
printf("%d\n", x + y);
}
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
struct SegmentTree
{
struct Node
{
ll val, sum;
void up(const Node &lc, const Node &rc)
{
sum = lc.sum + rc.sum;
val = max(lc.val + rc.sum, rc.val);
}
} v[N * 4];
void set(int p, ll val, int l = 1, int r = N, int rt = 1)
{
if (l >= r)
{
v[rt].sum = val, v[rt].val = val ? l + val : 0;
return;
}
int m = l + r >> 1;
if (p > m)
set(p, val, m + 1, r, rt << 1 | 1);
else
set(p, val, l, m, rt << 1);
v[rt].up(v[rt << 1], v[rt << 1 | 1]);
}
Node ask(int p, int q, int l = 1, int r = N, int rt = 1)
{
if (p <= l && r <= q)
return v[rt];
int m = l + r >> 1;
if (m >= q)
return ask(p, q, l, m, rt << 1);
if (m < p)
return ask(p, q, m + 1, r, rt << 1 | 1);
return v[0].up(ask(p, q, l, m, rt << 1), ask(p, q, m + 1, r, rt << 1 | 1)), v[0];
}
} t;
char s[9];
int n, a[N];
int main()
{
scanf("%d", &n);
for (int i = 1, y; i <= n; ++i)
{
scanf("%s%d", s, &a[i]);
if (s[0] == '+')
{
scanf("%d", &y);
t.set(a[i], y);
}
else if (s[0] == '-')
t.set(a[a[i]], 0);
else
printf("%lld\n", max(t.ask(1, a[i]).val - a[i], 0LL));
}
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
typedef long long ll;
vector<int> ans, v[N];
int n, k, cnt, a[N], b[N];
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i)
scanf("%d", &b[i]);
for (int i = 1; i <= n; ++i)
v[a[i]].push_back(b[i]);
for (int i = 1; i <= k; ++i)
{
if (v[i].empty())
{
++cnt;
continue;
}
sort(v[i].begin(), v[i].end());
for (int j = 0; j < v[i].size() - 1; ++j)
ans.push_back(v[i][j]);
}
sort(ans.begin(), ans.end());
ll tmp = 0;
for (int i = 0; i < cnt; ++i)
tmp += ans[i];
printf("%lld", tmp);
}