首页 > 其他分享 >ABC 369

ABC 369

时间：2024-09-01 09:52:11浏览次数：10  
标签：ABC int void long maxi 369 dfn id

ABC 369

刚才翻上次写的 abc 366 题解， 发现语言挺抽象， 导致自己都快看不懂了， 这回写好点

这段时间第一次 Rated， 情况一般吧， F 忘给同一个 \(x\) 的所有 \(y\) 排序了， 今天 (9.1) 早上突然看出来了。G 没有细看， 以为是个博弈论， 现在才发现是个简单贪心

369 这数挺吉利哈哈， 济南好像有说法是初三初六初九宜出行， 济南公交也有个 app 叫 369。这次就当作重新学 oi 的开始了， 369， 宜踏上新的征程！

A

题意

给定 \(a, b\)， 求一个 \(x\)， 使得三个数满足 \(q - p = r - q\) 的形式（\(a, b, x\) 顺序可变， 同一个 \((q, p, r)\) 只算一次）

解答

直接分类讨论即可， 重点是 \(a, b, x\) 存在至少两个数相等时怎么办

更简单的写法是直接枚举 \(x\)， 范围 \([-200, 200]\) ， map 判一下重的 \((q, p, r)\) 即可

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10, MOD = 998244353;

int a, b;
int ans;

signed main(){
    // freopen("1.in", "r", stdin);

    cin >> a >> b;

    ++ans;
    if((a + b) / 2 != a && (a + b) / 2 != b && (a + b) % 2 == 0) ++ans;
    if(a != b) ++ans;

    cout << ans << "\n";
}

B

题意

弹钢琴， 左右手相互独立， 按顺序给出每一步左/右手需要到达的位置坐标。

定义疲劳度为两坐标的差的绝对值， 手的起始位置由你决定， 求最小疲劳度

解答

这题有点诈骗啊

首先每步操作按顺序给出， 不能改变

然后起始位置设成左/右手分别的第一步操作的坐标即可， 剩下的是语法组内容

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10, MOD = 998244353;

int n, v;
char opt;
vector <int> l, r;

signed main(){
    // freopen("1.in", "r", stdin);

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> v >> opt;
        if(opt == 'L') l.push_back(v);
        else r.push_back(v);
    }

    // sort(l.begin(), l.end());
    // sort(r.begin(), r.end());

    int ans = 0;
    for(int i = 1; i < l.size(); i++){
        ans += abs(l[i] - l[i - 1]);
    }
    for(int i = 1; i < r.size(); i++){
        ans += abs(r[i] - r[i - 1]);
    }
    cout << ans << "\n";
}

C

题意

给定正整数序列， 求有序不可重数对 \((l, r)\) 的个数， 使得 \(a_l...a_r\) 是等差数列（\(l, r\) 可以相等）

解答

判断等差数列常见套路：差分相等

然后就没了

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10, MOD = 998244353;

int n;
int a[N], cha[N];

signed main(){
    // freopen("1.in", "r", stdin);

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        cha[i] = a[i] - a[i - 1];
    }

    int lst = cha[2], cnt = 1, ans = n;
    for(int i = 3; i <= n; i++){
        if(cha[i] == lst){
            ++cnt;
        }else{
            ans += (1 + cnt) * cnt / 2;
            cnt = 1;
            lst = cha[i];
        }
    }
    if(n != 1) ans += (1 + cnt) * cnt / 2;
    cout << ans << "\n";
}

D

题意

打怪， 打死每只怪物可以获得一定的经验， 必须按顺序， 但可以跳过一些怪物

对于你打死的第 \(i\) 只怪物， 如果 \(i\) 是偶数， 可以获得双倍经验

解答

小 DP

设 \(odd(i)\) 表示考虑到第 \(i\) 只怪物， 一共打死了奇数只， 获得的最大经验， \(even(i)\) 同理

每次转移是 \(O(1)\) 的

odd[i] = max(odd[i - 1], even[i - 1] + a[i]);
even[i] = max(even[i - 1], odd[i - 1] + a[i] * 2);

但是边界要稍微处理一下， 我因此 Wa 了一发

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10, INF = 1e18;

