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;
}
)
