题解 | #训练赛4#

题解按照题目顺序排列

A题

知识点：枚举
记录连胜次数即可，若连胜次数 $>=3$ 则 $+k$ ,否则 $+1$ ,若遇到 $'L'$ 则清空连胜并 $-1$
复杂度: $O(n)$

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int res = 0;
    int sum = 0;
    for (auto x : s) {
        if (x == 'W') {
            sum++;
            if (sum >= 3) {
                res += k;
            } else {
                res++;
            }
        } else {
            sum = 0;
            res--;
        }
    }
    cout << res << '\n';
}

B题

知识点:贪心,排序
贪心考虑，我们希望使用a的元素时，击败的时比他小的b数组中最接近的数字，故排序后依次枚举a，判断是否能击败b即可
主要时间在于排序，时间复杂度: $O(nlogn)$

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
	vector<i64> a(n);
	vector<i64> b(m);
	for(auto &x:a){
		cin>>x;
	}
	for(auto &x:b){
		cin>>x;
	}
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	int res=0; 
	int j=0;
	int len=b.size();
	for(int i=0;i<a.size();i++){
		if(j<len && a[i]>b[j]){
			res++;
			j++;
		}
	}
	cout<<res;
    return 0;
}

C题

知识点：dfs,暴力,数学
三角形为三个数字， $dfs$ 判断每个木棍放入三个位置或者不放四种情况，并判断是否能够组成三角形，然后使用海伦公式即可
最多八个木棍，每次四种情况，最大复杂度为 $4^8$ 可以通过

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<i64> f(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> f[i];
    }
    double res = -1;
    vector<i64> cnt(3);
    vector<i64> p(3);
    auto dfs = [&](auto dfs, int x) -> void {
        p[0] = cnt[0], p[1] = cnt[1], p[2] = cnt[2];
        sort(p.begin(), p.end());
        if (p[0] + p[1] > p[2]) {
            double sum = 1.0 * (p[0] + p[1] + p[2]) / 2.0;
            double ans = sqrt(sum * (sum - p[0]) * (sum - p[1]) * (sum - p[2]));
            res = max(res, ans);
        }
        if (x > n) {
            return;
        }
        for (int i = 0; i < 3; i++) {
            cnt[i] += f[x];
            dfs(dfs, x + 1);
            cnt[i] -= f[x];
        }
        dfs(dfs, x + 1);
    };
    dfs(dfs, 1);
    if (res < 0) {
        cout << -1 << '\n';
    } else {
        cout << fixed << setprecision(1) << res << "\n";
    }
    return 0;
}

D题

知识点：枚举，位运算
考虑按位或运算的性质，可以发现，有趣的区间即为区间内存在一个奇数
可以考虑从后往前预处理一个后缀最先出现奇数位置的数组 $back$
从左往右，将 $i$ 作为区间 $[L,R]$ 中的 $L$ ，故满足条件的第一个位置即为最先出现奇数位置即 $back[i]$ ,此时 $R$ 有 $n-back[i]+1$ 个选法
故答案为 $\sum_{i=1}^{n}n-back[i]+1$
时间复杂度： $O(n)$

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	vector<i64> f(n+1);
	for(int i=1;i<=n;i++){
		cin>>f[i];
	}
	vector<i64> back(n+2);
	back[n+1]=n+1;
	for(int i=n;i>=1;i--){
		if(f[i]&1){
			back[i]=i;
		}else{
			back[i]=back[i+1];
		}
	}
	i64 res=0;
	for(int i=1;i<=n;i++){
		res+=n-back[i]+1;
	}
	cout<<res;
	return 0;
}

E题

知识点：博弈论
选任意节点后根都无法再被选中，因此分两种情况，分别为先手第一步选非根结点胜，选非根结点败，若为情况一，则先手必胜；若为情况二，则 $Adam$ 选根节点，此时轮到 $David$ ， $David$ 只能选非根结点，而先选非根结点的一方必败（ $Adam$ 选任意节点时，与 $David$ 先手时选该节点时等价），因此 $David$ 必胜
时间复杂度: $O(1)$

F题

知识点：构造
可以先想象一个长度 $n$ 全为字符' $y$ '的字符串，向其中插入字符' $c$ '，每次插入时，若前面有 $k$ 个 $'y'$ ,则答案增加 $C_k^2$ ,故可以从位置大的贪心处理，每次遇到可以减的最大数，则将其减去，由于长度给的比上界高很多，实际上并不存在-1的情况
时间复杂度： $O(T*n)$

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
void solve() {
	i64 n;
	cin>>n;
	string res;
	i64 cnt=0;
	for(i64 i=45000; i>=1; i--) {
		i64 sum=(i-1)*i/2;
		while(n>=sum && n>0) {
			n-=sum;
			res+='c';
		}
		res+='y';
	}
    cout<<res.size()<<"\n";
    reverse(res.begin(),res.end());
    cout<<res<<"\n";
	return;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin>>t;
	while(t--) {
		solve();
	}
	return 0;
}

G题

知识点：动态规划,枚举\

