Doveqise

Doveqise

万事皆虚,诸行皆允

P2326 AKN’s PPAP 题解

posted on 2019-05-30 11:59:51 | under 题解 |

Orz机房dalao叫我来写这道题...
不想写正解系列...
然后想到了之前本校学长的《骗分导论》

骗分是我们的红太阳,没有他我们会死

话不多说,看起来数据不太强力,开始骗分
一开始想了一些奇淫技巧
不过忘了 1 & 0 = 0
47分代码(骗分:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
signed main()
{
    int T;
    scanf("%d",&T);
    for(int ti=1;ti<=T;ti++)
    {
        memset(a,0,sizeof(a));
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+1+n);
        int ans=0;
        for(int i=n-1;a[i]>=(a[n]>>4);i--)
            ans=max(ans,a[i]&a[n]);
        printf("Case #%d: %d\n",ti,ans);
    }
    return 0;
}

然后突然发现1 & 0 = 0... 所以换了一个写(pian)法(fen)
72分代码((骗分:

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
signed main()
{
    int T;
    scanf("%d",&T);
    for(int ti=1;ti<=T;ti++)
    {
        memset(a,0,sizeof(a));
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+1+n);
        int ans=0;
        int lim=a[n]>>1?a[n]>>1:1;
        for(int i=n;a[i]>=lim;i--)
            for(int j=i-1;a[j]>=lim;j--)
                ans=max(ans,a[i]&a[j]);
        printf("Case #%d: %d\n",ti,ans);
    }
    return 0;
}

这个其实是能骗满的emmm(但是懒得改无用部分)
所以又换了一种奇淫技巧
$O(n)$ 扫一遍然后记一下相邻&的最大值
93分代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
signed main()
{
    int T;
    scanf("%d",&T);
    for(int ti=1;ti<=T;ti++)
    {
        memset(a,0,sizeof(a));
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+1+n);
        int ans=0;
        for(int i=1;i<=n;i++)
            ans=max(ans,a[i]&a[i+1]);
        printf("Case #%d: %d\n",ti,ans);
    }
    return 0;
}

然后看了看WA的地方...我决定多来几个
AC代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
signed main()
{
    int T;
    scanf("%d",&T);
    for(int ti=1;ti<=T;ti++)
    {
        memset(a,0,sizeof(a));
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+1+n);
        int ans=0;
        for(int i=1;i<=n;i++)
            ans=max(max(max(max(ans,a[i]&a[i+1]),a[i]&a[i+2]),a[i]&a[i+3]),a[i]&a[i+4]);
        printf("Case #%d: %d\n",ti,ans);
    }
    return 0;
}

最后总结一下
骗分在你写(bu)不(xiang)出(xie)正解的时候还是有点用的
而且 这题数据好像该加强了
P.S. 刚刚机房dalao说讨论版里面有跟我做法差不多的emmm果然骗分技巧天下通用