看了第一题之后感觉上去没那么毒瘤,于是决定开坑。。
也没咕多久吧。。
背单词
原题链接:loj-2012
一个串肯定得在它的后缀都被填入后再填入,我们建出这些串的反串的 Trie,现在得到一棵树形结构,其上有若干个关键点,要求给这些关键点赋权($[n]$ 的全排列),满足对于任意关键点的权小于其子树内的关键点的权,然后最小化题目里求的那个东西。
由于我们仅需考察关键点,我们直接建一棵新树,新树的节点都是原来的 Trie 上的关键点以及 Trie 的根,每个节点的父亲是它在 Trie 上离他最近的一个祖先关键点。
理性分析一下,我们发现我们一定是按某个 dfs 序给这些点定权,换句话说就是一个子树内的权一定是一段连续的取值。
设 $u$ 子树大小为 $s(u)$,$f(u)$ 表示仅考虑 $u$ 的子树时,用 $[s(u)]$ 的全排列给 $u$ 的子树内的点赋权得到的最小答案。将权的值域从 $[1,s(u)]$ 转到到 $[1+\Delta,s(u)+\Delta]$ 的过程实际上就是给 $f(u)$ 加上 $\Delta$,因为子树内的点除了 $u$ 都是 $?-?$ 的形式,两边同加 $\Delta$ 后值不变。
现在来考虑转移,除去点 $u$ 的贡献以及让儿子的赋权偏移和将 $v$ 接在 $u$ 后减去 $u$ 的权 $1$,接下来实际上是考虑如何排列 $u$ 的儿子,当我们将某个儿子 $v$ 填在第 $k$ 位时,它会让后面的儿子的赋权偏移 $s(v)$,也就是产生额外的贡献 $s(v)\bigg{(}|son(u)|-k\bigg{)}$。由于无论如何排列,$f(v)$ 总是不变的,我们只需最小化额外的贡献,这是一个经典的贪心问题,我们让 $s(v)$ 小的尽量靠前即可。
正常计算后,取根的 $f$ 减 $1$ 即可。
时间复杂度 $O(n\log n)$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
| #include<bits/stdc++.h> #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; inline void read(int& x){ static char c; while(!isdigit(c=getchar())); x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); } inline void read(ll& x){ static char c; while(!isdigit(c=getchar())); x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); }
const int N=6e5+10,M=1e5+10;
int n; char str[N]; namespace Trie{ int tot; struct Tree{int ed,ch[26];}t[N]; inline void Init(){tot=1;} inline void Insert(char *str){ int now=1,len=strlen(str); for(int i=len-1;~i;--i){ if(!t[now].ch[str[i]-'a']) t[now].ch[str[i]-'a']=++tot; now=t[now].ch[str[i]-'a']; } t[now].ed=1; } }
using namespace Trie;
int cnt=1; vector<int> Edge[M];
void dfs(int now,int top){ if(t[now].ed) Edge[top].pb(++cnt),top=cnt; for(int c=0;c<26;++c) if(t[now].ch[c]) dfs(t[now].ch[c],top); }
int siz[M]; ll F[M]; void PreCalc(int now){ siz[now]=1; for(int v:Edge[now]) PreCalc(v),siz[now]+=siz[v]; sort(Edge[now].begin(),Edge[now].end(),[](const int &lhs,const int &rhs)->bool{return siz[lhs]<siz[rhs];}); } void Calc(int now){ int deg=Edge[now].size(); F[now]=1; for(int i=0;i<deg;++i) Calc(Edge[now][i]),F[now]+=F[Edge[now][i]]+1ll*siz[Edge[now][i]]*(deg-i-1); }
void Work(){ read(n),Init(); for(int i=1;i<=n;++i) scanf("%s",str),Insert(str); dfs(1,1),PreCalc(1),Calc(1); printf("%lld\n",F[1]-1); }
int main(){Work();}
|
幸运数字
原题链接:loj-2013
倍增维护某个点到其 $2^k$ 级祖先(我的实现是到 $2^k-1$ 级祖先)的链上的线性基,计算时合并线性基得到一条链的线性基,然后就是经典问题了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
| #include<bits/stdc++.h> #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; inline void read(int& x){ static char c; while(!isdigit(c=getchar())); x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); } inline void read(ll& x){ static char c; while(!isdigit(c=getchar())); x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); }
const int N=2e4+10,U=60,logN=16;
struct LinBas{ ll A[U+5]; int cnt; LinBas(){memset(A,0,sizeof A),cnt=0;} void Insert(ll x){ if(cnt==U) return; for(int i=U;~i;--i){ if(!x) return; if(!(x&(1ll<<i))) continue; if(A[i]) x^=A[i]; else{ for(int j=0;j<i;++j) if(x&(1ll<<j)) x^=A[j]; for(int j=i+1;j<=U;++j) if(A[j]&(1ll<<i)) A[j]^=x; A[i]=x,++cnt; return; } } } };
LinBas Merge(LinBas lhs,LinBas rhs){ LinBas res; if(lhs.cnt<rhs.cnt) swap(lhs,rhs); res=lhs; if(res.cnt==U) return res; for(int i=U;~i;--i) if(rhs.A[i]) res.Insert(rhs.A[i]); return res; }
ll QueryMax(LinBas lhs){ ll res=0; for(int i=0;i<=U;++i) res^=lhs.A[i]; return res; }
int n,q; ll val[N]; vector<int> Edge[N]; int fat[N][logN+5]; LinBas _fa[N][logN+5]; int _log2[N],dep[N];
void dfs(int now,int fa){ dep[now]=dep[fa]+1; _fa[now][0].Insert(val[now]),fat[now][0]=fa; for(int i=1;i<logN;++i) fat[now][i]=fat[fat[now][i-1]][i-1],_fa[now][i]=Merge(_fa[now][i-1],_fa[fat[now][i-1]][i-1]); for(int v:Edge[now]) if(v^fa) dfs(v,now); }
void Work(){ read(n),read(q); for(int i=2;i<=n;++i) _log2[i]=_log2[i>>1]+1; for(int i=1;i<=n;++i) read(val[i]); for(int i=1;i<n;++i){ int u,v;read(u),read(v); Edge[u].pb(v),Edge[v].pb(u); } dfs(1,1); while(q--){ int x,y;read(x),read(y); LinBas res; if(dep[x]<dep[y]) swap(x,y); while(dep[x]>dep[y]) res=Merge(res,_fa[x][_log2[dep[x]-dep[y]]]),x=fat[x][_log2[dep[x]-dep[y]]]; for(int i=logN-1;~i;--i) if(fat[x][i]!=fat[y][i]) res=Merge(res,Merge(_fa[x][i],_fa[y][i])),x=fat[x][i],y=fat[y][i]; if(x==y) res.Insert(val[x]),printf("%lld\n",QueryMax(res)); else res.Insert(val[x]),res.Insert(val[y]),res.Insert(val[fat[x][0]]),printf("%lld\n",QueryMax(res)); } }
int main(){Work();}
|
萌萌哒
原题链接:loj-2014
一个简单的想法是用并查集维护颜色必须相等的集合,这样答案就很好算,但是直接连边是 $O(n^2)$ 的。
考虑对于将每个点拆成 $\log$ 个点,每个点表示从该位置开始,长度为 $2^k$ 的区间,这样我们可以将一个区间拆成 $\log$ 个区间,然后对于两个区间将它们拆成的 $\log$ 个区间对应地连在一起,这样连边的复杂度就正确了。
至于计算答案,类似于标记下传,假如 $[l,l+2^k-1]$ 的父亲是 $[l’,l’+2^k-1]$,那么连 $[l,l+2^{k-1}-1]\rightarrow [l’,l’+2^{k-1}-1]$,$[l+2^{k-1},l+2^k-1]\rightarrow[l’+2^{k-1},l’+2^k-1]$ 即可。
时间复杂度 $O(n\log^2 n)$,有一个 $\log$ 是并查集的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
| #include<bits/stdc++.h> #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; inline void read(int& x){ static char c; while(!isdigit(c=getchar())); x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); } inline void read(ll& x){ static char c; while(!isdigit(c=getchar())); x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); }
const int N=2e4+10,U=60,logN=16;
struct LinBas{ ll A[U+5]; int cnt; LinBas(){memset(A,0,sizeof A),cnt=0;} void Insert(ll x){ if(cnt==U+1) return; for(int i=U;~i;--i){ if(!x) return; if(!(x&(1ll<<i))) continue; if(A[i]) x^=A[i]; else{ for(int j=0;j<i;++j) if(x&(1ll<<j)) x^=A[j]; for(int j=i+1;j<=U;++j) if(A[j]&(1ll<<i)) A[j]^=x; A[i]=x,++cnt; return; } } } };
LinBas Merge(LinBas lhs,LinBas rhs){ LinBas res; if(lhs.cnt<rhs.cnt) swap(lhs,rhs); res=lhs; if(res.cnt==U+1) return res; for(int i=U;~i;--i) if(rhs.A[i]) res.Insert(rhs.A[i]); return res; }
ll QueryMax(LinBas lhs){ ll res=0; for(int i=0;i<=U;++i) res^=lhs.A[i]; return res; }
int n,q; ll val[N]; vector<int> Edge[N]; int fat[N][logN+5]; LinBas _fa[N][logN+5]; int _log2[N],dep[N];
void dfs(int now,int fa){ dep[now]=dep[fa]+1; _fa[now][0].Insert(val[now]),fat[now][0]=fa; for(int i=1;i<logN;++i) fat[now][i]=fat[fat[now][i-1]][i-1],_fa[now][i]=Merge(_fa[now][i-1],_fa[fat[now][i-1]][i-1]); for(int v:Edge[now]) if(v^fa) dfs(v,now); }
void Work(){ read(n),read(q); for(int i=2;i<=n;++i) _log2[i]=_log2[i>>1]+1; for(int i=1;i<=n;++i) read(val[i]); for(int i=1;i<n;++i){ int u,v;read(u),read(v); Edge[u].pb(v),Edge[v].pb(u); } dfs(1,1); while(q--){ int x,y;read(x),read(y); LinBas res; if(dep[x]<dep[y]) swap(x,y); while(dep[x]>dep[y]) res=Merge(res,_fa[x][_log2[dep[x]-dep[y]]]),x=fat[x][_log2[dep[x]-dep[y]]]; for(int i=logN-1;~i;--i) if(fat[x][i]!=fat[y][i]) res=Merge(res,Merge(_fa[x][i],_fa[y][i])),x=fat[x][i],y=fat[y][i]; if(x==y) res.Insert(val[x]),printf("%lld\n",QueryMax(res)); else res.Insert(val[x]),res.Insert(val[y]),res.Insert(val[fat[x][0]]),printf("%lld\n",QueryMax(res)); } }
int main(){Work();}
|
妖怪
原题链接:loj-2015
容易发现最大化攻击和防御是两个独立的过程。
假设某个环境 $(a,b)$,某个怪物 $(c,d)$,那么它的战斗力应该是 $c+\frac{ad}{b}+d+\frac{bc}{a}$,化简一下,它就是:$c+d+\frac{a^2d+b^2c}{ab}$。
考虑二分 $mid$,判定是否对于任意 $(a,b)$,总存在一个 $(c,d)$ 的战斗力大于 $mid$。
在这个过程中,我们仅关注 $a,b$ 的比值,那么转而考虑是否任意正实数 $k$,总存在一个 $(c,d)$ 使得 $(1+\frac{1}{k})c+(1+k)d>mid$。
把上式化开,即 $\frac{c}{k}+dk> mid-c-d$。
由于 $c,d,k$ 都是正数,故 $\frac{c}{k}+dk\ge 2\sqrt{cd}$,这要求对于 $(c,d)$,应满足 $mid\ge c+d+2\sqrt{cd}$。
但是不能直接取最大值,因为有可能出现对于每个 $(c,d)$ 它们解集的交集为空的情况。对于某个 $(c,d)$,可行的 $k$ 应是一个区间,判它们有没有交集就好了。
时间复杂度 $O(n\log U)$,看起来有更高明的 $O(n\log n)$ 的计算几何做法,但是我又菜又懒,还是不想了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| #include<bits/stdc++.h> #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; inline void read(int& x){ static char c; while(!isdigit(c=getchar())); x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); } inline void read(ll& x){ static char c; while(!isdigit(c=getchar())); x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); } inline void chkmax(double &x,double y){if(y>x)x=y;} inline void chkmin(double &x,double y){if(y<x)x=y;}
const int N=1e6+10; const double eps=1e-6; int n; int C[N],D[N];
inline bool chk(double mid){ double L=0,R=1e14; for(int i=1;i<=n;++i){ double l=mid-C[i]-D[i]; if(l*l<4.0*C[i]*D[i]) continue; double Left=l/D[i],Right=sqrt(Left*Left-4.0*C[i]/D[i]); double nowL=(Left-Right); double nowR=(Left+Right); if(nowL>R) return true; if(L>nowR) return true; chkmax(L,nowL),chkmin(R,nowR); } return false; }
void Work(){ read(n); double l=0,r=1e10,mid; for(int i=1;i<=n;++i) read(C[i]),read(D[i]),chkmax(l,1.0*C[i]+1.0*D[i]+2.0*sqrt(1.0*C[i]*D[i])); while(r-l>eps){ mid=(l+r)/2; if(chk(mid)) l=mid; else r=mid; } printf("%.4lf\n",l); }
int main(){Work();}
|
美味
原题链接:loj-2016
从高到低依次考虑每一位。
因为有了加法,01Trie 就很难处理,我们回顾没有加法的时候是怎么应用 01Trie 的:每次走到一个节点,表示它确定了这个数的前几位,后几位还不确定,这其实就是值域上的一个区间。
那么如果有加法之后我们应该如何处理?我们发现直接将上面的那个区间平移就好了。
使用主席树维护这个走儿子的过程即可。
时间复杂度 $O(n\log n+q\log n\log a)$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| #include<bits/stdc++.h> #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; inline void read(int& x){ static char c; while(!isdigit(c=getchar())); x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); } inline void read(ll& x){ static char c; while(!isdigit(c=getchar())); x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); }
const int N=2e5+10,U=2e5; int n,q;
#define ls(now) (t[now].lson) #define rs(now) (t[now].rson) int rt[N],_tot; struct Tree{int lson,rson,val;}t[N*40]; void Build(int &now,int l,int r){ now=++_tot; if(l==r) return; const int mid=(l+r)>>1; Build(ls(now),l,mid),Build(rs(now),mid+1,r); } void Insert(int pre,int &now,int l,int r,int _val){ t[now=++_tot]=t[pre],t[now].val++; if(l==r) return; const int mid=(l+r)>>1; if(mid>=_val) Insert(ls(pre),ls(now),l,mid,_val); else Insert(rs(pre),rs(now),mid+1,r,_val); } int Ask(int L,int R,int l,int r,int x,int y){ if(x>y||l>r) return 0; if(l>=x&&r<=y) return t[R].val-t[L].val; const int mid=(l+r)>>1; int res=0; if(mid>=x) res+=Ask(ls(L),ls(R),l,mid,x,y); if(mid<y) res+=Ask(rs(L),rs(R),mid+1,r,x,y); return res; }
void Work(){ read(n),read(q); int a,b,x,l,r; Build(rt[0],0,U); for(int i=1;i<=n;++i) read(a),Insert(rt[i-1],rt[i],0,U,a); while(q--){ read(b),read(x),read(l),read(r),--l; int res=0; for(int B=18;~B;--B){ if(b&(1<<B)){ int L=max(res-x,0),R=res+(1<<B)-1-x; if(!Ask(rt[l],rt[r],0,U,L,R)) res|=(1<<B); } else{ int L=max(res+(1<<B)-x,0),R=res+(1<<(B+1))-1-x; if(Ask(rt[l],rt[r],0,U,L,R)) res|=(1<<B); } } printf("%d\n",res^b); } }
int main(){Work();}
|
围棋
原题链接:loj-2017
首先肯定是容斥,考虑计算一个棋盘怎么也没法匹配模板的情况。
然后不会了,瞄了一眼题解,轮廓线 DP……然后又不会了……然后又会了……
首先模板只有两行,这是好的,于是状态只和当前行及上一行有关,考虑轮廓线。
再仔细观察,我们发现棋盘当前行怎么填只和上一行是否匹配有关。
对于轮廓线上的格子,我们并不在意它填的具体是什么,我们只需要知道它是否可以和模板匹配就行了,所以一个位置是 $1$ 当且仅当棋盘中以它为末尾的一个串可以和模板第一行匹配。注意这里即使是当前行的轮廓线,也是和模板第一行匹配。
设 $F_{i,j,S,a,b}$ 表示当前正在填第 $i$ 行第 $j$ 列,轮廓线状态为 $S$,当前行已经匹配到了模板第一行的第 $a$ 位,当前行已经匹配到了模板第二行的第 $b$ 位。
首先填初值 $F_{1,1,0,0,0}=1$。
接着考虑如何将 $F_{i,j,S,a,b}$ 转移至 $F_{i,j+1}$。
分析填上一个数会对 $S,a,b$ 产生什么影响,如果填对了数(特别地如果 $a$ 或 $b$ 等于 $c$ 了,那么它填什么数都是错的),那么它会加一,否则应该不停跳 border,直到下一位可以匹配填的下个数,这部分可以 KMP 求。至于 $S$,看看 $a$ 是否会变为 $c$ 就可以了。
当然如果 $S$ 中表示 $j$ 的那一位为 $1$,且 $b$ 将变成 $c$,那么这时是无法转移的。
最后要求的是 $\sum_SF_{n+1,1,S,0,0}$。
跳 border 的过程可以预处理出来。
具体实现中,由于前 $c-1$ 列肯定无法匹配,所以 $S$ 实际上是整体右移使得第 $0$ 位表示的是第 $c$ 列。
滚动数组优化一下空间就好了。
时间复杂度 $O(nm2^{m-c+1}c^2)$,空间复杂度 $O(2^{m-c+1}c^2)$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
| #include<bits/stdc++.h> #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; inline void read(int &x){ static char c; while(!isdigit(c=getchar())); x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); } inline void read(ll &x){ static char c; while(!isdigit(c=getchar())); x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); }
const int Mod=1e9+7; void Add(int &x,int y){(x+=y)>=Mod?x-=Mod:x;} int Pow(int a,int b){ int res=1; while(b){ if(b&1) res=1ll*res*a%Mod; a=1ll*a*a%Mod,b>>=1; } return res; }
int n,m,c,q,All; char st[2][15]; int str[2][15],Bord[2][15],nxt[2][15][3];
void Init(){ for(int B:{0,1}) scanf("%s",st[B]+1); #define TRANS(i,j) str[i][j]=(st[i][j]=='X'?2:(st[i][j]=='B')) for(int i=1;i<=c;++i) for(int B:{0,1}) TRANS(B,i); #undef TRANS for(int B:{0,1}){ str[B][0]=str[B][c+1]=-1; for(int i=2;i<=c;++i){ int now=Bord[B][i-1]; while(now&&str[B][i]!=str[B][now+1]) now=Bord[B][now]; if(str[B][i]==str[B][now+1]) ++now; Bord[B][i]=now; } for(int i=0;i<=c;++i) for(int ch:{0,1,2}){ int now=i; while(now&&str[B][now+1]!=ch) now=Bord[B][now]; if(str[B][now+1]==ch) ++now; nxt[B][i][ch]=now; } } }
int DP[2][1030][15][15];
void Solve(){ Init(); int _S=(1<<(m-c+1)); int now=0; memset(DP,0,sizeof DP); DP[0][0][0][0]=1; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ memset(DP[now^1],0,sizeof DP[now^1]); #define FOR \ for(int S=0;S<_S;++S)\ for(int a=0;a<=c;++a)\ for(int b=0;b<=c;++b)\ for(int ch:{0,1,2}) FOR{ int _nxtS,_nxta=nxt[0][a][ch],_nxtb=nxt[1][b][ch]; if(j<c) _nxtS=S; else{ _nxtS=S|(1<<(j-c)); if(_nxta^c) _nxtS^=1<<(j-c); } if(_nxtb==c&&(S&(1<<(j-c)))) continue; if(j==m) Add(DP[now^1][_nxtS][0][0],DP[now][S][a][b]); else Add(DP[now^1][_nxtS][_nxta][_nxtb],DP[now][S][a][b]); } now^=1; #undef FOR } int Ans=0; for(int S=0;S<_S;++S) Add(Ans,DP[now][S][0][0]); Ans=(All-Ans+Mod)%Mod; printf("%d\n",Ans); }
void Work(){ read(n),read(m),read(c),read(q); All=Pow(3,n*m); while(q--) Solve(); }
int main(){Work();}
|