看书看不下去于是开始写总结了。
这是我们队第一次参加ACM现场比赛，虽然是邀请赛啦，不过蒟蒻们可以去现场赛还是很开森啦，最后两题第二水到了一个铜牌倒数。>_<
周六的热身赛就开始防AK了，最后一道计算几何别人都说写起来会很麻烦，wmn敲完了模板之后还差十分钟比赛结束，就弃疗了。
不过我发现我还是看到题就会蒙的状态，热身赛前十几分钟我都是蒙的，做哪个题都是队友定的，然后榜单出来刷出来后就跟着榜单做题了== 去年的网络赛我们就是这个样子，之前一直以为现场赛看不到榜单还想着到时候怎么数气球呢。
热身赛两题都是2Y,一个是因为结尾多输出了空格WA了，另一个是看错了题把距离公式求错TLE了。我可以说我第二天也看错了题吗== 不过幸好Debug Sample的时候发现了 So木有罚时。
不过热身赛的B题真的是DFS爆搞么？第二天问学长他说复杂度就是边的个数，逐个判断每条边即可，可我总觉得复杂度是N！ =。= 好吧我对复杂度太不敏感了，直接导致了第二天本来应该DP的题被我爆搞成了DFS彻底跑偏。
晚上看了看GCJ的一道数位DP的题解，之前一直对数位DP不太熟，So临时恶补一下，可第二天正式赛的一道DP+位运算的题却木有反应过来QAQ。
第二天就是正式赛，我觉得我看到满页满页英文的problem set还是蒙的== A题是签到题，不过题干很长，被我直接跳过，bxz老老实实地把那道题看完了。我看他们都从前往后翻题，我就从后往前翻，看到最后一题感觉有希望，就是BFS之类的，应该可以做出来。
比较坑的是B题，Sample有问题，到了很久很久以后Judge才改了题目。当初我问Judge “What is the exact meaning of Deadline in the Sample？”然后果真木有理我。果真提问应该问的具体一些的，我看后来有人问“Why does Doge travel to
DP2 at time of 8?” Judge就回复了。
过了签到题后我开始敲C，当然题目也不是我读的，C就是按照题目给出的公式求一个矩阵，再跑一遍最短路。本地Sample调试了好久，主要就是因为把题目输出的量看错了吧。提交了之后居然1Y，真心奇迹，Dijkstra好久都木有写了（其实也就是对着模板敲而已），而且我当时不太熟悉Dijsktra+优先队列是怎么写的了，每次都是遍历寻找最小的d[u],居然木有TLE。
可惜之后就木有再AC了。%>_<% D题是个构造题，我一看这种字符串+考验智商的构造就无从下手，于是就扔给了队友，我开始看J题。J最后有70+队伍AC，可惜我们不是其中之一。J先用BFS做个预处理，求出所有tunnel的出口到其余的tunnel的入口的距离，BFS我居然也能写出bug==当初弄模板的时候觉得BFS不常用就随便copy了一段以前写过的code，比赛时发现那段code不完全是标准的BFS，只好自己重头写。
然后我就栽进了DFS的坑里。其实算一算也知道15！肯定会爆掉的，可热身赛爆搞就过了啊==真后悔当初木有好好深究，热身赛那一题就是找到一个存在的解既可，和我们这个要找出最优解不一样。可我总觉得最坏情况下两者复杂度差不多啊，难道是数据太弱了==？
第一次TLE了之后，我做了剪枝处理，然后就返回了WA。。。真是坑啊，然后我就又以为爆搞是可以过的，然后我的重点就变成了满世界寻找为什么WA。。。如果剪枝后返TLE我估计我都会联想到DP去。 QAQ
期间联想过用DP，感觉这种 travel each of the tunnels once and only once和TSP很像，可我不知道怎么写啊，运筹学里学TSP的时候，状态都用集合表示的，然后我怎么写个集合。。。？
比赛结束后和学弟讨论了一下知道怎么做了。事实上还是用DP，可以用二进制数表示状态，最多也就有2^15个状态，肯定不会MLE。实际处理的时候可以将十进制数map到二进制数+位运算。
假设一共三个tunnel，状态数组标记为 pair<int,int>d[MAX];
MAX是二进制数map的十进制数，d[i].first是遍历标记为1的tunnels的最短距离，d[i].second该状态对应的出口。
d[1,1,0].first=min(d[0,1,0].first+dis[d[0,1,0].second][1],d[1,0,0].first+dis[d[1,0,0].second][2])
其中dis[x][y]表示从 tunnel x 的出口到 tunnel y 的入口的距离
然后对于具体的d[x]，可以通过
<span style="font-size:18px;">for(int i=0;i<15;i++)
{
if((1<<i)&&x==1)
{
int tmp=x-(1<<i);
if(d[x].first<d[tmp].first+dis[d[tmp].second][m-i];//m is the number of tunnels
{
d[x].first=d[tmp].first+dis[d[tmp].second][m-i];
d[x].second=m-i;
}
}
}</span>
进行状态转移。
就是位运算啊，前几天百度之星资格赛的那道字典树刚写过这个。。资格赛另一题是Bitonic TSP为神马当时木有好好看=。=
边界条件：
<span style="font-size:18px;">for(int i=0;i<m;i++)
{
d[1<<i].first=0;
d[1<<i].second=i+1;//the index starts from 1
}</span>
最后就可以直接打表了QAQ
<span style="font-size:18px;">for(int i=2;i<=m;i++)
{
用 next_permutation() 列出i个1的情况下的所有排列。
状态转移。
}</span>
d[1,1,1]就是最终结果。
感觉应该没啥问题吧，啥时候有空就把这题写一写，我这反应的延迟是不是太长了一些 QAQ 放我回西工大交题去！╮(╯▽╰)╭
剩下的时间我们都卡在了这两道题上，比赛结束后她们讨论了一下D题感觉再改一个地方也可以AC的。
其实我们就算过了J题估计也是铜
比赛前的目标是一人一个气球带回家的~~~~(>_<)~~~~ ，本来觉得两题肯定铁牌了，比赛结束两分钟终榜就放出来了，因为敲键盘比较快，还可以那个铜，好开森啊~
不过说好的最佳女队奖却木有发，是因为女队太少了么。。。
期待以后有更精彩的表现！