Ⅰ. 自描述序列
问题描述：
序列 1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,... 看似毫无规律，但若我们将相邻的数字合并 ： 1,22,11,2,1,22,1,22,11,2,11,22,1,... 再将每组替换为组内数字的个数，可以得到： 1,2,2,1,1,2,1,2,2,1,2,2,1,... 可以发现，这就是原序列，因此，这个序列可以无限生成下去。 现在你需要求这个序列的第 n 项（下标从 1 开始计算）。
输入格式：
本题有多组测试数据，第一行输入数据组数 T ，每组数据仅包含一行一个正整数 n 。
输出格式：
对每组数据，输出该序列的第 n 项。
数据范围：
1≤T≤10 , 1≤n≤10e7
这个就是一道模拟题，没有什么可以多说的。
Code：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int n,head,tail,lst,A[15],f[10000005];
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,65536,stdin),p1==p2)?EOF:*p1++)
char buf[65536],*p1,*p2;
inline int read()
{
char ch;int x(0);
while((ch=gc)<48);
do x=x*10+ch-48;while((ch=gc)>=48);
return x;
}
int main()
{
n=read(),f[1]=1,f[2]=f[3]=head=lst=2,tail=3;
for(register int i=1;i<=n;++i) A[i]=read(),A[0]=max(A[0],A[i]);
while(tail<A[0])
{
int k=f[++head];if(lst&1) lst=2;else lst=1;
for(register int i=1;i<=k;++i) f[++tail]=lst;
}
for(register int i=1;i<=n;++i) printf("%d\n",f[A[i]]);
return 0;
}
自描述序列
Ⅱ. 极限
问题描述：
输入格式：
第一行输入 1 个整数 n 。 第二行输入 n 个整数，f(1)、f(2)、...、f(n) 。
输出格式：
输出 n 个数 g(1)、g(2)、...、g(n) ，每个数一行。 可以证明在题目条件下，答案是有限的数值，且都能写成 p/q 的形式，其中 gcd(p,q)=1。因此输出格式为 p/q。
数据范围：
1≤n≤10e5 , 1≤f(i)≤n
首先，很显然，进行多次操作后 f( ) 是肯定会成周期的，即 成环，但会存在不在环上的点，由于 k 趋于无穷，所以不在环上的点形成的链是可以忽略其贡献的，所以直接搜就可以了。
离谱的是，在考试时，搜索居然没有记忆化，等于打了个 n2 的纯暴力！
离谱的是，考完之后，听见同学说是基环树，才恍然发现这不基环树吗？
离谱的是，考前一天，
基环树看这里
Code：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int n,lst,tot,A[100005],B[100005],Mark[100005];
long long C[100005],gcd,a,b,Ans1[100005],Ans2[100005];
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,65536,stdin),p1==p2)?EOF:*p1++)
char buf[65536],*p1,*p2;
inline int read()
{
char ch;int x(0);
while((ch=gc)<48);
do x=x*10+ch-48;while((ch=gc)>=48);
return x;
}
inline long long Gcd(long long x,long long y)
{
long long z=x%y;
if(!z) return y;
return Gcd(y,z);
}
int main()
{
n=read();
for(register int i=1;i<=n;++i) A[i]=read();
for(register int i=1,cnt;i<=n;++i)
{
if(Mark[i]) {printf("%lld/%lld\n",Ans1[Mark[i]],Ans2[Mark[i]]);continue;}
C[1]=lst=A[i],B[lst]=cnt=1,++tot;
while(1)
{
lst=A[lst];
if(Mark[lst]==tot) {a=C[cnt]-C[B[lst]-1],b=cnt-B[lst]+1,gcd=Gcd(a,b),Ans1[tot]=a/gcd,Ans2[tot]=b/gcd;;break;}
if(Mark[lst]) {Ans1[tot]=Ans1[Mark[lst]],Ans2[tot]=Ans2[Mark[lst]];break;}
++cnt,B[lst]=cnt,C[cnt]=C[cnt-1]+lst,Mark[lst]=tot;
}
printf("%lld/%lld\n",Ans1[tot],Ans2[tot]);
}
return 0;
}
极限
Ⅲ. 最大三角形
问题描述：
果果有一些木棍，长度分别为 a1,a2,...,an。 果果想知道，仅使用 al,al+1,...,ar 这些木棍，每根木棍只能使用一次，能够组成的三角形中周长最长是多少。
输入格式：
第一行输入 2 个整数 n、q。 第二行输入 n 个整数 a1,a2,...,an 。 接下来 q 行，每行有两个整数 li、ri 。
输出格式：
对每组询问，输出最大的周长，一行一个。如果无法组成三角形，输出 −1 。
数据范围：
1≤n、q≤10e5 , 1≤ai≤10e9 , 1≤li≤ri≤n
对于三角形大家一定不陌生，小学生一定都知道：三角形 任意两边之和大于第三边，任意两边之差小于第三边。
当然，其实三角形只需满足：最大边小于另两边之和。
那么，如果最大边确定，要构成三角形的话，我们一定会选择剩下的边中最大的两条，且同时满足了周长最大。
由此观之，对于一个区间，我们从最大的开始判断，随后，次大等等。
区间 k 大，这个明显主席树了。
最后发现一下复杂度：一段区间无法构成三角形，最长的区间一定是斐波那契数列，在该数据范围下最多 44 个，即每次询问在主席树中最大查询 44 次 ，所以是 O( 44 * n * log(n) )，并且，44次是远远跑不满的。
Code：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int n,m,k,tot,cnt,A[100005],B[100005];
struct node {int L,R,Sum,Id;}Tr[2000005];
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,65536,stdin),p1==p2)?EOF:*p1++)
char buf[65536],*p1,*p2;
inline int read()
{
char ch;int x(0);
while((ch=gc)<48);
do x=x*10+ch-48;while((ch=gc)>=48);
return x;
}
inline void Update(int x,int &y,int L,int R,int pos)
{
y=++cnt,Tr[y].L=Tr[x].L,Tr[y].R=Tr[x].R,Tr[y].Sum=Tr[x].Sum+1;
if(L==R) return;
int M=(L+R)>>1;
if(pos<=M) Update(Tr[x].L,Tr[y].L,L,M,pos);
else Update(Tr[x].R,Tr[y].R,M+1,R,pos);
}
inline int Get(int x,int y,int L,int R)
{
if(L==R) return B[L];
int M=(L+R)>>1,Tmp=Tr[Tr[y].L].Sum-Tr[Tr[x].L].Sum;
if(Tmp>=k) return Get(Tr[x].L,Tr[y].L,L,M);
k-=Tmp;return Get(Tr[x].R,Tr[y].R,M+1,R);
}
int main()
{
n=read(),m=read();
for(register int i=1;i<=n;++i) A[i]=B[i]=read();
sort(B+1,B+n+1),tot=unique(B+1,B+n+1)-(B+1);
for(register int i=1;i<=n;++i) A[i]=lower_bound(B+1,B+tot+1,A[i])-B;
for(register int i=1;i<=n;++i) Update(Tr[i-1].Id,Tr[i].Id,1,tot,A[i]);
for(register int i=1,kk,x,y;i<=m;++i)
{
x=read(),y=read();if(y-x<2) {printf("-1\n");continue;}
int t1,t2,t3,t4(2);
k=y-x+1,t1=Get(Tr[x-1].Id,Tr[y].Id,1,tot),
k=y-x,t2=Get(Tr[x-1].Id,Tr[y].Id,1,tot),
k=kk=y-x-1,t3=Get(Tr[x-1].Id,Tr[y].Id,1,tot);
while(t3+t2<=t1&&kk) t1=t2,t2=t3,kk=k=y-x-t4,++t4,t3=Get(Tr[x-1].Id,Tr[y].Id,1,tot);
if(!kk) printf("-1\n");
else printf("%lld\n",1LL*t3+t2+t1);
}
return 0;
}
最大三角形
Ⅳ. 彩色的树
问题描述：
第 1 行输入 1 个整数 n 。 第 2 行输入 n 个整数 c1、c2、...、cn 。 接下来 n−1 行，每行输入 2 个整数 ui、vi，表示一条树边。
输出格式：
输出题目要求的答案。
数据范围：
1≤n≤2×10e5 , 1≤ci≤n
美其名曰思维题，实则是道乱搞题。对于每一个点分别求贡献，最后加起来。
（这道题实在不好讲清楚，~qwq~）
Code：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
bool Mark[200005];
int n,tot,C[200005],Size[200005],Cnt,Head[200005],Next[400005],To[400005];
long long Sum[200005],Ans;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,65536,stdin),p1==p2)?EOF:*p1++)
char buf[65536],*p1,*p2;
inline int read()
{
char ch;int x(0);
while((ch=gc)<48);
do x=x*10+ch-48;while((ch=gc)>=48);
return x;
}
inline void ADD(int x,int y) {Next[++Cnt]=Head[x],Head[x]=Cnt,To[Cnt]=y;}
inline void DFS(int x,int fa)
{
Size[x]=1,++Sum[C[x]];long long Tmp=Sum[C[x]],Temp;
for(register int i=Head[x],j;i;i=Next[i])
{
j=To[i];if(j==fa) continue;
DFS(j,x),Size[x]+=Size[j],Temp=Size[j]-Sum[C[x]]+Tmp,Ans+=(1LL*Temp*(Temp-1))/2,Sum[C[x]]+=Temp,Tmp=Sum[C[x]];
}
}
int main()
{
n=read();
for(register int i=1;i<=n;++i)
{
C[i]=read();
if(!Mark[C[i]]) ++tot,Mark[C[i]]=1;
}
for(register int i=1,x,y;i<n;++i) x=read(),y=read(),ADD(x,y),ADD(y,x);
DFS(1,0);long long Tmp;
for(register int i=1;i<=n;++i)
if(Mark[i]) Tmp=n-Sum[i],Ans+=Tmp*(Tmp-1)/2;
printf("%lld",1LL*tot*n*(n-1)/2-Ans);
return 0;
}
彩色的树