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往下能到达的最远
标签:AtCoder,Beginner,int,vi,148,dep,ans,dis,mxdep
From: https://www.cnblogs.com/CTing/p/17264716.html