加载中...
题解 UVA1591 【数据挖掘 Data Mining】

前言:

这个题确实反应了自己的水平,刚开始读不懂原文,读翻译,但感觉好抽象,还是不理解,便又硬读原文,还是有很大的困难,但多少已经有一些思路了(大体方向

已经知道枚举),但最大的阻碍还是那个表达式,不隐瞒,我是借鉴了“代号4101”的博客后,知道了如何利用那个表达式。

思路分析:

根据题目的描述,我们是一定要用$Qofs$’$(i)$ $=$ $(Pofs(i) + Pofs(i)$ $<< A) >>$ B这个公式的,在看题目的输出要求,如果有多解,先输出$A$最小的,如果还是有多解,则

在输出$B$最小的,这样我们大体就可以猜到一定是两层循环$A$,$B$进行枚举的方式了,这样发现符合要求的,就可以满足$A$,$B$先以最小的输出,在看看暴力枚举会不会超时,题目中

$1 ≤ N ≤ 2^{20},1 ≤ SP ≤ 2^{10},1 ≤ SQ ≤ 2^{10}$,而这个题目的要求为求一个$K$ 稍微大于 $N * Sq$(就是比它大,而且最接近),所以$MAX = 2 * 10 ^ {30}$,所以A和B都是属于[ 0 , 32 )所以肯定不会超时的啦!

题目中说到P数组肯定是连续的,$Q$不一定是连续的,所以代入的时候,肯定$N$个数最大值要代入,根据这个式子Pofs(i−1)= Pofs(i)−Sp
得:$Pofs(N) $= $Pofs$(n-1) $+Sp$;

$Qofs$’$(N)$ = (($Pofs$($N - 1$) $+ Pofs$($N - 1$)<< $A)$ >> $B + Sp$ )大于等于$N * Sq$即可!($Pofs$($N - 1$) $=$ ($N - 1$)$Sp$)

教训:

这个题自己WA了好多遍,错误原因就在于:我直接让标记变量等于第一个值($i = 0, j = 0$)然后再让后面的和他进行比较,发现比它小,在让标记变量等于另一个更小的,但这是错误的,因为第一个变量可能不大于

$N * Sq$;

改进方法:

①:应该找第一个符合大于$N * Sq$的,在让标记变量等于它 在进行比较!

②:(代号$4101$)的方法,直接在循环时和一个不可能取到的非常大的数比较(标记变量为$N * Sq <<10$),这样也确实很简单,代码也相当少!值得学习!

注:$Pofs ( i ) = Sp * i$ 可以理解为空间大小的偏移量!

代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    unsigned long long Sp,Sq,N,c_ans,c_i,c_j,ans;
    while(cin>>N>>Sp>>Sq){
        int i,j,cont=0;
        for(i=0;i<32;i++){
            for (j=0;j<32;j++){
                ans=((Sp*(N-1)+(Sp*(N- 1)<<i))>>j)+Sq;
                if (ans>=N*Sq){
                    cont++;
                    if (cont==1)
                    {
                        c_ans=ans;
                        c_i=i;
                        c_j=j;
                    }
                    if (ans<c_ans){
                    c_ans=ans;
                    c_i=i;
                    c_j=j;
                    }
                }
            }
        }
        cout<<c_ans<<" "<< c_i<<" "<< c_j<<"\n";
    }
    return 0;
}

后记:

遇到难懂的题目,千万不要放弃,要仔细多读题目,想方法把它理解,测试代码时,要吸取$WA$的教训,仔细想方法,这样题目方能迎刃而解!

最后求评论和点赞QAQ


  目录
劳动
快乐