int n;
int a[N], odd[N], even[N];

signed main(){
    // freopen("1.in", "r", stdin);

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    odd[0] = -INF, even[0] = 0;
    for(int i = 1; i <= n; i++){
        odd[i] = max(odd[i - 1], even[i - 1] + a[i]);
        even[i] = max(even[i - 1], odd[i - 1] + a[i] * 2);
    }

    int ans = max(odd[n], even[n]);
    cout << ans << "\n";
}

E

题意

有一些节点和双向道路。

你的目标是从 1 走到 n， 每次指定 \(O(1)\) 条道路， 完成上述目标的同时必须经过这些道路至少一次， 求最短距离

解答

只限定了 \(5\) 条道路， \(3e3\) 次询问， 很难不想着钻空子

不妨枚举经过这些道路的顺序， 共 \(5！\) 种， 再枚举每条路从 \(u\) 到 \(v\) 还是反过来， \(2^5\) 种， 发现完全可过

然后就完事了， 最短路 Floyd 都可以做， 代码复杂度极低哈哈哈

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e2 + 10, M = 2e5 + 10, INF = 1e18;

int n, m;
int u, v, w;
int e[N][N], mini;

int q, k, b[N];

struct Edge{
    int u, v, w;
}rec[M];

void Floyd(){
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
            }
        }
    }
}

void Dfs(int x, int st, int dis){
    if(x == k + 1){
        mini = min(mini, dis + e[st][n]);
        return;
    }
    Dfs(x + 1, rec[b[x]].v, dis + e[st][rec[b[x]].u] + rec[b[x]].w);
    Dfs(x + 1, rec[b[x]].u, dis + e[st][rec[b[x]].v] + rec[b[x]].w);
}

signed main(){
    // freopen("1.in", "r", stdin);

    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            e[i][j] = INF;
        }
        e[i][i] = 0;
    }

    for(int i = 1; i <= m; i++){
        cin >> u >> v >> w;
        rec[i] = {u, v, w};
        e[u][v] = min(e[u][v], w);
        e[v][u] = e[u][v];
    }

    Floyd();

    cin >> q;
    for(int i = 1; i <= q; i++){
        cin >> k;
        for(int j = 1; j <= k; j++){
            cin >> b[j];
        }

        mini = INF;
        do{
            Dfs(1, 1, 0);
        }while(next_permutation(b + 1, b + 1 + k));
        cout << mini << "\n";
    }
}

F

题意

网格图上行走， 只能往右或往下， 其中一些格点打了标记。

问你从 \((1, 1)\) 走到 \((h, w)\) 的过程中最多经过多少标记点， 并且用 \(D, R\) 的方式输出一种行走方案

网格图的大小是 \(2e5 * 2e5\) 的， 总共 \(2e5\) 个标记点

解答

如果格子小一点， 那么就是个普及组题。既然这样， 那么我们的算法肯定是基于标记点个数而非整个网格的。

考虑 ”传统“ 的转移：

\[dp(i, j) = max\{dp(ii, jj)\} + 1 \]

\[(ii, jj) 在 (i, j) 的左上方 \]

所以想起了二维问题的常见处理思路：固定一维扫另一维

从上到下扫过 \(x\) 轴， 枚举当前 \(x\) 的对应的所有 \(y\) (这里一定要排序！！！， 我因此 Wa 了两发)。

对于确定的 \(y\) ， 求出 \(y' \le y\) 的 \(y'\) 对应的最大 \(dp\) 值， 因为固定了 \(x\) 的顺序是从上到下， 所以每一个 \(y'\) 内存储的信息都来自于小于当前 \(x\) 的 \(x'\)， 开个线段树维护一下即可

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e7 + 10, INF = 1e18;

int h, w, n;
int r[N], c[N], ir[N], ic[N], cnt;
map <int, int> rec, rcr, rcc;

int rr[N], cc[N], cntr, cntc;

int pre[N];
vector <int> ans;
vector <pair <int, int>> vec[N];

struct Segment_Tree{
    struct Node{
        int l, r;
        int maxi, id;
    }t[N];

