论程序设计中的“奇技淫巧”


在程序设计竞赛中呢,总有那样一些“奇技淫巧”,很少可以想到的Solution却可以解决大数据下的某些题。

话不多说,让我们切入主题。

注:例题均为水题


例题:抽签

你的朋友提议玩一个游戏:将写有数字的n个纸片放入口袋中,你可以从口袋中抽取4张纸片,每次记下卡片上的数字后都将其放回口袋中。如果这4个数字的和是m,就是你赢,否则就是你的朋友赢(这也够智障的qwq)。你挑战了好几回,结过一次也没赢过,于是怒而撕破口袋,取出所有纸片,检查自己是否真的有赢的可能性。请你编写一个程序,判断当纸片上所写的数字是k1,k2,......,kn时,是否存在抽取4次和为m的方案。如果存在,输出Yes;否则,输出No。
样例

INPUT OUTPUT
4 10
2
3
4
1
Yes

 


原题:4<=n<=50,a<=m,ki<=10^8

这题原题是Zero难度的qwq

由数据范围得出,本题卡牌数量极小,极其适合暴力,直接出解即可。

算法复杂度:O(n^4)

#include <cstdio>

int n,m,a[60];
bool ans;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            for(int k=1;k<=n;++k)
                for(int l=1;l<=n;++l)
                    if(a[i]+a[j]+a[k]+a[l]==m)
                        ans=true;
    printf("%s",ans?"Yes":"No"); 
    return 0;
}

假设2:4<=n<=1000,a<=m,ki<=10^8

这就不能单纯的使用O(n^4)进行运算了(晕),那么究竟该怎么办呢?

a[i]+a[j]+a[k]+a[l]==m => a[l]=m-a[i]-a[j]-a[k]

那么,我们就检查m-a[i]-a[j]-a[k](枚举i,j,k),如有a[l]符合条件,那么就Yes~

但是问题来了,枚举i,j,k已经很可怕了,难道还要我们枚举l?那不还是O(n^4)吗?

二分查找保平安

于是,时间复杂度变成了O(n^3*logn)

可是,当n=1000时,O≈10^9,仍然超出1s限制。

那么,又应该怎么办呢?

a[i]+a[j]+a[k]+a[l]==m => a[l]=m-a[i]-a[j]-a[k] => a[i]+a[j]=m-a[k]-a[l]

难道又要循环O(n^4)?

当然不是。

我们进行前缀和思想的优化,将a[i]+a[j]的所有可能性枚举并排序。

之后进行二分查找,如果在两数和数组s[]之中有s[i]=m-s[j]就可以了。

#include <cstdio>

int a[],s[],top;

bool search(int target)
{
    int l=1,r=top,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(target>s[mid]) l=mid+1;
        else if(target<s[mid]) r=mid;
        else return true;
    }
    return false;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        {
            scanf("%d",&a[i]);
            for(int j=1;j<=i;++j)
            {
                ++top;
                s[top]=a[j]*a[i];
            }
        }
    std::sort(s+1,s+top+1);
    for(int i=1;i<=top;++i)
    {
        if(search(m-s[i]))
        {
            printf("Yes");
            return 0;
        } 
    }
    printf("No");
    return 0;
}

可是似乎还有点麻烦啊qwq

没办法谁让这道题压缩起来那么难qwq

我技艺不精也就只能解决到这样了。

O(n^2*logn)

神犇有什么特殊解法就说一下吧qwq似乎有诶qwq

再进行压缩就变成O(n^2),似乎并没有什么卵用


例题v2.0:主元素问题

n个数中有一个数出现次数>=50%,请输出那个数。

内存限制:2MB

开不了数组qwq再小的数组也不行qwq别提存储所有数了qwq

怎么办呢qwq

其实并不是很难,只是很烧脑。

定义两个int a,b,in.

a存储数字,b存储这个数字出现的次数,in是读入时用于存储的临时变量。

每次读入一个数,如果a!=in,那么--b,反之++b.

如果上一步操作结束发现b==0,即已没有a这个数了,就使a=in,b++,表示有1个in加入。

最后输出a.

#include <cstdio>

int n,a,num,in;

int main()
{
    scanf("%d",&n);
    scanf("%d",&in);
    num=in;
    ++a;
    for(int i=2;i<=n;++i)
    {
        scanf("%d",&in);
        if(a==0)
        {
            num=in;
            ++a;
        }
        else if(in!=num) --a;
        else ++a; 
    }
    printf("%d",num);
    return 0;
}

这个东西看起来似乎没什么卵用,可是可以开拓思维嘛(捂脸跑

原题:JDOJ - random num 2236 2429

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 论程序设计中的“奇技淫巧”


不骗了,不骗了。
A Simple OIer fighting tooth and nail.