T1：自描述序列 NKOJ8660

序列：
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<=10; 1<=n<=10^7

是一道找规律题，可以处理出1,2,1,2...中每个的个数。

可以知道，最多第6666661个1,2就能达到10⁷

#include<stdio.h>
#include<algorithm>
using namespace std;
#define re register int
using namespace std;
int sum[7000000], num[7000000];
signed main()
{
    int rk=4, t=1;
    sum[1]=1;sum[2]=5;
    num[1]=1;num[2]=3;
    for(re i=3;i<=6666661;++i){
        while(sum[t]<rk)t++;
        int k=(t&1)?1:2;rk+=k;
        num[i]=num[i-1]+k;
        sum[i]=sum[i-1]+((i&1)?1:2)*k;
    }
    int T;scanf("%d",&T);
    while(T--){
        int x;scanf("%d",&x);
        int t=lower_bound(num+1, num+6666662, x)-num;
        printf("%d\n",(t&1)?1:2);
    }return 0;
}

View Code

T2：极限 NKOJ8661

函数f(x)的定义域和值域都是Zn+={1,2，...，n}。
定义fk(x)=f(fk-1(x))，特殊的f1(x)=f(x)。
x的平均能量记作：
g(x)=1/k*(sigma(i=1,i<=k)fi(x)), k趋近于无穷大
求g(1),g(2),...,g(n)。

数据范围：
1<=n<=10^5; 1<=f(i)<=n。

由于每个i都对应唯一一个f(i)，所以可以连边，画图画出基环树森林(这样好理解一些)，至于求的g(x)，就是环中的总值除以环中节点个数。

建议：分析不出来时，先用简单点的数据推，例如f(i)是1~n的排列，可以很容易推出环，然后再从排列推到一般。

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define LL long long
using namespace std;
inline LL gcd(const LL x,const LL y){return y==0?x:gcd(y,x%y);}
const int N=2e6+6;
int tt,las[N],ed[N],nt[N];
inline void add(const int x, const int y){ed[++tt]=y;nt[tt]=las[x];las[x]=tt;}
int vis[N],mk[N],lp[N],st,cnt,scc,book[N],fa[N];LL sum[N],num[N];
inline bool dfs(const int x){
    if(vis[x]==1){vis[x]=2,mk[x]=1,lp[++cnt]=x,sum[scc]+=x;return 1;}
    vis[x]=1;
    if(fa[x]&&dfs(fa[x])){
        if(vis[x]!=2)lp[++cnt]=x,sum[scc]+=x,mk[x]=1;
        else return 0;
        return 1;
    }return 0;
}
inline void DFS(const int x,const int bl){
    book[x]=bl;mk[x]=1;
    for(re i=las[x];i;i=nt[i])
    if(!mk[ed[i]])DFS(ed[i],bl);
}
inline void getloop(const int x){
    st=cnt+1;scc++;dfs(x);
    num[scc]=cnt-st+1;
    for(re i=st;i<=cnt;++i) DFS(lp[i],scc);
}
signed main()
{
    int n;scanf("%d",&n);
    for(re i=1;i<=n;++i){
        int x;scanf("%d",&x);
        add(x, i);fa[i]=x;
    }
    for(re i=1;i<=n;++i)if(!mk[i])getloop(i);
    for(re i=1;i<=n;++i){
        int t=book[i];LL a=sum[t],b=num[t],g=gcd(a,b);
        printf("%lld/%lld\n", a/g, b/g);
    }return 0;
}

View Code

这里的getloop(x)，也就是我写基环树找环的方法，dfs加上打标记vis，可以判环以及按顺序放进数组lp中，很方便

 

T3 最大三角形 NKOJ8662

有n个木棍，长度分别为ai。
q次询问，求仅使用区间[l,r]中的木棍，且每根木棍只能使用一次，能够组成的三角形中周长最大是多少，若无法组成三角形，输出-1。

数据范围：
1<=n, q<=10^5； 1<=ai<=10^9; 1<=li<=ri<=n。

我们先分析无法组成三角形的情况。

一段区间都无法组成三角形，那么斐波那契数列是能够形成的最长的区间，最长只有44位。

然后我们来想怎么构成三角形。

有一个很显然的贪心，我们可以每次选择最长的三根木棍，看能否构成三角形，若不行，则选择次三大，以此类推。

简单分析一下：

当前最长的三个，由大到小依次为a,b,c。

若a,b的组成有解，那么选c肯定可以。

如果选a有解，那么选b肯定可以。

 

