T1 斐波那契(fibonacci)
要死了。
一开始看这题，然后有点懵，一开始肯定想到的是$LCA$，但是又发现这图建不出图来，然后就开始想着卡测试点了。
测试点，当然是先找特殊规律啊。
先考虑特质1，根据提示，很容易发现这其实就是一个裸的斐波那契，然后又手玩了一代生命，然后发现数列全部分布在一条链上，由此得出结论：他们的$LCA$只可能是他们两个之间某一个编号较小点或者1。然后我们就可以快乐地qj测试点了。
然后暴力找了一下特质1，稳了40，就开始玩特质2。
特质2其实更简单了，既然他们之间差1或0，他们之间的祖先节点也只有两种情况：一是1，二是本身，特判一下就行了。
然后，我就放弃了。对！我就放弃了。
最后当我知道AC代码就900多B时，我的心在滴血。
正解其实蛮简单的，也是一个规律。
我们可以发现，一个节点与它父节点的差值，刚好比这个节点小的第一个斐波那契数，然后，嘿嘿嘿……
我们从最大的斐波那契开始枚举，只要这个点的点值大于我枚举的数，我就减去得到父节点，这样两个点同时进行操作，会得到$0 or x==y$，如果最后是0，说明他们的LCA就是1，反之，不要怀疑，LCA就是得到的数（$x or y$）。
至于为什么他们一定会在同一层一起向上跑呢，因为那个生的比较早的那个点是肯定小于晚点的，且他们之间一定存在一个斐波那契，一个循环，我们最后得到的，一定是两个点在同一代同时向上跑。
其实跟倍增LCA挺像的。
小弟不才。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #define int long long 5 #define HZOI using namespace std 6 HZOI; 7 const int MAXN=4e5+5; 8 int m; 9 int a[MAXN],b[MAXN],f[MAXN],ans[MAXN]; 10 inline int read(); 11 signed main() 12 { 13 m=read(); 14 f[0]=f[1]=1; 15 for (int i=2; i<=63; ++i) f[i]=f[i-1]+f[i-2]; 16 int flag1=0,flag2=0; 17 for (int i=1; i<=m; ++i) 18 { 19 a[i]=read(),b[i]=read(); 20 if (abs(a[i]-b[i])>1) flag1=1; 21 for (int j=1,aa=0,bb=0; j<=63; ++j) 22 { 23 if (a[i]==f[j]) aa=j; 24 if (b[i]==f[j]) bb=j; 25 if (!aa or !bb ) flag2=1; 26 if (aa and bb) 27 { 28 if ((aa%2 and bb%2) or (!(aa%2) and !(bb%2))) 29 ans[i]=min(f[aa],f[bb]); 30 else ans[i]=1; 31 break; 32 } 33 } 34 } 35 if (!flag1) 36 { 37 for (int i=1; i<=m; ++i) 38 if (a[i]==b[i]) printf("%lld ",a[i]); 39 else puts("1"); 40 return 0; 41 } 42 if (!flag2) 43 { 44 for (int i=1; i<=m; ++i) 45 printf("%lld ",ans[i]); 46 return 0; 47 } 48 for (int i=1; i<=m; ++i) 49 { 50 for (int j=63; j and (a[i]^b[i]); --j) 51 { 52 a[i]-=a[i]>f[j]?f[j]:0; 53 b[i]-=b[i]>f[j]?f[j]:0; 54 } 55 if (!a[i] and !b[i]) printf("1 "); 56 else printf("%lld ",a[i]); 57 } 58 } 59 inline int read() 60 { 61 int nn=0; char ch=getchar(); 62 while (ch<'0' or ch>'9') ch=getchar(); 63 while (ch>='0' and ch<='9') nn=(nn<<3)+(nn<<1)+(ch^48),ch=getchar(); 64 return nn; 65 }
T2 数颜色
这题，考试把我弄懵了，彻底暴露智商。
一看题，线段树，再看题，线段树+权值线段树。
然后我就在$TLE$的道路上越走越远。
其实这题没多难，就是一个权值线段树。
说起来倒是挺容易，不过目前的我想还是想不到的。
权值线段树，以颜色为下标，在n个位置上插入，然后就很显然了。
询问直接询问这个颜色的树上的区间和。
修改暴力改，在原来的颜色&位置上-1，在新的颜色&位置上+1。
解决了。
考试把握搞懵了。
还有，能不开$long long$尽量别开，很慢很慢很慢很慢很慢。
小弟不才。
1 #include<cstdio> 2 #include<algorithm> 3 #include<ctime> 4 #include<cstdlib> 5 #define HZOI using namespace std 6 HZOI; 7 int const L=1<<20|1; 8 char buf[L],*S,*T; 9 #define getchar() ((S==T && (T=(S=buf)+fread(buf,1,L,stdin),S==T))?EOF:*S++) 10 const int MAXN=5e6+5; 11 struct node{ 12 int lc,rc,num; 13 }tr[MAXN<<4]; 14 int n,m,cnt; 15 int a[MAXN],b[MAXN]; 16 void Change(int &,int ,int ,int ,int ); 17 int Query(int ,int ,int ,int ,int ); 18 inline int max(int a,int b) {return a>b?a:b;} 19 inline int read(); 20 signed main() 21 { 22 // freopen("test.in","r",stdin); 23 // freopen("T2.out","w",stdout); 24 n=read(),m=read(); 25 for (int i=1; i<=n; ++i) 26 a[i]=read(),cnt=max(cnt,a[i]),b[a[i]]=1; 27 for (int i=1; i<=n; ++i) 28 Change(a[i],1,n,i,1); 29 for (int i=1,opt,x,y,z; i<=m; ++i) 30 { 31 opt=read(); 32 if (opt^2) 33 { 34 x=read(),y=read(),z=read(); 35 if (!b[z]) {puts("0"); continue;} 36 printf("%d ",Query(z,1,n,x,y)); 37 } 38 else 39 { 40 x=read(); 41 if (a[x]==a[x+1] or x==n) continue; 42 Change(a[x],1,n,x,-1); 43 Change(a[x],1,n,x+1,1); 44 Change(a[x+1],1,n,x+1,-1); 45 Change(a[x+1],1,n,x,1); 46 a[x]^=a[x+1]^=a[x]^=a[x+1]; 47 } 48 } 49 } 50 int Query(int k,int l,int r,int L,int R) 51 { 52 if (l>=L and r<=R) 53 return tr[k].num; 54 int mid=l+r>>1,ans=0; 55 if (tr[k].lc and L<=mid and tr[tr[k].lc].num) ans+=Query(tr[k].lc,l,mid,L,R); 56 if (tr[k].rc and R>mid and tr[tr[k].rc].num) ans+=Query(tr[k].rc,mid+1,r,L,R); 57 return ans; 58 } 59 void Change(int &k,int l,int r,int pos,int data) 60 { 61 if (!k) k=++cnt; 62 if (l==r) { tr[k].num+=data; return ; } 63 int mid=l+r>>1; 64 if (pos<=mid) Change(tr[k].lc,l,mid,pos,data); 65 else Change(tr[k].rc,mid+1,r,pos,data); 66 tr[k].num=tr[tr[k].lc].num+tr[tr[k].rc].num; 67 } 68 inline int read() 69 { 70 int nn=0; char ch=getchar(); 71 while (ch<'0' or ch>'9') ch=getchar(); 72 while (ch>='0' and ch<='9') nn=(nn<<3)+(nn<<1)+(ch^48),ch=getchar(); 73 return nn; 74 }
T3 分组
这这这，考试想了半小时，果然没啥用。
只能qj。
直接说题解吧。
首先，我们得先搞出来k==1的情况，这种情况下，很显然是一个dp，找最长的没有加和为平方数的串。
数据范围不算大，所以我们可以考虑用桶，用来维护这个值在已有序列中有没有出现过。
这还是挺好维护的，我就不再缀述，只是注意一点，清空的时候要有多少清多少，千万不要$memset$，时间复杂度太高，所以我们要记录一下序列的起点，从起点开始把桶中元素清空。
注意要保证字典序最小。什么意思呢？就是第一个（包括以后）断点尽量靠前，这就是一个贪心了，我们从最后开始贪心枚举，就可以保证答案一定是最优解。
最重要的一点，我们不能一个个的扫前面的序列，考虑减小复杂度。在题中所给数据范围中，我们可是算出最大的开方数不过512。暴力打一个平方表，可以算出当前值与谁的和是平方数。$x^2-a_i=a_j$，结合前面的桶，就可是快乐地拿到40。
但是呢，我们的目标可不是40分，当然是AC了。我们观察k==2时图的性质，若给非法的两个数连边，那他们一定不可以出现奇环。题中所述，小组必须连续，团体可以不连续，那么只要排除奇环的影响，我们就可以保证特定抽取组中元素而他们之间合法（奇环无论怎么分都会有相连的两个点分到一组）。根据这个性质，我们用到了二分图的判定。最常用的方法是以DFS为框架的染色法，原理很简单，实现起来也不难，但是要注意一下循环内容。
若内层循环依然是40分做法显然常数会很大，我们使用开根号的方式判断它是不是平方数，预处理一下$1e18$的所有数的开根，然后暴力枚举经过的位置，复杂度$O(n^2)$。
还有一点，染色时最好使用2、3当作颜色，不要用1、2或0、1，前者时间慢，后者容易错。
小弟不才。
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<iostream> 5 #define HZOI using namespace std 6 HZOI; 7 const int L=1<<20|1; 8 char buf[L],*S,*T; 9 #define getchar() ((S==T&&(T=(S=buf)+fread(buf,1,L,stdin),S==T))?EOF:*S++) 10 int fang[531]={0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961,1024,1089,1156,1225,1296,1369,1444,1521,1600,1681,1764,1849,1936,2025,2116,2209,2304,2401,2500,2601,2704,2809,2916,3025,3136,3249,3364,3481,3600,3721,3844,3969,4096,4225,4356,4489,4624,4761,4900,5041,5184,5329,5476,5625,5776,5929,6084,6241,6400,6561,6724,6889,7056,7225,7396,7569,7744,7921,8100,8281,8464,8649,8836,9025,9216,9409,9604,9801,10000,10201,10404,10609,10816,11025,11236,11449,11664,11881,12100,12321,12544,12769,12996,13225,13456,13689,13924,14161,14400,14641,14884,15129,15376,15625,15876,16129,16384,16641,16900,17161,17424,17689,17956,18225,18496,18769,19044,19321,19600,19881,20164,20449,20736,21025,21316,21609,21904,22201,22500,22801,23104,23409,23716,24025,24336,24649,24964,25281,25600,25921,26244,26569,26896,27225,27556,27889,28224,28561,28900,29241,29584,29929,30276,30625,30976,31329,31684,32041,32400,32761,33124,33489,33856,34225,34596,34969,35344,35721,36100,36481,36864,37249,37636,38025,38416,38809,39204,39601,40000,40401,40804,41209,41616,42025,42436,42849,43264,43681,44100,44521,44944,45369,45796,46225,46656,47089,47524,47961,48400,48841,49284,49729,50176,50625,51076,51529,51984,52441,52900,53361,53824,54289,54756,55225,55696,56169,56644,57121,57600,58081,58564,59049,59536,60025,60516,61009,61504,62001,62500,63001,63504,64009,64516,65025,65536,66049,66564,67081,67600,68121,68644,69169,69696,70225,70756,71289,71824,72361,72900,73441,73984,74529,75076,75625,76176,76729,77284,77841,78400,78961,79524,80089,80656,81225,81796,82369,82944,83521,84100,84681,85264,85849,86436,87025,87616,88209,88804,89401,90000,90601,91204,91809,92416,93025,93636,94249,94864,95481,96100,96721,97344,97969,98596,99225,99856,100489,101124,101761,102400,103041,103684,104329,104976,105625,106276,106929,107584,108241,108900,109561,110224,110889,111556,112225,112896,113569,114244,114921,115600,116281,116964,117649,118336,119025,119716,120409,121104,121801,122500,123201,123904,124609,125316,126025,126736,127449,128164,128881,129600,130321,131044,131769,132496,133225,133956,134689,135424,136161,136900,137641,138384,139129,139876,140625,141376,142129,142884,143641,144400,145161,145924,146689,147456,148225,148996,149769,150544,151321,152100,152881,153664,154449,155236,156025,156816,157609,158404,159201,160000,160801,161604,162409,163216,164025,164836,165649,166464,167281,168100,168921,169744,170569,171396,172225,173056,173889,174724,175561,176400,177241,178084,178929,179776,180625,181476,182329,183184,184041,184900,185761,186624,187489,188356,189225,190096,190969,191844,192721,193600,194481,195364,196249,197136,198025,198916,199809,200704,201601,202500,203401,204304,205209,206116,207025,207936,208849,209764,210681,211600,212521,213444,214369,215296,216225,217156,218089,219024,219961,220900,221841,222784,223729,224676,225625,226576,227529,228484,229441,230400,231361,232324,233289,234256,235225,236196,237169,238144,239121,240100,241081,242064,243049,244036,245025,246016,247009,248004,249001,250000,251001,252004,253009,254016,255025,256036,257049,258064,259081,260100,261121,262144,263169,264196,265225,266256,267289,268324,269361,270400,271441,272484,273529,274576,275625,276676,277729,278784,279841,280900}; 11 int n,K,last,pos; 12 int a[1<<20],b[1<<20],ans[1<<20],chai[1<<20]; 13 int mm,tt,first[1<<20],vv[1<<24],nx[1<<24],col[1<<20]; 14 bool Dfs(int ,int ); 15 bool Judge(int ,int ); 16 inline void Add(int ,int ); 17 inline int read(); 18 int main() 19 { 20 // freopen("test.in","r",stdin); 21 // freopen("T3.out","w",stdout); 22 n=read(); K=read(); 23 for (int i=1; i<=n; ++i) a[i]=read(); 24 last=n; 25 if (K^2) 26 for (int i=n; i; --i) 27 { 28 for (int j=1; j<=512; ++j) 29 if (fang[j]>a[i] and b[fang[j]-a[i]]) 30 { 31 ans[++pos]=i; 32 for (int k=last; k>=i; --k) b[a[k]]=0; 33 last=i; 34 break; 35 } 36 b[a[i]]=1; 37 } 38 else 39 { 40 for (int i=0; i<=(1<<18); ++i) chai[i]=floor(sqrt(i)); 41 for (int i=n; i; --i) 42 { 43 int flag=0; 44 for (int j=last; j>i; --j) 45 if (Judge(a[i],a[j])) 46 Add(i,j); 47 if (first[i] and !Dfs(i,2)) 48 { 49 for (int j=last; j>=i; --j) first[j]=0; 50 ans[++pos]=last=i; 51 } 52 for (int j=last; j>=i; --j) col[j]=0; 53 } 54 } 55 printf("%d ",pos+1); 56 for (int i=pos; i; --i) printf("%d ",ans[i]); 57 return 0; 58 } 59 bool Dfs(int k,int color) 60 { 61 col[k]=color; 62 for (int i=first[k]; i; i=nx[i]) 63 { 64 int ver=vv[i]; 65 if (col[k]==col[ver]) {return false;} 66 if (!col[ver] and !Dfs(ver,color^1)) {return false;} 67 } 68 return true; 69 } 70 bool Judge(int x,int y) 71 { 72 int ooo=x+y; 73 return chai[ooo]*chai[ooo]==ooo; 74 } 75 inline void Add(int u,int v) 76 { 77 vv[++tt]=v; nx[tt]=first[u]; first[u]=tt; 78 vv[++tt]=u; nx[tt]=first[v]; first[v]=tt; 79 } 80 inline int read() 81 { 82 int nn=0; char ch=getchar(); 83 while (ch<'0' or ch>'9') { ch=getchar();} 84 while (ch>='0' and ch<='9') nn=(nn<<3)+(nn<<1)+(ch^48),ch=getchar(); 85 return nn; 86 }