Codeforces Round #805 (Div. 3)（A~G）

比赛链接：Dashboard - Codeforces Round #805 (Div. 3) - Codeforces

这波偷偷拿小小号，估计能上400+分吧，没有做出G题...太菜了，我估摸着这回G题得有2000分？

周中没有几场，这场搞到唯一一天假可累死我了！下午还有robocom...

这场前几题简直是STL专场..

这场重点在EFG题。

A. Round Down the Price（模拟）

直接按照题意最高位-1即可，也可以用字符串。我这里是写一个函数找有多少位，比如有3位就减去100.
参考代码：

inline int calc(int x)
{
    int res = 1;
    while (x>=10)
    {
        x/=10;
        res*=10;
    }
    return res;
}//找有多少位数字
inline void Case_Test()
{
    cin>>x;
    cout<<x-calc(x)<<endl;
}

B. Polycarp Writes a String from Memory（模拟）

按照题意模拟，我用一个set来存，如果size==3并且接下来一个数不在set里面，那么就清空并计数。
参考代码：

inline void Case_Test()
{
    cin>>s;
    n = s.size();
    set<char> st;//用来存放出现的字符是什么（不超过三个）
    ans = 1;
    for (int i=0;i<n;i++)
    {
        if (st.size()==3&&st.find(s[i])==st.end())//如果正好为3个并且在set中没有出现，需要清空计数
        {
            ans++;//计数
            st.clear();//情况
            st.insert(s[i]);//当前这个算上去
        }
        if (st.find(s[i])==st.end())
            st.insert(s[i]);//当前没出现，需要加上
    }
    cout<<ans<<endl;
}

C. Train and Queries（模拟）

每次对于x,y寻找第一个位置pos，然后找y中是否有pos之后的数。我用的set容器，然后因为数字很大所以用了离散化。

map<int,int> mp;
vector<int> v[N];
set<int> st[N];
inline void Case_Test()
{
    cin>>n>>m;
    mp.clear();cnt = 0;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        if (mp.find(x)==mp.end())
            mp[x]=++cnt;
        //v[mp[x]].push_back(i);
        st[mp[x]].insert(i);
    }
    while (m--)
    {
        cin>>x>>y;
        if (mp.find(x)==mp.end()||mp.find(y)==mp.end())
        {
            cout<<"NO"<<endl;
            continue;
        }
        int pos = *st[mp[x]].begin();
        if (st[mp[y]].lower_bound(pos)==st[mp[y]].end())
        {
            cout<<"NO"<<endl;
            continue;
        }
        cout<<"YES"<<endl;
    }
    for (int i=1;i<=cnt;i++)
        st[i].clear();
}

D. Not a Cheap String（贪心）

sort+排序，每次减最大的就行。
参考代码：

struct node
{
    char c;
    int id;
}ch[N];
inline void Case_Test()
{
    cin>>s>>p;
    n = s.size();
    s = '#'+s;
    int sum = 0;
    for (int i=1;i<=n;i++)
    {
        vis[i] = 1;
        ch[i].c = s[i];
        ch[i].id = i;
        sum += s[i]-'a'+1;
    }
    sort(ch+1,ch+n+1,[](node a,node b){return a.c>b.c;});//字符从大到小排序
    int t = 1;
    while (sum>p&&t<=n)
    {
        vis[ch[t].id] = 0;//删除
        sum -= ch[t].c-'a'+1;//减去这个的贡献
        t++;
    }
    for (int i=1;i<=n;i++)
        if (vis[i]) cout<<s[i];
    cout<<endl;
}

E. Split Into Two Sets（染色）

这个题可以用并查集（判奇数环），知乎上有些大佬是这样的，我写的很乱但是过了，wa是因为忘记删debug了。
(我赛时因为时间紧，过了就好，代码写的很丑...)

题意

给你$n$个牌九（有正反两个数字例如1 2），然后需要将其分为两类，每类中不能有一样的数字。

思路

我设了一个结构体

struct node
{
    int x,y,id;//x,y为数字,id为下标
}a[N];

我的主要思想一开始判环，想了一会还是想到了当天robocom的第五题染色，那就建边染色吧。当前读入的是x,y，那么与之前的x,y'的关系是什么呢？说明这二者不能在同一集合，所以在染色中需要连边，同理，对于x',y也连起来。

    ok = true;
    for (int i=1;i<=n;i++)
    {
        cin>>x>>y;
        col[i] = 0;
        if (x==y) ok = false;//特判
        a[i].x = x;
        a[i].y = y;
        a[i].id = i;
        e[x].push_back({x,y,i});//建边
        e[y].push_back({y,x,i});//只需要存{x,i}即可
    }

然后就是对于每一个染色就好，小技巧就是col[y] = 3-col[x]（应该很多都知道了）
我这里染色因为是分开写的，也就是对于每一个node都有一个id以及x,y对于x需要找其相连的边，对于y需要找相连的边。