    void Build(int id, int l, int r){
        t[id] = {l, r, 0};
        if(l == r) return;
        int mid = (l + r) / 2;
        Build(id * 2, l, mid);
        Build(id * 2 + 1, mid + 1, r);
    }

    void Modify(int id, int l, int r, int x, int idx){
        if(r < t[id].l || t[id].r < l) return;
        if(l <= t[id].l && t[id].r <= r){
            // t[id].maxi = max(t[id].maxi, x);
            if(x > t[id].maxi){
                t[id].maxi = x;
                t[id].id = idx;
            }
            return;
        }
        Modify(id * 2, l, r, x, idx), Modify(id * 2 + 1, l, r, x, idx);
        if(t[id * 2].maxi > t[id * 2 + 1].maxi){
            t[id].maxi = t[id * 2].maxi;
            t[id].id = t[id * 2].id;
        }else{
            t[id].maxi = t[id * 2 + 1].maxi;
            t[id].id = t[id * 2 + 1].id;            
        }
    }

    pair <int, int> Query(int id, int l, int r){
        if(r < t[id].l || t[id].r < l) return {0, 0};
        if(l <= t[id].l && t[id].r <= r){
            return {t[id].maxi, t[id].id};
        }
        auto a = Query(id * 2, l, r);
        auto b = Query(id * 2 + 1, l, r);
        if(b.first > a.first){
            a = b;
        }
        return a;
    }
}t;

signed main(){
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);

    cin >> h >> w >> n;
    for(int i = 1; i <= n; i++){
        cin >> r[i] >> c[i];
        rr[++cntr] = r[i];
        cc[++cntc] = c[i];
    }

    sort(rr + 1, rr + 1 + cntr);
    sort(cc + 1, cc + 1 + cntc);

    int ca = 0;
    for(int i = 1; i <= cntr; i++){
        if(!rcr[rr[i]]) rcr[rr[i]] = ++ca;
    }

    int cb = 0;
    for(int i = 1; i <= cntc; i++){
        if(!rcc[cc[i]]) rcc[cc[i]] = ++cb;
    }    

    for(int i = 1; i <= n; i++){
        vec[rcr[r[i]]].push_back({rcc[c[i]], i});
    }

    t.Build(1, 1, cb);
    for(int i = 1; i <= ca; i++){
        sort(vec[i].begin(), vec[i].end());
        for(auto j : vec[i]){
            auto v = t.Query(1, 1, j.first);
            pre[j.second] = v.second;
            t.Modify(1, j.first, j.first, v.first + 1, j.second);
        }
    }
    // cout << t.Query(1, 1, cb) << "\n"
    int anss = t.Query(1, 1, cb).first;
    int ret = t.Query(1, 1, cb).second;

    r[n + 10] = h, c[n + 10] = w;
    ans.push_back(n + 10);

    while(ret){
        ans.push_back(ret);
        ret = pre[ret];
    }


    r[n + 20] = 1, c[n + 20] = 1;
    ans.push_back(n + 20);

    reverse(ans.begin(), ans.end());

    // for(auto i : ans) cout << i << " ";
    // cout << "\n";

    cout << anss << "\n";
    for(int i = 1; i < ans.size(); i++){
        int id = ans[i], lst = ans[i - 1];
        int x = abs(r[id] - r[lst]), y = abs(c[id] - c[lst]);
        // cout << x << "+" << y << "\n";
        for(int j = 1; j <= x; j++) cout << "D";
        for(int j = 1; j <= y; j++) cout << "R";
    }
    cout << "\n";
}

G

题意

俩人在玩游戏， 对象是一棵树， 根为 1

其中一个人 A 在树上指定了 \(k\) 个节点， 另一个人 B 要从 1 出发， 经过这些点回到 1

A 想最大化路径长度， B 想最小化， 求对于 \(k = 1, 2, ..., n\) ， 最优策略下的路径长度

解答

披着博弈外皮的贪心

如果告诉你这 \(k\) 个点， 那么 \(B\) 的最优策略就是这 \(k\) 个点到根的路径并的长度 \(*2\) ， 这个显然， 或者手算一下就可以得出

