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

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

NOIP2012 提高组复赛


day1


这里写图片描述

1002. game

  • 状态压缩dp
  • 贪心(+高精度)

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

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

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

对于 n10 的数据,我们采用全排列暴力,时间复杂度 O(nn!)

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

对于 n20 的数据,我们采用状态压缩dp,时间复杂度为 O(n2n) 。具体实现是用二进制表示第i个大臣是否在目前序列中,得到转移方程式:

dp[S2i]=min(dp[S2i],max(dp[S],sum[S]r[i]))

/* 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,i1] i1j=0l[j] 不会因为 [1,i1] 的排序和元素i的选择产生影响。

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

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

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

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

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

  • 证法1(相邻交叉排序策略):设在中间序列中取出 a,b ,此时前面序列 T=p

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/71436.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注