## T1 - 碰一碰

### 题解

保持清醒的头脑仔细读完题会捕捉到一些关键信息，比如题目中特意写了：**数据保证能算出红包价值，并且答案唯一。**

那么只需要维护差值最大值就行啦！

### 标程

```cpp
int n, ans, x, y;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    while(n--)
    {
        cin >> x >> y;
        ans = max(ans, x - y);
    }
    cout << ans << '\n';
    return 0;
}
```

## T2 - TooY0ung的优秀板擦

### 题解

无非就是统计多少段 $0$，主要是需要注意末尾的一段 $0$ 的问题，所以可以给 $a[n+1]$ 赋一个初始值。

### 题解

```cpp
int n, ans, a[110], lst;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    a[n + 1] = 1e9;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++)
    {
        if(a[i] == 0 && a[i + 1] == 0)
        {
            continue;
        }
        else if(a[i] == 0 && a[i + 1] != 0)
        {
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}
```

## T3 - TooY0ung的诅咒

### 题解

从本道题目开始，是给算法同学准备的题目了。

但是实际上第四道题用贪心思想写一写也能得到$72$ 分。

简化题目意思就是，起点唯一，终点有多个，寻找一个从起点到任意一个终点深度最小的路径。

解法一：bfs松弛

可以使用类似于spfa广搜松弛的操作，对每个点的深度进行松弛操作。

用 $deep[i]$ 表示落脚点 $i$ 的深度

用 $sp[i]$ 表示起点与 $i$ 点之间存在一条深度为 $sp[i]$ 的路径
松弛的表达式是 $sp[to] = min( max(sp[from],deep[to]) , sp[to])$

最后遍历一遍所有点 找到一个 $deep$ 为 $0$ $sp$ 最小的点。

参考 $spfa$ 的玄学复杂度，最糟情况不会超过 $O(n^2)$

解法二：二分套搜索

因为深度给出明确的范围，所以对深度进行二分也是可行解

深度为 $x$ 时 $check$ 的是“搜索时只考虑深度不超过 $x$ 的点 是否能到达一个深度为 $0$ 的点”

搜索可以使用$bfs$

注意搜索时要边搜边染色，避免在环里 $TLE$

时间复杂度是 $O(nlog_2d)$

### 标程

```cpp
int n, m, s, deep[1010], vis[1010];
vector<int>G[1010];
queue<int>q;
int check(int mid)
{
    memset(vis, 0, sizeof(vis));
    while(q.empty() == 0) q.pop();
    q.push(s);
    while(q.empty() == 0)
    {
        int now = q.front(); q.pop();
        int siz = (int)G[now].size();
        for(int i = 0; i < siz; i++)
        {
            int x = G[now][i];
            if(deep[x] <= mid && vis[x] == 0)
            {
                if(deep[x] == 0) return 1;
                vis[x] = 1;
                q.push(x);
            }
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> s;
    for(int i = 1; i <= n; i++) cin >> deep[i];
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int l = deep[s], r = 10000010, ans = -1;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(check(mid) == 1) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    if(ans == -1) cout << "GG\n";
    else cout << ans << '\n';
    return 0;
}
```

## T4 - 被帽子叔叔带走喝茶

### 题解

故事是真实故事，希望同学们谨言慎行。

其实想明白就是一个类似染色的bfs，边界条件就是举报者所在的群就行了，我觉得算是个用搜索做的模拟？

### 标程

