估分：60+100+60=220
实际：80+50+0=130
打挂了110分？？！(ノ=Д=)ノ┻━┻
还我Rank3!!!
所以小G作为铁杆歌迷，也计划带着小Y去看周杰伦的演唱会。 演唱会当然要圈出一个空地，然后才能布置道具。 演唱会的第一站，公司临时跟当地的消防局借了n个栏杆，打算用这n个栏杆围出一个矩形。而麻烦的是，这些栏杆有长有短，这就给围场地带来了一些难度。 所以公司聘请你来写一个程序，计算用这n个栏杆做多围出面积多大的矩形。 （注：必须要刚好围成一个矩形，即不能出现多余的边长，且不能切断栏杆，但所给栏杆不一定要全部用上）
一开始打了一个错误的暴力：枚举边长再\(4*2^n\)把边组合起来
后来打了\(5^n\)的暴力才发现是错的
但是在随机数据下第一种方法有不错的正确率
于是把两种做法结合起来就有了80pts的好成绩
考虑状压
设f[s]表示选了s这个集合，这个集合里的栏杆能分成长度相等的两组（每个都必须选）
\(2^n\)枚举，再背包一下就好了
然后\(3^n\)枚举两个交集为空的集合，取最大值就好了
为了让游玩更有情趣，人们在池塘的中央建设了几座石墩和石桥，每座石桥连接着两座石墩，且每两座石墩之间至多只有一座石桥。这个景点造好之后一直没敢对外开放，原因是池塘里有不少危险的食人鱼。 豆豆先生酷爱冒险，他一听说这个消息，立马赶到了池塘，想做第一个在桥上旅游的人。虽说豆豆爱冒险，但也不敢拿自己的性命开玩笑，于是他开始了仔细的实地勘察，并得到了一些惊人的结论：食人鱼的行进路线有周期性，这个周期只可能是2，3或者4个单位时间。每个单位时间里，食人鱼可以从一个石墩游到另一个石墩。每到一个石墩，如果上面有人它就会实施攻击，否则继续它的周期运动。如果没有到石墩，它是不会攻击人的。 借助先进的仪器，豆豆很快就摸清了所有食人鱼的运动规律，他要开始设计自己的行动路线了。每个单位时间里，他只可以沿着石桥从一个石墩走到另一个石墩，而不可以停在某座石墩上不动，因为站着不动还会有其它危险。如果豆豆和某条食人鱼在同一时刻到达了某座石墩，就会遭到食人鱼的袭击，他当然不希望发生这样的事情。 现在豆豆已经选好了两座石墩Start和End，他想从Start出发，经过K个单位时间后恰好站在石墩End上。假设石墩可以重复经过（包括Start和End），他想请你帮忙算算，这样的路线共有多少种（当然不能遭到食人鱼的攻击）。
1 ≤ N ≤ 50 1 ≤ K ≤ 2,000,000,000 1 ≤ NFish ≤ 20
一眼题，显然矩乘
因为转移矩阵是变化的，就先处理出每12个单位时间的转移矩阵，再快速幂就好了
我数组开小了！！！
一条项链包含N 个珠子，每个珠子的颜色是1, 2, …, c 中的一种。项链被固定在一个平板上，平板的某个位置被标记位置1，按顺时针方向其他位置被记为2,3,…,N。
你将要编写的软件系统应支持如下命令： 1.R k(0 < K < N) 意为Rotate k。将项链在平板上顺时针旋转k 个位置, 即原来处于位置1 的珠子将转至位置k+1，处于位置2 的珠子将转至位置k+2，依次类推。
2.F 意为Flip。将平板沿着给定的对称轴翻转，原来处于位置1 的珠子不动，位置2 上的珠子与位置N 上的珠子互换，位置3 上的珠子与位置N-1 上的珠子互换，依次类推。
3.S i j(1≤I,j≤N) 意为Swap i , j。将位置i 上的珠子与位置j 上的珠子互换。
4.P I j x(1≤I,j≤N,x≤c) 意为Paint i , j , x。将位置i 沿顺时针方向到位置j 的一段染为颜色x。
5.C 意为Count。查询当前的项链由多少个“部分”组成，我们称项链中颜色相同的一段为一个“部分”。
6.CS i j(1≤I,j≤N) 意为CountSegment i , j。查询从位置i沿顺时针方向到位置j 的一段中有多少个部分组成。
1. 对于60%的数据，N ≤ 1 000，Q ≤ 1 000； 2. 对于100%的数据，N ≤ 500 000，Q ≤ 500 000，c ≤ 1 000。
一眼望过去：不就是splay嘛，前几天刚学
然而没时间打了
暴力打挂了。。。
gg
正解好像是线段树？
我不管我就要打splay!!
3537ms，跑最慢…
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct qy { int ch[2],fa,size,left,right,sum,sam,rev,col; }; int n,i,j,c,q,x,y,l1,r1,l2,r2,l,r,s,tot,ans,root,k,kk,gg; int a[500005],list[500005]; char str[10]; qy tree[500005]; int get(int x) { if (tree[tree[x].fa].ch[0]==x) return 0; else return 1; } void change_rev(int x) { swap(tree[x].ch[0],tree[x].ch[1]); swap(tree[x].left,tree[x].right); tree[x].rev^=1; } void change_sam(int x,int col) { tree[x].sum=1; tree[x].left=col; tree[x].right=col; tree[x].col=col; tree[x].sam=col; } void update(int x) { tree[x].size=tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+1; if (tree[tree[x].ch[0]].left) tree[x].left=tree[tree[x].ch[0]].left; else tree[x].left=tree[x].col; if (tree[tree[x].ch[1]].right) tree[x].right=tree[tree[x].ch[1]].right; else tree[x].right=tree[x].col; if (tree[x].col) tree[x].sum=1; else tree[x].sum=0; if (tree[x].ch[0]) tree[x].sum+=tree[tree[x].ch[0]].sum; if (tree[x].ch[1]) tree[x].sum+=tree[tree[x].ch[1]].sum; // tree[x].sum=tree[tree[x].ch[0]].sum+tree[tree[x].ch[1]].sum+1; if ((tree[x].ch[0])&&(tree[tree[x].ch[0]].right==tree[x].col)) tree[x].sum--; if ((tree[x].ch[1])&&(tree[tree[x].ch[1]].left==tree[x].col)) tree[x].sum--; } void pushdown(int x) { if (tree[x].rev) { if (tree[x].ch[0]) change_rev(tree[x].ch[0]); if (tree[x].ch[1]) change_rev(tree[x].ch[1]); tree[x].rev=0; } if (tree[x].sam) { if (tree[x].ch[0]) change_sam(tree[x].ch[0],tree[x].sam); if (tree[x].ch[1]) change_sam(tree[x].ch[1],tree[x].sam); tree[x].sam=0; } } void rotate(int x) { int y=tree[x].fa; int z=tree[y].fa; int k=get(x); int kk=get(y); if (z) tree[z].ch[kk]=x; tree[x].fa=z; tree[y].ch[k]=tree[x].ch[k^1]; if (tree[x].ch[k^1]) tree[tree[x].ch[k^1]].fa=y; tree[x].ch[k^1]=y; tree[y].fa=x; update(y); update(x); } void remove(int x,int y) { list[0]=0; while (x!=y) { list[++list[0]]=x; x=tree[x].fa; } for (int i=list[0];i>=1;i--) pushdown(list[i]); } void splay(int x,int goal) { remove(x,goal); while (tree[x].fa!=goal) { int y=tree[x].fa; if (tree[y].fa!=goal) { if (get(x)==get(y)) rotate(y); else rotate(x); } rotate(x); } if (goal==0) root=x; } int build(int l,int r,int fa) { if (l>r) return 0; int mid=(l+r)/2; int x=++tot; tree[x].fa=fa; tree[x].col=a[mid]; tree[x].sam=tree[x].rev=0; tree[x].ch[0]=build(l,mid-1,x); tree[x].ch[1]=build(mid+1,r,x); update(x); return x; } void find(int s) { int x=root; while (s!=0) { pushdown(x); if (tree[tree[x].ch[0]].size+1<s) { s-=tree[tree[x].ch[0]].size+1; x=tree[x].ch[1]; } else { if (tree[tree[x].ch[0]].size+1==s) s-=tree[tree[x].ch[0]].size+1; else x=tree[x].ch[0]; } } splay(x,0); } void Rotate(int x) { int k,kk,g; find(n-x+1); k=root; find(n+2); kk=root; splay(k,kk); g=tree[k].ch[1]; tree[k].ch[1]=0; update(k);update(kk); // splay(k,0); find(1); k=root; find(2); kk=root; splay(k,kk); tree[k].ch[1]=g; // update(k);update(kk); splay(k,0); } void Flip() { int k,kk; find(2); k=root; find(n+2); kk=root; splay(k,kk); change_rev(tree[k].ch[1]); } void Swap(int x,int y) { int k,kk; find(x+1); k=root; find(y+1); kk=root; swap(tree[k].col,tree[kk].col); splay(k,0); splay(kk,0); } void Paint(int x,int y,int col) { int k,kk; find(x); k=root; find(y+2); kk=root; splay(k,kk); change_sam(tree[k].ch[1],col); update(k); update(kk); } int Count() { int k,kk,ans; find(1); k=root; find(n+2); kk=root; splay(k,kk); ans=tree[tree[k].ch[1]].sum; find(2); k=root; find(n+1); kk=root; if ((tree[k].col==tree[kk].col)&&(ans>1)) ans--; return ans; } int CountSegment(int l,int r) { find(l); k=root; find(r+2); kk=root; splay(k,kk); return tree[tree[k].ch[1]].sum; } int main() { freopen("read.in","r",stdin); freopen("write.out","w",stdout); scanf("%d%d",&n,&c); for (i=1;i<=n;i++) scanf("%d",&a[i]); root=build(0,n+1,0); scanf("%d",&q); while (q--) { memset(str,0,sizeof(str)); scanf("%s",str+1); if (str[1]=='R') { scanf("%d",&x); Rotate(x); } if (str[1]=='F') { Flip(); } if (str[1]=='S') { scanf("%d%d",&x,&y); Swap(x,y); } if (str[1]=='P') { scanf("%d%d%d",&l,&r,&x); if (l<=r) Paint(l,r,x); else { Paint(l,n,x); Paint(1,r,x); } } if ((str[1]=='C')&&(str[2]==0)) { printf("%d\n",Count()); } if ((str[1]=='C')&&(str[2]=='S')) { scanf("%d%d",&l,&r); if (l<=r) { ans=CountSegment(l,r); } else { ans=CountSegment(l,n)+CountSegment(1,r); find(n+1); k=root; find(2); kk=root; if (tree[k].col==tree[kk].col) ans--; } printf("%d\n",ans); } } }转载于:https://www.cnblogs.com/leason-lyx/p/11147281.html
相关资源：centos7.6搭建zabbix总结-20200331.docx