syhc总结

· · 个人记录

令人期待的syhc终于开始了！！！

Day 1

我们首先迎来了铈哥的题目：

T1 Mush Dash(原创)

ljx正在玩一款叫Muse Dash的音乐节奏类游戏。

众所周知，ljx单身16年，所以手速特别快，每首曲子都能打出all perfect的最高评价。

然而这款游戏除了正常每个音符的固定得分外，还有一个fever机制。当你从游戏开始或上次fever状态结束后，击中每个音符都会为你的能量槽积攒能量，能量满后就可以进入fever状态，从而在接下来的q秒中对于击中的音符获得额外得分。

能量槽满时可以不立即进入fever状态，但由于能量槽已满，在此期间击中的音符不会为能量槽累积能量。

ljx想制霸该游排行榜，所以请你帮他计算一下他每首曲子可以在fever状态下击中几个音符。

---------------------------------------------------------------------------------------------

应该还是一道比较容易的DP吧，可是只有出题人铈哥自己以为是一道图论题(话说DP过程有点类似建图求最长路QWQ)

T2 情报(CF1098C Construct a Tree)

ljx为得到全球各地妹子的情报，打算建立自己的情报组织。

ljx雇佣了n个人，这n个人构成的情报网构成一棵有根树，且1为根节点。

我们规定每个人的领导力 为该人所在的子树大小，ljx的支出为所有人的领导力之和。

ljx带了m元钱，但ljx很挑剔，花的钱必须不多不少正好m元。

同时，ljx抓来的人并不是很擅长情报工作，所以ljx希望每个人直接领导的人(即除父节点外且与该节点直接相连的点)的最大值k最小。

请你判断是否有符合条件的情报组织，如果有，请你输出k值及情报组织的具体构造，具体方式为输出2~n的父节点。

本题为多组测试。

---------------------------------------------------------------------------------------------

对于第一问，直接判断md的值是否在\frac{n(n+1)}{2}(一条链的情况)和2n-1(菊花图的情况)之间即可

对于第二问，很容易想到二分，然后用完全k叉树贪心地验证花费是否小于等于m

此题难点在于第三问，但其实做出第二问之后第三问也不太难(可是窝考场上没敢写)。具体做法如下：在建树时，找出深度为某值的点有几个，然后微调树形。 在满k叉树基础上，选择一次转移整个深度能转移的点来调整树形。

T3 大写锁定(CF1111E Tree)

9岁拧魔方破世界纪录的神童ldy的Caps Lock键忽然坏了。

经ldy的仔细检查，发现是电脑程序的内存分配出了问题。

该程序由n个子程序构成，他们的调用关系构成了一棵无根树。

对于每个时刻，ldy的电脑会有一些关键程序以及一个核心程序rt，ldy需要在以rt为根节点的情况下将关键程序分配至k个段中，且同一个段中的程序不能为祖先-后代关系。

ldy早就想出了解决方案，但是他不知道有多少种解决方案，所以他把问题交给了你。

由于方案数可能很大，结果对1000000007取模。

---------------------------------------------------------------------------------------------

我的做法是虚树，固定一个根节点建树。

假设该节点到根节点的路径上的点都已经处理完，那么该节点的贡献对$dp[i]$的贡献为$dp[i-1]+dp[i]*(i-other) $,其中$other$为该点到虚树根节点路径上的点数。 听说这道题正解不是虚树$?!

ljx用LCT做的这道题?!

