JXOI2019前学习记录
本文只是本蒟蒻退役前的记录，参考价值不大QAQ
week1
2.21
参加了一下给高一同学的比赛
大概是简单题，易知对于一个‘A’前有几个’K’它就可以移动几次
DP题，可以用$f[i][j]$表示1~i个数可以最多捡几个数使得它们xor为j，由于毒瘤出题人E老板只给了4MB的空间所以滚动数组搞一下
week2
2.26-2.27
新学，主席树入门->维护静态区间第K小
思想大概是新版本用老版本没改过的信息也就是
o=++cnt;
val[o]=val[pre]+1;
lc[o]=lc[pre];rc[o]=rc[pre];
然后再用val[R]-val[L-1]表示这个区间中有几个数来看走左儿子还是右儿子
注意数组大小要开N«5
还有该打&的地方
void insert(int &o,int pre,int l,int r,int k)
由于$-10^9<=a_i<=10^9$所以离散化处理一下
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
b[i]=a[i];
}
sort(b+1,b+n+1);
sz=unique(b+1,b+n+1)-(b+1);
for(int i=1;i<=n;i++)
{
int pos=lower_bound(b+1,b+sz+1,a[i])-b;//lower_bound(b+1,b+n+1,a[i])-b
insert(rt[i],rt[i-1],1,sz,pos);
}
2.27
感觉好像还要比维护静态区间第K小简单一点点
版本复制rt[i]=rt[v]就可以
2.28
trie模板题，在每个单词结尾打上标记
查询时没边，或者到最后没标记就是查不到
一个trie的常见应用，把每个数字从高位到低位拆成31位的二进制数
每个节点左右儿子表示0/1
查异或最大时有不同走不同，否则走相同（可以直接走而不需判断有没有这个节点，因为当在trie中放完一个数后，每一位没0就肯定有1）
当然可以查一个放一个
与上题类似，可以把每个点到根节点的异或值放进去求XOR最大值
因为xor(i~j)=xor(i~root)^xor(j~root)，可证得所有xor情况都会包含进去
week3
3.5
这是一道对抗搜索题
由于n,m比较小，应该可以想到状压
用到了轮廓线状压的思想
还用了map来记忆化搜索
以下是比较关键的部分语句
map<long long,int> f;
int pos[N];
int trans1(long long x)
{
int sum=0;
for(int i=n;i>=1;i--)//for(int i=1;i<=n;i++)
{
pos[i]=x&15;
sum+=pos[i];
x>>=4;
}
return sum&1;
}
long long trans2()
{
long long x=0;//long long x;
for(int i=1;i<=n;i++)
x=x<<4|pos[i];
return x;
}
int dfs(long long x)
{
if(f.count(x))
return f[x];
int opt=trans1(x);
int ans;
if(opt) ans=inf;
else ans=-inf;//int ans=opt?inf:-inf;
for(int i=1;i<=n;i++)
if((i==1&&pos[i]<m)||pos[i]<pos[i-1])
{
pos[i]++;
long long y=trans2();
if(opt) ans=min(ans,dfs(y)-b[i][pos[i]]);
else ans=max(ans,dfs(y)+a[i][pos[i]]);
pos[i]--;////
}
return f[x]=ans;
}
int main()
{
long long mx=0;
for(int i=1;i<=n;i++)
mx=mx<<4|m;
f[mx]=0;
printf("%d\n",dfs(0));
}
3.5-3.6
实现上还是使用主席树
在实现过程中维护了每个点的dep（rank）进行按秩合并
（欸？为什么不能路径压缩？）
代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define mid ((l+r)>>1)
const int N=300005;
int n,m;
int lc[N*24],rc[N*24],fa[N*24],dep[N*24];
int rt[N],cnt;
void build(int &o,int l,int r)
{
o=++cnt;
if(l==r){fa[o]=l;return;}
build(lc[o],l,mid);build(rc[o],mid+1,r);
}
int query(int o,int l,int r,int pos)
{
if(l==r) return o;
if(pos<=mid) return query(lc[o],l,mid,pos);
else return query(rc[o],mid+1,r,pos);
}
int find(int o,int pos)
{
int now=query(o,1,n,pos);
if(fa[now]==pos) return now;
else return find(o,fa[now]);
}
void update(int o,int l,int r,int pos)
{
if(l==r){dep[o]++;return;}
if(pos<=mid) update(lc[o],l,mid,pos);
else update(rc[o],mid+1,r,pos);
}
void merge(int &o,int pre,int l,int r,int son,int f)
{
o=++cnt;
lc[o]=lc[pre];rc[o]=rc[pre];
if(l==r)
{
fa[o]=f;
dep[o]=dep[pre];//
return;
}
if(son<=mid) merge(lc[o],lc[pre],l,mid,son,f);
else merge(rc[o],rc[pre],mid+1,r,son,f);
}
int main()
{
scanf("%d%d",&n,&m);
build(rt[0],1,n);
for(int i=1;i<=m;i++)
{
int opt,x,y;
scanf("%d%d",&opt,&x);
if(opt==1)
{
scanf("%d",&y);
rt[i]=rt[i-1];////
int posx=find(rt[i],x);
int posy=find(rt[i],y);
if(fa[posx]!=fa[posy])
{
if(dep[posx]>dep[posy]) swap(posx,posy);
merge(rt[i],rt[i-1],1,n,fa[posx],fa[posy]);
//merge(rt[i],rt[i-1],1,n,x,fa[posy]);
if(dep[posx]==dep[posy]) update(rt[i],1,n,fa[posy]);
}
}
if(opt==2)
rt[i]=rt[x];
if(opt==3)
{
scanf("%d",&y);
rt[i]=rt[i-1];
int posx=find(rt[i],x);
int posy=find(rt[i],y);
if(fa[posx]==fa[posy]) printf("1\n");
else printf("0\n");
}
}
return 0;
}
3.6
几个世纪前写不出的题。。
主要就是
int Lucas(int n,int m,int p)
{
if(n<p&&m<p) return C(n,m,p);
else return 1ll*Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
trie题，本来想用vector统计每个单词在那几篇短文出现，但是好像只能用bitset？
trie题，我觉得关键在对读入的处理
char c;
int len=0;
while((c=getchar())!=EOF)
{
while(c=='\n') c=getchar();
if((c==' ')||(c==',')||(c=='.'))
{
query(s,len);
len=0;
if(c=='.') memset(b2,0,sizeof(b2));
continue;/////
}
s[len++]=c;
}
3.7
可持久化trie，主要是两个操作
void insert(int &o,int pre,int k)
{
o=++cnt;
int now=o;
for(int i=24;i>=0;i--)
{
int j=(k>>i)&1;
trie[j^1][now]=trie[j^1][pre];
trie[j][now]=++cnt;
now=trie[j][now];
pre=trie[j][pre];
num[now]=num[pre]+1;
}
}
int query(int l,int r,int k)
{
int ans=0;
for(int i=24;i>=0;i--)
{
int j=((k>>i)&1)^1;
if(num[trie[j][r]]-num[trie[j][l]]>0)
{
ans+=(1<<i);
l=trie[j][l];
r=trie[j][r];
}
else
{
l=trie[j^1][l];
r=trie[j^1][r];
}
}
return ans;
}
3.8
dfs序上建可持久化trie，加个LCA（我写的倍增）
week4
3.11-3.12
Splay平衡树
给出一开始学的时候调了很久的代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=100005;
struct Splay
{
int sz,rt;
int son[2][N],fa[N];
int sum[N],cnt[N],v[N];
Splay()
{
sz=rt=0;
memset(v,0,sizeof(v));memset(cnt,0,sizeof(cnt));memset(sum,0,sizeof(sum));
memset(son,0,sizeof(son));memset(fa,0,sizeof(fa));
}
void clear(int x)
{
son[0][x]=son[1][x]=fa[x]=sum[x]=cnt[x]=v[x]=0;
}
void update(int x)
{
if(x)
{
sum[x]=cnt[x];
if(son[0][x]!=0) sum[x]+=sum[son[0][x]];
if(son[1][x]!=0) sum[x]+=sum[son[1][x]];
}
}
void zig(int x)
{
int y=fa[x];
int z=fa[y];
fa[x]=z;
if(z!=0)
{
if(son[0][z]==y) son[0][z]=x;
else son[1][z]=x;
}
son[0][y]=son[1][x];
if(son[1][x]!=0)
fa[son[1][x]]=y;
son[1][x]=y;
fa[y]=x;
update(y);
update(x);
}
void zag(int x)
{
int y=fa[x];
int z=fa[y];
fa[x]=z;
if(z!=0)
{
if(son[0][z]==y) son[0][z]=x;
else son[1][z]=x;
}
son[1][y]=son[0][x];
if(son[0][x]!=0)
fa[son[0][x]]=y;
son[0][x]=y;
fa[y]=x;
update(y);
update(x);
}
void splay(int x)
{
int y=fa[x],z=fa[y];
while(y!=0)
{
if(z==0)
{
if(son[0][y]==x) zig(x);
else zag(x);
}
else
{
if(son[0][y]==x&&son[0][z]==y)
zig(y),zig(x);
else if(son[1][y]==x&&son[1][z]==y)
zag(y),zag(x);
else if(son[1][y]==x&&son[0][z]==y)
zag(x),zig(x);
else if(son[0][y]==x&&son[1][z]==y)
zig(x),zag(x);
}
y=fa[x];z=fa[y];/////////5
}
rt=x;//////2
}
void insert(int k)
{
if(rt==0)
{
sz++;
son[0][sz]=son[1][sz]=fa[sz]=0;
rt=sz;
sum[sz]=cnt[sz]=1;
v[sz]=k;
return;///////////4
}
int x=rt,nxt=0;
while(1)
{
if(v[x]==k)
{
cnt[x]++;
splay(x);
return;
}
if(v[x]>k) nxt=0;
else nxt=1;
if(son[nxt][x]==0)
{
sz++;
fa[sz]=x;
son[nxt][x]=sz;
son[0][sz]=son[1][sz]=0;
sum[sz]=cnt[sz]=1;
v[sz]=k;
splay(sz);
return;//3
}
else x=son[nxt][x];
}
}
int rank(int k)
{
int x=rt,ans=0;
while(1)
{
if(k<v[x]) x=son[0][x];
else
{
if(son[0][x]!=0) ans+=sum[son[0][x]];
if(k==v[x])
{
splay(x);
return ans+1;
}
ans+=cnt[x];
if(son[1][x]!=0) x=son[1][x];
else return 0;
}
}
}
int kth(int k)
{
int x=rt;
while(1)
{
if(son[0][x]!=0&&k<=sum[son[0][x]]) x=son[0][x];
else
{
int tot=cnt[x];
if(son[0][x]!=0) tot+=sum[son[0][x]];
if(k<=tot) return v[x];
k-=tot;x=son[1][x];
}
}
}
int prev(int k)
{
int x=rt,ans=-0x7fffffff;
while(1)
{
//if(son[0][x]==0&&son[1][x]==0) return ans;
if(v[x]>=k&&son[0][x]!=0)
{x=son[0][x];continue;}
else if(v[x]<k)
{
ans=v[x];
if(son[1][x]!=0)
{
x=son[1][x];
continue;
}//1
}
return ans;
}
}
int succ(int k)
{
int x=rt,ans=0x7fffffff;
while(1)
{
//if(son[0][x]==0&&son[1][x]==0) return ans;
if(v[x]<=k&&son[1][x]!=0)
{x=son[1][x];continue;}
else if(v[x]>k)
{
ans=v[x];
if(son[0][x]!=0)
{
x=son[0][x];
continue;
}//1
}
return ans;
}
}
int lmax()
{
int x=son[0][rt];
while(son[1][x]!=0) x=son[1][x];
return x;
}
void del(int k)
{
rank(k);//splay(k)
int x=rt;
if(cnt[rt]>1){cnt[rt]--;update(rt);return;}
if(son[0][rt]==0&&son[1][rt]==0){clear(rt);rt=0;return;}
if(son[0][rt]==0){rt=son[1][rt];fa[rt]=0;clear(x);return;}
if(son[1][rt]==0){rt=son[0][rt];fa[rt]=0;clear(x);return;}
splay(lmax());
son[1][rt]=son[1][x];
fa[son[1][x]]=rt;
clear(x);update(rt);
}
void search(int x)
{
if(x!=0)
{
printf("%d ",v[x]);
search(son[0][x]);
search(son[1][x]);
}
}
}t;
int main()
{
int n,opt,x;
scanf("%d",&n);
while(n--)
{
//t.search(t.rt);printf("\n");
scanf("%d%d",&opt,&x);
if(opt==1) t.insert(x);
if(opt==2) t.del(x);
if(opt==3) printf("%d\n",t.rank(x));
if(opt==4) printf("%d\n",t.kth(x));
if(opt==5) printf("%d\n",t.prev(x));
if(opt==6) printf("%d\n",t.succ(x));
}
return 0;
}
3.12
Splay的一个必备操作-区间翻转
除了区间翻转必须的reverse操作，还简化了一些zigzag之类的操作
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define mid ((l+r)>>1)
using namespace std;
const int N=100005;
const int inf=0x7fffffff;
int n,m;
int a[N];
struct Splay
{
int sz,rt;
int son[2][N],fa[N];
int sum[N],cnt[N],v[N];
int tag[N];
Splay()
{
sz=rt=0;
memset(v,0,sizeof(v));memset(cnt,0,sizeof(cnt));memset(sum,0,sizeof(sum));
memset(son,0,sizeof(son));memset(fa,0,sizeof(fa));
memset(tag,0,sizeof(tag));
}
void update(int x)
{
if(x)
{
sum[x]=cnt[x];
if(son[0][x]) sum[x]+=sum[son[0][x]];
if(son[1][x]) sum[x]+=sum[son[1][x]];
}
}
void pushdown(int x)
{
if(tag[x])
{
tag[son[0][x]]^=1;
tag[son[1][x]]^=1;
swap(son[0][x],son[1][x]);
tag[x]=0;
}
}
void rotate(int x,int op)
{
int y=fa[x],z=fa[y];
pushdown(y);pushdown(x);
fa[x]=z;
if(z)
{
if(son[0][z]==y) son[0][z]=x;
else son[1][z]=x;
}
son[op][y]=son[op^1][x];
if(son[op^1][x]) fa[son[op^1][x]]=y;
son[op^1][x]=y;
fa[y]=x;
update(y);
update(x);
}
void splay(int x,int target)//x become the son of target
{
int y=fa[x],z=fa[y];
while(y!=target)//////
{
//printf("x");
if(z==target)//////
{
if(son[0][y]==x) rotate(x,0);
else rotate(x,1);
}
else
{
if(son[0][y]==x&&son[0][z]==y)
rotate(y,0),rotate(x,0);
else if(son[1][y]==x&&son[1][z]==y)
rotate(y,1),rotate(x,1);
else if(son[1][y]==x&&son[0][z]==y)
rotate(x,1),rotate(x,0);
else if(son[0][y]==x&&son[1][z]==y)
rotate(x,0),rotate(x,1);
}
y=fa[x];z=fa[y];
}
if(target==0) rt=x;
}
int find(int k)
{
int x=rt;
while(1)
{
pushdown(x);
if(son[0][x]&&k<=sum[son[0][x]]) x=son[0][x];
else
{
int tot=cnt[x];
if(son[0][x]) tot+=sum[son[0][x]];
if(k<=tot) return x;//v[x]
k-=tot;x=son[1][x];
}
}
}
void reverse(int x,int y)
{
int l=x-1,r=y+1;
l=find(l);r=find(r);
splay(l,0);splay(r,l);
tag[son[0][son[1][rt]]]^=1;
}
int build(int l,int r,int f)
{
if(l>r) return 0;
int x=++sz;
fa[x]=f;
son[0][x]=son[1][x]=0;
sum[x]=cnt[x]=1;
v[x]=a[mid];
son[0][x]=build(l,mid-1,x);///build(l,mid,x);
son[1][x]=build(mid+1,r,x);
update(x);
return x;
}
void ans(int x)
{
pushdown(x);
if(son[0][x]) ans(son[0][x]);
if(v[x]!=-inf&&v[x]!=inf)
printf("%d ",v[x]);
if(son[1][x]) ans(son[1][x]);
}
}t;
int main()
{
scanf("%d%d",&n,&m);
a[1]=-inf;a[n+2]=inf;
for(int i=1;i<=n;i++) a[i+1]=i;
int x,y;
t.rt=t.build(1,n+2,0);
while(m--)
{
scanf("%d%d",&x,&y);
t.reverse(x+1,y+1);
}
t.ans(t.rt);
return 0;
}
3.15
验一下给高一新生出的题
3.16
验一下给高一新生出的题
3.17
验一下给高一新生出的题
week5
3.23
验一下给高一新生出的题
这题是Ebola搞的
我觉得是一道好题
我想到的写法是：
分析题意可知可以贪心连接，也就是对于一个关键点，如果它的子树中也有一个关键点，它就和这个关键点连
所以我想在dfs回溯时上传子树中有无关键点，如果有，到这个点的距离是多少（为什么不用记录几个？因为有2个以上就直接连并加进答案里）
具体实现还有一些细节
而Ebola大佬的方法是：
首先可以证明每条边对答案最多一次贡献
那么对于一条边，它有贡献的话一定是它的两个端点的子树中都有奇数个关键点
week6
3.27
大概开始停课了
P1201 [USACO1.1]贪婪的送礼者Greedy Gift Givers
3.28
3.29
3.30
3.31
week7
4.1
4.2
4.3
4.5
4.6
4.7
week8
4.8
4.9
4.10
P1250 种树区间约束写法
4.11
4.12
P1250 种树贪心写法
4.13
4.14
P3038 [USACO11DEC]牧草种植Grass Planting
week9
4.15
week10
4.27
这题主要思路是修改所有点的权值+-k等同于记录某个相对值-+k
这题我犯了一个错误，在平衡树中找到权值>=k的权值最小的点的找法应该是在当前节点>=k时，无论右儿子是不是>=k，都要走右儿子，因为有可能在右儿子的左儿子里面找到>=k的更优解
错误
void del(int k)
{
if(findmax()<k)
{
leave+=sum[rt];
clear();
return;
}
int now=rt;
while(1)
{
//cout<<val[now]<<endl;
if(val[now]<k)
{
if(son[0][now]) now=son[0][now];
else return;//qwq
}
else
{
if(son[1][now]&&val[son[1][now]]>=k) now=son[1][now];
else break;
}
}
//cout<<k<<' '<<val[now]<<endl;
splay(now,0);
if(son[1][rt]) leave+=sum[son[1][rt]];
son[1][rt]=0;
update(rt);
}
正确
void del(int k)
{
if(findmax()<k)
{
leave+=sum[rt];
clear();
return;
}
int now=rt,close=now;
while(1)
{
//cout<<val[now]<<endl;
if(val[now]>=k) close=now;
if(val[now]<k)
{
if(son[0][now]) now=son[0][now];
else break;//return??qwq???
}
else
{
if(son[1][now]) now=son[1][now];
else break;
}
}
//cout<<k<<' '<<val[close]<<endl;
splay(close,0);
if(son[1][rt]) leave+=sum[son[1][rt]];
son[1][rt]=0;
update(rt);
}