CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
调查问卷
借助位运算可以很快出解。
#include <bits/stdc++.h>
using namespace std;
const int N = 1023;
char s[N];
int kase, ans, t, n, m, k, a[N];
int main()
{
for (scanf("%d", &t); t--; printf("Case #%d: %d\n", ++kase, ans))
{
scanf("%d%d%d", &n, &m, &k);
for (int i = ans = 0; i < n; ++i)
{
scanf("%s", s);
for (int j = a[i] = 0; j < m; ++j)
a[i] |= (s[j] == 'A') << j;
}
for (int p = 1 << m; --p;)
{
vector<int> mp(p + 1, 0);
for (int i = 0; i < n; ++i)
++mp[p & a[i]];
for (int i = m = 0; i < mp.size(); ++i)
if (m += mp[i] * (n - mp[i]), m >= k * 2)
{
++ans;
break;
}
}
}
}
子串查询
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
char s[N];
int kase, t, n, q, a[N][26];
int main()
{
for (scanf("%d", &t); t--;)
{
printf("Case #%d:\n", ++kase);
scanf("%d%d%s", &n, &q, &s);
for (int i = 0; i < n; ++i)
copy(a[i], a[i] + 26, a[i + 1]), ++a[i + 1][s[i] - 'A'];
for (int i = 0, l, r; i < q; ++i)
{
scanf("%d%d", &l, &r);
for (int j = 0; j < 26; ++j)
if (a[r][j] != a[l - 1][j])
{
printf("%d\n", a[r][j] - a[l - 1][j]);
break;
}
}
}
}
整数规划
裸的 KM 最小权匹配。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 255, NPOS = -1;
const ll INF = 1e18;
struct Matrix
{
int n;
ll a[N][N];
};
struct KuhnMunkres : Matrix
{
ll hl[N], hr[N], slk[N];
int fl[N], fr[N], vl[N], vr[N], pre[N], q[N], ql, qr;
int check(int i)
{
if (vl[i] = 1, fl[i] != NPOS)
return vr[q[qr++] = fl[i]] = 1;
while (i != NPOS)
swap(i, fr[fl[i] = pre[i]]);
return 0;
}
void bfs(int s)
{
fill(slk, slk + n, INF), fill(vl, vl + n, 0), fill(vr, vr + n, 0);
for (vr[q[ql = 0] = s] = qr = 1;;)
{
for (ll d; ql < qr;)
for (int i = 0, j = q[ql++]; i < n; ++i)
if (d = hl[i] + hr[j] - a[i][j], !vl[i] && slk[i] >= d)
if (pre[i] = j, d)
slk[i] = d;
else if (!check(i))
return;
ll d = INF;
for (int i = 0; i < n; ++i)
if (!vl[i] && d > slk[i])
d = slk[i];
for (int i = 0; i < n; ++i)
{
if (vl[i])
hl[i] += d;
else
slk[i] -= d;
if (vr[i])
hr[i] -= d;
}
for (int i = 0; i < n; ++i)
if (!vl[i] && !slk[i] && !check(i))
return;
}
}
void ask()
{
fill(fl, fl + n, NPOS), fill(fr, fr + n, NPOS), fill(hr, hr + n, 0);
for (int i = 0; i < n; ++i)
hl[i] = *max_element(a[i], a[i] + n);
for (int j = 0; j < n; ++j)
bfs(j);
}
} km;
int main()
{
int t, kase = 0;
for (scanf("%d", &t); t--;)
{
scanf("%d", &km.n);
for (int i = 0; i < km.n; ++i)
for (int j = 0; j < km.n; ++j)
scanf("%lld", &km.a[i][j]), km.a[i][j] *= -1;
km.ask();
ll ans = 0;
for (int i = 0; i < km.n; ++i)
ans -= km.a[i][km.fl[i]];
printf("Case #%d: %lld\n", ++kase, ans);
}
}
点集划分
//假装这里有代码
序列计数
用树状数组维护 lis。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 7, M = 1e9 + 7;
typedef int ll;
struct BaseFenwick
{
vector<ll> v;
BaseFenwick(int N) : v(N + 1, 0) {}
void add(int x, ll w)
{
for (; x < v.size(); x += x & -x)
v[x] = (v[x] + w) % M;
}
ll ask(int x)
{
ll r = 0;
for (; x; x -= x & -x)
r = (r + v[x]) % M;
return r;
}
};
int t, kase, n, c[N], a[N], siz;
int main()
{
for (scanf("%d", &t); t--; printf("\n"))
{
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]), c[i] = 1;
printf("Case #%d:", ++kase);
for (long long r = siz = n; r; --siz)
{
printf(" %lld", r % M);
BaseFenwick t(n);
for (int i = r = 0; i < n; ++i)
t.add(a[i], c[i]), c[i] = t.ask(a[i] - 1), r = (r + c[i]) % M;
}
while (siz--)
printf(" 0");
}
}
三原色图
按两种方法分别求 MST 然后从小往里加边，对于每个 m 在两个结果取较优的那个。
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct UnionFindSet : vector<int>
{
int siz;
UnionFindSet(int n) : siz(n)
{
for (int i = 0; i < n; ++i)
push_back(i);
}
int fa(int u) { return at(u) != u ? at(u) = fa(at(u)) : u; }
void merge(int u, int w)
{
if (w = fa(w), u = fa(u), w != u)
at(w) = u, --siz;
}
};
struct Edge
{
int id, from, to, dist;
bool operator<(const Edge &e) const { return dist < e.dist; }
};
void kruskal(int n, int m, const vector<Edge> &ed, vector<Edge> &e, vector<int> &s)
{
int ret = 0;
UnionFindSet ufs(n);
for (sort(e.rbegin(), e.rend()); !e.empty(); e.pop_back())
if (ufs.fa(e.back().from) != ufs.fa(e.back().to))
{
ufs.merge(e.back().from, e.back().to);
ret += e.back().dist;
s[e.back().id] = 1;
}
for (int i = 0; i < ed.size(); ++i)
if (!s[ed[i].id])
e.push_back(ed[i]);
s.assign(m, INF);
if (ufs.siz > 1)
return;
sort(e.rbegin(), e.rend());
for (int i = n - 2; i < s.size(); ++i)
{
if (i >= 0)
s[i] = ret;
if (e.empty())
ret = INF;
else
ret += e.back().dist, e.pop_back();
}
}
char s[9];
int kase, t, n, m;
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d%d", &n, &m);
vector<Edge> rg, gb, e;
vector<int> r(m, 0), b(m, 0);
for (Edge ed = {0}; ed.id < m; ++ed.id)
{
scanf("%d%d%d%s", &ed.from, &ed.to, &ed.dist, s);
--ed.from, --ed.to, e.push_back(ed);
if (s[0] != 'B')
rg.push_back(ed);
if (s[0] != 'R')
gb.push_back(ed);
}
kruskal(n, m, e, rg, r), kruskal(n, m, e, gb, b);
printf("Case #%d:\n", ++kase);
for (int i = 0; i < m; ++i)
printf("%d\n", min(r[i], b[i]) < INF ? min(r[i], b[i]) : -1);
}
}