虚树做法：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define N 200020
typedef long long lint;
#define mod 1000000007
template<typename TP> inline void read(TP &ret)
{
    TP x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    ret=(TP)x*f;
}
int n,m;
int q,k,r;
struct apple
{
    int to,next;
}indexx[N];
int head[N],cnt;
void init(int x,int y)
{
    indexx[++cnt].to=y;
    indexx[cnt].next=head[x];
    head[x]=cnt;
}
int dep[N],f[N][25],indegree[N],tot;
void dfs1(int u,int fa)
{
    indegree[u]=++tot;
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<=20;i++)
    {
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(int i=head[u];i;i=indexx[i].next)
    {
        int v=indexx[i].to;
        if(v!=fa)
        {
            dfs1(v,u);
        }
    }
}
int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--)
    {
        if(dep[f[x][i]]>=dep[y])
        {
            x=f[x][i];
        }
    }
    if(x==y) return x;
    for(int i=20;i>=0;i--)
    {
        if(dep[f[x][i]]&&f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
vector<int> tmp;
bool mp[N];
bool cmp(int x,int y)
{
    return indegree[x]<indegree[y];
}
int st[N],tp;
struct orange
{
    int to,next;
}iindex[N];
int ihead[N],icnt;
void iiit(int x,int y)
{
    iindex[++icnt].to=y;
    iindex[icnt].next=ihead[x];
    ihead[x]=icnt;
}
void iinsert(int u)
{
    if(u==1) return;
    if(tp==1)
    {
        st[++tp]=u;
        return;
    }
    int lc=lca(st[tp],u);
    while(tp>1&&indegree[lc]<=indegree[st[tp-1]])
    {
        iiit(st[tp-1],st[tp]);
        iiit(st[tp],st[tp-1]);
        tp--;
    }
    if(st[tp]!=lc)
    {
        iiit(st[tp],lc);
        iiit(lc,st[tp]);
        st[tp]=lc;
    }
    st[++tp]=u;
    return;
}
lint dp[303];
void dfs2(int u,int fa,int num)
{
    if(mp[u])
    {
        for(int i=k;i>=0;i--)
        {
            if(i<=num) dp[i]=0;
            else dp[i]=(dp[i-1]+(i-num)%mod*dp[i])%mod;
        }
    }
    for(int i=ihead[u];i;i=iindex[i].next)
    {
        int v=iindex[i].to;
        if(v!=fa)
        {
            dfs2(v,u,num+mp[u]);
        }
    }
    ihead[u]=0;
    mp[u]=0;
}
int main()
{
//  freopen("capslock.in","r",stdin);
//  freopen("capslock.out","w",stdout);
    read(n),read(m);
    for(int i=1;i<n;i++)
    {
        int x,y;
        read(x),read(y);
        init(x,y);
        init(y,x);
    }
    dfs1(1,0);
    while(m--)
    {
        read(q),read(k),read(r);
        tmp.clear();
        for(int i=1;i<=q;i++)
        {
            int x;
            read(x);
            mp[x]=1;
            tmp.push_back(x);
        }
        if(!mp[r])
        {
            q++;
            tmp.push_back(r);
        }
        sort(tmp.begin(),tmp.end(),cmp);
        tp=0;
        icnt=0;
        st[++tp]=1;
        for(int i=0;i<q;i++)
        {
            iinsert(tmp[i]);
        }
        while(tp)
        {
            if(tp-1)
            {
                iiit(st[tp],st[tp-1]);
                iiit(st[tp-1],st[tp]);
            }
            tp--;
        }
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        dfs2(r,0,0);
        lint ans=0;
        for(int i=0;i<=k;i++)
        {
            ans=(ans+dp[i])%mod;
        }
        printf("%lld\n",ans);
    }
}

正解做法(出题人的代码)：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mod 1000000007
long long read()
{
    long long x=0,f=1;char ch;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
struct edge
{
    long long nxt,to;
}ed[205000];
long long head[105000],cnt;
long long n,q,a,b,c,d,dp[105000],rt_num[105000];
long long f[105000][21],dep[105000],used[105000];
long long que[205000],t,ta[205000],s[105000],e[105000];
bool cmp(long long a,long long b)
{
    return rt_num[a]<rt_num[b];
}
void change(long long x,long long v)
{
    if(x<=0)return ;
    for(;x<=n*2;x+=(x&-x))ta[x]+=v;
}
long long query(long long x)
{
    long long ans=0;
    for(;x;x-=(x&-x))ans+=ta[x];
    return ans;
}
void add(long long a,long long b)
{
    ed[++cnt].to=b;ed[cnt].nxt=head[a];head[a]=cnt;
    ed[++cnt].to=a;ed[cnt].nxt=head[b];head[b]=cnt;
}
void dfs(long long pos,long long fa)
{
    if(used[pos])return ;
    used[pos]++;
    f[pos][0]=fa;dep[pos]=dep[fa]+1;
    s[pos]=++t;
    for(long long i=head[pos];i;i=ed[i].nxt)
    {
        dfs(ed[i].to,pos);
    }
    e[pos]=++t;
}
void lca_init()
{
    for(long long i=1;i<=20;i++)
    {
        for(long long j=1;j<=n;j++)
        f[j][i]=f[f[j][i-1]][i-1];
    }
}
long long lca(long long a,long long b)
{
    long long ans=0;
    if(dep[a]<dep[b])swap(a,b);
    for(long long i=20;i>=0;i--)
    {
        if(dep[f[a][i]]>=dep[b])a=f[a][i];
    }
    if(a==b)return a;
    for(long long i=20;i>=0;i--)
    {
        if(f[a][i]==f[b][i])ans=f[a][i];
        else a=f[a][i],b=f[b][i];
    }
    return ans;
}
int main()
{
//  freopen("capslock.in","r",stdin);
//  freopen("capslock.out","w",stdout);
    n=read();q=read();
    for(long long i=1;i<n;i++)
    {
        a=read();b=read();
        add(a,b);
    }
    dfs(1,0);
    lca_init();
    for(long long i=1;i<=q;i++)
    {
        a=read();b=read();c=read();
        for(long long j=1;j<=a;j++)
        {
            que[j]=read();
            change(s[que[j]],1);
            change(e[que[j]],-1);
        }
        for(long long j=1;j<=a;j++)
        {
            long long now=lca(que[j],c);
            rt_num[que[j]]=query(s[que[j]])+query(s[c])-query(s[now])-query(s[f[now][0]])-1;//
        }
        sort(que+1,que+1+a,cmp);    
        dp[1]=1;
        for(int j=2;j<=min(a,b);j++)dp[j]=0;
        for(long long j=2;j<=a;j++)
        {
            for(long long k=min(a,b);k;k--)
            {
                dp[k]=(dp[k-1]+dp[k]*(k-rt_num[que[j]])%mod)%mod;
            }
        }
        long long ans=0;
        for(long long j=1;j<=min(a,b);j++)ans=(ans+dp[j])%mod;
        printf("%lld\n",ans);
        for(long long j=1;j<=a;j++)
        {
            change(s[que[j]],-1);
            change(e[que[j]],1);
        }
    }
    return 0;
}

(ljx巨佬LCT做法过于丑陋，就先不贴在这儿了"BakaBaka~")

本场个人得分(70+60+0)=130

**Day2** 窝竟然第二天就喜迎王师了$?!

我数据出锅了?!

全场人均得分这么低?!

还是看题目吧：

T1 摧毁敌人的秘密工厂(CF464E The Classic Problem)

绿元27年，Sora.Rikuki与Suffix.A.Maton正在执行指挥官Dr.Harris派给他们的一项任务：找到敌军的秘密工厂，并摧毁敌军正在建造的新型MA。根据工程部秘书长Slizard.C.Edward提供的地图，敌人的占领区是一个n个点，m条边的无向图(为了节省建造成本，其中没有重边和自环)，在敌军首席工程师David.Z.Dominic的设计下，所有道路的长度都是2的整数次幂。

$Sora.Rikuki$和$Suffix.A.Maton$被告知，敌人将在5s后启动新型MA。他们不能浪费任何时间去研究路线，只好把这个问题交给身为战场情报士的你。你只需要告诉他们$s$到$t$的最短路线的长度**对$1000000007$取模**后的值。 **如果不存在一条最短路线，请输出“$-1$”**。 **---------------------------------------------------------------------------------------------** 本题难点就在于维护$2^w$，直接进位和取模肯定是不行的(为什么当时我没想到这一点呢$QWQ$)，在这里我们用主席树维护二进制高进度，每次二分找到一段连续的$1$，并将其修改为$0$，同时将下一位改成$1$。 最短路什么的，直接$dijkstra$好了...... 为什么大家都说这道题太毒瘤了$?!

一开始没想到暴力进位会TLE，还有如何卡掉便跑dijkstra边取模的情况，好多错解都差点过了......结果当天造数据又用了一个下午和半个晚上(自己出题那天竟然是我改题时间最长的一天，枯了枯了(TwT))

修改过的标程如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
template<typename TP> inline void read(TP &ret)
{
    TP x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    ret=(TP)x*f;
}
#define N 100005
#define bas 233333
#define mod 1000000007
int n,m,cnt,head[N],dis[N],tot,lim,s,t;
lint punc1[N<<1],punc[N<<1];
bool vis[N];
struct apple
{
    int to,next;
    lint val;
}indexx[N*2];
struct Persistent_Segment_Tree
{
    int lson,rson,val;
    ulint has,has1;
}tree[N*240];
void init(int x,int y,lint w)
{
    indexx[++cnt].to=y;
    indexx[cnt].val=w;
    indexx[cnt].next=head[x];
    head[x]=cnt;
}
void push_up(int now)
{
    tree[now].val=tree[tree[now].lson].val+tree[tree[now].rson].val;
    tree[now].has=(tree[tree[now].lson].has+tree[tree[now].rson].has)%mod;
    tree[now].has1=(tree[tree[now].lson].has1+tree[tree[now].rson].has1);
}
bool ssame(int x,int y)
{
    int flag=1;
    flag&=(tree[x].has==tree[y].has);
    flag&=(tree[x].has1==tree[y].has1);
    flag&=(tree[x].val==tree[y].val);
    return flag;
}
bool comp(int x,int y,int l,int r)
{
    if (l==r) 
    {
        return tree[x].val>=tree[y].val;
    }
    int mid=(l+r)>>1;
    if (!ssame(tree[x].rson,tree[y].rson)) return comp(tree[x].rson,tree[y].rson,mid+1,r);
    else return comp(tree[x].lson,tree[y].lson,l,mid);
}
struct banana
{
    int f,t;
    banana(){}
    banana(int f,int t):f(f),t(t){};
    bool operator<(const banana &other)const
    {
        return comp(t,other.t,0,lim);
    }
};
priority_queue<banana> q;
int build(int l,int r,int x)
{
    int now=++tot;
    if(l==r)
    {
        tree[now].val=x;
        tree[now].has=punc[l]*x;
        tree[now].has1=punc1[l]*x;
        return now;
    }
    int mid=(l+r)>> 1;
    tree[now].lson=build(l,mid,x);
    tree[now].rson=build(mid+1,r,x);
    push_up(now);
    return now;
}
int query(int l,int r,int now,int st,int en)
{
    if (st>r||en<l) return 0;
    if (st<=l&&en>=r) 
    {
        return tree[now].val;
    }
    int mid=(l+r)>>1;
    return query(l,mid,tree[now].lson,st,en)+query(mid+1,r,tree[now].rson,st,en);
}
int find(int l,int r,int now,int p)
{
    if(l==r) return l;
    int mid=(l+r)>> 1;
    if(p>mid) return find(mid+1,r,tree[now].rson,p);
    if (query(l,mid,tree[now].lson,p,mid)==mid-p+1) return find(mid+1,r,tree[now].rson,mid+1);
    else return find(l, mid, tree[now].lson,p);
}
int insert(int l,int r,int las,int p)
{
    int now=++tot;
    tree[now].lson=tree[las].lson,tree[now].rson=tree[las].rson;
    if (l==r)
    {
        tree[now].val=1;
        tree[now].has=punc[l];
        tree[now].has1=punc1[l];
        return now;
    }
    int mid=(l+r)>> 1;
    if (p<=mid) tree[now].lson=insert(l,mid,tree[las].lson,p);
    else tree[now].rson=insert(mid+1,r,tree[las].rson,p);
    push_up(now);
    return now;
}
int merge(int l,int r,int x,int y,int st,int en)
{
    if (st>r||en<l) return x;
    if (st<=l&&en>=r) return y;
    int now=++tot;
    int mid=(l+r)>>1;
    tree[now].lson=merge(l,mid,tree[x].lson,tree[y].lson,st,en);
    tree[now].rson= merge(mid+1,r,tree[x].rson,tree[y].rson,st,en);
    push_up(now);
    return now;
}
int add(int now, int x)
{
    int p=find(0,lim,now,x);
    int tmp=insert(0,lim,now,p);
    if (p==x) return tmp;
    tmp=merge(0,lim,tmp,dis[0],x,p-1);
    return tmp;
}
void dijkstra()
{
    int tmp=build(0, lim, 1);
    for (int i=1;i<=n;i++)
    {
        dis[i]=tmp;
    }
    dis[0]=dis[s]=build(0,lim,0);
    q.push(banana(s,dis[s]));
    while(!q.empty())
    {
        while(!q.empty()&&vis[q.top().f]) 
        {
            q.pop();
        }
        banana temp=q.top();
        int u=temp.f;
        if(vis[u]) continue;
        vis[u]=1;
        for (int i=head[u];i;i=indexx[i].next)
        {
            int v=indexx[i].to;
            int tag=add(dis[u],indexx[i].val);
            if(!comp(0,lim,dis[v],tag)) continue;
            dis[v]=tag;
            q.push(banana(v,dis[v]));
        }
    }
    if(dis[t]==tmp)
    {
        puts("-1");
    }
    else
    {
        printf("%lld\n",tree[dis[t]].has%mod);
    }
    return;
}
int main()
{
//  freopen("destroy.in","r",stdin);
//  freopen("destroy.out","w",stdout);
    read(n),read(m);
    for (int i=1;i<=m;i++)
    {
        int x,y;
        lint z;
        read(x),read(y),read(z);
        init(x,y,z);
        init(y,x,z);
        lim=max((lint)lim,z);
    }
    lim+=300;
    punc[0]=1;
    punc1[0]=1;
    for (int i=1;i<=lim;i++)
    {
        punc[i]=punc[i-1]*2%mod;
        punc1[i]=punc1[i-1]*bas;
    }
    read(s),read(t);
    dijkstra();
    return 0;
}

震惊?!

wh竟然用了6天时间改这道题?!

(是我太毒瘤了吗?......)

T2 熊霸序列(AT3577 Largest Smallest Cyclic Shift)

绿元27年，在文化部长Physics.Orz提供的北宋地图的指引下，Sora.Rikuki与Suffix.A.Maton踏上了寻找了先史遗产♂的征途。

途中，二人路过了居住着可爱的熊霸们的熊熊村，并用爱与希望解开了龟霸头部的怨念，救回了之前被抓走的村中的成年熊霸。

在Sora.Rikuki和Suffix.A.Maton将要离开熊熊村时，村长Avocadogguy为了感谢他们，决定为他们组织一场特别的欢送仪式：让红(R)、蓝(B)、绿(G)三种颜色各r,b,g个小熊霸以一定顺序组成一串，组成一个序列。

**---------------------------------------------------------------------------------------------** 一道构造贪心题吧...... 性感理解一下：最小表示——最小的串放在最前面，最大——最大的串放在最小的后面。 结束了$?!$ 结束了$!!

代码也就不到二十行吧......

**T3 战争前后(CF1119F Tree Cutting(Hard Version))** 绿元28年，$Guyana$雨林。 电话响起：“$Dandelion$小队，我是$Dr.Harris$,$Kszyszy.D.Lot$总理刚刚过世了，新任总理$Licon.D.Yacques$对你们的行动持反对态度，你们的行动将不再得到国家政府的援助，今后的一切就只能靠你们自己了……祝好运，再见……”收到$Dr.Harris$的来电，$Dandelion$小队的心情是沉重的。 $Dandelion$小队一共有$k$名队员，他们的行踪散布在有着$n$个敌人据点的$Gunaya$树形雨林中，在接到Dr.Harris的电话前，他们每个人都独自攻下了一些敌人的据点，此时还有一些据点没有被攻占。即使不被支持，$Dandelion$小队也要完成未竟的任务——占领雨林中所有的敌人的据点。 作为$Dandelion$小队的队长，$Suffix.A.Maton$想要知道如何分配接下来的战斗任务，使得小队里的人员更容易地进行攻守，即每个人现在及接下来所攻下的据点都在同一个连通块中。 身为战场情报士的你需要告诉队长$Suffix.A.Maton$ $Dandelion$小队可能的作战**方案数**。 **---------------------------------------------------------------------------------------------** 难道是我题面表述不清楚$??! 我好$nan$啊~ 这道题目给人的第一印象应该就是一道DP吧…… 首先考虑无解的情况，可以发现如果以一个有队员的据点为根的子树不包括所有这个队员占据的据点，则这个据点与其父亲必须处于同一连通块中，我们可以据此让其父亲也被相同的队员占领。 对于一个有队员占领的据点，如果它的父据点有队员占领且占领这两个据点的队员不是同一人，则无解。 再来考虑有解的DP： $dp[u][0/1]$表示u据点的子树中是否还有与u相同的颜色的方案数。 对于颜色已经确定的一个连通块： $dp[u][1]=\prod_{v\epsilon u}(dp[v][0]+dp[v][1]) dp[u][0]=0

对于能由其他队员占领的据点：

dp[u][0]=\prod_{v\epsilon u}(dp[v][0]+dp[v][1]) dp[u][1]=\sum_{v \epsilon u}dp[v][1]\prod_{x \epsilon u,x!=v}(dp[x][0]+dp[x][1])

注意开long long(然而并没有什么太大的影响)和取模。

这大概是三道题里最水的一道了吧(#滑稽)~

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
#define N 1000010
#define mod 998244353
int n,k;
int a[N];
struct apple
{
    int to,next;
}indexx[N];
int head[N],cnt;
void init(int x,int y)
{
    indexx[++cnt].to=y;
    indexx[cnt].next=head[x];
    head[x]=cnt;
}
bool flag;
int c[N];
int tmp[N];
int dp[N][2];
int punc[N];
vector<int> q;
void dfs(int u,int fa)
{
    tmp[u]=a[u]>0;
    for(int i=head[u];i;i=indexx[i].next)
    {
        int v=indexx[i].to;
        if(v==fa) continue;
        dfs(v,u);
        if(!a[u]) a[u]=a[v];
        else if(a[v]&&a[u]!=a[v])
        {
            flag=1;
        }
        tmp[u]+=tmp[v];
    }
    q.clear();
    for(int i=head[u];i;i=indexx[i].next)
    {
        int v=indexx[i].to;
        if(v!=fa)
        {
            q.push_back(v);
        }
    }

    punc[0]=1;
    for(int i=0;i<(long long)q.size();i++)
    {
        int v=q[i];
        punc[i+1]=(long long)punc[i]%mod*(dp[v][0]%mod+dp[v][1]%mod)%mod;
    }
    int siz=q.size();
    if(!siz)
    {
        if(a[u])
        {
            dp[u][1]=1;
        }
        else
        {
            dp[u][0]=1;
            dp[u][1]=0;
        }
        if(c[a[u]]==tmp[u]) a[u]=tmp[u]=0;
        return;
    }
    if(a[u])
    {
        dp[u][1]=punc[siz];
    }
    else
    {
        dp[u][0]=punc[siz];
        int tot=1;
        for(int i=q.size()-1;i>=0;i--)
        {
            int v=q[i];
            dp[u][1]=(dp[u][1]+(long long)tot*dp[v][1]%mod*punc[i]%mod)%mod;
            tot=(long long)tot*(dp[v][0]+dp[v][1])%mod;
        }
    }
    if(tmp[u]==c[a[u]]) tmp[u]=a[u]=0;
}
signed main()
{
//  freopen("war.in","r",stdin);
//  freopen("war.out","w",stdout);
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        c[a[i]]++;
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%lld%lld",&x,&y);
        init(x,y);
        init(y,x);
    }
    dfs(1,0);
    printf("%lld\n",flag?0:dp[1][1]);
}

Day 3

在第三天，出现了! 黑蛤蟆的重工业题目!!

T1 零件制造(CF1163F Indecisive Taxi Fee)

绿元27年，Dr.Harris指挥了数场规模巨大的两栖登陆作战，兑现了将陆军送到大洋彼岸的承诺。然而海军旗舰黑蛤蟆号却被鱼雷轰炸机击沉，对此Dr.Harris十分受打击，决定将即将投产的最新型的航空母舰命名为黑蛤蟆号。为了让新的黑蛤蟆号尽快下水，Dr.Harris找到了：工程部部长Rikuki Licon，总工程师Physics Orz，和工程部秘书Slizard。

很明显，制造如此巨大的航空母舰需要许多巨大的钢构件。如此巨大的构件只能在位于1号城市的第一钢铁公司的工厂中制造加工，但足够容纳下黑蛤蟆号的船坞位于由于n号城市。但Dr.Harris对预期的下水时间十分不满，认为在转运零件上消耗了太多时间。所以Rikuki Licon和Slizard使用了魔法来加速零件的转运。具体来说，RiKuki Licon的魔法使得各零件的运输互不干扰。而Slizard的魔法使得对于某一个零件从城市A转运到城市B所需的时间发生变化（由于Slizard学艺不精，不一定是减少）。现在Dr.Harris想知道，对于每一个零件，它从制造完成到运输到船坞需要多少时间。

---------------------------------------------------------------------------------------------

和我T1体量相当的数据结构维护图论题。

很明显，边权的改变分4种情况：

在1->n的最短路上的一条边变长了

不在1->n的最短路上的一条边变长了

在1->n的最短路上的一条边变短了

不在1->n的最短路上的一条边变短了

对于情况2,3,4而言，问题非常的简单：

$3$. 原来的最短路长度-原来的边长+现在的边长 $4$. 在原来的最短路的长度和$1$到$u$的距离$+v$到$n$的距离$+$新的边长中取一个最小值。 都是$O(1)$出解，现在考虑如何在处理情况$1$。 实际上$3,4$可以合并。 我们提取出从$1$到$n$的一条最短路，设这条最短路上的点分别为$1,x1,x2…xk,n$。那么很明显，从1到某一个点的最短路一定会利用从1到n的最短路的一部分，即：从$1$到点$v$的最短路上的点一定是：$1,x1,x2…xL,a,b…c,v$。 我们记点$v$对应的$L$为$L[v]$。 同理，从一个点到$n$的最短路也一定会利用1到n的最短路的一部分。即：从点$v$到n的最短路上的点一定是：$v,a,b…c,xR,xR+1…xk,n$。我们记点$v$对应的$R$为$R[v]$。那么我们考虑用线段树维护不经过我们选定的最短路上的边$e$，而从点1到n的最短路径的长度。那么这样情况1的结果就可以写作： $min(query(e,1,1,len-1),dis(1,u)+dis(v,n)+e.val,dis(1,v)+dis(u,n)+e.val)

现在考虑如何构造线段树，首先，对于一条连接了u和v的边e而言，它很明显只会影响从点L[u]到R[v]的值，因而在此覆盖一下，然后取最小值即可。也就是：

add(1,L[u],R[v]-1,dis(1,u)+dis(v,n)+e.val,1,len-1)

以及：

add(1,L[v],R[u]-1,dis(1,v)+dis(u,n)+e.val,1,len-1)

那现在便只剩下一个问题了：如何计算L[u]和R[u]。 （鉴于计算R[u]就是在反向图跑和计算L[u]相同的过程，在此就不在赘述了）

方法嘛，就是先跑一遍dijkstra，选出那条特殊的最短路，然后再跑一遍dijkstra用上一个点的L来更新下一个点的L。在此注意一点要保证选中的那条最短路是相同的。另外请注意一个细节：由于这道题是用点来代表边，因此线段树要使用类似于扫描线的做法。即r需要-1。还有一个细节，就是对于在我们选择的这条最短路上的点xk而言，我们令L[xk]=R[xk]=k，这样代码会好写一点。

#include<bits/stdc++.h>
using namespace std;
#define N 400040
typedef long long lint;
template<typename TP> inline void read(TP &ret)
{
    TP x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    ret=(TP)x*f;
}
int n,m,p;
struct apple
{
    int to,next;
    lint val;
}indexx[N];
int head[N],cnt;
void init(int x,int y,lint w)
{
    indexx[++cnt].to=y;
    indexx[cnt].val=w;
    indexx[cnt].next=head[x];
    head[x]=cnt;
}
struct orange
{
    int x,y;
    lint z;
    orange(){}
    orange(int x,int y,lint z):x(x),y(y),z(z){};
}input[N];
lint dis[2][N],pre[2][N],from[2][N];
bool vis[2][N];
struct banana
{
    int f;
    lint t;
    banana(){}
    banana(int f,lint t):f(f),t(t){};
    friend bool operator<(banana a,banana b)
    {
        return a.t>b.t;
    }
};
priority_queue<banana> q;
void dijkstra(int s,int type)
{
    for(int i=1;i<=n;i++)
    {
        dis[type][i]=1000000000000000ll;
    }
    memset(vis[type],0,sizeof(vis[type]));
    while(!q.empty()) q.pop();
    dis[type][s]=0;
    q.push(banana(s,dis[type][s]));
    while(!q.empty())
    {
        banana temp=q.top();
        q.pop();
        int u=temp.f;
        if(vis[type][u]) continue;
        vis[type][u]=1;
        for(int i=head[u];i;i=indexx[i].next)
        {
            int v=indexx[i].to;
            if(dis[type][v]>dis[type][u]+indexx[i].val)
            {
                dis[type][v]=dis[type][u]+indexx[i].val;
                pre[type][v]=(i+1)>>1;
                from[type][v]=u;
                q.push(banana(v,dis[type][v]));
            }
        }
    }
}
bool used[N];
struct lemon
{
    int x;
    lint t;
}c;
lint ans;
bool type;
int top[2][N],dep[2][N];
void dfs(int u,int t)
{
    top[type][u]=t;
    for(int i=head[u];i;i=indexx[i].next)
    {
        int v=indexx[i].to;
        if(!top[type][v])
        {
            if(from[type][v]!=u) continue;
            if(used[pre[type][v]])
            {
                dep[type][v]=dep[type][u]+1;
                dfs(v,v);
            }
            else
            {
                dfs(v,t);
            }
        }
    }
}
struct node
{
    int l,r;
    lint minn;
}tree[N*4];
void build(int l,int r,int now)
{
    tree[now].l=l,tree[now].r=r;
    tree[now].minn=100000000000000ll;
    if(l==r)
    {   
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,now*2);
    build(mid+1,r,now*2+1);
}
void add(int l,int r,int now,lint x)
{
    if(l>r) return;
    if(l<=tree[now].l&&r>=tree[now].r)
    {
        tree[now].minn=min(tree[now].minn,x);
        return;
    }
    int mid=(tree[now].l+tree[now].r)>>1;
    if(l<=mid) add(l,r,now*2,x);
    if(r>mid) add(l,r,now*2+1,x);
}
lint query(int l,int r,int now,int p)
{
    if(l==r)
    {
        return tree[now].minn;
    }
    int mid=(tree[now].l+tree[now].r)>>1;
    lint tmp=tree[now].minn;
    if(p<=mid) tmp=min(tmp,query(l,mid,now*2,p));
    else tmp=min(tmp,query(mid+1,r,now*2+1,p));
    return tmp;
}
int main()
{
//    freopen("parts.in","r",stdin);
//    freopen("parts.out","w",stdout);
    read(n),read(m),read(p);
    for(int i=1;i<=m;i++)
    {
        read(input[i].x),read(input[i].y),read(input[i].z);
        init(input[i].x,input[i].y,input[i].z);
        init(input[i].y,input[i].x,input[i].z);
    }
    dijkstra(1,0);
    dijkstra(n,1);
    int now=n;
    while(now)
    {
        used[pre[0][now]]=1;
        now=from[0][now];
    }
    type=0;
    dep[0][1]=1;
    dfs(1,1);
    type=1;
    dep[1][n]=1;
    dfs(n,n);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        if(!used[i])
        {
            int x=input[i].x,y=input[i].y;
            int fx=top[0][x],fy=top[1][y];
            add(dep[0][fx],dep[0][fy]-1,1,dis[0][x]+dis[1][y]+input[i].z);
            fx=top[0][y],fy=top[1][x];
            add(dep[0][fx],dep[0][fy]-1,1,dis[0][y]+dis[1][x]+input[i].z);
        }
    }
    while(p--)
    {
        ans=dis[0][n];
        read(c.x),read(c.t);
        int x=input[c.x].x,y=input[c.x].y;
        if(top[0][x]!=x||top[0][y]!=y||(from[0][x]!=y&&from[0][y]!=x))
        {
            if(c.t<input[c.x].z)
            {
                ans=min(ans,min(dis[0][x]+dis[1][y],dis[1][x]+dis[0][y])+c.t);
            }
        }
        else
        {
            if(dep[0][x]>dep[0][y]) swap(x,y);
            if(c.t<=input[pre[0][y]].z) ans+=(c.t-input[pre[0][y]].z);
            else if(c.x==pre[0][y]) ans=min(ans+(c.t-input[pre[0][y]].z),query(1,n,1,dep[0][x]));
        }
        printf("%lld\n",ans);
    }
}

打公式好累啊~TWT~

T2 反应堆组装(原创 题面有误，已删除)

---------------------------------------------------------------------------------------------

如果题面不错的话，大致就是一个弱化版的维修数列吧......

(什么?! 你没做过维修数列，还不快去做)

T3 母港选择(CF1182D Complete Mirror)

绿元31年，新的黑蛤蟆号下水了，如此巨大的军舰需要选择一个理想的母港，由于像Physics Orz这样的天才并不常见，他立刻被调到了负责研发原木的部门。选择母港的任务自然就落到了Slizard身上。

在选定母港之前Dr.Harris命令扫雷舰队清除了 个港口之间的 条航线附近的水雷，这样就使得军舰在这 个港口间周转时无需扫雷舰开路。当然，航线一定是双向的。海军总司令Dynamic Licon和空军总司令St\cdot Yuri认为一个港口是好的母港，当且仅当对于任意的两点 ，如果满足从母港 到 和 所需经过的航线数目相等，则必有和所能直接到达的港口数目相等。由于Dynamic Licon还要负责船队的护航工作，St\cdot Yuri还要负责对陆军进行补给和支援，但Slizard并不能在理想的时间内选择出满足条件的母港，因此这个任务还是要由你来完成。

---------------------------------------------------------------------------------------------

很明显，如果我们选定的母港root有不止一个儿子，那么这几个儿子必然是完全相同的。所以这种情况下root是树的重心。先找出树的重心，然后检查一下。如果可以，那么直接输出即可。现在我们考虑一下母港的度数为1的情况。这样，就说明从母港向下是一条连向重心的链。而从重心向下是若干条长度相同的链。

所以母港存在时重心连接链的有两种可能：

$2.$若干条同构的子树和一条与之前不同的子树。 对于情况$1$，任意一棵子树的叶子都可以是母港。对于情况$2$，这条不同子树的叶子即为母港。而如果以上三种情况均不成立，就说明不存在一个合法的母港。 但事实上，还有一些别的做法吧...... 本场个人得分$(40+0+50)=90

Day 4

老大爷令人想要割jj的数学赛

T1 大保健(某咕P3986 斐波那契数列)

听说她不但数学特别好，智商很高，而且玩传奇也是校内一流。 一天，她在玩一款传奇游戏时，突然她大喊一声：”爆$zuang$备了啊！这样不就可以吊打$LinkJavaX$了吗…” 这个神装叫做$Ex-Fibonacci$大保健，它有两个初始攻击值$a$和$b$（$a,b$均为正整数）可以自己设置，即在前两次攻击所造成的伤害$x_1,x_2$，在接下来的攻击中，满足$x_i=x_{i-1}+x_{i-2}$。 在$LinkZaneJ$心中有一个幸运数字$k$，她并不在意她砍几下能干爆boss，她在意的是这件神装要如何设计初始攻击值才可能打出伤害为$k$的攻击，另外她不希望在前两次攻击就打出$k$，也就是说，$a$与$b$不能等于$k$。 可爱的 便把这个问题交给了你，如果你无法在$1.5s$之内回答出来的话，她会怀疑你的智力水平的！ **---------------------------------------------------------------------------------------------** 比较水的$exgcd

写出x的前几项：a,b,a+b,2a+3b,3a+5b......发现系数就是斐波那契数列 和，而且写到第大概90项的时候就超过long long了，枚举k的出现位置，因此问题转化为ax+by=k的正整数解 的个数，求出最小正整数解。再搞一搞就好了(通解为x=x_0+bt，y=y_0-at)计数时注意特判。

T2 58号元素(CF1132G Greedy Subsequences)

听说她不但数学特别好，智商很高，而且对蜥蜴也是情有独钟。 她在家里养了若干条小蜥蜴，每个小蜥蜴都有它的长度。她突然对这个长度序列的最长贪心严格上升子序列有了想法(fà)。 定义了一个序列的最长贪心严格上升子序列为：设原序列为$a$，其长度为$n$，则需找出满足条件的最长的下标序列$d_i,i\epsilon[1,m]

使得：

1.d_1<d_2<d_3<......<d_m 2.a_{d_1}<a_{d_2}<......<a_{d_m} 3.\forall i\epsilon(1,m]$，不存在$k\epsilon(d_i,d_i+1)$，使得$a_k>a_{d_i}

现在 给(gēi)了你一个序列 ，她希望你找出一些子序列的最长贪心严格上升子序列的长度为多少。 可爱的LinkZaneJ便把这个问题交给了你，如果你无法在1s之内回答出来的话，她会怀疑你的智力水平的！

---------------------------------------------------------------------------------------------

题目比较套路吧......

首先用单调栈就可以轻松求出nxt的值，然后就像弹飞绵羊那道题，我们可以建出一棵树来，如果某元素后面没有比它大的那就连向n+1，问题就变成求树上的点的最长父子链。

考虑用线段树维护该树的dfs序，如果在这个子区间内增加一个a[x]，那就是以x这个点的子树内的点为起点的最长贪心严格上升子序列都加上1，删除就是减去1。 操作涉及区间加，全局求_{max}。

就是让你dfs爆栈!!!

#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
#define N 1000010
template<typename TP> inline void read(TP &ret)
{
    TP x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    ret=(TP)x*f;
}
int n,k;
struct lemon
{
    int x;
    lint y;
    bool operator<(const lemon &other)const
    {
        if(y==other.y)
        {
            return x<other.x;
        }
        return y<other.y;
    }
}input[N];
int high[N],tot;
int st[N],top;
int f[N];
struct apple
{
    int to,next;
}indexx[N];
int head[N],cnt;
void init(int x,int y)
{
    indexx[++cnt].to=y;
    indexx[cnt].next=head[x];
    head[x]=cnt;
}
int l[N],idcnt,siz[N];
stack<int> tmp;
void bfs()
{
    tmp.push(n);
    while(!tmp.empty())
    {
        int u=tmp.top();
        tmp.pop();
        l[u]=++idcnt;
        for(int i=head[u];i;i=indexx[i].next)
        {
            int v=indexx[i].to;
            tmp.push(v);
        }
    }
}
struct node
{
    int l,r;
    int val,maxn;
}tree[4*N];
void push_up(int now)
{
    tree[now].maxn=max(tree[now*2].maxn,tree[now*2+1].maxn)+tree[now].val;
}
void build(int l,int r,int now)
{
    tree[now].l=l,tree[now].r=r;
    if(l==r)
    {
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,now*2);
    build(mid+1,r,now*2+1);
}
void add(int l,int r,int now,int x)
{
    if(l<=tree[now].l&&r>=tree[now].r)
    {
        tree[now].val+=x;
        tree[now].maxn+=x;
        return;
    }
    int mid=(tree[now].l+tree[now].r)>>1;
    if(l<=mid) add(l,r,now*2,x);
    if(r>mid) add(l,r,now*2+1,x);
    push_up(now);
    return;
}
int main()
{
//  freopen("lizard.in","r",stdin);
//  freopen("lizard.out","w",stdout);
    read(n),read(k);
    for(int i=1;i<=n;i++)
    {
        read(input[i].y);
        input[i].x=i;
        siz[i]=1;
    }
    siz[n+1]=1;
    sort(input+1,input+n+1);
    for(int i=1;i<=n;i++)
    {
        if(input[i].y!=input[i-1].y) ++tot;
        high[input[i].x]=tot;
    }
    for(int i=1;i<=n;i++)
    {
        while(top&&high[st[top]]<high[i]) siz[i]+=siz[st[top]],f[st[top--]]=i;
        st[++top]=i;
    }
    while(top) siz[n+1]+=siz[st[top]],f[st[top--]]=n+1;
    for(int i=1;i<=n;i++)
    {
        init(f[i],i);
    }
    n++;
    bfs();
    build(1,n,1);
    for(int i=1;i<n;i++)
    {
        add(l[i],l[i]+siz[i]-1,1,1);
        if(i>k)add(l[i-k],l[i-k]+siz[i-k]-1,1,-1);
        if(i>=k) printf("%d ",tree[1].maxn);
    }
}

T3 整数([JLOI2015]有意义的字符串)

求下式的值:

(\lfloor \sqrt{9t^2+4t+\frac{1}{4}}+3t+\frac{1}{2})^n \rfloor mod7528443412579576937

---------------------------------------------------------------------------------------------

就连大爷自己一开始也没想到的神仙题目......

首先，令b=6t+1,d=36t^2+16t+1 则\sqrt{9t^2+4t+\frac{1}{4}}+3t+\frac{1}{2}=\frac{b+\sqrt{d}}{2}。

再令f(n)=(\frac{b+\sqrt d}{2})^n+(\frac{b-\sqrt d}{2})^n，可以根据对称性得出，f(n)应为有理数，因为\sqrt d的系数抵消了。

接下来写出f(n),f(n+1),f(n+2)的值：

显然(#滑稽)： f(n+2)=(6t+1)f(n+1)+tf(n) ，所以写一发矩阵乘法就可以求出f(n)。

然后我们发现：b<\sqrt d<b+1。因此-1<\frac{b-\sqrt d}{2}<0，那么原式的值就和f(n)的值差1，至于+1还是-1和n的奇偶性相关。

神奇思路：3t+\frac{1}{2}+\sqrt{9t^2+4t+\frac{1}{4}}=\frac{-b+\sqrt{\Delta}}{2a}

构造方程：x^2-(6t+1)x-t=0

得到数列：a_{n+2}=(6t+1)a_{n+1}+ta_n

#include<bits/stdc++.h>
using namespace std;
#define mod 7528443412579576937ll
typedef unsigned long long lint;
int m;
lint t,n;
struct matrix
{
    lint num[2][2];
};
lint add(lint a,lint b)
{
    return (a+b>mod)?a+b-mod:a+b;
}
lint multiply(lint a,lint b)
{
    lint sum=0,f=1;
    if(a<0) a=-a,f=-f;
    if(b<0) b=-b,f=-f;
    while(b)
    {
        if(b&1)
        {
            sum=add(sum,a);
            b--;
        }
        a=add(a,a);
        b>>=1;
    }
    return sum*f%mod;
}
matrix A;
matrix multiply(matrix a,matrix b)
{
    matrix c;
    memset(&c,0,sizeof(c));
    for(int i=0;i<=1;i++)
    {
        for(int j=0;j<=1;j++)
        {
            for(int k=0;k<=1;k++)
            {
                c.num[i][j]=add(c.num[i][j],multiply(a.num[i][k],b.num[k][j]));
            }
        }
    }
    return c;
}
matrix E=
{
    1,0,
    0,1
};
matrix ksm(matrix a,lint b)
{
    matrix product=E;
    while(b)
    {
        if(b&1)
        {
            product=multiply(product,a);
            b--;
        }
        a=multiply(a,a);
        b>>=1;
    }
    return product;
}
int main()
{
//  freopen("int.in","r",stdin);
//  freopen("int.out","w",stdout);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%llu%llu",&t,&n);
        if(!n||!t)
        {
            printf("1\n");
            continue;
        }
        A.num[0][0]=(6*t+1)%mod;
        A.num[1][0]=t;
        A.num[0][1]=1;
        A.num[1][1]=0;
        matrix B=ksm(A,n-1);
        printf("%llu\n",add(multiply(B.num[0][0],(6*t+1)),multiply(B.num[1][0],2))+(n&1?0:-1));
    }
}
p.s.$毒瘤大爷，三道题全需要快($gui$)速乘($jia$)，还爆栈，卡空间$FAQ

本场个人得分(30+0+20)=50(不卡空间的话，135，TWT......)

Day 5

周老师：今天考谁的题?

答：ljx的吧......

周老师：好，就考ljx的题!

T1 在水下我们是无敌的([COCI2015] Divljak)

众所周知，九条理希是一个有着强大力量的魔女，现正在Dr.Harris麾下任海军工程部长兼对舰特种战员。

绿元27年，在Dr.Harris#指挥的一场大规模登陆作战期间，我军以黑蛤蟆号为旗舰的舰队受到\mathbb{CC} \pounds国的主力舰队拦截。

混战之中，敌军旗舰“杆孒徳”号不慎独自脱离了战场。亲临战场指挥的Dr.Harris当机立断，命理希前去袭击“杆孒徳”号。

但意想不到的是，“杆孒徳”号作为超重战列舰却有着远超轻型驱逐舰的80kn的航速，在海面上疯狂逮虾户，难以被击中。于是理希决定释放大规模魔法冻住海面，困住“杆孒徳”号。

由于理希记性不好，她对需要背一大堆奇怪咒语的魔法一窍不通，而不巧的是这种冻结魔法就是这样的。

经过理希研究，这种古老的只由小写字母组成的不明所以的冻结魔法的咒语看似冗长，实际只有n个关键词，而念出的咒语只要包含这些关键词就会发挥威力，包含的关键词越多威力越大。

具体规则：

对于吟唱的一个字符串S，如果它包含了关键词s_i，那么关键词s_i将会释放\lvert S \rvert-\lvert s_i\rvert点冷气。

理希背不下来关键词，于是放空大脑，吟唱各种奇怪的字符串，反正最后是成功困住并击沉了“杆孒徳”号。

理希对魔法的效果感到十分惊讶，于是在战后决定再次测试瞎吟唱来发动魔法的效果，这次她请到了你来帮忙记录。

现在你已经知道了这n个关键词，理希会进行q次操作，每次操作为如下格式中的一种：

第一种：1\cdot S 表示理希吟唱了一个字符串S。

第二种：2\cdot a 表示理希询问你此时由第a个关键词所释放的冷气为多少。

---------------------------------------------------------------------------------------------

看到子串考虑建出fail树，之后对于增加的一个字符串，对于其走到的每一个点到fail树根的路径上面的点都会被包含。

这个做法好像叫什么“树链的并”。

简而言之： 所有走到的点按dfs序排序，dfs序相邻的两个点的lca赋上负值，每个走到的点上赋上正值，用树状数组维护。

查询时直接查询对应点所在子树也就是[l[x],r[x]]这个区间就行。至于求\sum \lvert S \rvert-\lvert s_i\rvert嘛，两个树状数组分别记录该点被包含次数和包含它的字符串的总长度。

然而窝铈在了玄学类型转换上......

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
#define N 2000020
#define M 100010
#define lint long long
template<typename TP> inline void read(TP &ret)
{
    TP x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    ret=(TP)x*f;
}
int n;
char s[N];
int pos[M],lx[M];
struct Trie
{
    int to[26],fail;
}tree[N];
int root=1,tot=1;
void insert(char *c,int id)
{
    int len=strlen(c),now=root;
    for(int i=0;i<len;i++)
    {
        int cc=c[i]-'a';
        if(!tree[now].to[cc]) tree[now].to[cc]=++tot;
        now=tree[now].to[cc];
    }
    pos[id]=now;
    lx[id]=len;
}
queue<int> q;
void get_fail()
{
    for(int i=0;i<26;i++)
    {
        tree[0].to[i]=1;
    }
    q.push(root);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            int &v=tree[u].to[i];
            if(v)
            {
                tree[v].fail=tree[tree[u].fail].to[i];
                q.push(v);
            }
            else
            {
                v=tree[tree[u].fail].to[i];
            }
        }
    }
}
struct apple
{
    int to,next;
}indexx[N];
int head[N],cnt;
void init(int x,int y)
{
    indexx[++cnt].to=y;
    indexx[cnt].next=head[x];
    head[x]=cnt;
}
int dep[N],f[N],top[N],siz[N],max_son[N],l[N],r[N],dfn_id;
void dfs1(int u,int fa)
{
    f[u]=fa;
    dep[u]=dep[fa]+1;
    siz[u]=1;
    for(int i=head[u];i;i=indexx[i].next)
    {
        int v=indexx[i].to;
        if(v!=fa)
        {
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[max_son[u]])
            {
                max_son[u]=v;
            }
        } 
    } 
}
void dfs2(int u,int t)
{
    top[u]=t;
    l[u]=++dfn_id;
    if(!max_son[u]) 
    {
        r[u]=dfn_id;
        return;
    }
    dfs2(max_son[u],t);
    for(int i=head[u];i;i=indexx[i].next)
    {
        int v=indexx[i].to;
        if(v!=f[u]&&v!=max_son[u])
        {
            dfs2(v,v);
        }
    }
    r[u]=dfn_id;
}
int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=f[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    return x;
}
int m;
bool cmp(int a,int b)
{
    return l[a]<l[b];
}
lint c1[N],c2[N];
int lowbit(int x)
{
    return x&(-x);
}
void add(lint *c,int p,int x)
{
    while(p<=2000000)
    {
        c[p]+=x;
        p+=lowbit(p);
    }
}
lint query(lint *c,int p)
{
    lint ans=0;
    while(p)
    {
        ans+=c[p];
        p-=lowbit(p);
    }
    return ans;
}
vector<int> val;
int main()
{
//  freopen("invincibility.in","r",stdin);
//  freopen("invincibility.out","w",stdout);
    read(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s);
        insert(s,i);
    }
    get_fail();
    for(int i=2;i<=tot;i++)
    {
        init(tree[i].fail,i);
    }
    dfs1(1,0);
    dfs2(1,1);
    read(m);
    while(m--)
    {
        int op;
        read(op);
        switch(op)
        {
            case 1:
            {
                scanf("%s",s);
                int len=strlen(s),now=root;
                val.clear();
                for(int i=0;i<len;i++)
                {
                    now=tree[now].to[s[i]-'a'];
                    val.push_back(now);
                }
                sort(val.begin(),val.end(),cmp);
                for(int i=0;i<val.size();i++)
                {
                    add(c1,l[val[i]],1);
                    add(c2,l[val[i]],len);
                }
                for(int i=0;i<val.size()-1;i++)
                {
                    add(c1,l[lca(val[i],val[i+1])],-1);
                    add(c2,l[lca(val[i],val[i+1])],-len);
                }
                break;
            }
            case 2:
            {
                int x;
                read(x);
                lint tmp1=(query(c1,r[pos[x]])-query(c1,l[pos[x]]-1))*lx[x];
                lint tmp2=(query(c2,r[pos[x]])-query(c2,l[pos[x]]-1));
                printf("%lld\n",tmp2-tmp1);
                break;
            }
        }
    }
    return 0;
}

