2020-2021:teams:die_java:front_page_summertrain2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:front_page_summertrain2 [2020/07/17 17:57] fyhssgss [题目名字] |
2020-2021:teams:die_java:front_page_summertrain2 [2020/10/17 23:02] (当前版本) fyhssgss |
||
|---|---|---|---|
| 行 239: | 行 239: | ||
| 水题 | 水题 | ||
| + | ===== E.Exclusive OR ===== | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 给了 $n$ 个数，让你求 $1 \le i \le n$ ,选 $i$ 个数（可以选相同的数）异或和的最大值。 | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 发现 $i$ 在19之后答案和 $i-2$ 一致，原理参考线性基。所以我们只需求前19个的答案，用FWT即可完成。 | ||
| + | |||
| + | <hidden 代码> | ||
| + | <code cpp> | ||
| + | #include<iostream> | ||
| + | #include<cstdio> | ||
| + | #include<algorithm> | ||
| + | #include<cstring> | ||
| + | #define ll long long | ||
| + | using namespace std; | ||
| + | int read() | ||
| + | { | ||
| + | int k=0,f=1;char c=getchar(); | ||
| + | for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; | ||
| + | for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f; | ||
| + | } | ||
| + | const int M=1050000; | ||
| + | int n,N,a[M],b[M],c[M],ans[M]; | ||
| + | void FWT(int *a,int opt) | ||
| + | { | ||
| + | for(int i=1;i<N;i<<=1) | ||
| + | for(int p=i<<1,j=0;j<N;j+=p) | ||
| + | for(int k=0;k<i;++k) | ||
| + | { | ||
| + | int X=a[j+k],Y=a[i+j+k]; | ||
| + | a[j+k]=(X+Y);a[i+j+k]=(X-Y); | ||
| + | if(opt==-1)a[j+k]=1ll*a[j+k]/2,a[i+j+k]=1ll*a[i+j+k]/2; | ||
| + | } | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | n=read();int mx=0,x; | ||
| + | for(int i=1;i<=n;i++) | ||
| + | { | ||
| + | x=read(); | ||
| + | a[x]=1;b[x]=1;mx=max(mx,x); | ||
| + | } | ||
| + | for(N=1;N<=mx;N<<=1); | ||
| + | ans[1]=mx; | ||
| + | FWT(b,1); | ||
| + | for(int i=2;i<=min(25,n);i++) | ||
| + | { | ||
| + | for(int j=0;j<N;j++) | ||
| + | if(a[j]) a[j]=1; | ||
| + | FWT(a,1); | ||
| + | for(int j=0;j<N;j++) | ||
| + | a[j]=a[j]*b[j]; | ||
| + | FWT(a,-1); | ||
| + | for(int j=N-1;j>=0;j--) | ||
| + | { | ||
| + | if(a[j]) {ans[i]=j;break;} | ||
| + | } | ||
| + | // for(int j=0;j<N;j++) | ||
| + | // cout<<a[j]<<" "; | ||
| + | // cout<<endl; | ||
| + | } | ||
| + | for(int i=1;i<=n;i++) | ||
| + | { | ||
| + | if(i>25) | ||
| + | { | ||
| + | if(i&1) printf("%d ",ans[25]); | ||
| + | else printf("%d ",ans[24]); | ||
| + | } | ||
| + | else printf("%d ",ans[i]); | ||
| + | } | ||
| + | puts(""); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| ===== F.Fake Maxpooling ===== | ===== F.Fake Maxpooling ===== | ||
| 行 462: | 行 540: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| - | ===== 题目名字 ===== | ||
| - | === 题意 === | ||
| - | |||
| - | === 题解 === | ||
| - | |||
| - | <code cpp> | ||
| - | |||
| - | </code> | ||
| ===== J.Just Shuffle ===== | ===== J.Just Shuffle ===== | ||
2020-2021/teams/die_java/front_page_summertrain2.1594979823.txt.gz · 最后更改: 2020/07/17 17:57 由 fyhssgss