显而易见的，一个数若能被三整除，各位数上之和一定也能被三整除
故题意等效为九个数字，有多少种组合，能使和为 $3$ 的倍数
考虑 $dp$ ，去计算每个余数数量
转移方程很简单， $dp_{ij}$ 表示当枚举到第 $i$ 个数字，余数为 $j$ 的种类数
其中 $cnt0,cnt1,cnt2$ 为第i种数组能组合出来余数分别为 $0,1,2$ 的种类数
$dp[i][0]=dp[i-1][0]+dp[i-1][0]*cnt0+dp[i-1][1]*cnt2+dp[i-1][2]*cnt1$
$dp[i][1]=dp[i-1][1]+dp[i-1][1]*cnt0+dp[i-1][2]*cnt2+dp[i-1][0]*cnt1$
$dp[i][2]=dp[i-1][2]+dp[i-1][2]*cnt0+dp[i-1][0]*cnt2+dp[i-1][1]*cnt1$
其中注意 $cnt0,cnt1,cnt2$ 数量的计算即可
由于更新为固定的常数次操作,时间复杂度： $O(1)$

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 MOD = 1e9 + 7;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<i64> f(10);
    vector<vector<i64>> res(10, vector<i64>(3));
    for (int i = 1; i <= 9; i++) {
        cin >> f[i];
    }
    res[0][0] = 1;
    i64 cnt0, cnt1, cnt2;
    for (int i = 1; i <= 9; i++) {
        if (i % 3 == 0) {
            cnt0 = f[i], cnt1 = cnt2 = 0;
        } else if (i % 3 == 1) {
            cnt0 = f[i] / 3, cnt1 = cnt0 + (f[i] % 3 != 0), cnt2 = cnt0 + (f[i] % 3 == 2);
        } else {
            cnt0 = f[i] / 3, cnt1 = cnt0 + (f[i] % 3 == 2), cnt2 = cnt0 + (f[i] % 3 != 0);
        }
        res[i][0] = (res[i - 1][0] + res[i - 1][0] * cnt0 % MOD + res[i - 1][1] * cnt2 % MOD + res[i - 1][2] * cnt1 % MOD) % MOD;
        res[i][1] = (res[i - 1][1] + res[i - 1][0] * cnt1 % MOD + res[i - 1][1] * cnt0 % MOD + res[i - 1][2] * cnt2 % MOD) % MOD;
        res[i][2] = (res[i - 1][2] + res[i - 1][0] * cnt2 % MOD + res[i - 1][1] * cnt1 % MOD + res[i - 1][2] * cnt0 % MOD) % MOD;
    }
    cout << res[9][0];
    return 0;
}

H题