如果这 \(k\) 个点是依次加入集合的， 那么每次的增量就是加入点到根的路径上、之前没被走过的边的边权和 (\(*2\))

对于 A， 他的策略就是选一个当前情况（有一些边被走过， 不重复计入）下距离 1 最远的点， 加入集合

所以只需要实现一个数据结构， 支持：

  1. 查询到 1 的最大距离
  2. 点到根的路径上边权置零

性质： 路径都是向根且连续的！并且每条边只会修改一次

求一下 Dfn 然后线段树维护即可

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, MOD = 998244353;

int n;
int u, v, w;
int dfn[N], cdfn, fa[N][2], dis[N], si[N];	// fa : father, edge_val
int tag[N];

struct Edge{
	int v, w;
};
vector <Edge> e[N];

struct Segment_Tree{
	struct Node{
		int l, r;
		int maxi, maxid, tag;
	}t[N];

	struct Ret{
		int maxi, maxid;
	}ret;

	void Update(int id, int x){
		t[id].maxi += x;
		t[id].tag += x;
	}

	void Push_down(int id){
		Update(id * 2, t[id].tag);
		Update(id * 2 + 1, t[id].tag);
		t[id].tag = 0;
	}

	void Push_up(int id){
		if(t[id * 2].maxi > t[id * 2 + 1].maxi){
			t[id].maxi = t[id * 2].maxi;
			t[id].maxid = t[id * 2].maxid;
		}else{
			t[id].maxi = t[id * 2 + 1].maxi;
			t[id].maxid = t[id * 2 + 1].maxid;			
		}
	}

	void Build(int id, int l, int r){
		t[id].l = l, t[id].r = r;
		if(l == r){
			t[id].maxi = dis[l];
			t[id].maxid = l;
			return;
		}
		int mid = (l + r) / 2;
		Build(id * 2, l, mid);
		Build(id * 2 + 1, mid + 1, r);
		Push_up(id);
	}

	void Modify(int id, int l, int r, int x){
		if(r < t[id].l || t[id].r < l){
			return;
		}
		if(l <= t[id].l && t[id].r <= r){
			Update(id, x);
			return;
		}
		Push_down(id);
		Modify(id * 2, l, r, x);
		Modify(id * 2 + 1, l, r, x);
		Push_up(id);
	}

	Ret Query(int id, int l, int r){
		if(r < t[id].l || t[id].r < l){
			return {0, 0};
		}
		if(l <= t[id].l && t[id].r <= r){
			return {t[id].maxi, t[id].maxid};
		}
		Push_down(id);
		Ret a = Query(id * 2, l, r);
		Ret b = Query(id * 2 + 1, l, r);
		a = (a.maxi > b.maxi) ? a : b;
		return a;
	}
}tr;

void Get_Dfn(int x, int y, int w){
	dfn[x] = ++cdfn;
	si[dfn[x]] = 1;
	dis[dfn[x]] = dis[dfn[y]] + w;
	fa[dfn[x]][0] = dfn[y], fa[dfn[x]][1] = w;
	for(auto i : e[x]){
		if(i.v == y) continue;
		Get_Dfn(i.v, x, i.w);
		si[dfn[x]] += si[dfn[i.v]];
	}
}

struct Delete{
	int idx, val;
};

vector <Delete> del;

void Del(int x){
	int p = x;
	while(!tag[p]){
		tag[p] = 1;
		tr.Modify(1, p, p + si[p] - 1, -fa[p][1]);
		p = fa[p][0];
	}
}

signed main(){
	// freopen("1.in", "r", stdin);

	cin >> n;
	for(int i = 1; i < n; i++){
		cin >> u >> v >> w;
		e[u].push_back({v, w});
		e[v].push_back({u, w});
	}

	Get_Dfn(1, 0, 0);
	tr.Build(1, 1, n);

	tag[1] = 1;	// 终止点
	int ans = 0;
	for(int i = 1; i <= n; i++){
		auto ret = tr.Query(1, 1, n);

		// cout << ret.maxid << " " << ret.maxi << "\n";

		ans += ret.maxi * 2;
		cout << ans << "\n";

		Del(ret.maxid);
	}
}

