P2326 AKN’s PPAP 题解
Doveqise
2019-05-30 11:59:51
Orz机房dalao叫我来写这道题...
不想写正解系列...
然后想到了之前本校学长的《骗分导论》
#### 骗分是我们的红太阳,没有他我们会死
话不多说,看起来数据不太强力,开始骗分
一开始想了一些奇淫技巧
不过忘了 1 & 0 = 0
47分代码(骗分:
```c++
#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分代码((骗分:
```c++
// 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分代码:
```c++
#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代码:
```c++
#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果然骗分技巧天下通用