今天第一次模拟NOI类型的题目。其实题出得挺好。
A：hdu5350 MZL's munhaff function
lyd说那个奇奇怪怪的日文念出来是"manhafu"..还不如原题的提示，明明就是在卖萌嘛!!
方法一：
本质：哈夫曼树
解决如下问题：有一堆数，每次拿2个数，换成它们的和，代价是它们的和，求把数变为1个的最小花费
显然每次取当前最小（构建哈夫曼树）
考虑本题，f[i][j] 表示拿了 前Ai个数，当前最后那层有j个空的叶节点
我们可以拿一个数去填空点，不需要代价f[i+1][j-1]
也可以把叶子节点上有数往下画一层 f[i][2j] 代价就是上面所有取的数 Bi
这样一看代码就简单爆了啊!
方法二：四边形不等式
【code from lyd】
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int kMod = 1000000007;
const int kMaxM = 100, kMaxN = 100;
int m, n;
const int kMaxNodeCnt = 222;
int dp[2][4][kMaxM + 1][kMaxNodeCnt];
struct Node {
Node *son[2], *fail;
int msk;
} node_pool[kMaxNodeCnt], *node_idx, *root;
Node *alloc() {
Node *res = node_idx ++;
res->son[0] = res->son[1] = NULL;
res->msk = 0;
return res;
}
#define UPT(x, y) { \
(x) += (y); \
if ((x) >= kMod) (x) -= kMod; \
}
void buildAC() {
Node *q[kMaxNodeCnt];
int qh = 0, qt = 0;
for (int t = 0; t < 2; ++ t)
if (root->son[t]) {
q[qt ++] = root->son[t];
root->son[t]->fail = root;
}
else
root->son[t] = root;
while (qh != qt) {
Node *u = q[qh ++];
for (int t = 0; t < 2; ++ t)
if (u->son[t]) {
u->son[t]->fail = u->fail->son[t];
u->son[t]->msk |= u->son[t]->fail->msk;
q[qt ++] = u->son[t];
}
else
u->son[t] = u->fail->son[t];
}
}
int main() {
freopen("square.in","r",stdin);
freopen("square.out","w",stdout);
int T;
for (scanf("%d", &T); T --; ) {
scanf("%d%d", &m, &n);
char buf[260];
node_idx = node_pool;
root = alloc();
for (int i = 0; i < 2; ++ i) {
scanf("%s", buf);
int l = strlen(buf);
Node *pos = root;
for (int j = 0; j < l; ++ j) {
int t = (buf[j] == 'D');
if (!pos->son[t]) pos->son[t] = alloc();
pos = pos->son[t];
}
pos->msk |= 1 << i;
}
buildAC();
int des = 0, src = 1;
memset(dp[des], 0, sizeof(dp[des]));
dp[des][0][0][0] = 1;
int upper = node_idx - node_pool;
for (int i = 0; i < m + n; ++ i) {
des ^= 1, src ^= 1;
memset(dp[des], 0, sizeof(dp[des]));
for (int msk = 0; msk < 4; ++ msk)
for (int k = 0; k <= m; ++ k)
for (int s = 0; s < upper; ++ s)
if (dp[src][msk][k][s]) {
for (int t = (k == m); t < 2; ++ t) {
Node *pos = (node_pool + s)->son[t];
int _msk = msk | pos->msk;
int _k = k + (t == 0);
int _s = pos - node_pool;
UPT(dp[des][_msk][_k][_s], dp[src][msk][k][s]);
}
}
}
int res = 0;
for (int s = 0; s < upper; ++ s) UPT(res, dp[des][3][m][s]);
printf("%d\n", res);
}
return 0;
}
B：AC自动机+DP。
50%的数据：
考虑状态：
对R,D个数有限制=>其中两维i,j表示有了i个R，j个D
分别与两串进行匹配=>另两维k,l表示与第一个串匹配到了第k个位置，与第二个串匹配到了第l个位置
∴F[i,j,k,l]表示上述情况的方案数。
转移：
其实是KMP的思想。
提前对读入的两个串用KMP自匹配求出p数组。
枚举下一位是什么，
如果匹配成功，第三维（或第四维）+1；
如果匹配失败，那么就按照KMP算法的p数组来回到上一个匹配的位置看能否匹配……
100%的数据：
可以尝试考虑对上述状态进行优化：
F[i,j,k,l]表示有了i个R，j个D，与第k (k=1,2) 个串匹配长度较长，匹配到了第l个位置。
这样对于另一个串的匹配长度是可以算出来的。
但是转移会变得非常繁琐…… 至少%%%lyd觉得这个方法是不太可做的。。。（= =）
正解是：
对两个串建一个AC自动机，
F[i][j][k][l]表示的状态：
长度为i，有j个R（i-j个D），走到了AC自动机上的k节点，包含的字符串状态为l (l=0 1 2 3为二进制状态，表示两个串是否被包含)的方案数。
边界：F[0][0][1][0]=1;
转移：F[i][j][k][l]-->F[i+1][j+1][trie[k]['R']][l']//当前为R
F[i+1][j][trie[k]['D']][l']//当前为D
如果trie[k]['R']是第i个单词的结尾，那么l'=l | 1<<i-1;
不是结尾 l'=l
目标：F[N+M][M][?][3]。
【code from CH#17】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int SIZE = 100010;
int a[SIZE], b[SIZE], d[SIZE];
long long f[SIZE];
int T, n;
struct rec
{
int p, l, r;
rec() {}
rec(int P, int L, int R) { p = P, l = L, r = R; }
}q[SIZE];
long long calc(int i, int j)
{
if (2 * i - j + 1 < 1) return 1ll << 62;
return f[j] + b[2 * i - j + 1];
}
bool compare(int i, int j, int k)
{
long long x = calc(i, j), y = calc(i, k);
if (x != 1ll << 62 && x < y) return 1;
if (y == 1ll << 62 && x == 1ll << 62 && j < k) return 1;
return 0;
}
int main()
{
freopen("function.in", "r", stdin);
freopen("function.out", "w", stdout);
while (cin >> n)
{
//a[0] = 10000;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
//a[i] = rand() % a[i - 1] + 1;
b[n + 1] = 0;
for (int i = n; i; i--)
{
b[i] = b[i + 1] + a[i];
//cout << b[i] << ' ';
}
if (n == 1)
{
puts("0");
continue;
}
f[n] = 0;
int l = 1, r = 1;
q[1] = rec(n, 1, n - 1);
for (int i = n - 1; i; i--)
{
f[i] = calc(i, q[l].p);
//cout << f[i] << ',' << q[l].p << endl;
//cout << f[i] << ' ';
while (l <= r)
{
if (q[l].l >= i) l++;
else {
q[l].r = i - 1;
break;
}
}
int now = -1;
while (l <= r)
{
if (compare(q[r].r, i, q[r].p)) now = q[r].r, r--;
else if (compare(q[r].l, q[r].p, i)) break;
else {
int L = q[r].l, R = q[r].r;
while (L < R)
{
int mid = (L + R + 1) >> 1;
if (compare(mid, i, q[r].p)) L = mid; else R = mid - 1;
}
q[r].l = L + 1; now = L;
break;
}
}
if (now != -1) q[++r] = rec(i, 1, now);
}
cout << f[1] << endl;
/*f[n] = 0, d[n] = n;
f[n - 1] = b[n - 1], d[n - 1] = n;
for (int i = n - 2; i; i--)
{
f[i] = f[i + 1] + b[i];
d[i] = i + 1;
for (int j = i + 2; j <= 2 * i; j++)
{
long long temp = f[j] + b[2 * i - j + 1];
if (temp < f[i])
{
f[i] = temp;
d[i] = j;
}
if (j > n) break;
//if (j > d[i + 1]) break;
}
//cout << f[i] << ',' << d[i] << endl;
}
cout << f[1] << endl;*/
}
}
C:(最小)路径覆盖问题
DAG中我们讨论
最小路径点覆盖：二分图解决
最小路径边覆盖：网络流解决
if 不能重复覆盖
ans=Σmax(in[i]-out[i],0)
方案:code
else if 可重复覆盖
1、
我们可以重复走边使答案更优
重复走一条边=加入一条重边
now what we should do is：
add edges{(u,v)|in[u]>out[u],in[v]<out[v]}
即 添加一些从入度>出度的点到入度<出度的点的路径，使答案最优。
2、
重复覆盖指的是点、边均可重复经过
考虑点边转化：
——拆点：//注意:从右向左连边
addedge(u2,u1,inf);
//原图中的边(u,v)：
addedge(u1,v2,inf);
//for each i that in[i]>out[i]:
addedge(S,i1,in[i]-out[i]);
//for each i that in[i]<out[i]:
addedge(i2,T,out[i]-in[i])
3、
ans=n-maxflow;//求最小流
方案：num(e)=f(e)//一条边上有多少流量，就要添加多少条重边
dfs输出
else//不是DAG？
tarjan()缩点变为DAG
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N = 1010, M = 10010, INF = 1 << 20;
int n, m, t, ans;
int head[N], ver[M], edge[M], Next[M], tot, fa[N];
int dfn[N], low[N], s[N], p, num, ins[N], c[N], need[M];
bool d[N][N], a[N][N], v[N];
vector<int> poi;
void add(int x, int y, int z)
{
ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}
void tarjan(int x)
{
dfn[x] = low[x] = ++num;
s[++p] = x, ins[x] = 1;
for (int i = head[x]; i; i = Next[i])
{
int y = ver[i];
if (!dfn[y])
{
tarjan(y);
low[x] = min(low[x], low[y]);
}
else if (ins[y])
low[x] = min(low[x], dfn[y]);
}
if (low[x] == dfn[x])
{
t++; int y;
do { y = s[p--]; ins[y] = 0; c[y] = t; } while (x != y);
}
}
bool dfs(int x)
{
for (int i = 1; i <= n; i++)
{
if (!a[x][i] || v[i]) continue;
v[i] = 1;
if (!fa[i] || dfs(fa[i]))
{
fa[i] = x;
return 1;
}
}
return 0;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
m = t;
for (int x = 1; x <= n; x++)
for (int i = head[x]; i; i = Next[i])
{
int y = ver[i];
if (c[x] == c[y])
{
if (edge[i]) need[c[x]] = 1;
continue;
}
if (edge[i]) ++m, d[c[x]][m] = d[m][c[y]] = 1, need[m] = 1;
else d[c[x]][c[y]] = 1;
}
for (int i = 1; i <= m; i++) d[i][i] = 1;
for (int k = 1; k <= m; k++)
for (int i = 1; i <= m; i++)
for (int j = 1; j <= m; j++)
d[i][j] |= d[i][k] & d[k][j];
for (int i = 1; i <= m; i++)
if (need[i]) poi.push_back(i);
n = poi.size();
for (int i = 0; i < poi.size(); i++)
{
int x = poi[i];
for (int j = 0; j < poi.size(); j++)
{
int y = poi[j];
if (d[x][y] && x != y) a[i + 1][j + 1] = 1;
}
}
for (int i = 1; i <= n; i++)
{
memset(v, 0, sizeof(v));
if (dfs(i)) ans++;
}
cout << n - ans << endl;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N = 100010, M = 1000010, INF = 1 << 20;
int ver[M], edge[M], Next[M], head[N], tot;
vector<int> go[N], cover[N];
int dfn[N], low[N], s[N], ins[N], c[N], p, num;
int need[N], in[N], out[N], d[N];
int n, m, scc, st, ed, maxflow, ST, ED;
void tarjan(int x)
{
dfn[x] = low[x] = ++num;
s[++p] = x, ins[x] = 1;
for (int i = 0; i < go[x].size(); i++)
{
int y = go[x][i];
if (!dfn[y])
{
tarjan(y);
low[x] = min(low[x], low[y]);
}
else if (ins[y])
low[x] = min(low[x], dfn[y]);
}
if (dfn[x] == low[x])
{
scc++; int y;
do { y = s[p--]; ins[y] = 0; c[y] = scc; } while (x != y);
}
}
void add(int x, int y, int lb, int ub)
{
ver[++tot] = y, edge[tot] = ub - lb, Next[tot] = head[x], head[x] = tot;
ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
in[y] += lb, out[x] += lb;
}
void add(int x, int y, int z)
{
ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
}
bool bfs()
{
memset(d, 0, sizeof(d));
queue<int> q;
q.push(ST); d[ST] = 1;
while (q.size())
{
int x = q.front(); q.pop();
for (int i = head[x]; i;i=Next[i])
if (edge[i] && !d[ver[i]])
{
d[ver[i]] = d[x] + 1;
q.push(ver[i]);
if (ver[i] == ED) return 1;
}
}
return 0;
}
int dinic(int x, int f)
{
if (x == ED) return f;
int rest = f;
for (int i = head[x]; i && rest; i = Next[i])
if (edge[i] && d[ver[i]] == d[x] + 1)
{
int now = dinic(ver[i], min(rest, edge[i]));
if (!now) d[ver[i]] = 0;
edge[i] -= now;
edge[i ^ 1] += now;
rest -= now;
}
return f - rest;
}
int main()
{
//freopen("graph1.in","r",stdin);
//freopen("graph1.out","w",stdout);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
go[x].push_back(y);
cover[x].push_back(z);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
tot = 1;
for (int x = 1; x <= n; x++)
for (int i = 0; i < go[x].size(); i++)
{
int y = go[x][i], z = cover[x][i];
if (c[x] == c[y])
{
if (z) need[c[x]] = 1;
continue;
}
add(c[x] + scc, c[y], z, INF);
}
st = 0, ed = 2 * scc + 1;
for (int i = 1; i <= scc; i++)
{
add(st, i, 0, INF);
add(i, i + scc, need[i], INF);
add(i + scc, ed, 0, INF);
}
ST = ed + 1, ED = ed + 2;
for (int i = st; i <= ed; i++)
{
if (in[i] > out[i]) add(ST, i, in[i] - out[i]);
else if (in[i] < out[i]) add(i, ED, out[i] - in[i]);
}
int cur;
while (bfs())
while (cur = dinic(ST, INF)) maxflow += cur;
add(ed, st, INF);
while (bfs())
while (cur = dinic(ST, INF)) maxflow += cur;
cout << edge[tot] << endl;
}
心得：
1、暴力：
如果把暴力理解为模拟、枚举就太弱了，算法的掌握是必须的。
暴力与正解通常为递进的关系，要得分往往考虑方向先要正确。
2、做题看本质，挖掘更深东西。
评论 (0)