代码

int col[N];
struct node
{
    int x,y,id;
}a[N];
vector<node>e[N];
bool ok = true;
inline void dfs(node cur)
{
    for (auto e:e[cur.y])
    {
        int y = e.y, id = e.id;
        if (col[id] == 0)
        {
            col[id] = 3-col[cur.id];
            dfs(a[id]);
        }
        else 
        {
            if (id!=cur.id&&col[id] == col[cur.id])
            {
                ok = false;
                return;
            }
        }
    }
    for (auto e:e[cur.x])
    {
        int y = e.y, id = e.id;
        if (col[id] == 0)
        {
            col[id] = 3-col[cur.id];//对于目标结点染色
            dfs(a[id]);//传入的是类型为node的结点
        }
        else 
        {
            if (id!=cur.id&&col[id] == col[cur.id])//不能是自己且颜色相同
            {
                ok = false;
                return;
            }
        }
    }
}
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) e[i].clear();
    ok = true;
    for (int i=1;i<=n;i++)
    {
        cin>>x>>y;
        col[i] = 0;
        if (x==y) ok = false;
        a[i].x = x;
        a[i].y = y;
        a[i].id = i;
        e[x].push_back({x,y,i});
        e[y].push_back({y,x,i});
    }
    for (int i=1;i<=n;i++)
    {
        if (col[i]==0)//如果还没找过
        {
            col[i] = 1;
            dfs(a[i]);
        }
    }
    if (ok) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

F. Equate Multisets（贪心）

题意

给你一个长度为$n(1\leq n\leq 2\times 10^5)$的数组$a,b$，$a$数组不可移动，你用两种方式可以改变$b$数组，问是否可以变成$a$数组，方式为：

• 选择$b_i$使得$b_i = \left \lfloor \frac{b_i}{2} \right \rfloor $
• 选择$b_i$使得$b_i = b_i \times 2$

思路

这个题是abc254的EX（待补），不过那个题是求最小次数。Ex - Multiply or Divide by 2 (atcoder.jp)

这个题我认为跟前几天的2C很像：Codeforces Global Round 21 （C构造贪心，D分治ST表，E组合数学） - CarryNotKarry 中的C题。

虽然告诉你数组$a$不能动，但是因为$b$的操作是可以逆操作的（那篇博客也说了），所以我们可以修改 $a$：
对于一个$2$的倍数的$a_i$，我们可以一直除以2，例如现在$a_i=28$，那么除以二为$14$，是二的倍数，还可以除，变成$7$之后不变了。

    for (int i=1;i<=n;i++)
    {
        cin>>x;
        while (x%2==0) x/=2;
        mp[x]++;
    }

为什么可以这么做，假如原来有个数可以变成$28$，例如$14$或者$56$，他们同样也能变为$7$。如果是$57$呢？请往后看。

就这样我们都存放在了map里面，因为可能会有相同数字，就不用set了，接下来就是对$b$数组的处理，对于每一个$b_i$来说判断mp[b[i]]是否大于0，大于0说明有对应的$a$数组的数，所以就可以mp[b[i]]--，如果没有呢？那么就除以$2$.（这里不用考虑乘以$2$的事情，如果真的符合，$a$那边自己会除以$2$的，否则不可能相等）

    for (int i=1;i<=n;i++)
    {
        cin>>x;
        while (x&&mp[x]==0) x/=2;//一直除以二
        if (mp[x]) mp[x]--;//如果是mp[x]>0出循环的 那么就--
        else ok = false;
    }

就这样下去即可

代码

inline void solve()
{
    cin>>n;
    map<int,int> mp;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        while (x%2==0) x/=2;
        mp[x]++;
    }
    bool ok = true;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        while (x&&mp[x]==0) x/=2;
        if (mp[x]) mp[x]--;
        else ok = false;
    }
    if (ok) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

G2. Passable Paths (hard version)（LCA+DFS序）

题意

给你一颗有$n(1\leq 2\times 10^5)$个结点的树，并且有$q(1\leq q\leq 10^5)$次询问，一共最多询问$2\times 10^5$次。
每次询问一个总数$k$，然后有$k$个数字，问这$k$个点是否在同一路线上，也就是每条边只能够走一次并且走完所有的点，输出YES或者NO

思路

Codeforces Round #805 (Div. 3) E(染色) F(贪心) G(lca) - 知乎 (zhihu.com)

看大佬严格鸽补题的，内容大致与其一样，接下来是我的思考与理解（在大佬的基础上）。

首先比较重要的是DFS序，用$O(1)$的时间复杂度判断。
请见这一篇文章：DFS序 - CarryNotKarry

