2
2
2016
0

【郑州培训】上机测试day5

今天第一次模拟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、做题看本质,挖掘更深东西。 

 

Category: 未分类 | Tags: 网络流 强连通分量 哈夫曼树 动归优化 | Read Count: 585

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com