A：msc和mas
Solved.
考虑斐波那契数列，即最多加45次即会超过1e9,直接暴力即可
#include <bits/stdc++.h>
using namespace std; int a, b, l; int solve(int st)
{
int A = a, B = b;
while ()
{
if (st == )
{
if (A > l) return printf("Yes");
else
{
int B0 = B;
while (B < * B0) B += A;
}
}
else
{
if (B > l) return printf("No");
else
{
int A0 = A;
while (A < * A0) A += B;
}
}
st ^= ;
}
} int main()
{
while (scanf("%d%d%d", &a, &b, &l) != EOF)
{
solve(); putchar(' ');
solve(); putchar('\n');
}
return ;
}
B：msc和mcc
Solved.
考虑如果有一个区间满足，那么左右两边扩展区间肯定也是满足的
再考虑从左到右，如果$1-x满足，那么2-y满足的话， 显然有y >= x$
那么只需要双指针找到以i为左界，找到最近的右界，那么这个点的贡献就是n - r + 1
再考虑怎么判断是否合法
不难发现，只有mscmcc 和 mccmsc 两种情况，注意其中可以加入其他字符，但是最终取出的子序列都会归结到这两种情况 都判断一下即可
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 100010
int n;
char str[N];
set <int> m, s, c;
int st_m[], pos_s, pos_c[]; bool check1()
{
// mscmcc
if (s.upper_bound(st_m[]) == s.end()) return false;
pos_s = *s.upper_bound(st_m[]);
if (c.upper_bound(pos_s) == c.end()) return false;
pos_c[] = *c.upper_bound(pos_s);
if (c.upper_bound(max(st_m[], pos_c[])) == c.end()) return false;
pos_c[] = *c.upper_bound(max(st_m[], pos_c[]));
if (c.upper_bound(pos_c[]) == c.end()) return false;
return true;
} bool check2()
{
// mccmsc
if (c.upper_bound(st_m[]) == c.end()) return false;
pos_c[] = *c.upper_bound(st_m[]);
if (c.upper_bound(pos_c[]) == c.end()) return false;
pos_c[] = *c.upper_bound(pos_c[]);
if (s.upper_bound(st_m[]) == s.end()) return false;
pos_s = *s.upper_bound(st_m[]);
if (c.upper_bound(max(pos_s, pos_c[])) == c.end()) return false;
return true;
} bool ok()
{
if (m.size() < ) return false;
if (s.size() < ) return false;
if (c.size() < ) return false;
st_m[] = *m.begin(); m.erase(m.begin());
st_m[] = *m.begin(); m.insert(st_m[]);
if (check1()) return true;
if (check2()) return true;
return false;
} int main()
{
while (scanf("%d", &n) != EOF)
{
m.clear(); s.clear(); c.clear();
ll res = ;
scanf("%s", str + );
for (int i = , r = ; i <= n; ++i)
{
while (r < n && !ok())
{
++r;
if (str[r] == 'm') m.insert(r);
else if (str[r] == 's') s.insert(r);
else c.insert(r);
}
if (!ok()) break;
res += n - r + ;
if (str[i] == 'm') m.erase(i);
else if (str[i] == 's') s.erase(i);
else c.erase(i);
}
printf("%lld\n", res);
}
return ;
}
C：msc的宠物
Upsolved.
先二分答案，再DP求解最少需要删去的边数。
设$g[u] 表示 以 u 为根的子树下最少需要删去的边数，f[u][x] 表示以u为根的子树下u所处的连通块中点权最大值为x的情况下最少需要删去的边数$
$对于u 和 v 如果 a[u] < x 并且 a[v] < x 并且 abs(a[u] - a[v]) < x 那么 u 和 v 就可以同属一个连通块 $
$那么转移就是 f[u][x] += min(g[v] +1, f[v][x])$
其他情况的转移都是 $f[u][x] += g[v] +1$
最后 $g[u] = min(f[u][x])$
#include <bits/stdc++.h>
using namespace std; #define N 1010
#define INF 0x3f3f3f3f
#define ll long long
int n, k, a[N], f[N][N], g[N]; ll x;
vector <int> G[N]; void dp(int u, int fa = )
{
for (auto v : G[u]) if (v != fa)
{
dp(v, u);
for (int i = ; i <= n; ++i)
{
if (a[u] <= a[i] && a[v] <= a[i] && abs(a[u] - a[v]) <= x)
f[u][i] += min(g[v] + , f[v][i]);
else
f[u][i] += g[v] + ;
}
}
for (int i = ; i <= n; ++i)
g[u] = min(g[u], f[u][i]);
} bool check()
{
memset(g, 0x3f, sizeof g);
for (int i = ; i <= n; ++i) for (int j = ; j <= n; ++j)
f[i][j] = (abs(a[i] - a[j]) <= x) ? : INF;
dp();
return g[] <= k;
} void Run()
{
while (scanf("%d%d", &n, &k) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", a + i);
for (int i = , u, v; i < n; ++i)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
ll l = , r = , res = -;
while (r - l >= )
{
x = (l + r) >> ;
if (check())
{
res = x;
r = x - ;
}
else
l = x + ;
}
printf("%d\n", res);
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}
D：msc的背包
Unsolved.
E：msc的序列
Unsolved.
F：msc的无向图
Unsolved.