T2 牛油果(CF986F Oppa Funcan Style Remastered)

题目背景取自ljx自己被飞来的牛油果砸到的经历......(如果点赞的话，没准我还会告诉你事情的真相......)

众所周知，九条理希是一个可爱的小萝莉。

众所周知，在上一题中她刚刚击沉了“杆孒徳”号战列舰，战斗结束后准备买菜回家。

在这时，从远处突然飞来好几批的牛油果，径直向理希飞来。

理希并没有马上躲避，因为她注意到这些牛油果每一批的数量都是同一个数的约数而且都不为1。

于是她想知道一共有多少牛油果飞了过来。但在这之前一个大牛油果径直打在了理希的头上给她砸晕了。理希醒来之后除了牛油果个数的特点以外什么也记不起来了，所以她按照仅有的记忆猜测有多少牛油果以及那个数是多少。

也就是说，她会询问Q次，每次询问在保证每一波牛油果的个数都是非1的K的因数的前提下，飞过来的牛油果的总数能否是N。

---------------------------------------------------------------------------------------------

我们发现只用k的所有质因数便足以表示k的所有因数，而且k只有50种。 两个以内质因数用exgcd解同余方程即可。 三个以上质因数的话可知它们都不大于100000，跑同余最短路，模数为最小的一个质因数p1，跑完之后对于n，如果dis[n _{mod} k] \leq n则证明可以拼出来。