我们确定了大致思路：在一段区间内，看最大的三个，若不行，找次大的三个，以此类推。

复杂度呢？如果我们用主席树来找第k大，看起来复杂度为O(nqlogn)，但实际上我们找第k大不会找超过44次。

也就是说，数据不可能构造出需要找最值次数超过44次的，我们的复杂度因此变为O(44*n*logn)，且远远跑不满。

 

还有一种方法，就是线段树维护区间的前44个最大值，但这样我们需要像归并排序一样在线段树中维护，复杂度是严格的O(44*n*logn)，要慢上亿点。

注意主席树前要离散化，输出答案的时候要记得答案不是离散化的东西，而是原数......

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define LL long long
const int N=1e6+6;
int seg, root[N];
struct segment{int a, b, v, ls, rs;}tr[N<<2];
inline int build(int l, int r)
{
    int p=++seg;
    tr[p].a=l;tr[p].b=r;
    if(l!=r)
    {
        int mid=(l+r)>>1;
        tr[p].ls=build(l,mid);
        tr[p].rs=build(mid+1,r);
    }
    return p;
}
inline int merge(int pre, int t)
{
    int p=++seg;
    tr[p]=tr[pre];tr[p].v=tr[pre].v+1;
    if(tr[p].a<tr[p].b)
    {
        int mid=(tr[p].a+tr[p].b)>>1;
        if(t<=mid)tr[p].ls=merge(tr[pre].ls,t);
        else tr[p].rs=merge(tr[pre].rs,t);
    }
    return p;
}
inline int query(int p1, int p2, int k)
{
    if(tr[p1].a==tr[p1].b)return tr[p1].a;
    int t=tr[tr[p2].rs].v-tr[tr[p1].rs].v;
    if(k<=t) return query(tr[p1].rs, tr[p2].rs, k);
    else return query(tr[p1].ls, tr[p2].ls, k-t);
}

int A[N], B[N];
signed main()
{
    int n, q;
    scanf("%d%d",&n,&q);
    for(re i=1;i<=n;++i)scanf("%d",&A[i]),B[i]=A[i];
    sort(B+1,B+1+n);
    int cnt=unique(B+1,B+1+n)-B-1;
    for(re i=1;i<=n;++i)A[i]=lower_bound(B+1,B+1+cnt,A[i])-B;

    root[0]=build(1,cnt);
    for(re i=1;i<=n;++i)root[i]=merge(root[i-1],A[i]);
    while(q--)
    {
        int l,r,s;
        scanf("%d%d",&l,&r);
        s=r-l+1;
        int p1=root[l-1], p2=root[r], t=3;
        LL a=B[query(p1, p2, 1)];
        LL b=B[query(p1, p2, 2)];

        while(t<=s)
        {
            LL c=B[query(p1, p2, t)];
            if(a<b+c){
                printf("%lld\n", a+b+c);
                break;
            }
            a=b;b=c;t++;
        }
        if(t>s)puts("-1");
    }
    return 0;
}

View Code

 

T4 彩色的树 NKOJ8663

一棵n个节点的树，每个节点都有对应的颜色ci。
记f(x,y)为x节点到y节点的最短路径上经过节点的颜色种类数，求：
sigma f(i,j)，1<=i<=n&&i+1<=j<=n

数据范围：
1<=n<=2*10^5; 1<=ci<=n。

乱搞题，拿一个sum[c]记录之前已经讨论颜色c的区域，将这段去掉即可。

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define LL long long

const int N=1e6+6;
int tt,las[N],ed[N],nt[N];
inline void add(int x,int y){ed[++tt]=y;nt[tt]=las[x];las[x]=tt;}
int sum[N],co[N],sz[N],n;
LL Ans;
inline void DFS(int x,int fa)
{
    const int col=co[x];
    int lst=sum[col],s=1;
    sz[x]=1;
    for(re i=las[x];i;i=nt[i])
    {
        int v=ed[i];
        if(v==fa)continue;
        int tmp=sum[col];
        DFS(v,x);sz[x]+=sz[v];
        tmp=sz[v]-(sum[col]-tmp);
        Ans+=1ll*tmp*s;s+=tmp;
    }
    int t1=sz[x]-(sum[col]-lst);
    int t2=n-sz[x]-lst;
    Ans+=1ll*t2*t1;
    sum[col]=lst+sz[x];
}
signed main()
{
    scanf("%d",&n);
    for(re i=1;i<=n;++i)
    scanf("%d",&co[i]);
    for(re i=1;i<n;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    DFS(1,0);
    printf("%lld\n",Ans);
    return 0;
}

View Code