```cpp
vector<int>e1[maxn]; // 人 -> 群
vector<int>e2[maxn]; // 群 -> 人
int num[maxn], vis0[maxn], ans, m, k;
int vis1[maxn]; // 人
int vis2[maxn]; //群
queue<int>q;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> m;
    for(int i = 0; i < m; i++)
    {
        vis0[i] = 0;
        cin >> k;
        for(int j = 0; j < k; j++)
        {
            cin >> num[j];
            if(num[j] == 0)
            {
                vis0[i] = 1;
            }
        }
        for(int j = 0; j < k; j++)
        {
            e1[num[j]].push_back(i);
            if(vis0[i] == 0) e2[i].push_back(num[j]);
        }
    }
    q.push(0);
    while(q.empty() == 0)
    {
        int now = q.front();
        for(auto it : e2[now])
        {
            if(vis1[it] == 0)
            {
                vis1[it] = 1;
                ans++;
                for(auto it2 : e1[it])
                {
                    if(vis2[it2] == 0)
                    {
                        vis2[it2] = 1;
                        q.push(it2);
                    }
                }
            }
        }
        q.pop();
    }
    cout << ans << '\n';
    return 0;
}
```
## T5 - 自动关禁言程序

### 题解

这个题如果不会期望的同学可以跳过，其实也不是 $J$ 组会考的问题，只是觉得题目背景比较有趣，所以出了个题，这也是真实故事 ~~(截图都放出来了)~~

其实就是个简单到不能再简单的概率 $dp$，$dp$ 转移就类似于 $dp[i+3] += dp[i] * 0.3$ 等等，具体看代码吧。

### 标程
```cpp
double dp[510];
int n;
double dfs(int x)
{
    if(x <= 0) return 0;
    if(dp[x] > -0.000001) return dp[x];
    dp[x] = 1;
    dp[x] += dfs(x - 3) * 0.3;
    dp[x] += dfs(x - 7) * 0.3;
    dp[x] += dfs(x - 15) * 0.2;
    return dp[x];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i = 0; i < 510; i++) dp[i] = -1;
    while(cin >> n)
    {
        printf("%.2f\n", dfs(n));
    }
    return 0;
}
```

### didi 的代码（再次感谢独立验题人 didi）

```cpp
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 3: 30%  7: 30%  15: 20%  /: 20%
    vector<double> f(555, 0);
    f[1] = 1.00;
    for (int i = 1; i <= 500; i++) {
        f[i + 3] += f[i] * 0.3;
        f[i + 7] += f[i] * 0.3;
        f[i + 15] += f[i] * 0.2;
        f[i] += f[i - 1];
    }

    int n;
    while (cin >> n) {
        cout << fixed << setprecision(2) << f[n] << endl;
    }
    
    return 0;
}
```

## T6 - TooY0ung取数字

### 题解

这还是个 $dp$ ，首先显然，我们可以把数字做个排序，然后从大到小来进行 $dp$ 转移，定义一个 $ans[i]$  记录中间答案，$sum[i]$ 表示最终结果。其实过程是和前缀和完全类似的。

转移就是如果，$a[i] == a[i + 1]$ ，那么继承答案，即 $ans[i] = ans[i + 1]$ 和 $sum[i] = sum[i + 1]$ 。

如果 $i * 2 > n$ 就没办法转移，存 $0$。

其他情况就是 $ans[i] = sum[i * 2] + 1$，以及 $sum[i] = sum[i + 1] + ans[i]$。记得取模，最后答案记得 $+1$，因为你可以直接选最大的把所有的数删掉。

同学们可以想想这样做的原因（仔细想想是很容易想懂的）

这样，我们就写完了跨年场的所有题解。（好累，写了三遍，第一遍写完一半按了下刷新，第二次写完网卡了没保存上，所以这是我写的第三次。。。）

### 标程
```cpp
int n;
ll a[maxn], sum[maxn], ans[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    for(int i = n; i >= 1; i--)
    {
        if(a[i] == a[i + 1] && i != n)
        {
            ans[i] = ans[i + 1];
            sum[i] = sum[i + 1];
        }
        else if(i * 2 > n)
        {
            ans[i] = sum[i] = 0;
        }
        else
        {
            ans[i] = (sum[i * 2] + 1) % mod1;
            sum[i] = (sum[i + 1] + ans[i]) % mod1;
        }
    }
    cout << sum[1] + 1 << '\n';
    return 0;
}
```