不知道O(\sqrt{n})分解质因数为什么不会TLE......

反正我写的Pollard-Rho，复杂度O(^3\sqrt{n})，卡不掉的~~~

#include<bits/stdc++.h>
using namespace std;
#define N 200020
typedef long long lint;
template<typename TP> inline void read(TP &ret)
{
    TP x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    ret=(TP)x*f;
}
int t;
struct node
{
    lint n,k;
    int id;
    bool operator<(const node &other)const
    {
        return k<other.k;
    }
}a[10010];
lint bas[5]={2,3,7,61,24251};
lint gcd(lint x,lint y)
{
    if(!y)
    {
        return x;
    }
    return gcd(y,x%y);
}
lint add(lint a,lint b,lint mod)
{
    return (a+b>mod)?a+b-mod:a+b;
}
lint ksc(lint a,lint b,lint mod)
{
    lint sum=0;
    while(b)
    {
        if(b&1)
        {
            sum=add(sum,a,mod);
            b--;
        }
        a=add(a,a,mod);
        b>>=1;
    }
    return sum%mod;
}
lint ksm(lint a,lint b,lint mod)
{
    lint product=1;
    while(b)
    {
        if(b&1)
        {
            product=ksc(product,a,mod);
            b--;
        }
        a=ksc(a,a,mod);
        b>>=1;
    }
    return product%mod;
}
bool Miller_Rabin(lint x,lint b)
{
    if(ksm(b,x-1,x)!=1) return 0;
    lint k=x-1;
    while(!(k&1))
    {
        k>>=1;
        lint d=ksm(b,k,x);
        if(d!=1&&d!=x-1) return 0;
        if(d==x-1) return 1;
    }
    return 1;
}
bool Miller_Rabin(lint x)
{
    if(x<2||x==46856248255981) return 0;
    for(int i=0;i<5;i++)
    {
        if(x==bas[i]) return 1;
    }
    for(int i=0;i<5;i++)
    {
        if(!Miller_Rabin(x,bas[i])) return 0;
    }
    return 1;
}
lint Mandelbrot(lint x,lint c,lint p)
{
    return (ksc(x,x,p)+c)%p;
}
lint Pollard_Rho(lint x)
{
    lint s,t,c=1ll*rand()%(x-1)+1;
    s=t=0;
    lint val=1;
    int goal=1;
    for(;;goal<<=1,s=t,val=1)
    {
        for(int i=1;i<=goal;i++)
        {        
            t=Mandelbrot(t,c,x);
            val=ksc(val,abs(t-s),x);
            if(!(i%127))
            {
                lint g=gcd(val,x);
                if(g>1) return g;
            }
        }
        lint g=gcd(val,x);
        if(g>1) return g;
    }
}
vector<lint> fac;
lint min_factor;
void divide(lint x)
{
    if(x<2)
    {
        return;
    }
    if(Miller_Rabin(x))
    {
        min_factor=min(min_factor,x);
        fac.push_back(x);
        return;
    }
    lint p=x;
    while(p>=x) p=Pollard_Rho(x);
    while(!(x%p))
    {
        x/=p;
    }
    divide(x);
    divide(p);
}
lint exgcd(lint a,lint b,lint &x,lint &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    lint d=exgcd(b,a%b,x,y);
    lint res=x;
    x=y;
    y=res-a/b*y;
    return d;
}
lint dis[N];
bool vis[N];
queue<int> q;
void spfa(lint mod)
{
    for(int i=0;i<mod;i++)
    {
        dis[i]=1000000000000000000ll;
        vis[i]=0;
    }
    dis[0]=0;
    q.push(0);
    vis[0]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=1;i<fac.size();i++)
        {
            int v=(u+fac[i])%mod;
            if(dis[v]>dis[u]+fac[i])
            {
                dis[v]=dis[u]+fac[i];
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
bool ans[10010];
int main()
{
//  freopen("bpk.in","r",stdin);
//  freopen("bpk.out","w",stdout);
    srand(time(NULL));
    read(t);
    for(int i=1;i<=t;i++)
    {
        read(a[i].n),read(a[i].k);
        a[i].id=i;
    }
    sort(a+1,a+t+1);
    for(int i=1;i<=t;i++)
    {
        int now=i;
        while(now<t&&a[now+1].k==a[i].k) now++;
        if(a[i].k==1)
        {
            i=now;
            continue;
        }
        fac.clear();
        min_factor=1000000000000000000ll;
        divide(a[i].k); 
        sort(fac.begin(),fac.end());
        if(fac.size()==1)
        {
            for(int j=i;j<=now;j++)
            {
                if(!(a[j].n%fac[0])) ans[a[j].id]=1;
            }
            i=now;
            continue;
        }
        if(fac.size()==2)
        {
            lint x,y;
            lint g=exgcd(fac[0],fac[1],x,y);
            lint b=fac[1]/g;
            x=add(x,b,b);
            for(int j=i;j<=now;j++)
            {
                if(!(a[j].n%g))
                {
                    lint dx=x,dy=y;
                    dx=ksc(dx,a[j].n/g,b);
                    dy=(a[j].n-fac[0]*dx)/fac[1];
                    if(dy>=0) ans[a[j].id]=1;
                }
            }
            i=now;
            continue;
        }
        spfa(min_factor);
        for(int j=i;j<=now;j++)
        {
            if(dis[a[j].n%min_factor]<=a[j].n) ans[a[j].id]=1;
        }
        i=now;
    }
    for(int i=1;i<=t;i++)
    {
        printf("%s\n",ans[i]?"YES":"NO");
    }
    return (0^0);
}

T3 孕育禁果的蔷薇(CF1140G Double Tree)

众所周知，九条理希是一个强大的魔女。

众所周知就在上一题理希被牛油果砸晕了，在这之后，她灵机一动创作了一个的可以扔水果攻击的魔法，命名为Rose Pregnant With Forbidden Fruit。 所谓什么Rose Pregnant With Forbidden Fruit的奇怪玩意就是一棵有n个点的带边权的树。

由于是由理希的魔力凝结而成，这棵树有着奇特的力量，它上面的每个节点都一分为二。

说白了这棵树有n对节点，第i对节点的编号分别是i*2-1,i*2。

这棵树有三组边：

第一组：对于每个i \epsilon [1,n],i*2-1和i*2之间有一条边。

第二组：对于所有奇数点，共有n-1条边将它们连接成一棵树。

第三组：对于每一条第二组中的边u->v，则有一条边u+1->v+1，虽然这一对边的权值不一定相同。

问题很简单了：因为理希要尽量减少魔力流动的损耗以便尽可能多地用这个魔法蹂躏Slizard，她给你q组询问，每次询问一对点x,y之间的最短路

---------------------------------------------------------------------------------------------

首先将这个咋看都是图的玩意重新变为每个点有两个状态的树。

可以先通过树上DP求出每个点转换状态的最小花费。

在这之后我们要考虑一下如何求出任意两点到LCA的花费。

设dp[x][j][sx][sf]为由sx状态的点x转换到sf状态的f[x][j]的花费，这个是可以在倍增求LCA的过程中合并的。

之后对于一对点的询问的答案将在求LCA过程中得出。

ljx本人口口声声说只有离线Tarjan能过，可我改完的倍增跑的比ta快多了......

倍增版：

#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
#define N 600060
template<typename TP> inline void read(TP &ret)
{
    TP x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    ret=(TP)x*f;
}
int n;
lint a[N];
int lg2[N];
struct apple
{
    int to,next;
    lint val1,val2;
}indexx[N];
int head[N],cnt;
void init(int x,int y,lint z,lint w)
{
    indexx[++cnt].to=y;
    indexx[cnt].val1=z;
    indexx[cnt].val2=w;
    indexx[cnt].next=head[x];
    head[x]=cnt;
}
lint dp[N][20][2][2];
int f[N][20];
int dep[N];
void switch01(int u,int fa)
{
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=head[u];i;i=indexx[i].next)
    {
        int v=indexx[i].to;
        if(v!=fa)
        {
            switch01(v,u);
            a[u]=min(a[u],indexx[i].val1+a[v]+indexx[i].val2);
        }
    }
}
void switch10(int u,int fa)
{
    for(int i=head[u];i;i=indexx[i].next)
    {
        int v=indexx[i].to;
        if(v!=fa)
        {
            a[v]=min(a[v],indexx[i].val1+a[u]+indexx[i].val2);
            switch10(v,u);
        }
    }
}
void dfs1(int u,int fa)
{
    for(int i=head[u];i;i=indexx[i].next)
    {
        int v=indexx[i].to;
        if(v!=fa)
        {
            dp[v][0][0][0]=min(indexx[i].val1,indexx[i].val2+a[u]+a[v]);
            dp[v][0][0][1]=min(a[v]+indexx[i].val2,a[u]+indexx[i].val1);
            dp[v][0][1][0]=min(a[v]+indexx[i].val1,a[u]+indexx[i].val2);
            dp[v][0][1][1]=min(indexx[i].val2,indexx[i].val1+a[u]+a[v]);
            dfs1(v,u);
        }
    }
}
void up()
{
    for(int j=1;j<=lg2[n];j++)
    {
        for(int i=1;i<=n;i++)
        {
            f[i][j]=f[f[i][j-1]][j-1];
            dp[i][j][0][0]=min(dp[i][j-1][0][0]+dp[f[i][j-1]][j-1][0][0],dp[i][j-1][0][1]+dp[f[i][j-1]][j-1][1][0]);
            dp[i][j][0][1]=min(dp[i][j-1][0][0]+dp[f[i][j-1]][j-1][0][1],dp[i][j-1][0][1]+dp[f[i][j-1]][j-1][1][1]);
            dp[i][j][1][0]=min(dp[i][j-1][1][0]+dp[f[i][j-1]][j-1][0][0],dp[i][j-1][1][1]+dp[f[i][j-1]][j-1][1][0]);
            dp[i][j][1][1]=min(dp[i][j-1][1][1]+dp[f[i][j-1]][j-1][1][1],dp[i][j-1][1][0]+dp[f[i][j-1]][j-1][0][1]);
        }
    }
}
int m;
int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=lg2[n];i>=0;i--)
    {
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    }
    if(x==y) return x;
    for(int i=lg2[n];i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
lint f1[N],f2[N];
lint solve(int x,int y)
{
    int u=(x+1)>>1,v=(y+1)>>1;
    if(dep[u]<dep[v])
    {
        swap(u,v);
        swap(x,y);
    }
    int lc=lca(u,v);
    f1[(x+1)&1]=0;
    f1[((x+1)&1)^1]=a[u];
    for(int i=lg2[n];i>=0;i--)
    {
        if(dep[f[u][i]]>=dep[lc])
        {
            lint w0=f1[0],w1=f1[1];
            f1[0]=min(w0+dp[u][i][0][0],w1+dp[u][i][1][0]);
            f1[1]=min(w0+dp[u][i][0][1],w1+dp[u][i][1][1]);
            u=f[u][i];
        }
    }
    u=v;
    f2[(y+1)&1]=0;
    f2[((y+1)&1)^1]=a[u];
    for(int i=lg2[n];i>=0;i--)
    {
        if(dep[f[u][i]]>=dep[lc])
        {
            lint w0=f2[0],w1=f2[1];
            f2[0]=min(w0+dp[u][i][0][0],w1+dp[u][i][1][0]);
            f2[1]=min(w0+dp[u][i][0][1],w1+dp[u][i][1][1]);
            u=f[u][i];
        }
    }
    return min(f1[0]+f2[0],f1[1]+f2[1]);
}
int main()
{
//  freopen("rose.in","r",stdin);
//  freopen("rose.out","w",stdout);
    read(n);
    lg2[1]=0;
    for(int i=2;i<=n;i++)
    {
        lg2[i]=lg2[i>>1]+1;
    }
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        lint z,w;
        read(x),read(y),read(z),read(w);
        init(x,y,z,w);
        init(y,x,z,w);
    }
    memset(&dp,127/2,sizeof(dp));
    switch01(1,0);
    switch10(1,0);
    dfs1(1,0);
    up();
    read(m);
    while(m--)
    {
        int x,y;
        read(x),read(y);
        printf("%lld\n",solve(x,y));
    }
}

