暑期训练8
E. G-C-D, Unlucky!
题目要求
判断是否存在一个长度为 n 的数组 a，使得
p[i]是a[0..i]的前缀 GCDs[i]是a[i..n-1]的后缀 GCD
思路
前缀 GCD 非递增
后缀 GCD 非递减
首尾 GCD 一致
桥梁条件成立
对于每个位置
i，gcd(p[i], s[i+1])必须等于整个数组的 GCD（即s[0]）。这一步是构造合法中间元素
a[i]的必要条件。
全部满足 → 输出 YES，否则 NO。
代码
#include<bits/stdc++.h>
using namespace std;
void solve(){long long n;cin>>n;vector<long long>p(n);vector<long long>s(n);for(int i=0;i<n;i++)cin>>p[i];for(int i=0;i<n;i++)cin>>s[i];if(p[n-1]!=s[0]){ //if(p.back()!=s[0])cout<<"NO"<<endl;return;}for(int i=1;i<n;i++){if(p[i-1]%p[i]&&i-1>=0){cout<<"NO"<<endl;return;}}for(int i=n-2;i>=0;i--){if(s[i+1]%s[i]&&i+1<n){cout<<"NO"<<endl;return;}}for(int i=0;i<n-1;i++){if(__gcd(p[i],s[i+1])!=s[0]){cout<<"NO"<<endl;return;}}cout<<"YES"<<endl;
}
int main(){long long t;cin>>t;while(t--){solve();}return 0;
}C. I Will Definitely Make It
本题要求
判断能否在水位不断上涨的情况下，从初始塔出发，通过多次传送最终到达最高的塔
思路
排序塔高度：
将所有塔按高度升序排序，方便后续贪心处理。找到初始塔位置：
在排序后的数组中找到初始塔的高度x所在的位置m。快速判断边界情况：
如果最高塔与初始塔的高度差 ≤ 初始塔高度（
h[n] - x ≤ x），可以直接传送到最高塔，输出YES。如果初始塔的下一个塔就比初始塔高太多（
h[m+1] - x > x），第一步就无法传送，直接输出NO。
贪心验证后续跳跃：
从初始塔
x开始，依次向后检查是否能“逐级跳跃”到最高塔。每次跳跃的代价是
h[i] - x，累计代价不能超过当前塔高度x。每次跳跃后，更新基准高度
x = h[i]（重置起点），继续向后验证。
代码
#include<bits/stdc++.h>
using namespace std;
void solve(){long long n,k;cin>>n>>k;long long h[n+1];for(int i=1;i<=n;i++)cin>>h[i];int x=h[k];sort(h+1,h+n+1);int m;for(int i=1;i<=n;i++){if(h[i]==x)m=i;}if(h[n]-x<=x){cout<<"YES"<<endl;return;}else if(h[m+1]-x>x){cout<<"NO"<<endl;return;}else{bool flag=1;int c=0;for(int i=m+1;i<=n;i++){c+=h[i]-x; //易错点，这里是比较时间，一定是累计时间总和，千万不要直接if(c<=x)x=h[i]; //用h[i]-x<=x来判断，虽然样例过了，但实际上逻辑一点不对else{cout<<"NO"<<endl;flag=0;break;}}if(flag)cout<<"YES"<<endl;}
}
int main(){long long t;cin>>t;while(t--)solve();return 0;
}D. This Is the Last Time
题目要求
有 n 家赌场，第 i 家给出 (l_i, r_i, real_i)，当前硬币数 k 必须满足 l_i ≤ k ≤ r_i 才能进入第 i 家赌场，进入后硬币数立即变成 real_i，每家赌场只能去一次，顺序可以任意，求 最多 能带走的硬币数。
思路
先把所有赌场按“门槛”从小到大排好，然后从左到右扫一遍：只要当前手里的钱 k 够得着某家赌场，并且进去后钱会更多，就立刻进去把钱换成更大的 real_i；扫完一遍后手里的钱就是最大可能值。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
struct node{long long l,r,re;
}p[N];
bool cmp(node x,node y){if(x.l==y.l)return x.r<y.r;return x.l<y.l;
}
void solve(){long long n,k;cin>>n>>k;for(int i=0;i<n;i++){cin>>p[i].l>>p[i].r>>p[i].re;}sort(p,p+n,cmp);for(int i=0;i<n;i++){if(k>=p[i].l&&k<=p[i].r&&k<p[i].re){k=p[i].re;}}cout<<k<<endl;
}
int main(){int t;cin>>t;while(t--)solve();return 0;
}
F. 1-1-1, Free Tree!
题目要求
给定一棵 n 个点的无根树，每条边连接 (u,v) 并有一个权值 c，每个顶点有一个颜色 a[i]。
边权规则：
如果两端颜色相同，这条边对总代价贡献 0；
不同则贡献 c。
接下来有 q 次查询：
每次给出 (u, x) —— 把顶点 u 的颜色改成 x，每次改色后，输出整棵树当前的总代价，颜色变化会累计，查询之间互相关联。
思路
建立树结构
用邻接表存无向边。预处理：DFS 把无向树变成“以 1 为根的有根树”
• 记录每个节点 u 的父节点 fa[u] 以及到父节点的边权 c[u]。
• 同时计算初始总代价 ans：对于每条树边 (u,fa[u])，若 a[u] ≠ a[fa[u]]，就把 c[u] 累进 ans。
• 用 map<int,int> mp[u] 记录“u 的所有子节点中颜色为 col 的边权和”，方便后面 O(log deg(u)) 批量更新。处理查询
对于每次 (u, x)：
• 若 x == a[u]，颜色无变化，直接输出当前 ans。
• 否则：处理父边：
– 若 u 不是根，判断原来 u 与父节点颜色是否相同。
– 同色→不同色：ans += c[u]（原来贡献 0，现在贡献 c[u]）。
– 不同色→同色：ans -= c[u]（原来贡献 c[u]，现在贡献 0）。
– 在父节点的 mp 表中把旧颜色减、新颜色加。处理子边：
– 原来与 u 同色→不同色：把 mp[u][old] 全部加回 ans。
– 原来与 u 不同色→同色：把 mp[u][new] 全部减掉。真正更新 a[u] = x，并输出 ans。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;typedef pair<int,int> PII;
const int N=2e5+10;/* ---------- 全局变量 ---------- */
int n,q,a[N]; // a[i]: 节点 i 的当前颜色
map<int,int> mp[N]; // mp[u][col]: 节点 u 的所有子节点中颜色为 col 的边权和
vector<PII> g[N]; // 邻接表: g[u] = {v,w}
int ans; // 整棵树当前总边权和
int fa[N],c[N]; // fa[i]: i 的父节点 c[i]: i 到父节点的边权/* ------------------------------------------------------------------* dfs(u): 以 u 为根向下遍历* 1. 建立父子关系* 2. 计算初始 ans* 3. 填充 mp[u][col] 方便后续查询* ------------------------------------------------------------------ */
void dfs(int u) {for (size_t i = 0; i < g[u].size(); ++i) {int v = g[u][i].first;int w = g[u][i].second;if (v == fa[u]) continue; // 不往回走fa[v] = u; // 记录父节点c[v] = w; // 记录到父节点的边权if (a[v] != a[u]) ans += w; // 两端颜色不同 → 产生代价mp[u][a[v]] += w; // 把这条边挂到父节点的“子边表”dfs(v); // 继续向下}
}/* ------------------------------------------------------------------* 主逻辑：读入 → 建树 → 预处理 → 处理每个查询* ------------------------------------------------------------------ */
void solve() {cin >> n >> q;ans = 0;/* ---------- 清空上一组数据 ---------- */for (int i = 1; i <= n; ++i) {fa[i] = -1;g[i].clear();mp[i].clear();c[i] = 0;}/* ---------- 读入颜色 ---------- */for (int i = 1; i <= n; ++i) cin >> a[i];/* ---------- 读入 n-1 条无向边 ---------- */for (int i = 1; i < n; ++i) {int u, v, w;cin >> u >> v >> w;g[u].push_back(make_pair(v, w));g[v].push_back(make_pair(u, w));}/* ---------- 以 1 为根做 DFS，建立父子关系并算初始答案 ---------- */dfs(1);/* ---------- 处理每个查询 ---------- */while (q--) {int u, x; // 把顶点 u 的颜色改成 xcin >> u >> x;if (a[u] == x) { // 颜色没变？直接输出cout << ans << '\n';continue;}/* 1. 先处理 u 与父节点之间的边 */if (fa[u] != -1) {int w = c[u]; // u 到父节点的边权// 原来同色 → 现在不同色：要加 wif (a[u] == a[fa[u]]) ans += w;// 原来不同色 → 现在同色：要减 wif (x == a[fa[u]]) ans -= w;/* 更新父节点的 mp 表：旧颜色减，新颜色加 */mp[fa[u]][a[u]] -= w;mp[fa[u]][x] += w;}/* 2. 再处理 u 与其所有子节点之间的边 */// 原来同色 → 现在不同色：把子边全加回来if (mp[u].count(a[u])) ans += mp[u][a[u]];// 原来不同色 → 现在同色：把子边全减掉if (mp[u].count(x)) ans -= mp[u][x];/* 3. 真正修改颜色 */a[u] = x;/* 4. 输出更新后的总边权和 */cout << ans << '\n';}
}/* ---------- 主函数：多组数据 ---------- */
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while (T--) solve();return 0;
}A Only One Digit
代码
#include<bits/stdc++.h>
using namespace std;
void solve(){int x;cin>>x;int mn=10;while(x){mn=min(mn,x%10);x/=10;}cout<<mn<<endl;
}
int main(){int t;cin>>t;while(t--)solve();return 0;
}