AtCoder Beginner Contest 148

https://atcoder.jp/contests/abc148
这场比较简单

D - Brick Break

二分 or LIS

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 200005;
int a[N], n, ans = 1, f[N]; //f[i]:以i结尾
map<int, int> mp;
bool suc;
set<int> s[N];

int main () {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 1)  suc = true;
        s[a[i]].insert (i);
    }
    if (!suc) {
        cout << -1;
        return 0;
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] != i)  break;
        cnt ++;
    }
    if (cnt == n) {
        cout << 0;
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        if (a[i] != 1)  continue;
        int st = i;
        for (int j = 2; j <= n; j++) {
            auto it = s[j].upper_bound (st);
            if (it == s[j].end ()) {
                ans = max (ans, j - 1);
                break;
            }
            st = *it;
            // cout << j  << ' ' << st << endl;
        }
        //cout << endl;
        break;
    }
    
    cout << n - ans;
}

//只需要第一个1

E - Double Factorial

首先如果是奇数就为 \(0\)。因为，奇数没有 \(2\) 的因子（每次转移的距离是 \(2\) ，奇数永远都是奇数）
统计 \(2\) 和 \(5\) 的因子个数，答案为 \(min(cnt2_n,cnt5_n)\)
又 \(2\) 的增长速度比 \(5\) 快，所以只需统计含 \(5\) 的因子个数。
5,25,125,...这样统计即可。
最开始除2是因为，以2为间隔，除去一个数先。

#include <bits/stdc++.h>
#define ll long long

using namespace std;
typedef pair<int, int> pii;
ll n, ans, p = 5;

int main () {
    cin >> n;
    if (n & 1) {
        cout << 0;
        return 0;
    }
    n /= 2;
    while (p <= n) {
        ans += n / p;
        p *= 5;
    }
    cout << ans;
}

//统计2和5的个数
//打表发现2一定必5多(除非不是偶数)
//统计n/2中5,25,125的数量

F - Playing Tag on Tree

偷洛谷题解的图：

注意 \(dep\) 从0开始

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int n, u, v;
vector<int> vi[N];
int dep[N], ans;
int mxdep[N]; //mxdep[i]: i往下能到的最深深度

void dfs (int u, int fa) {
    dep[u] = dep[fa] + 1;
    for (auto v : vi[u]) {
        if (v == fa)    continue;
        dfs (v, u);
        mxdep[u] = max(mxdep[u], mxdep[v] + 1);
    }
}

void dfs2 (int x, int dis) { //dis是x与u的距离
    if (dis < dep[x])   ans = max (ans, dep[x] + mxdep[x] - 1);
    for (auto j : vi[x]) {
        if (dep[j] > dep[x])    continue;
        dfs2 (j, dis + 1);
    }
}

int main () {
    cin >> n >> u >> v;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        vi[a].push_back (b), vi[b].push_back (a);
    }
    dep[0] = -1;
    dfs (v, 0);
    dfs2 (u, 0);
    cout << ans;
}

//v为根
//u所有能到的点的最大深度
//枚举u到根这条路径上的所有满足dis{x,u}<dis{x,v}的点t
//t往下能到达的最远