惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

宝玉的分享
宝玉的分享
T
Threat Research - Cisco Blogs
H
Hacker News: Front Page
N
News and Events Feed by Topic
Know Your Adversary
Know Your Adversary
Cisco Talos Blog
Cisco Talos Blog
SecWiki News
SecWiki News
C
Cisco Blogs
D
Darknet – Hacking Tools, Hacker News & Cyber Security
T
Tor Project blog
K
Kaspersky official blog
Forbes - Security
Forbes - Security
Webroot Blog
Webroot Blog
Schneier on Security
Schneier on Security
P
Privacy & Cybersecurity Law Blog
H
Heimdal Security Blog
Y
Y Combinator Blog
The GitHub Blog
The GitHub Blog
S
SegmentFault 最新的问题
V
Vulnerabilities – Threatpost
T
Tenable Blog
T
Tailwind CSS Blog
P
Privacy International News Feed
WordPress大学
WordPress大学
大猫的无限游戏
大猫的无限游戏
小众软件
小众软件
博客园 - Franky
Hacker News: Ask HN
Hacker News: Ask HN
Jina AI
Jina AI
C
Cybersecurity and Infrastructure Security Agency CISA
CTFtime.org: upcoming CTF events
CTFtime.org: upcoming CTF events
雷峰网
雷峰网
Vercel News
Vercel News
A
About on SuperTechFans
爱范儿
爱范儿
Simon Willison's Weblog
Simon Willison's Weblog
AWS News Blog
AWS News Blog
The Last Watchdog
The Last Watchdog
Engineering at Meta
Engineering at Meta
Spread Privacy
Spread Privacy
Security Archives - TechRepublic
Security Archives - TechRepublic
博客园 - 司徒正美
量子位
博客园 - 三生石上(FineUI控件)
J
Java Code Geeks
Hacker News - Newest:
Hacker News - Newest: "LLM"
Recorded Future
Recorded Future
H
Hackread – Cybersecurity News, Data Breaches, AI and More
Martin Fowler
Martin Fowler
Project Zero
Project Zero

hsfzxjy 的博客

解决 VSCode + CMake + MSVC 编译器信息乱码的问题 使用 3090 部署 1.58bit 动态量化版 DeepSeek R1 671b 如何在 VS Code DevContainer 中配置 HTTP 代理 如何在跳板机背后的服务器上使用 VS Code Remote - Containers Cohesive Digests for Ints and Floats Rust 中的隐匿概念 —— Place(位置) 美术馆 一尺之槌,日取其半,1075日而竭 老生常谈:使用 Cloudflare 自选 IP 加速站点访问 辩义 State、Nation 与 Country 将 Base64 编码的数据快速转换为 Uint8Array 折腾 NPU·第1章 —— 搭建 Level Zero 开发环境 折腾 NPU·第0章 —— Intel NPU 概述与 Level-Zero 新增域名 monad.run CSS 中为特定字符设置不同字体 Arbitary Lifetime Transmutation via Rust Unsoundness Dijkstra 算法的延伸 Manacher 回文计数算法 硬卧 Go Fact: Zero-sized Field at the Rear of a Struct Has Non-zero Size Display *big.Rat Losslessly and Smartly in Golang 代码的仪式 Building Electron From Scratch 中式亲属称谓研究之一:构建半群 Some Notes on Kotlin Coroutines Git sparse-checkout and partial clones for Mega-Repos 辩义“封建” Diving from the CUDA Error 804 into a bug of libnvidia-container Modern Cryptography, GPG and Integration with Git(hub) Move the Root Partition of Ubuntu A New Programmer Kicks a Roadblock Git-based Dependencies in Dart and Go Reversy Naming 人类一败涂地 Invalid Golang Pointers Can Bite You Even If You Don't Dereference Side Project(副业) A Flaw of Promoting Complex Trait Bounds in Rust Initialize Process Pool Worker with Individual Value Rust - Python FFI From Scratch [Extending Hexo For My Site] Part 1 [Extending Hexo For My Site] Part 0 Debug a 'torch.tensor(1).cuda()' hanging 不自由的互联网 Retrieve Contents over HTTP without curl or wget [Unravelling mocona] Part 1 - Verbosity or Anti-Pattern [Unravelling mocona] Part 0 - Preface Understanding pickle in Python Rough Notes on Deploying Vaultwarden & NextCloud Bookmarks 语言狂热者与实用主义者 Demystify the randomness in CUDA kernels Performant Bulk Mutations in IndexedDB Auto Rebuild .pyx Files with pyximport Cython and Threads Obtain a Random Available TCP Port with Bash Information Theory: KL Divergence Information Theory: Entropy and Mutual Information 铁板烧 西郊线 Proof of the Gumbel Max Trick Option::as_ref Rc, RefCell and Interior Mutability Visualizing Correlation 三月十日杂感 三月一日杂感 二月十一日杂感 一月二十六日杂感 SS Configuration 一月七日杂感 四月·病 Haskell 笔记:State Monad Haskell 笔记:Monad 引论 Haskell 笔记:Applicative Haskell 笔记:Category Theory and Functor Haskell 笔记:data, type, newtype Haskell 笔记:folds 使用 Aria2 在 Ubuntu 中下载百度云资源 从伪并行的 Python 多线程说起 一个 Reentrant Error 引发的对 Python 信号机制的探索和思考 Linux 文件权限 HSFZMUN 4.0 部署小记 午后雨·科大 最后的雨夜·广州 揭秘·变态的平方根倒数算法 神坑·Python 装饰类无限递归 Python“黑魔法”之 Encoding & Decoding Ubuntu 重新映射键盘布局 为什么我要翻墙 Python“黑魔法”之 Generator Coroutines 数学美 之 判断线段相交的最简方法 除夕杂感 17 行代码实现的简易 Javascript 字符串模板 Python“黑魔法”之 Meta Classes 诗集 生活,需要被“发现” 家书·十八岁成人礼 炫技?还是需求? 【译】响应式图片的现状 【译】“为什么有这么多的编程语言?” Wisecity 商赛总结——也谈前端自动化测试 记一次 DoS 诈骗网站的经历
UVa12186 Another Crisis && [Dynamic Arrays in Pascal]
2014-09-27 · via hsfzxjy 的博客

