本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-02-26 19:02:04

A - Edge Checker

题目大意：

1 到 10 按顺序组成一个环（1 和 10 首尾连接）
给定两个数，问是否相邻。

题目分析：

签到题不需要分析。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if((a==1&&b==10)||(a==10&&b==1))
    {
        cout<<"Yes";
        return 0;
    }
    if(abs(a-b)<=1)cout<<"Yes";
    else cout<<"No";
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

B - Count Distinct Integers

题目大意：

给定一个长度为 $n$ 的数组，问有多少不同的数字。

题目分析：

签到题不需要分析。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
const int maxn=1005;
int a[maxn];
map<int,int> im;
int main()
{
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(!im[a[i]])ans++;
        im[a[i]]=1;
    }
    cout<<ans;
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

C - Jumping Takahashi

题目大意：

某人的起始坐标为0（向左为负向右为正）。给定两个长度为 $N$ 的数组，$a$ 和 $b$，这个人第 $i$ 次跳可以向右移动 $ai$ 个单位或 $bi$ 个单位。问经过 $n$ 次跳跃之后是否能到达点 $X$（必须跳 $N$ 次）。
$1 \le N \le 100$

题目分析：

由于本人太菜，只会 $O(2^n)$ 的爆搜，所以就来说一下怎么写爆搜过题，正确算法等我看了官方题解之后再放上来。
首先，朴素的爆搜肯定大家都会写，但是 $O(2^n)$ 的复杂度就算评测机能 $n^2$ 过百万也不行。所以要加剪枝，现在来讲一下怎么写剪枝。
剪枝一：如果当前搜到的数总和超过了 $X$ ,那么返回。
剪枝二：如果当前搜到的数字总和，后面即使每次都选最大的数，总和仍然比 $X$ 小，那么返回。
剪枝三：如果当前搜到的数字总和，后面即使每次都选最小的数，总和仍然比 $X$ 大，那么返回。 来看一看效果：

可见剪枝效果显著，但是仍然无法通过此题。
怎么办？
为了 AC，我加了一个错误的剪枝：
如果递归超过 2000万次还没有搜到结果，那么有解的可能很小（随机数据下），那么直接输出 No。
但是这个是错的，我自己就能 hack 掉。但是 At 的数据太水了所以过了。
正确做法我看完官方题解再放上来。
（还好不是 CF 赛制）

$\color{red}\text{错误}$ $\color{blue}\text{但是}$$\color{green}\text{AC的代码：}$

#include <bits\/stdc++.h>
using namespace std;
const int maxn=105;
int a[maxn];
int b[maxn];
int qzh[maxn];
int qzh2[maxn];
int n,x;
int cnt=0;
bool dfs(int i,int col)
{
    if(++cnt>=20000000)return 0;
 \/\/   cout<<"i: "<<i<<" col"<<col<<endl;
    if(col==x&&i==n+1)return 1;
    if(i==n+1)return 0;
    if(col>x)return 0;
\/\/    cout<<"qzh"<< qzh[n]-qzh[i]<<endl;
\/\/    cout<<"qzh"<< qzh2[n]-qzh2[i]<<endl;
\/\/cout<<col+(qzh[n]-qzh[i])<<endl;
\/\/cout<<col+(qzh2[n]-qzh2[i])<<endl;
    if(col+(qzh[n]-qzh[i])>x)return 0;
    if(col+(qzh2[n]-qzh2[i])<x)return 0;
 \/\/   cout<<"i: "<<i<<endl;
    if(dfs(i+1,col+a[i+1]))return 1;
    if(dfs(i+1,col+b[i+1]))return 1;
    return 0;
}

int main()
{
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        qzh[i]=qzh[i-1]+min(a[i],b[i]);
        qzh2[i]=qzh2[i-1]+max(a[i],b[i]);
    }
    if(dfs(1,a[1])||dfs(1,b[1]))cout<<"Yes";
    else cout<<"No";
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

