题目背景
历史 / 落在 / 赢家 / 之手
至少 / 我们 / 拥有 / 传说
谁说 / 败者 / 无法 / 不朽
拳头 / 只能 / 让人 / 低头
念头 / 却能 / 让人 / 抬头
抬头 / 去看 / 去爱 / 去追
你心中的梦
题目描述
又想起了四月.
如果不是省选, 大家大概不会这么轻易地分道扬镳吧? 只见一个又一个昔日的队友离开了机房.
凭君莫话封侯事, 一将功成万骨枯.
梦里, 小 $F$ 成了一个给将军送密信的信使.
现在, 有两封关乎国家生死的密信需要送到前线大将军帐下, 路途凶险, 时间紧迫. 小 F 不因为自己的祸福而避趋之, 勇敢地承担了这个任务.
不过, 小 $F$ 实在是太粗心了, 他一不小心把两封密信中的一封给弄掉了.
小 $F$ 偷偷打开了剩下的那封密信. 他发现一副十分详细的地图, 以及几句批文 -- 原来这是战场周围的情报地图. 他仔细看后发现, 在这张地图上标记了 $n$ 个从 $1$ 到 $n$ 标号的 驿站,$n\sim 1$ 条长度为 $1$ 里的小道, 每条小道双向连接两个不同的驿站, 并且驿站之间可以通过小道两两可达.
小 $F$ 仔细辨认着上面的批注, 突然明白了丢失的信的内容了. 原来, 每个驿站都可以驻扎一个小队, 每个小队可以控制距离不超过 $k$ 里的驿站. 如果有驿站没被控制, 就容易产生危险 -- 因此这种情况应该完全避免. 而那封丢失的密信里, 就装着朝廷数学重臣留下的精妙的排布方案, 也就是用了最少的小队来控制所有驿站.
小 $F$ 知道, 如果能计算出最优方案的话, 也许他就能够将功赎过, 免于死罪. 他找到了你, 你能帮帮他吗? 当然, 小 $F$ 在等待你的支援的过程中, 也许已经从图上观察出了一些可能会比较有用的性质, 他会通过一种特殊的方式告诉你.
输入格式
从标准输入中读入数据.
输入第 $1$ 行一个正整数 $n,k,t$, 代表驿站数, 一支小队能够控制的最远距离, 以及特殊性质所代表的编号. 关于特殊性质请参照数据范围.
输入第 $2$ 行至第 $n$ 行, 每行两个正整数 $u_i?,v_i?$, 表示在 $u_i$ 和 $v_i$ 间, 有一条长度为一里的小道.
输出格式
输出到标准输出中.
输出一行, 为最优方案下需要的小队数.
样例
样例输入 1:
- 4 1 0
- 1 2
- 1 3
- 1 4
样例输出 1:
1
样例输入 2:
- 6 1 0
- 1 2
- 1 3
- 1 4
- 4 5
- 4 6
样例输出 2:
2
数据范围与提示
样例 $1$ 说明:
如图. 由于一号节点到周围的点距离均是 $1$, 因此可以控制所有驿站.
样例 $2$ 说明:
如图, 和样例 $1$ 类似.
数据范围:
子任务会给出部分测试数据的特点. 如果你在解决题目中遇到了困难, 可以尝试只解决一部分测试数据.
关于的含义如下:
$t=0$: 该测试点没有额外的特殊性质;
$t=1$: 保证最多 $8$ 个点的所连接的小道超过 $1$ 条;
$t=2$: 保证所有点到 $1$ 号点的距离不超过 $2$.
每个测试点的数据规模及特点如下表:
题解
$5\%$ 算法:
$k=0$, 直接输出 $n$ 就好了.
时间复杂度:$\Theta(1)$.
期望得分:$5$ 分.
实际得分:$5$ 分.
$45\%$ 算法:
$k=1$, 每个点只会被儿子 $(0)$, 自己 $(1)$ 或父亲 $(2)$ 控制, 直接 $DP$ 就好啦.
来看状态转移方程:
- $dp[u][0]=\sum \min(dp[v][0],dp[v][1])-\min(0,\max(dp[v][1]-dp[v][0]))$
- $dp[u][1]=\sum \min(dp[v])$
- $dp[u][2]=\sum \min(dp[v][0],dp[v][1])$
时间复杂度:$\Theta(n)$.
期望得分:$45$ 分.
实际得分:$45$ 分.
$75\%$ 算法:
$k=2$
每个点被自己 $(0)$, 儿子 $(1)$, 孙子 $(2)$ 控制; 或者孙子和儿子全部被控制但是自己没有被控制 $(3)$, 孙子全部被控制但是自己和儿子不被控制 $(4)$.
时间复杂度:$\Theta(n)$.
期望得分:$75$ 分.
实际得分:$75$ 分.
$90\%$ 算法:
依然是状态转移.
时间复杂度:$\Theta(n)$.
期望得分:$90$ 分.
实际得分:$90$ 分.
$100\%$ 算法:
考虑贪心.
让点按深度从大到小排序 ($BFS$ 序倒序即可).
然后检查该节点是否被控制, 如果没有被控制, 就去驻扎他的 $k$ 级父亲, 肯定不劣.
因为 $k$ 比较小, 暴力更新即可.
时间复杂度:$\Theta(k\times n)$.
期望得分:$100$ 分.
实际得分:$100$ 分.
代码时刻
$5\%$ 算法:
- #include<bits/stdc++.h>
- int n,k,t;
- int main()
- {
- scanf("%d%d%d",&n,&k,&t);
- printf("%d",n);
- return 0;
- }
$45\%$ 算法:
- #include<bits/stdc++.h>
- using namespace std;
- struct rec
- {
- int nxt;
- int to;
- }e[200000];
- int head[100001],cnt;
- int n,k,t;
- int dp[100001][3],du[100001];
- bool vis[100001];
- void add(int x,int y)
- {
- e[++cnt].nxt=head[x];
- e[cnt].to=y;
- head[x]=cnt;
- }
- void dfs(int x)
- {
- vis[x]=1;
- if(du[x]==1&&x!=1)
- {
- dp[x][1]=1;
- dp[x][2]=0;
- return;
- }
- dp[x][0]=dp[x][1]=dp[x][2]=0;
- int minn=1<<30;
- bool flag=0;
- for(int i=head[x];i;i=e[i].nxt)
- {
- if(!vis[e[i].to])
- {
- dfs(e[i].to);
- dp[x][1]+=min(dp[e[i].to][0],min(dp[e[i].to][1],dp[e[i].to][2]));
- dp[x][2]+=min(dp[e[i].to][0],dp[e[i].to][1]);
- if(dp[e[i].to][1]<=dp[e[i].to][0])flag=1;
- else minn=min(minn,dp[e[i].to][1]-dp[e[i].to][0]);
- }
- }
- dp[x][1]++;
- if(flag)dp[x][0]=dp[x][2];
- else dp[x][0]=dp[x][2]+minn;
- }
- int main()
- {
- scanf("%d%d%d",&n,&k,&t);
- if(!k){printf("%d",n);return 0;}
- for(int i=1;i<n;i++)
- {
- int x,y;
- scanf("%d%d",&x,&y);
- du[x]++;
- du[y]++;
- add(x,y);
- add(y,x);
- }
- memset(dp,0x3f,sizeof(dp));
- dfs(1);
- printf("%d",min(dp[1][0],dp[1][1]));
- return 0;
- }
$100\%$ 算法:
- #include<bits/stdc++.h>
- using namespace std;
- struct rec
- {
- int nxt;
- int to;
- }e[200000];
- int head[100001],cnt;
- int n,k,t;
- int que[100001],wzc[100001],fa[100001];
- int ans;
- void add(int x,int y)
- {
- e[++cnt].nxt=head[x];
- e[cnt].to=y;
- head[x]=cnt;
- }
- void pre_bfs()
- {
- int he=1,ta=1;
- que[1]=1;
- fa[1]=1;
- while(he<=ta)
- {
- for(int i=head[que[he]];i;i=e[i].nxt)
- if(!fa[e[i].to])
- {
- que[++ta]=e[i].to;
- fa[e[i].to]=que[he];
- }
- he++;
- }
- }
- void change(int x)
- {
- if(!wzc[x])return;
- for(int i=head[x];i;i=e[i].nxt)
- if(wzc[e[i].to]<wzc[x]-1)
- {
- wzc[e[i].to]=wzc[x]-1;
- change(e[i].to);
- }
- }
- int main()
- {
- memset(wzc,-1,sizeof(wzc));
- scanf("%d%d%d",&n,&k,&t);
- for(int i=1;i<n;i++)
- {
- int x,y;
- scanf("%d%d",&x,&y);
- add(x,y);
- add(y,x);
- }
- pre_bfs();
- for(int i=n;i;i--)
- if(wzc[que[i]]==-1)
- {
- ans++;
- int flag=que[i];
- for(int j=k;j;j--)flag=fa[flag];
- wzc[flag]=k;
- change(flag);
- }
- cout<<ans;
- return 0;
- }
- rp++
[洛谷 P3942]: 将军令 (贪心)
来源: http://www.bubuko.com/infodetail-3152722.html