noip2020提高组复赛_解题经典有用吗[通俗易懂]

NOIP2012 提高组复赛

$$day\;1$$

1002. game

• 状态压缩dp
• 贪心（+高精度）

因为意识到本题做法必然是定义一个玄学的比较顺序，然后整个序列sort一波即可，所以我没敢直接写。毕竟自己遇到这种题目就出现问题，而且在思考的半小时中也没有搜刮到合理的贪心方法和证明（实际上只是因为我忘记以前写过的这类贪心该如何证明，估计是被上次ACM镜像赛上的有一题恶心到了）。最后没办法只好在敲好随机化之后，去敲第三题了（事实证明这个策略是对的，第三题异常水）。

最后的时候我尴尬地发现随机化部分不需要高精。而且由于第一次敲高精除感觉出了点问题。所以最后只水了40分。

这一题出的问题感觉比较难避免吧。既然知道自己已经想不到暴力就应该稳住部分分，结果好高骛远敲了高精。不应该啊。

对于$n\le 10$的数据，我们采用全排列暴力，时间复杂度$O(n\cdot n!)$。

【探索本条线路获得物品：随机化】通过利用上述暴力程序进行对拍，我们会发现对于当前的数据，构成最优解的序列非常多。这点是随机化60分的基础。

对于$n\le 20$的数据，我们采用状态压缩dp，时间复杂度为$O(n\cdot 2^n)$。具体实现是用二进制表示第i个大臣是否在目前序列中，得到转移方程式：

$$dp[S\mid 2^i]=min\left(dp[S\mid 2^i],max(dp[S]\;,\frac{sum[S]}{r[i]})\right)$$

/* 40分 状压dp写法 */
static const int S=20;
long long sum[1<<S],dp[1<<S];
#define fi first
#define se second
pair<int,int> s[S+5];
int main(){
    int n;
    scanf("%d",&n);
    if(n>20)exit(0);
    for(int i=0;i<=n;i++)
        scanf("%d %d",&s[i].fi,&s[i].se);
    for(int k=0;k<(1<<n);k++){
        sum[k]=s[0].fi;
        for(int i=0;i<n;i++)
            if(k>>i&1)sum[k]*=s[i+1].fi;
    }
    clear(dp,0x3f);
    int Allset=(1<<n)-1;
    dp[0]=0;
    for(int k=0;k<(1<<n)-1;k++)
        for(int i=0;i<n;i++)
            if(!(k>>i&1))dp[k|1<<i]=min(dp[k|1<<i],max(dp[k],sum[k]/s[i+1].se));
    cout<<dp[Allset]<<endl;
}

接下来还会发现一个显而易见的性质：

• 对于元素i的前面$[0,i-1]$，$\prod_{j=0}^{i-1}l[j]$不会因为$[1,i-1]$的排序和元素i的选择产生影响。

说的深入点，就是对于两个相近元素的交换，只会对小范围内的最优解产生影响。根据这点有两种思路方向：

• 思路1：这种性质和冒泡排序类似，小范围的改变会逐渐地使答案靠近最优，并且与前面所做的选择无关。于是我们采用冒泡排序对序列进行不断交换。时间复杂度为$O(n^2)$，预计得分60分。
• 思路2：由于序列满足“前无向性”，因此基于前面的最优解，我们需要让当前相邻两个元素也达到最优。于是开始推论相邻两个元素的关系。

正解的思路基于相邻交叉排序策略：

• 对于前面已经不会发生改变的最优解，解出后续相邻元素$\{a,b\}$接到该最优解后，仍然使得序列最优的条件式。通过该条件式可以对序列进行排序。

本题的结论是为了$\{a,b\}$顺序更优，有$l[a]\cdot r[a]<l[b]\cdot r[b]$。下面有两种均不严谨（均没有考虑向下取整这一条件——虽然即使不考虑也不会有问题。当然跪求大神严谨证明）的证法：

• 证法1（相邻交叉排序策略）：设在中间序列中取出$a,b$，此时前面序列 T=∏p

今天的文章noip2020提高组复赛_解题经典有用吗[通俗易懂]分享到此就结束了，感谢您的阅读。