Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)

2016年11月10日4210
A. Checking the Calendar
问有没有可能存在一年中的连续两个月,第一个月的第一天的星期是给定的第一个字符串,第二个月的第一天的星期是给定的第二个字符串
模拟即可

B. Batch Sort

给你n行,每行都是一个1-m的排列。

\(1\leq n\leq 20,1\leq m\leq 20\)

你可以交换任意两列,并且你可以每行最多交换两个元素,问你能不能使得每行都是单增的

枚举两列交换,每行贪心

C. Ray Tracing

从(0,0)向(1,1)发射光线,在一个\(n*m\)的矩形里面不断反射

然后k个询问,问你第一次到某个点的时间

\(1\leq n,m,K\leq 10^5\)

其实可以用数论求解QAQ

考虑经过某个点的光线为\(y=x+b\)或\(y=-x+b\)

比较难写的模拟。。。用两个set维护所有的点,每次删去一条光线上经过的点,并计算反射后的光线

D. Dense Subsequence
给一个字符串,从中选出一串字符,使得这串字符的排序后字典序最小
若上一次选第i个字符 ,\([i+1,i+m]\)中至少选一个
贪心,枚举选到某一个字母x,比x的全都选,然后选尽量少的x

E. Goods transportation
给n个城市,每个城市可以往比它编号大的城市运输c的货物,每个城市有\(p_i\)的货物,最多消耗\(s_i\)的货物
问最多消耗多少货物
\(1\leq n\leq 10000\)
依据题意可以建立网络流模型,然而图太大无法套用网络流算法
考虑S到T的最小割,用\(F(i,j)\)表示前i个结点,有j个结点属于T集的最小割,考虑第i个结点是否属于T集
那么\(F(i,j)=min(F(i-1,j)+p_i+j*c,F(i-1,j-1)+s_i)\)