UOJ Test Round 3

A.幾何沖刺

感覺自己的智商爆炸。

顯然是按照極角序排列之后依次加點，判斷是否有點。

保證一個點在兩個角的范圍內就OK了啊，想了半天叉積。。。

#include "triangles.h"
#include <bits/stdc++.h>
#define for1(a,b,i) for(int i=a,end_=b;i<=end_;++i)
#define FOR2(a,b,i) for(int i=a,end_=b;i>=end_;--i)
using namespace std;
typedef long long ll;
#define M 20005struct node {int id,x,y;double c;inline bool operator <(const node &a) const {return c<a.c;}
}a[M];const double pi=acos(-1);void check_triangles(int n,int m,int *ax,int *ay,int *bx,int *by,int **f) {for1(1,n,i) a[i]=(node){i,ax[i-1],ay[i-1]};for1(1,m,i) a[i+n]=(node){i+n,bx[i-1],by[i-1]};for1(1,n+m,i) a[i].c=atan2(a[i].y,a[i].x);sort(a+1,a+n+m+1);for1(1,n+m,i) a[n+m+i]=a[i],a[n+m+i].c+=2*pi;int tot=2*(n+m);for1(1,n,i) for1(i+1,n,j) f[i-1][j-1]=-1;for(int l=1;l<=n+m;++l) {while (l<=n+m&&a[l].id>n) ++l;if(l>n+m) break;bool t=a[l].c<0;int pos=l,Max_pos=-1;double num=a[l].c+pi,Max=-1e18;while (pos<tot&&a[pos+1].c<num) {++pos;//這里可以改成向量會快很多double x=atan2(a[pos].y-a[l].y,a[pos].x-a[l].x);if(!t&&x<0) x+=2*pi;if(a[pos].id>n) {if(x>Max) {Max=x;Max_pos=a[pos].id-n-1;}}else {if(x<Max) {int x_[2]={a[l].id,a[pos].id};if(x_[0]>x_[1]) swap(x_[0],x_[1]);f[x_[0]-1][x_[1]-1]=Max_pos;}}}}
}

B.去月球

感覺我寫的hash+線段樹做法挺顯然的吧，$O(m*log^2n)$。

然后優化就可以用后綴自動機搞個$O(1)$lca就OK了，但是太碼農了，沒寫。

myy的思路非常6。

考慮建出一個trie樹，表示$[1,i]$的消除完之后的序列。

然后$dis(pos[l-1],pos[r])$就是不能得到的點的個數。

證明的話就是我們考慮在$pos[l-1]$后加上$[l,r]$消除完的區間。

和$[1,l-1]$內配對的點是一個前綴，對應了走到lca，之后對應了走到pos[r]。

很巧妙了，$O(n*logn+m*logn)$。

#include <bits/stdc++.h>
#include "mythological.h"
#define for1(a,b,i) for(int i=a,end_=b;i<=end_;++i)
#define FOR2(a,b,i) for(int i=a,end_=b;i>=end_;--i)
using namespace std;
typedef long long ll;#define M 200005
int n;
int a[M],pos[M];
int dep[M],fa[M][20];
map <int,int> cc[M];inline int Lca(int x,int y) {if(dep[x]<dep[y]) swap(x,y);FOR2(16,0,i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];if(x==y) return x;FOR2(16,0,i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];return fa[x][0];
}int query(int l,int r) {--l;return r-l-dep[pos[l]]-dep[pos[r]]+2*dep[Lca(pos[l],pos[r])];
}void init(int n_,int _,int s_[],int t) {n=n_;for1(1,n,i) a[i]=s_[i];int cur=0;for1(1,n,i) {if(a[i]==a[cur]) cur=fa[cur][0];else {if(cc[cur].count(a[i])) cur=cc[cur][a[i]];else cc[cur][a[i]]=i,fa[i][0]=cur,cur=i;}pos[i]=cur;}for1(1,n,i) dep[i]=dep[fa[i][0]]+1;for1(1,16,i) for1(1,n,j) fa[j][i]=fa[fa[j][i-1]][i-1];
}

?C.量子破碎

fwt的應用。

$cnt(x\&pos)+cnt(y\&pos)=cnt(x\&y\&pos)$

fwt之后pos點不為0的條件就是上面的式子為偶數。

然后直接check解就好了。

#include <bits/stdc++.h>
#include "quantumbreak.h"
#define for1(a,b,i) for(int i=a,end_=b;i<=end_;++i)
#define FOR2(a,b,i) for(int i=a,end_=b;i>=end_;--i)
using namespace std;
typedef long long ll;
inline int read() {int f=1,sum=0;char x=getchar();for(;(x<'0'||x>'9');x=getchar()) if(x=='-') f=-1;for(;x>='0'&&x<='9';x=getchar()) sum=sum*10+x-'0';return f*sum;
}const int M=(1<<20)+5;
int ans[M];
double a[2][2];
const double c=1/sqrt(2);int query_xor(int n,int t) {int cnt=(1<<n)-1;for1(1,(1<<n)-1,i) ans[i]=i;for1(0,1,i) for1(0,1,j) a[i][j]=c;a[1][1]=-c;while (cnt>1) {FOR2(n,1,i) manipulate(a,i-1);int tot=0;int pos=query();for1(1,cnt,i) if(__builtin_parity(ans[i]&pos)==0) ans[++tot]=ans[i];cnt=tot; }return ans[1];
}

?