D - Strange Balls

题目大意：

有 $n$ 个球，每个球都有一个数值 $a_i$。
这些球按照顺序从第 $1$ 个到第 $n$ 个依次放入一个瓶子里。放入一个球后如果出现了有连续 $a_i$ 个球的数值为 $a_i$。那么这连续 $a_i$ 个球都会消失。
问每放入一个球之后瓶子里有多少球。

题目分析：

可以创建一个栈 $sta$，对于每一块连续的球都用一个节点 $sta_i$ 表示。对于每个节点 $sta_i$ 存储当前块有多少个球，以及当前块存的球的数值。
插入一个球之后，如果这个球数值与栈顶节点不一样，那么新建一个节点插入栈顶。如果一样，那么栈顶节点 $sta_{top}$ 存储的球数 $+1$，如果发现 $sta_{top}$ 存储的球数 $ = sta_{top}$的数值，那么删除 $sta_top$ 即可。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n;
int a[maxn];
int top;
struct Sta
{
    int size;
    int val;
}sta[maxn];
int ans=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=sta[top].val)
        {
            sta[++top]={1,a[i]};
            ans++;
            printf("%d\n",ans);
        }
        else
        {
            sta[top].size++;
            ans++;
            if(sta[top].size==a[i])
            {
                ans-=sta[top].size;
                top--;
            }
            printf("%d\n",ans);
        }
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

E - Ranges on Tree

题目大意：

$[l,r] = l,l+1,l+2.......r-1,r$
给定一棵树。树上的每个点都有两个值 $(l_i,r_i)$。
设第 $i$ 个节点的子树为集合 $s_i$。
每个点的值应满足一下要求：
一、如果点 $a$ 是点 $b$ 的子节点，那么 $[l_a,r_a]$ 应包含在 $[l_b,r_b]$ 中。
二、如果点 $a$ 和点 $b$ 是独立的两棵树，那么 $[l_a,r_a]$ 应和 $[l_b,r_b]$ 无交集。
对每个节点安排它的 $(l,r)$，使得 $max(l_1,l_2,l_3......l_n,r_1,r_2,r_3......r_n)$ 最小。

题目分析

大力 dfs!
首先确定叶子节点的值，然后，每个节点的 father 节点的值也就是 $(min({{s_i}_j}.l),max({{s_i}_j}.r))$
注： ${{s_i}_j}$ 代表 $s_i$ 的第 $j$ 个元素。
如何确定叶子结点的值呢？ 定义一个变量 $sum$ ，当前点每搜到一个子节点点就 sum++。（为了避免误差，每个点搜到第一个子节点时不用增加 $sum$）
对于搜到的每个点首先把这个点的 $l$ 设为 $sum$，从这个点搜完它的所有子节点之后，再把它的 $r$ 设为 $sum$。
这样就完成了。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int head[maxn<<1];
struct EDGE
{
    int to,nxt;
}edge[maxn<<1];
int tot;
inline void add(int u,int to)
{
    edge[++tot].to=to;
    edge[tot].nxt=head[u];
    head[u]=tot;
}
int n;
int rd[maxn];\/\/存储入度
struct Val
{
    int l,r;
}val[maxn];\/\/存储每个点的取值范围
int dbg;
bool vis[maxn];
int sum=1;
void dfs(int u)
{
    val[u].l=sum;
    vis[u]=1;
    bool flag=0;
    \/\/因为如果当前点有子树的话
    \/\/统计答案会多统计1
    \/\/在此需要标明以来
    \/\/减去这个误差
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(vis[to])continue;
        if(flag)sum++;
        flag|=1;
        dfs(to);
    }
    val[u].r=sum;
}
int main()
{
    scanf("%d",&n);
    int ut,vt;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&ut,&vt);
        add(ut,vt);
        add(vt,ut);
        rd[ut]++;
        rd[vt]++;
    }
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        printf("%d %d\n",val[i].l,val[i].r);
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}