离线Tarjan版：

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::min;
typedef long long lint;
const int N=300069,M=600069;
template<typename TP>
inline void read(TP &_t)
{
    TP _r=0,_f=1;char _c=getchar();
    while(_c<'0'||_c>'9'){if(_c=='-')_f=-1;_c=getchar();}
    while(_c>='0'&&_c<='9'){_r=_r*10+_c-'0';_c=getchar();}
    _t=_r*_f;
}
struct sumireko{int to,ne;lint w1,w2;}e[M];
int he[N],ecnt;
void addline(int f,int t,lint w1,lint w2)
{
    e[++ecnt].to=t;
    e[ecnt].ne=he[f];
    e[ecnt].w1=w1,e[ecnt].w2=w2;
    he[f]=ecnt;
}
int n;
lint scost[N];
void gsc1(int x,int f)
{
    for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)
        if(t!=f) gsc1(t,x),scost[x]=min(scost[x],scost[t]+e[i].w1+e[i].w2);
}
void gsc2(int x,int f)
{
    for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)
        if(t!=f) scost[t]=min(scost[t],scost[x]+e[i].w1+e[i].w2),gsc2(t,x);
}
/*
    *0->00
    *1->01
    *2->10
    *3->11
*/
lint dp[N][4];
void gdp(int x,int f)
{
    for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)
        if(t!=f)
            dp[t][0]=min(e[i].w1,e[i].w2+scost[x]+scost[t]),
            dp[t][1]=min(e[i].w2+scost[t],e[i].w1+scost[x]),
            dp[t][2]=min(scost[x]+e[i].w2,e[i].w1+scost[t]),
            dp[t][3]=min(e[i].w2,e[i].w1+scost[x]+scost[t]),
            gdp(t,x);
}
void get_switch_cost(){gsc1(1,0),gsc2(1,0),gdp(1,0);}
int fa[N];
int T;
void find(int x)
{
    if(fa[x]!=fa[fa[x]])
    {
        find(fa[x]);
        int f=fa[x];
        dp[0][0]=dp[0][1]=dp[0][2]=dp[0][3]=0;
        dp[0][0]=min(dp[x][0]+dp[f][0],dp[x][1]+dp[f][2]);
        dp[0][1]=min(dp[x][0]+dp[f][1],dp[x][1]+dp[f][3]);
        dp[0][2]=min(dp[x][2]+dp[f][0],dp[x][3]+dp[f][2]);
        dp[0][3]=min(dp[x][3]+dp[f][3],dp[x][2]+dp[f][1]);
        memcpy(dp[x],dp[0],sizeof(dp[x]));
        fa[x]=fa[fa[x]];
    }
}
struct ques{int ne,id;}q[M<<1];
int qh[N],qcnt;
void addques(int f,int id)
{
    q[++qcnt].id=id;
    q[qcnt].ne=qh[f];
    qh[f]=qcnt;
}
int qt[M<<1][2],qs[M<<1];
struct gat{int id,ne;}g[M<<1];
int gh[N],gcnt;
void addgat(int f,int id)
{
    g[++gcnt].id=id;
    g[gcnt].ne=gh[f];
    gh[f]=gcnt;
}

