HDU 2121 Ice_cream’s world II 最小树形图模板

Posted on 2014-11-01 Edited on 2016-01-11 In 算法学习

开始学习最小树形图，模板题。

Ice_cream’s world II

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

After awarded lands to ACMers, the queen want to choose a city be her capital. This is an important event in ice_cream world, and it also a very difficult problem, because the world have N cities and M roads, every road was directed. Wiskey is a chief engineer in ice_cream world. The queen asked Wiskey must find a suitable location to establish the capital, beautify the roads which let capital can visit each city and the project’s cost as less as better. If Wiskey can’t fulfill the queen’s require, he will be punishing.

The 2014 ACM-ICPC Asia Regional Anshan

Posted on 2014-10-31 Edited on 2018-09-23 In ACM-比赛

继续复盘下一场Regional！

【A】-_-///

【B】模拟（之前每次遇到模拟、暴搜都直接跳了，题目太长也是一个原因…下次是在不行可以尝试一下）

【C】数论互质、容斥？

~~【D】数学推导（方差）+贪心~~

~~【E】签到DP~~

【F】-_-///

【G】最小割的灵活运用

【H】搜索+打表

~~【I】签到题~~

【J】-_-///

【K】计算几何、置换群（Polya计数）

【L】AC自动机+树链剖分

The 2014 ACM-ICPC Asia Mudanjiang Regional

Posted on 2014-10-30 Edited on 2016-01-11 In ACM-比赛

继续复盘之前的Regional……出题者说这一套题太简单，对当时没有AK很不满……真是醉了，弱校没法活了

~~【A】签到题~~

~~【B】树结构，树的中心~~

【C】-_-///

~~【D】概率DP~~

【E】-_-///

【F】树结构填数

【G】-_-///

【H】模拟

~~【I】签到题~~

【J】-_-///

【K】贪心，构造后缀表达式

The 2013 ACMICPC Asia Regional Chengdu

Posted on 2014-10-27 Edited on 2016-01-11 In ACM-比赛

还有19天出发北京站，今年北京站的出题方是上交，去年他们出的成都现场的赛题，首先复盘一下。

去年的成都是我经历的第一次现场赛，也是近距离第一次见到了CLJ的真人，最后也是被虐惨了，那时候是声闻大神带着我们去的，也是在那次现场之后，深深地感受到了差距。现在我们进步了，只可惜选手都在发展，比赛也在发展，别人大概是进步得更多吧，上场西安赛站也只能遗憾。

没想到最后一场居然又能碰到开场第一次能够遇上的出题方，也是个奇妙的巧合吧。

~~【A】构造图~~

【B】模拟

【C】-_-///

~~【D】BFS（写的时候遇到一个大坑）~~

【E】计算几何

~~【F】构造生成树~~

【G】在线AC自动机

~~【H】签到题~~

【I】模拟（用STL中的set）

~~【J】数论~~

The 2014 ACMICPC Asia Regional Xian

Posted on 2014-10-27 Edited on 2016-01-11 In ACM-比赛

2题继续遗憾收场，每次都是只差最后一步。这一场却是之前那么多场中感觉距离奖牌最近的时候。好好总结一下经验教训，复盘之后好好准备下一场北京的最后一战吧。

一开始的状态非常不错，10分钟跟榜完成1A，第二个题是K，虽说开始的时候卡了不少时间，后来还是努力在1小时左右的时候出了，算是跟榜跟的还行。最终的问题应该是出在后面的3小时的策略上。

教训：

1.把3小时全部赌在一题上，现在想想确实是有点冒险，下次应该最多留一人或者两人继续磕题就好，剩下的可以看下别的。从这一点上来说，从一开始一个队友一人做F，然后一个还在看计算几何，我是把各道题差不多都翻了一遍，但是没有看到明显可出的题。这个时候状态还没算偏了太多。下面就是第二个教训；

2.不要轻易下决心把所有的胜算都赌在一道题上，决定要赌上的话也要特别确认此题可出才可。我们最终的选择是因为发现其他的题可出性不太大了，然后毅然决定放弃其他的题目，死磕出这一题就是最后的胜利了。最最遗憾的是没有让队友敲一下计算几何的，其实这题也是可出。等到最后结束时发现组合数不对而且公式也不对的时候已经来不及了；

3.今天在出题者讲解出题思路的时候特别需要重视的是逆向思维，几道题里面都需要逆向思维考虑一下。

4.牢牢跟榜确实没错，但是有时候也是要注意榜单存在一定误导性，不能盲目追一题死磕。前两题的榜单跟的很好，F题则真的是个坑了，早点发现此题确实知识不够不可出的话应该会磕一下其他题。