NOIP选讲

---

P2822 [NOIP2016 提高组] 组合数问题

---

给定两个整数$N,M$和一个整数$K$，求对于所有的二元组$(i,j),0 \leq i \leq N , 0 \leq j \leq min(i,M)$中，有多少对二元组满足$C ^i _j \ mod \ K =0$？ $T$组数据。
$N \leq 2000 , M \leq 2000 ,T \leq 10^4，K$对于$T$组数据永远不变。

---

首先一个十分简单的方法：枚举所有$(i,j)$,计算$C^i _j$，并判断。
这种做法对于$T=1$的时候绰绰有余，但我们发现$T \leq 10^4$，因此，我们不得不来想一些优化。

我们要解决的就是如何优化掉$O(N \times M)$的答案统计。由于$K$对于所有$T$数据是不变的，因此我们可以预处理出$N \leq 2000 , M \leq 2000$的所有组合数。然后我们可以用前缀和统计出答案数组。若$c[i][j]\%K==0$,则$a[i][j]++$。然后用前缀和统计$a$数组。最有求答案就是$O(1)$的，直接输出$a[n][m]$即可。

另外就是$N \leq 2000 , M \leq 2000$的话，组合数算出来会非常大，$long \ long$根本就存不下。因此，我们不能用直接阶乘算组合数的方法(会有除法操作，不好取模)。这里就要用到另一种高级的组合数求法：组合数递推求法:

$$c[i][j]=c[i-1][j]+c[i-1][j-1]。$$ 这样，取模操作就很好完成，此题也完美解决了。

---

P1314 [NOIP2011 提高组] 聪明的质监员

一个质监员要对一批货物进行质监。一共$N$个矿石，每个矿石有两个属性$w_i$和$v_i$，表示矿石的重量以及价值。质监流程如下：

• 给定$M$个区间$[l_i,r_i]$；
• 选定一个参数$W$；
• 对于第$i$个区间，求出这个区间的质监值： $$y_i= \displaystyle \sum ^{r_i} _{j=l_i} [w_j \geq W] \times \displaystyle \sum ^{r_i} _{j=l_i} [w_j \geq W]v_j$$ 其中中括号返回一个$bool$值，表示判断条件是否成立。

最后这批矿产的总质监值为$Y= \sum y_i$。

另外给出一个参数$s$,求一个参数$W$，使得$|Y-s|$最小。求出这个最小值。

$N,M \leq 2 \times 10^5 ,0 < w_i,v_i \leq 10^6 ,0 < s < 10^{12}。$

---

不难想到二分$W$。对于每一个$mid$值，我们枚举暴力求出$Y$值。

然后就来想一想如何优化这个暴力。

看到$\sum$这个符号，你能想到什么吗？

对了！那就是前缀和！

我们对于每个mid，求出$y_i= \displaystyle \sum ^{r_i} _{j=l_i} [w_j \geq W]$部分与$\displaystyle \sum ^{r_i} _{j=l_i} [w_j \geq W]v_j$的前缀和$a[]$和$b[]$。
然后对于每一个区间$[l_i,r_i]$，直接$O(1)$便可以求出值:

$Y+=(a[r[i]]-a[l[i]-1])*(b[r[i]]-b[l[i]-1])$。

然后对于这两个数组的求法也非常简单。判断$w_i$是否$\geq mid$。若是，则

$$a[i]=a[i-1]+1 , b[i]=b[i-1]+v[i]$$ 若否，则 $$a[i]=a[i-1],b[i]=b[i-1]$$

最后求出答案即可。

---

P1073 [NOIP2009 提高组] 最优贸易

一张$N$点$M$边的有向图，一个商人会从点$1$走到点$N$。这个商人会利用不同城市之间物价不同来赚取差价。每个城市的物品价格为$w_i$。商人会在某个城市买入物品，并在另一个城市卖出。这样他会赚得一些差价。一个点可以被多次通过，且不要求走完所有城市。问这个商人从点$1$走到点$N$的过程中，进行一次买卖能获得的最大差价是多少？

$N \leq 10^5,M \leq 5 \times 10 ^5 ,1 \leq w_i \leq 100$。

---

由于一个点可以反复被经过，因此不难想到利用$tarjan$缩点。那么一个连通分量里的点，一定可以取到最大值和最小值，里面走成什么样子可以不关心。

缩完点后，我们需要知道每一个联通分量与点$1$所在的联通分量所连成的路径中的最小值，记为$f[i]$。然后对于每一个连通分量，用该连通分量中的最大值减去$f[i]$，在所有值中取$max$即为答案。

那么为了做到这一点，我们就要使用拓扑。拓扑过程中可以顺便将$f$数组更新出来，并同步计算$ans$:

$$f[v]=min(f[v],f[u]),ans=max(ans,maxn[i]-f[i])$$ $f$数组初始化为每个联通分量的最小值。

另外要注意的是，在进行更新时，不是每个点都可以进行更新。要判断从这个点能否走到$N$点。这可以通过建反图并简单的$dfs$就可以做到。代码如下：

inline void dfs(int u){
    if(now[u]) return ;now[u]=1; // u点可以走到n点
    for(int i=fh[u];i;i=fne[i])
        dfs(fgo[i]);
}

然后拓扑：

inline void topsort(){
    int f[N];
    memset(f,0x3f,sizeof f); 
    for(int i=1;i<=scc;i++){
        if(!degin[i]) q.push(i);
        f[i]=minn[i];//初始化f数组
    }
    while(!q.empty()){
        int u=q.front();q.pop();
        if(now[u])ans=max(ans,maxn[u]-f[u]); //可以到达n，才更新
        for(int i=rh[u];i;i=ne[i]){
            int v=go[i];
            f[v]=min(f[u],f[v]);
            if(!--degin[v]) q.push(v);
        }
    }
    cout<<ans;
}

代码有点长，看这里：点我