P2326 AKN’s PPAP 题解

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果然骗分技巧天下通用