int in[N],out[N],dfn;
inline void dfs(int x,int fa)
{
    in[x] = ++dfn;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y = edge[i].to;
        if (y!=fa)
            dfs(y,x);
    }
    out[x] = dfn;
}
inline bool isp(int u,int v)
{
    return in[u]<=in[v] && out[v]<=out[u];//判断v是否是在u的子树内
}

该题有两种情况，一种是没有拐点，另一种是有拐点的情况：

(两种情况)

第一种情况可以直接判断是否在一条链上，将所有的点都放在一个vector上，然后对深度进行排序，这里从小到大排序，然后每次按照相邻的u,v判断是否v是否在u的子树内，如果这一串下来都符合，那么说明这是一条链，如上图(1)。如果不符合，那么就是第二种情况——有拐点的情况。

然后选出两个且在不同边的最深的结点，可以排序也可以sort，找到st和en，也就是上图（2）的st=7,en=5，注意需要是结点两边的,因此不能选en=6。

然后通过st和en找到拐点G=Lca(st,en)，也就是上图的4：

        vector<int> p(k);
        int st = 0, en = 0;
        for (int i=0;i<k;i++)
        {
            cin>>p[i];
            if (dep[p[i]]>dep[st]) st = p[i];//先找到最深的结点
        }
        if (isLink(p)) {cout<<"YES"<<endl;continue;}
        for (int i=0;i<k;i++)
        {
            if (p[i]==st) continue;
            if (Lca(st,p[i])!=p[i]&&dep[p[i]]>dep[en])
                en = p[i];
        }
        int G = Lca(st,en);

然后再循环所有的要询问的点，如果满足下列两种情况说明是符合的：

• Lca(x,st)==x&&Lca(x,en)==G 也就是在st的一边

Lca(x,st)==x并且Lca(x,en)==G

• Lca(x,st)==G&&Lca(x,en)==x 也就是在en的一边

Lca(x,st)==G并且Lca(x,en)==x

        for (int x:p)
        {
            if (Lca(x,st)==x&&Lca(x,en)==G) continue;
            if (Lca(x,en)==x&&Lca(x,st)==G) continue;
            ok = false;
        }
        if (ok) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;

然后就是LCA的板子了

代码

int head[N],cnte,n,dep[N],f[N][21],lg2[N],q;
struct node
{
    int to,next;
}edge[N<<1];
inline void add(int x,int to)
//inline void add(int x,int to,int w)
{
    edge[++cnte].to = to;
    edge[cnte].next = head[x];
    //edge[cnte].w = w;
    head[x] = cnte;
}
inline void build(int x,int fa)
{
    dep[x] = dep[fa] + 1;
    f[x][0] = fa;
    for (int i=1;i<=20;i++)
        f[x][i] = f[ f[x][i-1] ][i-1];
    for (int i=head[x];i;i=edge[i].next)
        if (edge[i].to!=fa)
            build(edge[i].to,x);
}
int Lca(int x,int y)
{
    if (dep[x]<dep[y]) swap(x,y);
    while (dep[x]>dep[y])
        x = f[x][lg2[dep[x]-dep[y]]];
    if (x==y) return x;
    for (int i=lg2[dep[x]];i>=0;i--)
        if (f[x][i]!=f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}
inline bool cmp(int a,int b)
{
    return dep[a]>dep[b];
}
int in[N],out[N],dfn;
inline void dfs(int x,int fa)
{
    in[x] = ++dfn;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y = edge[i].to;
        if (y!=fa)
            dfs(y,x);
    }
    out[x] = dfn;
}
inline bool isp(int u,int v)
{
    return in[u]<=in[v] && out[v]<=out[u];
}
inline bool isLink(vector<int> p)
{
    sort(p.begin(),p.end(),cmp);reverse(p.begin(),p.end());
    for (int i=1;i<p.size();i++)
        if (!isp(p[i-1],p[i])) return 0;
    return 1;
}
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);add(v,u);
    }
    for (int i=2;i<=N-2;i++)
        lg2[i] = lg2[i>>1]+1;
    build(1,0);
    dfs(1,0);
    cin>>q;
    while (q--)
    {
        bool ok = true;
        int k;
        cin>>k;
        vector<int> p(k);
        int st = 0, en = 0;
        for (int i=0;i<k;i++)
        {
            cin>>p[i];
            if (dep[p[i]]>dep[st]) st = p[i];
        }
        if (isLink(p)) {cout<<"YES"<<endl;continue;}
        for (int i=0;i<k;i++)
        {
            if (p[i]==st) continue;
            if (Lca(st,p[i])!=p[i]&&dep[p[i]]>dep[en])
                en = p[i];
        }
        int G = Lca(st,en);
        for (int x:p)
        {
            if (Lca(x,st)==x&&Lca(x,en)==G) continue;
            if (Lca(x,en)==x&&Lca(x,st)==G) continue;
            ok = false;
        }
        if (ok) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

signed main() 
{
    IOS
    int _=1;
    while (_--)
    {
        Case_Test();
    }
}