2016 ACM/ICPC Asia Regional Qingdao Online

1001 – I Count Two Three

水题,大表+二分即可

1002 – Cure

打表即可。

1003 – Family View

给出文本串,给出一些单词,将文本中出现的单词全部变成*。
水题,单词插入自动机,维护状态能得通过回溯匹配到的最大长度,接着O(n)扫描文本串对每个匹配的位置打标记[i – len + 1, i]全部加1,这个可以O(n),接着扫描一边即可。

1004 – Tea

水体,xjb搞

1005 – Balanced Game

5种状态的锤子剪刀布,偶数赢奇数输。

1006 – The Best Path

计算给出图的欧拉回路或者欧拉路经过点的权值最大异或和。
这个将自环和其他边分开考虑,然后判断这些情况:1.是否连通;2.奇数点个数(0或者2才有解)3.如果是欧拉环需要枚举每个点作为起点去最优解。

1007 – Sort

给出n个数字,合并一些数字需要花这些数字和的花费。给出最大限额的花费,求最小的一个k,k表示每次能够合并的最多数字个数。
我们二分这个k,接着就是计算n个数字的k叉哈夫曼树,对于x = (n – 1) % (k – 1) + 1,如果结果不是1,那么就需要将x个小的数字先合并,这样后面一定可以k个准确的合并。用堆写写挂了TLE,有一种奇淫巧技,原序列排序好,用两个队列维护,一个是原序列,一个是合并后的序列,于是类似归并排序的方法去去两个队列最小的前k个即可。这样总复杂度是O(nlogn)

1009 – Tower Defence

题意转化后就是求将不同的边删除后,两部分树直径的最大值的总和。
用树形dp维护直径就好了,处理的方式和上次ccpc网赛那倒树形dp是一样的,很水的树形dp。

1010 – Herbs Gathering

100个物品的01背包,但是每个物品的重量和价值都可以达到1e9,数据是随机的。
xjb去dfs,然后弄一个强力剪纸就过了。剪纸:将每个物品根据单位体积价值逆序排好,于是dfs到某个物品i时(当前剩余容量v),如果v < 全部物品最小体积就跳出dfs,如果v * i的单位体积价值 < ans就跳出dfs。

1011 – Barricade

一个很老的网络流题目,跑一边spfa,对最短路的边构造图,用网络流搞出最小割即可。

1012 – Eighty seven

给出n <= 50个数字,q个询问:删除i,j,k三个数字,求剩下数字是否存在10个数字和等于87.
首先对于每个询问去dp,dp[i][j][k]表示前i个物品选择了j个数字时总和等于87是否可行,这样显然是要挂的,但是可以发现第三维可以用bitset优化到k / 32,那么就去xjb优化一下,但是还是会超时!这是我们发现删除数字的总方案比询问少10倍,于是我们对所有删除方案dp预处理出这些方案是否可行,但是这样还是会超时!那么会发现对于每个删除方案我们都有许多重复计算dp的地方,我们稍微保存下上次dp的结果,这样优化一下!于是就可以卡这时限过了!

 

1001:

 

1002:

 

1003:

 

1004:

 

1005:

 

1006:

 

1007:

 

1009:

 

1010:

 

1011:

 

1012:

 

 

LEAVE A COMMENT