标签：ABC,int,void,long,maxi,369,dfn,id
From： https://www.cnblogs.com/Bubblee/p/18391033

相关文章

  • Atcoder Beginner Contest 369
    AtcoderBeginnerContest369C-CountArithmeticSubarrays题意给出一个长度为\(n\)的序列\(A\)，求有多少个\(A\)的连续子序列为等差数列。思路对于递增的右端点，左端点不减。使用双指针，枚举右端点，扫描左端点。时间复杂度：\(O(n)\)。代码#include<bits/stdc++.h>usi......
  • AtCoder Beginner Contest 369 补题记录（A~G）
    AconstintN=1000100;inta[N];signedmain(){intx,y;cin>>x>>y;if(x==y)cout<<"1\n";elseif(x%2==y%2)cout<<"3\n";elsecout<<"2\n";}BconstintN=1000100;inta[N];sign......
  • AtCoder Beginner Contest 369 A~D
    封面原图画师かにょこAtCoderBeginnerContest369我愿称之为等差数列场A-369题意给两个数，问能和他们构成等差数列的数有多少个代码#include<bits/stdc++.h>#definemod998244353usingnamespacestd;typedeflonglongll;typedefdoubledb;type......
  • ABC369
    Alink判断\(A\)，\(B\)之间可不可以放一个数，如果可以就是\(3\)个，不行就是\(2\)个（左右），但是如果\(A\)，\(B\)相等就只有一个。点击查看代码#include<bits/stdc++.h>usingnamespacestd;signedmain(){ inta,b; cin>>a>>b; intx=b-a; if(x!=0){ if(x%2==0......
  • Atcoder Beginner Contest 369
    AtcoderBeginnerContest369唯一的一发罚时吃在A题，消息了。A挂一发的原因是以为\(A,B\)都是一位数，然后循环范围开了\([-10,20]\)。#include<bits/stdc++.h>usingnamespacestd;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr);// int_;cin>>_;while......
  • luoguP5369 [PKUSC2018] 最大前缀和
    题目n<=20题解想了半天3位状态的折半，然后发现空间开不下（时间也不太行）所以放弃思考，直接枚举答案答案是a中的一个集合，设为S；记集合S的和为sum[S]考虑当S确定时，有多少种方案能使答案恰好为sum[S]。为了处理多种sum相同的情况，记S为从前往后考虑，第一次出现最大ans的集合；记剩余部......
  • Versal Prime 系列 VM2202 自适应 SoC平台，XCVM2202-1LSINSVH1369、XCVM2202-1MLINSVH1
    VersalPrime系列是一款高度集成、多核、异构计算平台，适用于数据中心网络、存储和有线通信等多种应用。它通过在优化了连接性的设备中实现低延迟的内联加速，为这些应用提供突破性的性能。VersalPrime系列VM2202自适应SoC相关型号：XCVM2202-1LSINSVH1369XCVM2202-2LSENSVH13......
  • ABC368
    Alink先输出后面，在输出前面。神奇的代码#include<bits/stdc++.h>usingnamespacestd;intn,k;inta[105];signedmain(){ cin>>n>>k; for(inti=1;i<=n;++i){ cin>>a[i]; if(i>=n-k+1)cout<<a[i]<<"......
  • ABC_234_ex sol
    题意在平面直角坐标系中找出所有\(dist(i,j)\leqk\)的点对个数\(\leq4\times10^5\)\(1\len\le2\times10^5\)\(1\lek\le1.5\times10^5\)hint分块不是dssol考虑将网格分割，每\(k\)行\(k\)列分一格。注意到分完块以后对于一个点\((i,j)\)所在的块\(B_{(i,j)}......
  • 题解 [ABC199F] Graph Smoothing（中文/English）
    本题解提供英文版，位于示例代码之后。Englishversionofthiseditorialisprovidedafterthesamplecode.设行向量：\[A^{(k)}=\begin{bmatrix}a_1^{(k)}&a_2^{(k)}&\cdots&a_n^{(k)}\end{bmatrix}\]表示\(k\)次操作后每个节点点权的期望。特别地，\(A^{(0)}\)表......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99