模拟测试60
T1: 约瑟夫问题。 经证(da)明(biao)可知,最终答案计算方法是: 答案由$1$开始,每次加$m$,若大于次数加一,就对次数加一取模。 可以$O(1)$计算每次取模的位置,取模不超过$mlogn$次,于是时间复杂度为$O(mlogn)$。 T2: 普及:向量叉积:$v_1=(x_1,y_1),v_2=(x_2,y_2) Rightarrow vec{v_1}times vec{v_2}=x_1*y_2-x_2*y_1$ 然而我只会拆平方干推式子: $large begin{array}{ll} ans &=& sum limits_{i=l}^r sum limits_{j=i+1}^r (v_i times v_j)^2 &=& sum limits_{i=l}^r sum limits_{j=i+1}^r (x_iy_j-x_jy_i)^2 end{array}$ 考虑拆平方: $large begin{array}{ll} ans &=& sum limits_{i=l}^{r} sum limits_{j=i+1}^r (x_i^2y_j^2+x_j^2y_i^2-2x_iy_ix_jy_j) &=& sum limits_{i=l}^r sum limits_{j=i+1}^r x_i^2y_j^2 + sum limits_{i=l}^r sum limits_{j=i+1}^r x_j^2y_i^2 - sum limits_{i=l}^r sum limits_{j=i+1}^r 2x_iy_ix_jy_j &=& sum limits_{i=l}^r sum limits_{j=l}^r [i!=j]*x_i^2y_j^2 - sum limits_{i=l}^r sum limits_{j=l}^r [i!=j]*x_iy_ix_jy_j &=& sum limits_{i=l}^r x_i^2 (sum limits_{j=l}^r y_j^2 -y_i^2) - (sum limits_{i=l}^r x_iy_i (sum limits_{j=l}^r x_jy_j - x_iy_i)) &=& sum limits_{i=l}^r x_i^2 sum limits_{j=l}^r y_j^2 - sum limits_{i=l}^r x_i^2y_i^2 - (sum limits_{i=l}^r x_iy_i sum limits_{j=l}^r x_jy_j - sum limits_{i=l}^r x_i^2 y_i^2) &=& sum limits_{i=l}^r x_i^2* sum limits_{i=l}^ry_i^2 - (sum limits_{i=l}^r x_iy_i)^2end{array}$ 线段树中维护$sum limits_{i=l}^r x_i^2$,$sum limits_{i=l}^r y_i^2$和$sum limits_{i=l}^r x_iy_i$即可。 时间复杂度$O((n+m)logn)$。 T3: 经典的LCIS(最长公共上升子序列)问题。 设$dp[i][j]$为第一个串考虑到第$i$位,第二个串选择第$j$位的最优答案。 则有状态转移方程: 我们发现第二维只能从小向大转移,所以从小到大枚举,同时更新当前最优答案,直接更新即可。 至于方案,记录转移前驱即可。 时间复杂度$O(nm)$。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |