2018年5月

Problem

Bob有一棵 n 个点的有根树,其中1号点是根节点。Bob在每个点上涂了颜色,并且每个点上的颜色不同。

定义一条路径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色。

Bob可能会进行这几种操作:

1 x
把点 x 到根节点的路径上所有的点染上一种没有用过的新颜色。

2 x y
求 x 到 y 的路径的权值。

3 x
在以x为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值。

Bob一共会进行 m 次操作

Solution

emm我并没做出来
我一开始想着怎么维护让一段区间的点的所有为0的儿子变成1,然后这思路有各种问题
我果然还是太年轻

题解传送门:https://www.luogu.org/blog/newuser/solution-p3703

重点在于怎么快速进行操作1,操作2/3的思路都差不多
树剖的做法是暴力更改??恕我没看懂代码...

一种优美的做法是LCT的Access本质思想应用?
果然每种专题都有对本质思想的应用啊..

以及我一开始的查询其实是num[a]+num[b]-num[lca(a,b)]-num[fa[lca(a,b)]]类似这样的
然后这玩意是错的
所以为什么呢,请看下面的代码把ww

Code

// Code by ajcxsu
// Problem: color on the tree

#include<bits/stdc++.h>
using namespace std;

template <typename T> inline void gn(T &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
} 

const int N=1e5+10, M=2e5+10;
int n,m;
int h[N], to[M], nexp[M], p=1;
inline void ins(int a,int b) {
    nexp[p]=h[a], h[a]=p, to[p]=b, p++;
}

namespace ST {
    #define ls x<<1
    #define rs x<<1|1
    int num[N*6], t[N*6];
    inline void pud(int x) {
        if(!t[x]) return;
        t[ls]+=t[x], t[rs]+=t[x];
        num[ls]+=t[x], num[rs]+=t[x];
        t[x]=0;
    }
    void updata(int x, int l, int r, int xl, int xr, int d) {
        pud(x);
        if(xl<=l && r<=xr) {
            num[x]+=d, t[x]+=d;
            return;
        }
        int mid=(l+r)>>1;
        if(xl<=mid) updata(ls, l, mid, xl, xr, d);
        if(xr>mid) updata(rs, mid+1, r, xl, xr, d); // 使得区间一定有交集,避免无谓的搜索 
        num[x]=max(num[ls], num[rs]);
    }
    int query(int x, int l, int r, int xl, int xr) {
        pud(x);
        if(xl<=l && r<=xr) return num[x];
        int mid=(l+r)>>1;
        if(xr<=mid) return query(ls, l, mid, xl, xr);
        else if(xl>mid) return query(rs, mid+1, r, xl, xr);
        else return max(query(ls, l, mid, xl, mid), query(rs, mid+1, r, mid+1, xr));
    }
}

int dep[N], son[N], fa[N], siz[N];
int dfn[N], top[N], idx;
int nl[N], nr[N];

struct Node *nil;
struct Node {
    int id;
    Node *f, *ch[2];
    Node (int id=0):id(id) {
        f=ch[0]=ch[1]=nil;
    }
    bool nroot() {
        return f->ch[0]==this || f->ch[1]==this;
    }
    int dir() {
        if(!nroot()) return -1;
        return f->ch[1]==this;
    }
} *nd[N];
void ini() {
    nil=new Node;
    nil->f=nil->ch[0]=nil->ch[1]=nil;
}

void rot(Node *x) {
    Node *y=x->f, *z=y->f;
    int d=x->dir();
    y->ch[d]=x->ch[!d];
    if(x->ch[!d]!=nil) x->ch[!d]->f=y;
    x->f=z;
    if(y->dir()!=-1) z->ch[y->dir()]=x;
    x->ch[!d]=y, y->f=x;
}

void splay(Node *x) {
    Node *y; 
    while(x->nroot()) {
        y=x->f;
        if(!y->nroot()) rot(x);
        else if(y->dir() == x->dir()) rot(y), rot(x);
        else rot(x), rot(x);
    }
}

Node *find(Node *r) {
    while(r->ch[0]!=nil) r=r->ch[0];
    return r;
}

void access(Node *x) {
    Node *y=nil;
    int a;
    while(x!=nil) {
        splay(x);
        if(x->ch[1]!=nil) {
            a=find(x->ch[1])->id;
            ST::updata(1, 1, n, nl[a], nr[a], 1);
        }
        x->ch[1]=y;
        if(y!=nil) {
            a=find(y)->id;
            ST::updata(1, 1, n, nl[a], nr[a], -1);
        }
        y=x, x=x->f;
    }
}

void dfs1(int x, int k) {
    dep[x]=k, siz[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(!dep[to[u]]) {
            fa[to[u]]=x, nd[to[u]]->f=nd[x], dfs1(to[u], k+1);
            siz[x]+=siz[to[u]];
            if(siz[to[u]]>siz[son[x]]) son[x]=to[u];
        }
}
void dfs2(int x, int t) {
    nl[x]=dfn[x]=++idx;
    ST::updata(1, 1, n, dfn[x], dfn[x], dep[x]);
    top[x]=t;
    if(son[x]) dfs2(son[x], t);
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) dfs2(to[u], to[u]);
    nr[x]=idx;
}
int lca(int x,int y) {
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) return y;
    return x; 
}

int main() {
    ini();
    gn(n), gn(m);
    int u,v;
    for(int i=1;i<n;i++) gn(u), gn(v), ins(u,v), ins(v,u);
    for(int i=1;i<=n;i++) nd[i]=new Node(i);
    dfs1(1,1), dfs2(1,1);
    int a,b,c,d;
    while(m--) {
        gn(a), gn(b);
        if(a==1) access(nd[b]);
        else if(a==2) {
            gn(c), d=lca(b,c);
            printf("%d\n", ST::query(1,1,n,dfn[b],dfn[b])+ST::query(1,1,n,dfn[c],dfn[c])
                            -2*ST::query(1,1,n,dfn[d],dfn[d])+1); // 由于两个都减去了d所在的splay,因此得把它加回来
            // 由于fa[d]和d有可能是在同一个splay,所以仍然导致少算上一个splay 
        }
        else if(a==3) printf("%d\n", ST::query(1,1,n,nl[b],nr[b]));
    }
    return 0;
}

Problem

程序有赋值语句和声明语句
a[<value>]
a[<expression>]=<expression>/<value>
模拟程序,并找出两种BUG:

  • 越界
  • 调用了未声明的变量

Solution

填了个远古大坑。
STL全家福+完全乱搞

// Code by ajcxsu
// Problem: BUGHUNT

#include<bits/stdc++.h>
using namespace std;

int lim[500];
map<int, int> ma[500];

bool found;
typedef pair<char, int> mpair;
mpair analyze(string x) {
    vector<char> stk;
    string num;
    for(int i=0;i<x.size();i++) 
        if((x[i]>='a' && x[i]<='z') || (x[i]>='A' && x[i]<='Z')) stk.push_back(x[i]);
        else if(x[i]>='0' && x[i]<='9') num+=x[i]; 
    int nx=stoi(num);
    if(stk.size()==0) return mpair('*', nx);
    for(int i=stk.size()-1;i>0;i--) {
        if(nx<=lim[stk[i]] && ma[stk[i]].count(nx)) nx=ma[stk[i]][nx];
        else { 
            found=1;
            break;
        }
    }
    return mpair(stk[0], nx);
}

int main() {
    string cmd;
    while(1) {
        memset(lim,-1,sizeof(lim));
        for(int i=0;i<500;i++) ma[i].clear();
        found=0;
        cin>>cmd;
        if(cmd[0]=='.') break;
        int cnt=0;
        do {
            cnt++;
            string a, b;
            mpair ra, rb;
            bool ass=false;
            for(int i=0;i<cmd.size();i++)
                if(cmd[i]=='=') a=cmd.substr(0, i), b=cmd.substr(i+1, cmd.size()-i), ass=true;
            if(ass) {
                ra=analyze(a), rb=analyze(b);
                if(!found && lim[ra.first]>=ra.second && rb.first=='*') 
                    ma[ra.first][ra.second]=rb.second; 
                else if(!found && lim[rb.first]>=rb.second && ma[rb.first].count(rb.second) && lim[ra.first]>=ra.second)
                    ma[ra.first][ra.second]=ma[rb.first][rb.second];
                else found=1;
            }
            else ra=analyze(cmd), lim[ra.first]=ra.second-1;
            if(found) {
                while(cmd[0]!='.') cin>>cmd;
                cout<<cnt<<endl;
            }
            else cin>>cmd;
        } while(cmd[0]!='.'); 
        if(!found) cout<<0<<endl; 
    }

    return 0;
}

Solution

酷爱日料的小Z经常光顾学校东门外的回转寿司店。在这里,一盘盘寿司通过传送带依次呈现在小Z眼前。不同的寿
司带给小Z的味觉感受是不一样的,我们定义小Z对每盘寿司都有一个满意度,例如小Z酷爱三文鱼,他对一盘三文
鱼寿司的满意度为10;小Z觉得金枪鱼没有什么味道,他对一盘金枪鱼寿司的满意度只有5;小Z最近看了电影“美
人鱼”,被里面的八爪鱼恶心到了,所以他对一盘八爪鱼刺身的满意度是-100。特别地,小Z是个著名的吃货,他
吃回转寿司有一个习惯,我们称之为“狂吃不止”。具体地讲,当他吃掉传送带上的一盘寿司后,他会毫不犹豫地
吃掉它后面的寿司,直到他不想再吃寿司了为止。今天,小Z再次来到了这家回转寿司店,N盘寿司将依次经过他的
面前,其中,小Z对第i盘寿司的满意度为Ai。小Z可以选择从哪盘寿司开始吃,也可以选择吃到哪盘寿司为止,他
想知道共有多少种不同的选择,使得他的满意度之和不低于L,且不高于R。注意,虽然这是回转寿司,但是我们不
认为这是一个环上的问题,而是一条线上的问题。即,小Z能吃到的是输入序列的一个连续子序列;最后一盘转走
之后,第一盘并不会再出现一次。

Problem

有趣的题目。

按照套路,前缀和$S_i$。

题目变成了要求$l\leq S_j-S_i\leq r\ (0\leq i < j)$,满足条件的(i,j)对数。

然后化一下变成了$S_j-r\leq S_i \leq S_j-l$。

然后把出现的数字离散化一下。

然后树状数组统计范围内数字个数就行了。

Code

// Code by ajcxsu
// Problem: round_sushi

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e6+10;
ll S[N];
ll lisan[N];
int p=1;
ll ans=0;
map<ll, int> na;