bool vv[N];
lint ans[M];
void dfs(int x,int f)
{
    vv[x]=1;
    for(int i=qh[x],t;i;i=q[i].ne)
    {
        t=qt[q[i].id][1];
        if(vv[t]) find(t),addgat(fa[t],q[i].id);
    }
    for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)
        if(t!=f) dfs(t,x),fa[t]=x;
    for(int i=gh[x],id;i;i=g[i].ne)
    {
        id=g[i].id;
        if(qt[id][1]!=x)
        {
            int xi=qt[id][0],yi=qt[id][1];
            int xp=qs[id]>>1,yp=qs[id]&1;
            find(xi),find(yi);
            ans[id>T?id-T:id]=min(dp[xi][xp<<1]+dp[yi][yp<<1],dp[xi][(xp<<1)|1]+dp[yi][(yp<<1)|1]);
        }
        else find(qt[id][0]),ans[id>T?id-T:id]=dp[qt[id][0]][qs[id]];
    }
}

int xi,yi,xp,yp;
lint wi1,wi2;
signed main()
{
//  freopen("rose.in","r",stdin);
//  freopen("rose.out","w",stdout);
    read(n);
    for(int i=1;i<=n;i++) read(scost[i]),fa[i]=i;
    for(int i=1;i<n;i++) read(xi),read(yi),read(wi1),read(wi2),addline(xi,yi,wi1,wi2),addline(yi,xi,wi1,wi2);
    get_switch_cost();
    read(T);
    for(int i=1;i<=T;i++)
    {
        read(xi),read(yi);
        xp=(xi&1)^1,xi=xi+1>>1;
        yp=(yi&1)^1,yi=yi+1>>1;
        qt[i][0]=qt[i+T][1]=xi;
        qt[i][1]=qt[i+T][0]=yi;
        qs[i]=(xp<<1)|yp,qs[i+T]=(yp<<1)|xp;
        if(xi==yi){ans[i]=xp==yp?0:scost[xi];continue;}
        addques(xi,i),addques(yi,i+T);
    }
    dfs(1,0);
    for(int i=1;i<=T;i++) printf("%I64d\n",ans[i]);
    return 0;
}

本场得分(100+100+40)=240(不考虑类型转换上出的锅TwT)

持续更新中......