2020-2021:teams:wangzai_milk:20200725比赛记录
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:20200725比赛记录 [2020/07/30 23:16] infinity37 [题解] |
2020-2021:teams:wangzai_milk:20200725比赛记录 [2020/07/31 20:57] (当前版本) zars19 [比赛情况] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| ^题号 ^A ^B ^C ^D ^E ^F ^G ^H ^I ^J ^K | | ^题号 ^A ^B ^C ^D ^E ^F ^G ^H ^I ^J ^K | | ||
| - | ^状态 |- |- |- |O |O |O |- |- |O |- |- | | + | ^状态 |- |Ø |- |O |O |O |- |- |O |- |- | |
| //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试// | //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试// | ||
| 行 13: | 行 13: | ||
| ===== 题解 ===== | ===== 题解 ===== | ||
| + | |||
| + | ==== B - Graph ==== | ||
| + | |||
| + | 不好意思我人傻了，这题我三年前做过。 | ||
| + | |||
| + | 可以发现两点间路径的异或和是不变的，所以可以用 $a_u$ 表示从根节点到这里的异或和， $u,v$ 间的边权即 $a_u\oplus a_v$ ，求一个最小生成树。其实不太知道boruvka是什么，但当时yy的一个做法是从高到低位考虑，为 $ 0 $ 的和为 $1$ 的自然而然分两个连通块递归地处理，而两个连通块间连一条边用trie树找最小的。 | ||
| + | |||
| + | <hidden><code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define pa pair<int,int> | ||
| + | #define inf 0x3f3f3f3f | ||
| + | #define mp make_pair | ||
| + | using namespace std; | ||
| + | const int maxn=2e5; | ||
| + | int n,tot,a[maxn],s[maxn],t[maxn]; | ||
| + | long long sum; | ||
| + | struct Trie | ||
| + | { | ||
| + | int cnt,nxt[2]; | ||
| + | }tr[maxn*30]; | ||
| + | inline int read() | ||
| + | { | ||
| + | char ch=getchar();int x=0; | ||
| + | while(!(ch>='0'&&ch<='9'))ch=getchar(); | ||
| + | while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); | ||
| + | return x; | ||
| + | } | ||
| + | inline void init() | ||
| + | { | ||
| + | for(int i=0;i<=tot;i++)tr[i].nxt[0]=tr[i].nxt[1]=tr[i].cnt=0; | ||
| + | tot=0; | ||
| + | } | ||
| + | inline void insert(int x) | ||
| + | { | ||
| + | int p=0; | ||
| + | for(int i=30,y;i>=0;i--) | ||
| + | { | ||
| + | y=(x>>i)&1; | ||
| + | if(!tr[p].nxt[y])tr[p].nxt[y]=++tot; | ||
| + | p=tr[p].nxt[y]; | ||
| + | } | ||
| + | tr[p].cnt++; | ||
| + | } | ||
| + | inline pa find(int x) | ||
| + | { | ||
| + | int p=0,ans=0; | ||
| + | for(int i=30,y;i>=0;i--) | ||
| + | { | ||
| + | y=(x>>i)&1; | ||
| + | if(tr[p].nxt[y])p=tr[p].nxt[y],ans|=y<<i; | ||
| + | else p=tr[p].nxt[y^1],ans|=(y^1)<<i; | ||
| + | } | ||
| + | return mp(ans^x,tr[p].cnt); | ||
| + | } | ||
| + | inline void solve(int l,int r,int dep) | ||
| + | { | ||
| + | if(l>=r)return; | ||
| + | if(dep<0)return; | ||
| + | int cnt1=0,cnt2=0; | ||
| + | for(int i=l;i<=r;i++) | ||
| + | if((a[i]>>dep)&1)s[cnt1++]=a[i];else t[cnt2++]=a[i]; | ||
| + | for(int i=0;i<cnt1;i++)a[l+i]=s[i]; | ||
| + | for(int i=0;i<cnt2;i++)a[l+cnt1+i]=t[i]; | ||
| + | init(); | ||
| + | pa tmp;int ans=inf,cnt=0; | ||
| + | for(int i=0;i<cnt2;i++)insert(t[i]); | ||
| + | for(int i=0;i<cnt1;i++) | ||
| + | { | ||
| + | tmp=find(s[i]); | ||
| + | if(tmp.first<ans)ans=tmp.first,cnt=tmp.second; | ||
| + | else if(tmp.first==ans)cnt+=tmp.second; | ||
| + | } | ||
| + | if(ans!=inf&&cnt)sum+=ans; | ||
| + | solve(l,l+cnt1-1,dep-1);solve(l+cnt1,r,dep-1); | ||
| + | } | ||
| + | int head[maxn],cnt; | ||
| + | struct Node{int nxt,to,w;}edges[maxn*2]; | ||
| + | void addedge(int u,int v,int w){edges[++cnt]=Node{head[u],v,w},head[u]=cnt;} | ||
| + | void dfs(int u,int f) | ||
| + | { | ||
| + | for(int i=head[u];~i;i=edges[i].nxt) | ||
| + | { | ||
| + | int v=edges[i].to; | ||
| + | if(f!=v)a[v]=a[u]^edges[i].w,dfs(v,u); | ||
| + | } | ||
| + | } | ||
| + | int main(){ | ||
| + | memset(head,-1,sizeof(head)); | ||
| + | n=read(); | ||
| + | for(int i=1;i<n;i++) | ||
| + | { | ||
| + | int u=read(),v=read(),w=read(); | ||
| + | addedge(u,v,w),addedge(v,u,w); | ||
| + | } | ||
| + | dfs(0,0); | ||
| + | solve(1,n,30); | ||
| + | printf("%lld\n",sum); | ||
| + | return 0; | ||
| + | } | ||
| + | </code></hidden> | ||
| + | \\ | ||
| ==== D - Drop Voicing ==== | ==== D - Drop Voicing ==== | ||
| 行 145: | 行 246: | ||
| </code> </hidden> | </code> </hidden> | ||
| \\ | \\ | ||
| + | |||
| + | ==== I - Hard Math Problem ==== | ||
| + | |||
| + | 每个''H''四周要有一个''E''和一个''G''，方格填字母，问 $n,m$ 趋于无穷大时，''H''最多方案能使得其密度为多少。 | ||
| + | |||
| + | $\frac23$ 。可以使得每个''E''被 $4$ 个''H''占有，''G''同， $1:1:4$ 。 | ||
| + | |||
| + | |||
| ===== 比赛总结与反思 ===== | ===== 比赛总结与反思 ===== | ||
2020-2021/teams/wangzai_milk/20200725比赛记录.1596122171.txt.gz · 最后更改: 2020/07/30 23:16 由 infinity37