知识点：树的直径,dfs,单调队列，线段树
由于写题解的人太菜，图论比较菜，线段树开摆了
需要找到一条路径，其长度小于等于 $s$ ，使其所有点到这条路径的最大值最小
由于任意两个城市之间仅存在唯一一条路径，故其是一个无环图
直觉告诉我们，这条路径是在树的直径上的
因为，若我们选择将直径上的边去掉任意一条，去选择相邻的另外一条，都会产生一条比原来更长的路径，明显不满足题目的最大值最小的要求
可以先跑两遍 $dfs$ ，找到直径上的所有点（在第二次 $dfs$ 时，记录每一个节点的前序节点即可），将其存入数组
由于只能选择一条，故需要找到一条连续的子段，其和小于等于 $s$ ,可以考虑滑动窗口
我们需要对每一种情况，计算其答案，
先对直径上所有点，跑一遍不经过直径上点的 $dfs$ ，获得每个直径上点不经过其他直径点的最远距离 $dis_i$
此时，对于一个选定的区间 $[L,R]$ ,其答案为 $max(max(dis_i+distance(i,L))(i\in[1,L],max(dis_i+distance(R,i))(i\in[R,len],max(dis_L,...,dis_R))$
这些数值都是线段树很容易获取的
多开几颗简单又无脑，但是代码变的有点史

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using PII = pair<int, int>;

template<class T>
struct Segt {
    struct node {
        int l, r;
        T w, rmq, lazy;
    };

    vector<T> w;
    vector<node> t;

    Segt() {
    }

    Segt(int n) { init(n); }

    Segt(vector<int> in) {
        int n = in.size() - 1;
        w.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            w[i] = in[i];
        }
        init(in.size() - 1);
    }

#define GL (k << 1)
#define GR (k << 1 | 1)

    void init(int n) {
        w.resize(n + 1);
        t.resize(n * 4 + 1);
        auto build = [&](auto self, int l, int r, int k = 1) {
            if (l == r) {
                t[k] = {l, r, w[l], w[l], -1};
                return;
            }
            t[k] = {l, r, 0, 0, -1};
            int mid = (l + r) / 2;
            self(self, l, mid, GL);
            self(self, mid + 1, r, GR);
            pushup(k);
        };
        build(build, 1, n);
    }

    void pushdown(node &p, T lazy) {
        p.w += (p.r - p.l + 1) * lazy;
        p.rmq += lazy;
        p.lazy += lazy;
    }

    void pushdown(int k) {
        if (t[k].lazy == -1)
            return;
        pushdown(t[GL], t[k].lazy);
        pushdown(t[GR], t[k].lazy);
        t[k].lazy = -1;
    }

    void pushup(int k) {
        auto pushup = [&](node &p, node &l, node &r) {
            p.w = l.w + r.w;
            p.rmq = max(l.rmq, r.rmq);
        };
        pushup(t[k], t[GL], t[GR]);
    }

    void modify(int l, int r, T val, int k = 1) {
        if (r < l) {
            return;
        }
        if (l <= t[k].l && t[k].r <= r) {
            pushdown(t[k], val);
            return;
        }
        pushdown(k);
        int mid = (t[k].l + t[k].r) / 2;
        if (l <= mid)
            modify(l, r, val, GL);
        if (mid < r)
            modify(l, r, val, GR);
        pushup(k);
    }

    T rmq(int l, int r, int k = 1) {
        if (l <= t[k].l && t[k].r <= r) {
            return t[k].rmq;
        }
        pushdown(k);
        int mid = (t[k].l + t[k].r) / 2;
        T ans = numeric_limits<T>::lowest();
        if (l <= mid)
            ans = max(ans, rmq(l, r, GL));
        if (mid < r)
            ans = max(ans, rmq(l, r, GR));
        return ans;
    }

    T ask(int l, int r, int k = 1) {
        if (l <= t[k].l && t[k].r <= r) {
            return t[k].w;
        }
        pushdown(k);
        int mid = (t[k].l + t[k].r) / 2;
        T ans = 0;
        if (l <= mid)
            ans += ask(l, r, GL);
        if (mid < r)
            ans += ask(l, r, GR);
        return ans;
    }

    void debug(int k = 1) {
        cout << "[" << t[k].l << ", " << t[k].r << "]: ";
        cout << "w = " << t[k].w << ", ";
        cout << "Max = " << t[k].rmq << ", ";
        cout << "lazy = " << t[k].lazy << ", ";
        cout << endl;
        if (t[k].l == t[k].r)
            return;
        debug(GL), debug(GR);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, s;
    cin >> n >> s;
    vector<vector<PII>> edge(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[u].push_back({v, w});
        edge[v].push_back({u, w});
    }
    int st = 0;
    vector<int> d(n + 1, 0);
    vector<PII> prev(n + 1);
    auto dfs = [&](auto dfs, int u, int fa) -> void {
        for (auto [v, w]: edge[u]) {
            if (v == fa) {
                continue;
            }
            d[v] = d[u] + w;
            if (d[v] > d[st]) {
                st = v;
            }
            prev[v] = {u, w};
            dfs(dfs, v, u);
        }
    };
    dfs(dfs, 1, 0);
    d[st] = 0;
    prev.assign(n + 1, {0, 0}); // 需要清空，防止下一个记录路径时死循环
    dfs(dfs, st, 0);
    vector<int> dis(1, 0); //记录直径点
    vector<int> val(1); //直径第i个点到第i+1个点之间的距离
    vector<bool> diam(n + 1); //记录是否为直径上的点
    while (st > 0) {
        dis.push_back(st);
        diam[st] = true;
        val.push_back(prev[st].second);
        st = prev[st].first;
    }
    int len = dis.size();
    auto dfs2 = [&](auto dfs2, int u, int fa) -> int {
        //计算距离最远的点(不经过直径)
        int sum = 0;
        for (auto [v, w]: edge[u]) {
            if (v == fa || diam[v]) {
                //是直径点则跳过
                continue;
            }
            sum = max(sum, dfs2(dfs2, v, u) + w);
        }
        return sum;
    };
    vector<int> dismx(len + 1);
    for (int i = 1; i < len; i++) {
        dismx[i] = dfs2(dfs2, dis[i], 0);
    }
    Segt<int> sg(dismx), sg2(dismx), st3(dismx);
    vector<int> prem(len + 1), back(len + 1);
    for (int i = len - 1; i >= 1; i--) {
        //记录[R,len]内最大值
        sg.modify(i + 1, len - 1, val[i]);
        back[i] = sg.rmq(i, len - 1);
    }
    for (int i = 1; i < len; i++) {
        //记录[1,L]最大值
        sg2.modify(1, i - 1, val[i - 1]);
        prem[i] = sg2.rmq(1, i);
    }
    vector<int> pre(len + 1);
    for (int i = 0; i < len; i++) {
        //前缀和记录直径点之间的距离
        pre[i + 1] = pre[i] + val[i];
    }
    queue<int> que;
    int res = INT_MAX;
    for (int i = 1; i < len; i++) {
        que.push(i);
        while (pre[i] - pre[que.front()] > s) {
            //若距离超过s，弹出左端点
            que.pop();
        }
        int ans = max({prem[que.front()], back[i], st3.rmq(que.front(), i)});
        res = min(ans, res);
    }
    cout << res;
    return 0;
}