Post 10

Veröffentlicht am | Edited on

那些上演着繁华不肯谢幕的年华里开出一朵地老天荒的花。—From zyf 学姐

[CQOI2017]小Q的棋盘

题目描述

小 Q 正在设计一种棋类游戏。

在小 Q 设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能在有连线的格点之间移动。整个棋盘上共有 V 个格点，编号为0,1,2 … , V− 1，它们是连通的，也就是说棋子从任意格点出发，总能到达所有的格点。小 Q 在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。

小 Q 现在想知道，当棋子从格点 0 出发，移动 N 步最多能经过多少格点。格点可以重复经过多次，但不重复计数。

输入输出格式

输入格式：

第一行包含2个正整数V, N，其中 V 表示格点总数，N 表示移动步数。

接下来V − 1行，每行两个数a_i,b_iai,bi，表示编号为a_i,b_iai,bi的两个格点之间有连线。

输出格式：

输出一行一个整数，表示最多经过的格点数量。

输入输出样例

输入样例#1：

1
2
3
4
5
5 2
1 0
2 1
3 2
4 3

输出样例#1：

1
3

输入样例#2：

1
2
3
4
5
6
7
8
9
9 5
0 1
0 2
2 6
4 2
8 1
1 3
3 7
3 5

输出样例#2：

1
5

说明

【输入输出样例 1 说明】

从格点 0 出发移动 2 步。经过 0, 1, 2 这 3 个格点。

【输入输出样例 2 说明】

一种可行的移动路径为 0 → 1 → 3 → 5 → 3 → 7，经过 0, 1, 3, 5, 7 这 5 个格点。

【数据规模与约定】

对于 100%的测试点，N,V ≤ 100, 0 ≤a_i,b_i< V

题解

我想到了一个很不好写的dp做法。。。

设

表示节点u走k步不回来/回来访问的最大节点数。

对于回来的转移比较简单，因为回到这个点意味着访问完它的子树都要回去，一个纯粹的树上背包。

这部分时间复杂度是

但是对于不回来的转移就比较麻烦了，我们需要枚举当前点状态的基础上枚举每个回来的点和其状态，然后对于剩下的步数再做完全背包，时间复杂度在

以上。这样应该能勉强通过。

不过十分难写。。。

可以参考一下别人的代码

他加了一个优化：除掉一颗子树虽然没有办法直接减，但是可以处理f的前后缀最大值数组，然后把儿子看做线性排列每次转移0系列状态就直接用前后缀合并就可以了。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 205;
struct edge {
    int v, next;
} e[maxn << 1];
int head[maxn], cnt;
void adde(const int &u, const int &v) {
    e[++cnt] = (edge) {v, head[u]};
    head[u] = cnt;
}
int n, k, u, v, f[maxn][maxn];
int Lf[maxn][maxn], Rf[maxn][maxn], g[maxn][maxn];
int L[maxn], R[maxn], lst[maxn], tmp[maxn][maxn];
void merge(int a[maxn], int b[maxn]) {
    for(register int j = k; j >= 2; --j) {
        for(register int l = j - 2; l >= 0; --l)
            a[j] = max(a[j], a[j - l - 2] + b[l]);
    }
}
void DPpref(int u) {
    int now = lst[u];
    if(now == -1) return;
    while(~L[now]) merge(Rf[L[now]], Rf[now]), now = L[now];
    while(~R[now]) merge(Lf[R[now]], Lf[now]), now = R[now];
}
void DPF(int u, int p) {
    int last = -1;
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == p) continue;
        if(~last) 
            lst[u] = v, L[v] = last, R[last] = v;
        last = v, DPF(v, u);
        merge(f[u], f[v]);
        memcpy(Rf[v], f[v], sizeof(f[v]));
        memcpy(Lf[v], f[v], sizeof(f[v]));
    }
    DPpref(u);
    for(register int j = k; j >= 0; --j)
        if(f[u][j]) ++f[u][j];
    f[u][0] = 1;
}

void DPG(int u, int p) {
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == p) continue;
        DPG(v, u);
        if(~L[v]) merge(tmp[v], Lf[L[v]]);
        if(~R[v]) merge(tmp[v], Rf[R[v]]);
        for(register int j = k; j >= 1; --j) {
            for(register int l = j - 1; l >= 0; --l)
                tmp[v][j] = max(tmp[v][j], tmp[v][j - l - 1] + g[v][l]);
            g[u][j] = max(g[u][j], tmp[v][j]);
        }
    }
    for(register int j = k; j >= 0; --j)
        if(g[u][j]) ++g[u][j];
    g[u][0] = 1;
}

int main() {
    memset(L, -1, sizeof(L));
    memset(R, -1, sizeof(R));
    memset(lst, -1, sizeof(lst));
    scanf("%d%d", &n, &k);
    for(register int i = 1; i < n; ++i)
        scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
    DPF(0, -1); 
    DPG(0, -1);
    printf("%d", g[0][k]);
    return 0;
}

我的暴力dp不知怎么错了。。。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 105
int head[maxn] , cnt , f[maxn][maxn][2] , n ,  m , sz[maxn];
struct edge{
	int next , to;
}e[maxn<<1];
inline void add(int x, int y)
{
	e[++cnt].next = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
void dfs(int u , int fa)
{
	f[u][0][1] = f[u][0][0] = 1;
	sz[u] = 1;
	for(int i = head[u] ; i ; i = e[i].next)
	{
		int v = e[i].to;
		if(v == fa) continue;
		dfs(v ,u);
		sz[u] += sz[v];
		for(int j = sz[u] ; j >= 1; --j)
			for(int k = std::min(sz[v] , j - 2) ; k >= 0 ; --k)
				if(j-k-2 >= 0)
					f[u][j][1] = std::max(f[u][j][1] , f[v][k][1] + f[u][j-k-2][1]);
	}
		for(int i = head[u] ; i ; i = e[i].next)
	{
		int v = e[i].to;
		if(v == fa) continue;
		for(int j = std::min(sz[u] , m) ; j >= 1 ; --j)
		{
			int tmp = 0;
			for(int k = 0 ; k <= j && k <= sz[v] && k <= m - 1 && j - k - 1 >= 0; ++k)
			{
				int rem = j - k - 1;
				for(int p = head[u] ; p ; p = e[p].next)
				{
					if(p == fa || p == v) continue;
					for(int step = 1 ; step <= sz[p] ; ++step)
						if(rem-step-2>=0)
							tmp = std::max(tmp , f[v][k][0] + f[u][rem-step-2][1] + f[p][step][1]);
				}
			}
			f[u][j][0] = tmp;
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int x ,y;
	for(int i = 1 ; i <= n - 1 ; ++i)
	{
		scanf("%d%d",&x,&y);
		add(x+1,y+1) , add(y+1,x+1);
	}
	dfs(1,0);
	printf("%d",std::max(f[1][m][1], f[1][m][0])+1);
}

UVA1185 Big Number

题意翻译

题目背景没有营养，大意为求一个大数（很大很大）的阶乘的位数（即这个数的阶乘是几位数）

题解

刚学的log函数性质emm

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
#define maxn 10000007
int T , n;
double lg[maxn];
int main()
{
    for(int i = 1 ; i <= 1e7 ; ++i)
        lg[i] = (double)log10(i);
    for(int i = 1 ; i <= 1e7 ; ++i)
        lg[i] += lg[i-1];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%d\n",(int)lg[n]+1);
    }
}

9:00了，今天除了道水题就做了一道题。。。死磕不是个好办法啊qwq，