刚入坑没多久写的代码
[复制链接] 分享：
https://www.luogu.com.cn/problem/P3185
问题是：证明sg和lookupsg函数确实符合题目。
要数学证明，而不是“经验证21以内符合”。
我拿这个出题是因为洛谷讨论区一堆人都说O(n^3)。
似乎可以继续优化到O(nlgn)，不过我还比较菜，想不出来。
#include<bits/stdc++.h>
using namespace std;
int sg(int a){
return (a?(2*a-1-__builtin_popcount(a-1)%2):0);}
int lookupsg(int a){
return __builtin_popcount(a)%2?(a/2+1):(a?-1:0);}
int main(){
int t,n,i,j,p[21],s,u,v,w,x;
cin>>t;
for (i=0;i<t;i++){
cin>>n;
s=0;
x=0;
for(j=0;j<n;j++){
cin>>p[j];
if(p[j]%2)
s^=sg(n-1-j);
}
if(s){
for (u=0;u<n-1;u++){
for(v=u+1;v<n;v++){
w=n-1-lookupsg(s^sg(n-1-u)^sg(n-1-v));
if((w<n)&&(w>=v)&&p[u]){
if(!x)
cout<<u<<" "<<v<<" "<<w<<endl;
x++;
}
}
}
cout<<x<<endl;
}
else
cout<<"-1 -1 -1"<<endl<<0<<endl;
}
}
有一层的循环大小是t不是n
Mister (鱼我所欲也) 在 ta 的帖子中提到：
这段代码确实是O(N^3)呀
签名档
发信人: Nachtmusik (Thielemann), 信区: sysop
标 题: Re: 恳请老师们重新考虑「站务校内化」的方针
站务校内化这件事情，出发点从来就不是如何能把BBS发展的更好。
显然校内在读学生相比已经毕业的校友好控制的多。
我强烈的支持lz的倡议，但我不抱有任何希望。我记得我老早就说过，BBS自从有某机构大
规模介入管理以来，走到今天，是迟早的事情。
我这个算法（的数学原理）好理解吗
__builtin_popcount是二进制数字和的意思
Mister (鱼我所欲也) 在 ta 的帖子中提到：
哦我看错了，是n^2
签名档
██◣ ◢ █ ◢ ◣ 感谢新水freshtime制作，
█ █ █ █ █ █ 在此说明B4代表before，
██◤ █ █ █ █ 也就是说跑的比你快。
○ █ ◣ ████◣ ○ █ █ ○
<\╰ █ █ █ /\> █ █ /\)
<╲ ██◤ █ (╲ ◥███◤ /╰