链接:Link 耗时:0.586s

昨晚做的太急了,没时间写总结,正好下午有空,补上。

这是一道典型的树形动态规划,不是很难,但十分坑语言。思路大致如下:

对于第 $i$ 个节点,用 $d(i)$ 表示其上诉所需的最小工人数。若 $i$ 为叶节点,则 $d(i)=1$;否则,遍历求出 $i$ 的子节点所对应的 $d$ 值,并由小到大排序,取出最小的几个相加,即为 $d(i)$。

很容易想到用递归来实现。但对于“子节点的 d 值的排序”实现起来却十分困难:因为事先不知道有多少个数。当然啦,如果是 C++ 组,用 vector 可以轻松搞定,可至于 P 党,实现起来却难上加难。思来想去,决定试试 Pascal 的动态数组。磕磕碰碰调了近 1 个小时,终于 AC 了。


var
tree: array [0..100000] of array of int64;
T: Integer;
f: array [0..100000] of int64;
i,l,n,x:longint;

function min(x,y: int64): int64;
begin
if x<y then exit(x) else exit(y);
end;

procedure sort(var arr: array of int64;l,r:longint); overload;
var
i,j:longint;
m,t: int64;
begin
i := l;
j := r;
m := arr[(l+r) >> 1];
repeat
while arr[i]<m do inc(i);
while arr[j]>m do dec(j);
if i<=j then
begin
t := arr[i];
arr[i] := arr[j];
arr[j] := t;
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(arr, i, r);
if l<j then sort(arr, l, j);
end;

procedure sort(var arr: array of int64); overload;
begin
sort(arr, low(arr), high(arr));
end;
function dp(x: longint): int64;
var
arr: array of int64;
l,i, num: longint;
begin
if f[x] <> 0 then
begin
dp := f[x];
exit;
end;
if length(tree[x]) = 0 then
begin
dp := 1;
f[x] := 1;
exit;
end;
l := length(tree[x]);
SetLength(arr, l);
for i := Low(tree[x]) to High(Tree[x]) do
arr[i] := dp(tree[x][i]);
Sort(arr);
num := (l*T-1) div 100+1;
for i := Low(arr) to num-1 do
f[x] := f[x] + arr[i];
dp := f[x];
end;

begin
assign(input, 'main.in');reset(input);
assign(output,'main.out');rewrite(output);
readln(n, T);
while n>0 do
begin
fillchar(f, sizeof(f), 0);
fillchar(tree, sizeof(tree), 0);
for i := 1 to n do
begin
read(x);
SetLength(tree[x], length(tree[x])+1);
tree[x][high(tree[x])] := i;
end;
readln;
dp(0);
writeln(f[0]);
readln(n, T);
end;
close(input); close(output);
end.

Dynamic Arrays

这里,再总结一下动态数组的用法。

  1. 定义:a: array of [type];
  2. 设置长度: SetLength(a, 10);
  3. 长度加一: SetLength(a, Length(a)+1);
  4. 取得最大、最小下标: High(a), Low(a)

事实上,从 1.1 版本开始 FPC 就支持 Dynamic Arrays 了。所以在 NOIP 竞赛中我们大可放心使用。


作者:hsfzxjy
链接:
许可:CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途,非商业转载请注明出处。