A.Ichihime and Triangle

题意：

给定四个数，要求确定使其构成三角形的三条边，

题解：

令三个数为即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    ll a, b, c, d;
    scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
    printf("%lld %lld %lld\n", b, c, c);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Kana and Dragon Quest game

题意：

给一个数,你可以进行两种操作：

问能否通过至多次操作和至多次操作使得

题解：

令，得，因此当时进行操作反而会使变大，所以先将通过操作尽可能的降至且最小的位置，再用操作判断其是否会

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int h, n, m;
    scanf("%d%d%d", &h, &n, &m);
    while (h > 20 && n)
    {
        n--;
        h = h / 2 + 10;
    }
    puts(h <= m * 10 ? "YES" : "NO");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Linova and Kingdom

题意：

给定个节点条边组成且以节点为根的树，
现需要选出个节点作为工业城市，其余城市均为旅游城市
问从所有工业城市出发走到根节点所经过的旅游城市数量之和的最大值

题解：

首先可以发现贪心将所有深度尽可能大的节点染成白色是最优的，但是要算最大值所以还需要确定具体的值，如果只取深度最大的个因为无法确定其父节点是否也为工业城市，所以这个贪心策略不行。考虑到如果加入一个节点的话，那么它的儿子节点肯定已经记为工业城市，所以这个点的贡献就是，所以可以算出每个节点的，取前大个即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
vector<int> G[maxn], v;
int dfs(int u, int f, int dep)
{
    int son = 1;
    for (auto v : G[u])
    {
        if (v == f)
            continue;
        son += dfs(v, u, dep + 1);
    }
    v.push_back(dep - son + 1);
    return son;
}
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0, 0);
    sort(v.rbegin(), v.rend());
    printf("%lld\n", accumulate(v.begin(), v.begin() + k, 0ll));
    return 0;
}

D.Xenia and Colorful Gems

题意：

给定三种数字，三种数字分别有个，现在要在每种数字中取出个，使得最小

题解：

枚举其中一种数，另外两种二分找最接近的即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
inline ll calc(ll x, ll y, ll z) { return (x - y) * (x - y) + (y - z) * (y - z) + (z - x) * (z - x); }
int n[3], v[3][maxn], p[3] = {0, 1, 2};
void solve()
{
    scanf("%d%d%d", &n[0], &n[1], &n[2]);
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < n[i]; j++)
            scanf("%d", &v[i][j]);
        sort(v[i], v[i] + n[i]);
    }
    ll ans = 6e18 + 10;
    do
    {
        for (int i = 0; i < n[p[0]]; i++)
        {
            int pos1 = lower_bound(v[p[1]], v[p[1]] + n[p[1]], v[p[0]][i]) - v[p[1]];
            int pos2 = upper_bound(v[p[2]], v[p[2]] + n[p[2]], v[p[0]][i]) - v[p[2]];
            if (pos1 != n[p[1]] && pos2 != 0)
                ans = min(ans, calc(v[p[0]][i], v[p[1]][pos1], v[p[2]][pos2 - 1]));
        }
    } while (next_permutation(p, p + 3));
    printf("%lld\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

E.Kaavi and Magic Spell

题意：

给定一个长度为的字符串和一个长度为的字符串,其中。
现有一个空串,可以对进行至多次操作，一共有两种不同的操作，操作如下：

1. 将的首部添加到的首部，并从中删除
2. 将的首部添加到的尾部，并从中删除

询问有多少中不同的操作组合可以使得的前缀等于,输出所有的操作组合数，长度不同或者是操作序列中有某个地方不同可视为是不同的操作。

题解：

区间。描述当前和在区间的匹配个数。这里将长度扩展为，但是从之后的顺序是任意的。
转移方程:
注意到插入空串的时候前后算是两种，所以没必要特殊处理，把初始化成就可以了。
最终所求就是的总和。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 3005;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
char S[maxn], T[maxn];
ll dp[maxn][maxn];
int main()
{
    scanf("%s%s", S + 1, T + 1);
    int n = strlen(S + 1), m = strlen(T + 1);
    for (int i = 1; i < maxn; i++)
        dp[i][i - 1] = 1;
    for (int i = 1; i <= n; i++)
        for (int l = 1, r = l + i - 1; r <= n; l++, r++)
        {
            if (l > m || S[i] == T[l])
                dp[l][r] = (dp[l][r] + dp[l + 1][r]) % mod;
            if (r > m || S[i] == T[r])
                dp[l][r] = (dp[l][r] + dp[l][r - 1]) % mod;
        }
    ll ans = 0;
    for (int i = m; i <= n; i++)
        ans = (ans + dp[1][i]) % mod;
    printf("%lld\n", ans);
    return 0;
}