Comet OJ - Contest #8

　　　　　Comet OJ - Contest #8参赛总结——林荫

1. 本人还是一如既往的菜。
2. Comet OJ - Contest #X属于ACM赛制
3. 六道题目难度从入门到金牌递增

　　本次总结给出T3,4分析与解法（5，6以后填坑）

　　T3：符文能量

• 1000ms，256MB

1. 题目描述

   米薇女王万万没有想到考德威尔男爵的真实意图。她的脑海里浮现出莱里亚的秀美山河，可惜再也回不去了。

   不过所幸的是，她还有着军队和重整山河的勇气。雷纳德为米薇女王呈上了 nnn 块符文石。符文石可以帮助你更好的战斗。每个符文石拥有能量，米薇可以挑选类型相近的符文石融合并释放出能量。

   形象的，我们可以把每个符文石 PiP_iPi? 描述成一个二元组 (ai,bi)(a_i,b_i)(ai?,bi?) 。对于两个相邻的符文石 PiP_iPi? 与 Pi+1 P_{i+1}Pi+1?，可以把他们融合为 (ai,bi+1)(a_i,b_{i+1})(ai?,bi+1?) 并释放出 ai+1?bia_{i+1}*b_iai+1??bi? 的能量。融合完的符文石会替换掉原本的两个二元组，出现在他们的位置上。米薇希望把所有的 nnn 个符文石融合成 111 个符文石。你可以以任意顺序合并相邻的两个符文石。

   幸运的是，米薇找到了一个法力通天的术士，在全部融合过程前你可以选择一段连续的区间将里面的符文石精炼。即把原本的一段二元组 (ai,bi?) 乘 kkk 变为 (ai?k,bi?k)(a_i cdot k,b_i cdot k)(ai??k,bi??k)。当然你也可以不选择任何区间。注意此操作必须在初始状态进行。

   她希望她释放的能量尽可能小并想知道这个值是多少。

   你可以结合样例解释来理解题目。

   ?

2. 输入描述

   第 111 行 222 个整数 nnn 与 kkk 。 代表有 nnn 块符文石，精炼符文石的倍率为kkk。

   接下来 nnn 行，每行 222 个整数 aia_iai? 与 bib_ibi? 。描述第 iii 个符文石的属性。

   • 2≤n≤1052leq nleq 10^52≤n≤105
   • 0≤∣ai∣,∣bi∣,∣k∣≤2000 leq |a_i|,|b_i|,|k|leq 2000≤∣ai?∣,∣bi?∣,∣k∣≤200

   输出描述

   一个整数，释放能量的最小值

3. 样例输入 1

   4 -1
   -1 -2
   2 3
   3 4
   -3 5

4. 样例输出 1

　　　　-25

　　分析：提供一种和正解不沾边的做法：观察题目可知，所给入的参数a[1]和b[n]是不参与计算的。进而可得知如果不考虑精炼的话，原始式子的答案固定，即为sum(i=1,i<n)a[i+1]*b[i]。下面开始考虑精炼的情况。

　　　手动推导式子可以得到一个神奇的发现：如果假设精炼的区间为L，R，那么答案就是a[2]*b[1]+a[3]*b[2]+a[4]*b[3]......+a[L-1]*b[L-2]+a[L]*b[L-1]*K+a[L+1]*b[L]*K^2+a[L+2]*b[L+1]*K^2.......a[R]*b[R-1]*K^2+a[R+1]*b[R]*K+a[R+2]*b[R+1].......

　　然后这个问题就变成了求上述式子的最小值。

　　那果断DP啊。

　　至于方程？状态：DP[i][0]在1——i的区间内不使用精炼的最小值，DP[i][1]在1——i的区间内已经开始精炼，但是精炼未结束的最小值。DP[i][2]在1——i的区间内已经完成精炼的最小值

for(int i=1;i<n;i++)
    {
        dp[i][0]=dp[i-1][0]+sum[i];
        dp[i][1]=min(dp[i-1][0]+sum[i]*k,dp[i-1][1]+sum[i]*k*k);
        dp[i][2]=min(dp[i-1][1]+sum[i]*k,dp[i-1][2]+sum[i]);
    }

　　标程放上！

#include<iostream>
#include<cstdio>
using namespace std;
long long int n,k,a1,a2;
long long int sum[100001];
long long int dp[100001][3];
int main()
{
    scanf("%lld%lld",&n,&k);
    scanf("%lld",&a1);
    for(int i=1;i<n;i++)
    {
        scanf("%lld%lld",&a1,&a2);
        sum[i]=a1*a2;
    }
    scanf("%lld",&a1);
    for(int i=1;i<n;i++)
    {
        dp[i][0]=dp[i-1][0]+sum[i];
        dp[i][1]=min(dp[i-1][0]+sum[i]*k,dp[i-1][2]+sum[i]);
    }
    cout<<min(dp[n-1][0],min(dp[n-1][2],dp[n-1][1]));
    return 0;
}

?T4：

题目描述

?

菜菜太菜，但他不想种菜。

有 nnn 块土地，每块土地有一个菜值。它们之间有 mmm 条小路，每条连接两块土地，小路只能单向通行，不存在一条小路两端连接同一块土地，但可能存在两条小路两端连接的土地分别相同。如果存在一条从土地 uuu 到土地 vvv 的小路，则称 uuu 能直接到达?vvv。

菜菜可以购买一些土地，他必须在其中选择一块建造自己的家，所购买的剩下的土地都被作为菜地。因为菜菜不想种菜，所以他希望从他家能直接到达的土地中，一块菜地也没有（如果菜菜家不能直接到达任何一块土地，这也能满足他的愿望）。

菜菜提出了 qqq 个问题，每个问题给出 L,RL,RL,R ，询问如果他购买了第 LLL 到第 RRR 块之间的所有土地，那么所有满足他愿望的建造家的选址的菜值之和是多少？

?

4 2 2
3 5 10 6
1 4
2 3
2 3
1 3

16

5 6 3
114 29 219 231 165
5 4
1 2
1 3
5 3
3 2
3 4
2 2
1 2
4 5

658
好吧我老实交待我考场上3，4都没做出来，3还想了想，4压根没看
首先分析题目，发现只有当某块地它左边直接相连的土地为L以外的点右边为R以外的点时，这块土地才可以作为菜地
记这两个直接相连的点为xi，yi(如果不存在的话xi=0，yi=n+1)，所以原题求对于每一组询问[L,R],求出L<=I<=R且XI<L&&YI>R时的Val[i]之和
下面我们生成六个神奇参数：a<=i<=b,c<=xi<=d,e<=yi<=f
这样的话就可以用6个神奇参数约束出每一种情况，记作S(a,b,c,d,e,f)
答案即为S(L,R,L-1,R+1,n+1),但是这个鬼东西不会算啊
不虚，咱能差分
S(L,n+1)=S(L,n+1,n+1)-S(L,L,R)+S(L,R)
这样的话就变成了一次枚举两个参数的二维数点二维数点有经典做法，将所有询问离线，点和询问按第一维排序，第二维作为 下标，顺次扫描，遇到一个点将它第二维对应的位置加上它的权值，遇到一个 询问就查询对应第二维的对应的区间和，只需一个支持单点加，区间求和的数 据结构，树状数组即可胜任。