暑期训练8

发布于：2025-07-20 ⋅ 阅读:(15) ⋅ 点赞:(0)

E. G-C-D, Unlucky!

题目要求

判断是否存在一个长度为 n 的数组 a，使得

  • p[i] 是 a[0..i] 的前缀 GCD

  • s[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

本题要求

判断能否在水位不断上涨的情况下，从初始塔出发，通过多次传送最终到达最高的塔

思路

  1. 排序塔高度：
    将所有塔按高度升序排序，方便后续贪心处理。

  2. 找到初始塔位置：
    在排序后的数组中找到初始塔的高度 x 所在的位置 m。

  3. 快速判断边界情况：

    • 如果最高塔与初始塔的高度差 ≤ 初始塔高度（h[n] - x ≤ x），可以直接传送到最高塔，输出 YES。

    • 如果初始塔的下一个塔就比初始塔高太多（h[m+1] - x > x），第一步就无法传送，直接输出 NO。

  4. 贪心验证后续跳跃：

    • 从初始塔 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，每次改色后，输出整棵树当前的总代价，颜色变化会累计，查询之间互相关联。

思路

  1. 建立树结构
    用邻接表存无向边。

  2. 预处理：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)) 批量更新。

  3. 处理查询
    对于每次 (u, x)：
    • 若 x == a[u]，颜色无变化，直接输出当前 ans。
    • 否则：

    1. 处理父边：
      – 若 u 不是根，判断原来 u 与父节点颜色是否相同。
      – 同色→不同色：ans += c[u]（原来贡献 0，现在贡献 c[u]）。
      – 不同色→同色：ans -= c[u]（原来贡献 c[u]，现在贡献 0）。
      – 在父节点的 mp 表中把旧颜色减、新颜色加。

    2. 处理子边：
      – 原来与 u 同色→不同色：把 mp[u][old] 全部加回 ans。
      – 原来与 u 不同色→同色：把 mp[u][new] 全部减掉。

    3. 真正更新 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 的颜色改成 x
        cin >> u >> x;
        if (a[u] == x) {        // 颜色没变？直接输出
            cout << ans << '\n';
            continue;
        }

        /* 1. 先处理 u 与父节点之间的边 */
        if (fa[u] != -1) {
            int w = c[u];       // u 到父节点的边权
            // 原来同色 → 现在不同色：要加 w
            if (a[u] == a[fa[u]]) ans += w;
            // 原来不同色 → 现在同色：要减 w
            if (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;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布