学海泛舟

发表于 | 分类于 |

原题

传送门

题目大意

给一块n*m的巧克力，要切k刀（只能沿个分割线切，即横着切或竖着切），问切完后，最小的那块的最大面积是多少

分析

为使最小的面积最大，无论在行还是列，我们都应该尽量等分。
那么，最小面积的表达式就不难列出了，area=(n/x)(m/y)（这里的除法都是地板除），其中x表示被分成了x行，y表示被分成了y列，剩下的问题是如何求出面积的最大值。
基于x+y=k+2这个等式，我们不难发现，倘若n/x（m/y）固定时，只要使x（y）尽可能大，那么area就会取到当前的最大值。
那么我们就先枚举n/x的值，x的取值范围是[1,n]，n/x的值的个数一定是小于2sqrt(n)，所以枚举这个想法在时间复杂度是可行的。然后我们再枚举m/y的值，不断更新area的值，最后就能得到最小的最大面积了。

参考代码

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
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
int main(){
	LL n,m,k;
	LL ans=0;
	scanf("%I64d %I64d %I64d",&n,&m,&k);
	if(n+m<k+2) {
		puts("-1");
		return 0;
	}
	int i;
	for(i=1;i<=n/i&&i<k+2;i++){
		ans=max(ans,(n/i)*(m/(k+2-i)));
	}
	for(i=n/i;i>=1&&n/i<k+2;i--){
		ans=max(ans,i*(m/(k+2-n/i)));
	}
	for(i=1;i<=m/i&&i<k+2;i++){
		ans=max(ans,(m/i)*(n/(k+2-i)));
	}
	for(i=m/i;i>=1&&m/i<k+2;i--){
		ans=max(ans,i*(n/(k+2-m/i)));
	}
	printf("%I64d\n",ans);
	return 0;
}
学海泛舟

发表于 | 分类于 |

原题

传送门

题目大意

n个人组成的树型结构，要求选最多的人参加晚会，但不能同时选一个人和他的直属上司，求最多的人数和在人数最多的前提下，方案是否唯一

分析

这道就是一个树的最大独立集问题，但要求判断方案是否唯一。
如果我们用d(u,0)和d(u,1)分别表示以u为根的子树中，不选u所能得到的最大人数和选u所能得到的最大人数，那么同样我们可以在设一个f(u,0)和f(u,1)表示在方案的唯一性(f(…)=1表示唯一，f(…)=0表示不唯一)。
然后我们考虑转移方程。
对于d(u,1)，由于u已经选择了，那么u的所有子节点都不能选，所以d(u,1)=sum(d(v,0))+1,而且容易知道，只有每个f(v,0)=1,f(u,1)才是1.
对于d(u,0)，由于u没有选，对于u的所有子节点都可以选或者不选，所以d(u,0)=sum(max(d(v,0),d(v,1)))，这里的唯一性要考虑两个方面，其一，如果d(v,0)=d(v,1)，那么结果是不唯一的，其二，如果max取得的那个结果所对应的f=0，那么结果显然也是不唯一的

参考代码

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
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
const int maxn=200+5;
map<string,int> mp;
vector<int> vc[maxn];
int d[maxn][2];
int f[maxn][2];
void dp(int root){
    d[root][1]=1;
	for(int i=0;i<vc[root].size();++i){
		int v=vc[root][i];
		if(f[v][0]==-1) dp(v);
		d[root][1]+=d[v][0];
		if(f[v][0]==0) f[root][1]=0;
	}
	if(f[root][1]==-1) f[root][1]=1;
	for(int i=0;i<vc[root].size();++i){
		int v=vc[root][i];
		d[root][0]+=max(d[v][1],d[v][0]);
		if(d[v][1]==d[v][0]) f[root][0]=0;
		if(d[v][1]>d[v][0]&&f[v][1]==0) f[root][0]=0;
		if(d[v][1]<d[v][0]&&f[v][0]==0) f[root][0]=0;
	}
	if(f[root][0]==-1) f[root][0]=1;
}
int main(){
	int n;
	while(scanf("%d",&n)!=EOF&&n){
		mp.clear();
		for(int i=0;i<maxn;++i){
			vc[i].clear();
		}
		memset(d,0,sizeof d);
		memset(f,-1,sizeof f);
		string a,b;
		cin>>a;
		int cnt=1;
		if(mp[a]==0) mp[a]=cnt++;
		for(int i=1;i<n;++i){
			cin>>a>>b;
			if(mp[a]==0) mp[a]=cnt++;
			if(mp[b]==0) mp[b]=cnt++;
			vc[mp[b]].push_back(mp[a]);
		}
		dp(1);
		if(d[1][0]==d[1][1]){
			printf("%d No\n",d[1][0]);
		} else if (d[1][0]>d[1][1]) {
			printf("%d ",d[1][0]);
			if(f[1][0]==1) printf("Yes\n");
			else printf("No\n");
		} else {
			printf("%d ",d[1][1]);
			if(f[1][1]==1) printf("Yes\n");
			else printf("No\n");
		}
	}
	return 0;
}
学海泛舟

发表于 | 分类于 |

原题

传送门

题目大意

给定一颗n个结点的树，求出每个结点到离它最远的点的距离

分析

虽然每条边都有权值，但其本质并没有变化。
这个问题与求树的直径基本相似。
很容易想清楚，树上任意一个结点的最远点必然是树的直径的两个端点中的一个。
那么，这个问题就只需要三次dfs就能解决了。
第一个dfs，找到其中一个端点。
第二个dfs，以找到的一个端点为起点，找到另一个，并且顺便更新所有点到起点的距离。
第三个dfs，以另一个端点为起点，更新所有点的最远距离。

参考代码

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<vector>
using namespace std;
const int maxn=10010;
struct Edge
{
    int to,next,w;
}edge[maxn<<1];
int head[maxn];
int dist[maxn];
int tot;
void addedge(int u,int v,int w)
{
    edge[tot].to=v;
    edge[tot].w=w;
    edge[tot].next=head[u];
    head[u]=tot++;
}
int flag;
int tdis;
void dfs(int root,int pre,int dis)
{
    dist[root]=max(dist[root],dis);
    if(dis>tdis)
    {
        flag=root;
        tdis=dis;
    }
    for(int i=head[root];~i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==pre) continue;
        dfs(v,root,dis+edge[i].w);
    }
}
void solve()
{
    tdis=0;
    dfs(flag,-1,0);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        tot=0;
        memset(head,-1,sizeof head);
        memset(dist,0,sizeof dist);
        int v,len;
        for(int i=2;i<=n;++i)
        {
            scanf("%d %d",&v,&len);
            addedge(i,v,len);
            addedge(v,i,len);
        }
        flag=1;
        for(int i=0;i<3;++i)
        {
            solve();
        }
        for(int i=1;i<=n;++i)
        {
            printf("%d\n",dist[i]);
        }
    }
	return 0;
}
学海泛舟

发表于 |

试水

列表

  • 无序
  • 无序
  • 无序
  1. 有序
  2. 有序
  3. 有序

引用

苟利国家生死以

插入链接

Myblog

粗体和斜体

粗粗粗

脉动

代码框

cout<<"HEllo World"<<endl;

学海泛舟

发表于 |

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment