Contest Info

date: 2019.06.16 16:45-21:45

practice link

Solutions

B. Cosmetic Survey

题目大意：有\(n\)个人和\(m\)个产品，每个人都要对每个产品进行一次打分，给出每个人的打分表。定义\(d(x,y)\)为给产品\(x\)打分严格比\(y\)好的人数，如果\(d(x,y)>d(y,x)\)，就在图中建一条\(x\)到\(y\)的有向边，边权为\(d(x,y)\)。定义\(S(x,y)\)为所有从\(x\)到\(y\)的路径中，需要经过的最小边权的最大值，求哪些点\(x\)满足\(S(x,y)\ge S(y,x)\)对所有\(y\)都成立。(\(n,m\le500\))

题解：令\(S(x,y)\)初值为\(d(x,y)\)（如果\(d(x,y)>d(y,x)\)）或负无穷。用\(S(i,j)=\max(S(i,j),\min(S(i,k),S(k,j)))\)来跑floyd算法即可，时间复杂度\(O(nm+m^3)\)。

F. Parentheses

题目大意：给出一个由单个小写字母的运算元，加减乘除取模运算符，小括号，和空白字符组成的字符串\(s\)。判断\(s\)是否是合法的c语言算式表达式，若是，进一步判断其括号是否符合要求。

题解：判断合法用栈计算表达式的算法，同时判断一些非法情况。判断括号符合要求用递归下降法。

J. Starwars

题目大意：给出一个有向图，\(n\le1000\)个顶点，\(m\le8000\)条边，每条边上有一个\(1\)到\(20\)范围的数字。已知其中一部分点为黑色，剩下的为白色；已知一部分点为可终止节点，可以是黑色也可以是白色。问是否存在两条路径，一条从黑点出发到达某个可终止节点，另一条从白点出发到达某个可终止节点，且路径上的数字序列相同。

题解：令状态\((x,y)\)表示两条路径当前分别在\(x\)和\(y\)且后面的路径的数字序列相同的，从所有的可终止节点pair开始逆推，如果能搜到两个颜色不同的点，则输出yes。扩展状态时，枚举上一条边上的数字\(i\)，令\(N_i(x)\)为所有可以通过数字为\(i\)的点直接到达\(x\)的点的集合，不妨设\(|N_i(x)|\le|N_i(y)|\)，枚举\(|N_i(x)|\)中每个点\(z\)，用bitset枚举所有未访问过的\((z,w)\)状态。时间复杂度为\(O(20N^2+NW^2/64)\).