int C[N];
#define lowbit(x) x&-x
void updata(int x, int d) {
    while(x<N) {
        C[x]+=d;
        x+=lowbit(x);
    }
}
int query(int x) {
    int ret=0;
    while(x) {
        ret+=C[x];
        x-=lowbit(x);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    ll l,r;
    cin>>n>>l>>r;
    for(int i=1;i<=n;i++) cin>>S[i], S[i]+=S[i-1], lisan[p++]=S[i], lisan[p++]=S[i]-r-1, lisan[p++]=S[i]-l; 
    sort(lisan, lisan+p);
    p=unique(lisan, lisan+p)-lisan;
    for(int i=0;i<p;i++) {
        na[lisan[i]]=i+1;
    }
    updata(na[0],1);
    for(int i=1;i<=n;i++) {
        ans+=query(na[S[i]-l])-query(na[S[i]-r-1]);
        updata(na[S[i]],1);
    }
    cout<<ans<<endl;
    return 0;
} 

Problem

为了得到书法大家的真传,小 E 同学下定决心去拜访住在魔法森林中的隐 士。魔法森林可以被看成一个包含 n 个节点 m 条边的无向图,节点标号为 1,2,3,…,n,边标号为 1,2,3,…,m。初始时小 E 同学在 1 号节点,隐士则住在 n 号节点。小 E 需要通过这一片魔法森林,才能够拜访到隐士。

魔法森林中居住了一些妖怪。每当有人经过一条边的时候,这条边上的妖怪 就会对其发起攻击。幸运的是,在 1 号节点住着两种守护精灵:A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量,达到自己的目的。

只要小 E 带上足够多的守护精灵,妖怪们就不会发起攻击了。具体来说,无 向图中的每一条边 ei 包含两个权值 ai 与 bi 。若身上携带的 A 型守护精灵个数不 少于 ai ,且 B 型守护精灵个数不少于 bi ,这条边上的妖怪就不会对通过这条边 的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向 小 E 发起攻击,他才能成功找到隐士。

由于携带守护精灵是一件非常麻烦的事,小 E 想要知道,要能够成功拜访到 隐士,最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的 个数与 B 型守护精灵的个数之和。

Solution

我觉得自己最终算是想出来了这题怎么做orz

两个权值难维护。因此按$a_i$排序,之后到了满足$a_i$的边就把边加到图中。现在的问题就是查找目前图中1到n的路径上最大$b_i$的最小值。

维护一个最小生成树即可。即维护整个图为一棵生成树。插入一条边如果形成环,将环上的最大边删去。这样可以保证解不会更差。因为1到n的路径若经过了最大边,则走另一条路径肯定可以更小。若没经过,则1到n的路径可以选择不经过新增的边(因为原本这里没有联通,联通之后不走也是一回事),则保证这个路径不会变得更差。

按照这样的贪心想法,用LCT来维护这样的操作就行了(找最大边并删去,然后加入新边)。

也不一定要求现在一定是一棵生成树。如果此时1跟n联通了,split(1,n)更新一下答案就OK了~

然而如何找边删边?
我一开始以为只要把某个边权随便转移到一个点上就OK了,结果这样是不行的orz

按照xzz的做法,把边换成点,记录一下边点所连接的两个点,只有边点带上权值就行了~

话说这题绝对比那个国集队的Tree要难吧

Code

// Code by ajcxsu
// Problem: magic forest

#include<bits/stdc++.h>
using namespace std;

inline void gn(int &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=3e5+10, M=5e4+10;
struct Node *nil;
struct Node {
    bool tag;
    int ma, val, id;
    Node *f, *ch[2], *man, *u, *v;
    Node(int va=0, int id=0):tag(0), ma(va), val(va), id(id) { 
        u=v=f=ch[0]=ch[1]=nil;
        man=this;
    }
    bool nroot() {
        return f->ch[0]==this || f->ch[1]==this;
    } 
    int dir() {
        if(!nroot()) return -1;
        return f->ch[1]==this;
    }
    void pud() {
        if(!tag) return;
        tag=0;
        swap(ch[0], ch[1]), ch[0]->tag^=1, ch[1]->tag^=1;
    }
    void upd() {
        ma=val, man=this;
        if(ch[0]->ma>ma) ma=ch[0]->ma, man=ch[0]->man;
        if(ch[1]->ma>ma) ma=ch[1]->ma, man=ch[1]->man;
    }
} *nd[N];
void ini() {
    nil=new Node(0);
    nil->u=nil->v=nil->ch[0]=nil->ch[1]=nil->f=nil;
}

void rot(Node *x) {
    Node *y=x->f, *z=y->f;
    int d=x->dir();
    y->ch[d]=x->ch[!d];
    if(x->ch[!d]!=nil) x->ch[!d]->f=y;
    x->f=z;
    if(y->dir()!=-1) z->ch[y->dir()]=x;
    x->ch[!d]=y, y->f=x;
    y->upd(); 
}

Node* stk[N];
void splay(Node *x) {
    Node *y=x;
    int z=0;
    stk[++z]=y;
    while(y->nroot()) stk[++z]=y=y->f;
    while(z) stk[z--]->pud();
    while(x->nroot()) {
        y=x->f;
        if(!y->nroot()) rot(x);
        else if(y->dir()==x->dir()) rot(y), rot(x);
        else rot(x), rot(x); 
    }
    x->upd();
}

void access(Node *x) {
    Node *y=nil;
    while(x!=nil) {
        splay(x), x->ch[1]=y, x->upd();
        y=x, x=x->f;
    }
}

void makeroot(Node *x) {
    access(x), splay(x);
    x->tag^=1;
}

int fa[N];
int Find(int x) {
    if(!fa[x]) return x;
    return fa[x]=Find(fa[x]);
}
bool Union(int a, int b) {
    int af=Find(a), bf=Find(b);
    if(af!=bf) fa[af]=bf;
    return af!=bf;
}

void split(Node *x, Node *y) {
    makeroot(x), access(y), splay(y);
}

void link(Node *x, Node *y) {
    makeroot(x); 
    x->f=y;
}
void cut(Node *x, Node *y) {
    split(x,y);
    x->f=y->ch[0]=nil, y->upd(); 

}

struct Edge {
    int u,v,b,id;
};
vector<Edge> as[N];

int main() {
    ini();
    int n,m;
    int u,v,a,b;
    gn(n), gn(m);
    for(int i=1;i<=n;i++) nd[i]=new Node(0,i);
    for(int i=1;i<=m;i++) {
        gn(u), gn(v), gn(a), gn(b);
        as[a].push_back({u,v,b,i+M});
        nd[i+M]=new Node(b, i+M);
        nd[i+M]->u=nd[u], nd[i+M]->v=nd[v];
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<=50000;i++) {
        for(int j=0, len=as[i].size();j<len;j++) {
            u=as[i][j].u, v=as[i][j].v, b=as[i][j].b, a=as[i][j].id;
            if(!Union(u,v)) {
                split(nd[u], nd[v]);
                if(nd[v]->ma>b) {
                    Node *aim=nd[v]->man;
                    cut(aim->u, aim);
                    cut(aim, aim->v);
                    link(nd[u], nd[a]), link(nd[a], nd[v]);
                }
            }
            else link(nd[u], nd[a]), link(nd[a], nd[v]);
        }
        if(Find(1)!=Find(n)) continue;
        split(nd[1], nd[n]);
        ans=min(ans, i+nd[n]->ma);
    }
    if(ans!=0x3f3f3f3f) printf("%d\n", ans);
    else printf("-1\n");
    return 0;
}