2020-2021:teams:die_java:front_page_summertrain2

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:die_java:front_page_summertrain2 [2020/07/17 18:00]
fyhssgss [D.Duration]
+++ 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$ 个数（可以选相同的数）异或和的最大值。
 === 题解 ===
-<code cpp>
+发现 $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 =====

2020-2021/teams/die_java/front_page_summertrain2.1594980047.txt.gz · 最后更改: 2020/07/17 18:00 由 fyhssgss