首页 > 其他分享 >Atcoder ABC 346 全题解

Atcoder ABC 346 全题解

时间：2024-03-25 20:11:06浏览次数：25  
标签：Atcoder return min int 题解 ll 346 max define

闲话

  1. 上一篇全题解反向不错，如果大家支持我就会继续更。

  2. 我 ABC 也打了，ARC 也打了，没打好，疯狂掉大分……包括本场比赛也是整整补了 EFG 三道题，以及 ARC 死磕 D 结果使赛后五分钟 AC 又有素材了……

A

懒得讲

B

由于我被 B 题坑了，所以在此纪念。

最简单的方法就是把字符串复制 N 遍，然后暴力找。

N 太小会 WA，太大会 TLE，我选的 1024 遍，AC 了。

// Problem: B - Piano
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346)
// URL: https://atcoder.jp/contests/abc346/tasks/abc346_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#ifdef LOCAL
#include "debugger.h"
#define debug(x) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::print(x), cerr << endl)
#define debug_arr(x, n) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::printarr(x, n), cerr << endl)
#else
#include <bits/stdc++.h>
#define debug(x) 114514
#define debug_arr(x, n) 1919810
#endif

using namespace std;

#define ll long long
ll max(int a, ll b) { return max((ll)a, b); }
ll min(int a, ll b) { return min((ll)a, b); }
ll max(ll a, int b) { return max(a, (ll)b); }
ll min(ll a, int b) { return min(a, (ll)b); }

// Your code goes here...

string s = "wbwbwwbwbwbw";

int main() {
	int a, b;
	scanf("%d %d", &a, &b);
	for (int i = 0; i < 10; i++) { // 注：2^10=1024
		s = s + s;
	}
	for (int i = 0; i < s.size(); i++) {
		int ca = 0, cb = 0;
		for (int j = 0; j < a + b; j++) {
			ca += (s[i + j] == 'w');
			cb += (s[i + j] == 'b');
		}
		if (ca == a && cb == b) {
			puts("Yes");
			return 0;
		}
	}
	puts("No");
}

C

我们可以用 $ 1 \sim K $ 的和减去其中出现在数组里的数的和。

每遍历到一个数：

  • 如果它出现过或者 $ > K $，那就不理它。

  • 否则，就把这个数从和里剪掉。

至于怎么看它出没出现过，用 set 就可以了。

// Problem: C - Σ
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346)
// URL: https://atcoder.jp/contests/abc346/tasks/abc346_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#ifdef LOCAL
#include "debugger.h"
#define debug(x) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::print(x), cerr << endl)
#define debug_arr(x, n) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::printarr(x, n), cerr << endl)
#else
#include <bits/stdc++.h>
#define debug(x) 114514
#define debug_arr(x, n) 1919810
#endif

using namespace std;

#define ll long long
ll max(int a, ll b) { return max((ll)a, b); }
ll min(int a, ll b) { return min((ll)a, b); }
ll max(ll a, int b) { return max(a, (ll)b); }
ll min(ll a, int b) { return min(a, (ll)b); }

// Your code goes here...

unordered_set<int> st;

int main() {
	int n;
	ll k, sum;
	scanf("%d %lld", &n, &k);
	sum = k * (k + 1) / 2;
	for (int i = 0; i < n; i++) {
		ll x;
		scanf("%lld", &x);
		if (x <= k && !st.count(x)) {
			st.insert(x);
			sum -= x;
		}
	}
	printf("%lld", sum);
}

D

官方说有两种方法，一种是直接从头 DP，一种是从两端 DP，我是从头 DP 的。

设 $ f(i, j, k) $ 表示目前到第 $ i $ 位，上一个是 $ j $，已经出现了 $ k $ 对相邻的 00 或 11。

为了表述方便，设 $ g(i, j) $ 为把第 $ i $ 位变成 $ j $ 所需的代价。

则：

\[\begin{cases} f(i, 0, 0) = f(i - 1, 1, 0) + g(i, 0) \\ f(i, 1, 0) = f(i - 1, 0, 0) + g(i, 1) \\ f(i, 0, 1) = \min(f(i - 1, 1, 1), f(i - 1, 0, 0)) + g(i, 0) \\ f(i, 1, 1) = \min(f(i - 1, 0, 1), f(i - 1, 1, 1)) + g(i, 1) \end{cases} \]

最终答案显然就是 $ \min(f(n, 0, 1), f(n, 1, 1))) $。

// Problem: D - Gomamayo Sequence
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346)
// URL: https://atcoder.jp/contests/abc346/tasks/abc346_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#ifdef LOCAL
#include "debugger.h"
#define debug(x) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::print(x), cerr << endl)
#define debug_arr(x, n) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::printarr(x, n), cerr << endl)
#else
#include <bits/stdc++.h>
#define debug(x) 114514
#define debug_arr(x, n) 1919810
#endif

using namespace std;

#define ll long long
ll max(int a, ll b) { return max((ll)a, b); }
ll min(int a, ll b) { return min((ll)a, b); }
ll max(ll a, int b) { return max(a, (ll)b); }
ll min(ll a, int b) { return min(a, (ll)b); }

// Your code goes here...

ll f[200005][2][2];
ll a[200005];

int main() {
	int n;
	string s;
	cin >> n;
	cin >> s;
	for (int i = 0; i < n; i++) {
		scanf("%lld", &a[i]);
	}
	memset(f, 0x3f, sizeof f);
	f[0][0][0] = (s[0] != '0') * a[0];
	f[0][1][0] = (s[0] != '1') * a[0];
	for (int i = 1; i < n; i++) {
		f[i][0][0] = f[i - 1][1][0] + (s[i] != '0') * a[i];
		f[i][1][0] = f[i - 1][0][0] + (s[i] != '1') * a[i];
		f[i][0][1] = min(f[i - 1][0][0], f[i - 1][1][1]) + (s[i] != '0') * a[i];
		f[i][1][1] = min(f[i - 1][1][0], f[i - 1][0][1]) + (s[i] != '1') * a[i];
	}
	printf("%lld", min(f[n - 1][0][1], f[n - 1][1][1]));
}

E

老正难则反了。

假如我们从后往前，那么操作就变成了：

  • 把某一行（列）上所有还未确定颜色的格子确定颜色 $ X $。

当然了，最后还得加一个：

  • 把所有还未确定颜色的格子确定颜色 $ 0 $。

这样就好办了。

当我们对行操作的时候，就把总列数减去操作过的列数，即为当前操作确定的格子数。对列同理。

注意一下我们操作一行（列）第二次时不会有任何效果，因此还得额外开一个数组记录每行（列）有没有被操作过。

// Problem: E - Paint
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346)
// URL: https://atcoder.jp/contests/abc346/tasks/abc346_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#ifdef LOCAL
#include "debugger.h"
#define debug(x) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::print(x), cerr << endl)
#define debug_arr(x, n) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::printarr(x, n), cerr << endl)
#else
#include <bits/stdc++.h>
#define debug(x) 114514
#define debug_arr(x, n) 1919810
#endif

using namespace std;

#define ll long long
ll max(int a, ll b) { return max((ll)a, b); }
ll min(int a, ll b) { return min((ll)a, b); }
ll max(ll a, int b) { return max(a, (ll)b); }
ll min(ll a, int b) { return min(a, (ll)b); }

// Your code goes here...

struct op {
	int t, a, x;
} a[200005];

bool hvis[200005], wvis[200005];

map<int, ll> mp;

int main() {
	int h, w, n;
	scanf("%d %d %d", &h, &w, &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d %d", &a[i].t, &a[i].a, &a[i].x);
		a[i].a--;
	}
	ll hcnt = h, wcnt = w;
	for (int i = n - 1; i >= 0; i--) {
		if (a[i].t == 1) {
			if (!hvis[a[i].a]) {
				hvis[a[i].a] = 1;
				hcnt--;
				mp[a[i].x] += wcnt;
			}
		} else {
			if (!wvis[a[i].a]) {
				wvis[a[i].a] = 1;
				wcnt--;
				mp[a[i].x] += hcnt;
			}
		}
	}
	mp[0] += hcnt * wcnt;
	int ans = mp.size();
	for (auto xzcyyds : mp) {
		if (!xzcyyds.second) {
			ans--;
		}
	}
	printf("%d\n", ans);
	for (auto xzcyyds : mp) {
		if (xzcyyds.second) {
			printf("%d %lld\n", xzcyyds.first, xzcyyds.second);
		}
	}
}

F

显然，假如 $ g(T, k) $ 是 $ f(S, N) $ 的子串，那么 $ g(T, k - 1) $ 也是 $ f(S, N) $ 的子串，因此我们可以二分。

对于 $ T $ 的每一个字符，我们可以分开处理，维护每一个字符后会匹配到 $ f(S, N) $ 的哪里。（应该）有两种方式：

  1. 把 $ S $ 的前缀后缀某个字符的个数都统计出来，然后把 $ k $ 个字符分成三段：一段后缀、重复循环，一段前缀。巨难写。

  2. 倍增。没写过，不知道好不好写。

假如你 WA 了，可以试试这组数据：

2
aa
aa

// Problem: F - SSttrriinngg in StringString
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346)
// URL: https://atcoder.jp/contests/abc346/tasks/abc346_f
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#ifdef LOCAL
#include "debugger.h"
#define debug(x) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::print(x), cerr << endl)
#define debug_arr(x, n) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::printarr(x, n), cerr << endl)
#else
#include <bits/stdc++.h>
#define debug(x) 114514
#define debug_arr(x, n) 1919810
#endif

using namespace std;

#define ll long long
ll max(int a, ll b) { return max((ll)a, b); }
ll min(int a, ll b) { return min((ll)a, b); }
ll max(ll a, int b) { return max(a, (ll)b); }
ll min(ll a, int b) { return min(a, (ll)b); }

// Your code goes here...

#define ll long long

ll lim;
int n, m;
string s, t;
ll pre[30][100005];
ll suf[30][100005];

bool check(ll k) {
	// cerr << k << endl;
	ll rep = 0;
	int idx = 0;
	for (int i = 0; i < m; i++) {
		int x = t[i] - 'a';
		if (!suf[x][0]) {
			return 0;
		}
		if (suf[x][idx] >= k) { // 如果一个 S 可以解决问题
			idx = lower_bound(pre[x], pre[x] + n, (idx ? pre[x][idx - 1] : 0) + k) - pre[x] + 1;
		} else { // 否则
			ll cnt = k - suf[x][idx]; // 后缀
			// cerr << "#" << suf[0][0] << endl;
			rep++;
			idx = 0;
			rep += (cnt - 1) / suf[x][0]; // 循环
			cnt %= suf[x][0];
			if (!cnt) {
				cnt += suf[x][0];
			}
			idx = lower_bound(pre[x], pre[x] + n, cnt) - pre[x] + 1; // 前缀
		}
		// cerr << t[i] << " " << rep << " " << idx << endl;
		if (rep >= lim && (rep != lim || idx)) {
			// cerr << endl;
			return 0;
		}
	}
	// cerr << endl;
	return rep < lim || (rep == lim && !idx);
}

int main() {
	cin >> lim >> s >> t;
	n = s.size(), m = t.size();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 26; j++) {
			if (s[i] == 'a' + j) {
				pre[j][i] = (i ? pre[j][i - 1] : 0) + 1;
			} else {
				pre[j][i] = (i ? pre[j][i - 1] : 0);
			}
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j < 26; j++) {
			if (s[i] == 'a' + j) {
				suf[j][i] = suf[j][i + 1] + 1;
			} else {
				suf[j][i] = suf[j][i + 1];
			}
		}
	}
	ll l = 0, r = lim * (s.size()) / (t.size());
	// 因为这个上界我 WA 了好多次，选这个就对了
	while (l < r) { // 二分
		ll mid = l + ((r - l) >> 1) + 1;
		if (check(mid)) {
			l = mid;
		} else {
			r = mid - 1;
		}
	}
	printf("%lld", l);
}

G

闲话：我在补这题时在题解里看到了 Lazy Segment Tree，然而直到我补掉这题我还是不知道这是个什么东东。

首先，可以发现，对于每一个数 $ A_i $，可以找到它左边跟它相同的数和右边跟它相同的数，设它们的位置为 $ l, r $，则 $ (l + 1 \sim i, i \sim r - 1) $ 都是符合条件的。

考虑维护一个二维数组 $ f $，其中 $ f(i, j) $ 代表 $ (i, j) $ 符不符合条件。那么，对于上面提到的 $ l, i, r $，就相当于把 $ f(l + 1, i) \sim f(i, r - 1) $ 给置成 $ 1 $，就相当于是放置一个矩形，答案就是矩形的面积并。

因此用扫描线搞搞就结束了。

注：数组大小要开的大一点，不然会蜜汁 RE。

// Problem: G - Alone
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346)
// URL: https://atcoder.jp/contests/abc346/tasks/abc346_g
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#ifdef LOCAL
#include "debugger.h"
#define debug(x) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::print(x), cerr << endl)
#define debug_arr(x, n) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::printarr(x, n), cerr << endl)
#else
#include <bits/stdc++.h>
#define debug(x) 114514
#define debug_arr(x, n) 1919810
#endif

using namespace std;

#define ll long long
ll max(int a, ll b) { return max((ll)a, b); }
ll min(int a, ll b) { return min((ll)a, b); }
ll max(ll a, int b) { return max(a, (ll)b); }
ll min(ll a, int b) { return min(a, (ll)b); }

// Your code goes here...

struct node {
	ll cover, ans;
	node() {
		cover = ans = 0;
	}
} tree[3200005];

// 扫描线专用的线段树
// 关于扫描线的知识请自行 bdfs

void reload(int l, int r, int p) {
	if (tree[p].cover > 0) {
		tree[p].ans = (r - l + 1);
	} else {
		tree[p].ans = (tree[p * 2].ans + tree[p * 2 + 1].ans);
	}
}

void update(int L, int R, int x, int l, int r, int p) {
	if (L <= l && r <= R) {
		tree[p].cover += x;
		reload(l, r, p);
	} else {
		int mid = (l + r) / 2;
		if (mid >= L) {
			update(L, R, x, l, mid, p * 2);
		}
		if (mid < R) {
			update(L, R, x, mid + 1, r, p * 2 + 1);
		}
		reload(l, r, p);
	}
}

ll getans() {
	return tree[1].ans;
}

vector<int> idx[400005]; // 为了找 l，r 用的 idx 数组
int a[400005];

struct edge {
	int l, r, val;
	edge(int _l = 114, int _r = 514, int v = 0) {
		l = _l, r = _r, val = v;
	}
};

vector<edge> change[400005];

void add_rect(int r1, int c1, int r2, int c2) {
	change[r1].push_back(edge(c1, c2, 1));
	change[r2 + 1].push_back(edge(c1, c2, -1));
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= 400000; i++) {
		idx[i].push_back(0);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		idx[a[i]].push_back(i);
	}
	for (int i = 1; i <= 400000; i++) {
		idx[i].push_back(n + 1);
	}
	for (int i = 1; i <= n; i++) {
		int pos = lower_bound(idx[a[i]].begin(), idx[a[i]].end(), i) - idx[a[i]].begin();
		// 这里的 l，r 事实上是题目中的 l + 1 和 r - 1
		// 直接二分，为了避免越界在 idx 里面各加一个 0 和一个 n + 1
		// 这样左边没有时 l = 1，代表 L 从 1 开始到 i 都可以
		// r 同理
		int l = idx[a[i]][pos - 1] + 1;
		int r = idx[a[i]][pos + 1] - 1;
		add_rect(l, i, i, r);
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		for (edge x : change[i]) {
			update(x.l, x.r, x.val, 1, n, 1);
		}
		ans += getans();
	}
	printf("%lld", ans);
}

标签：Atcoder,return,min,int,题解,ll,346,max,define
From： https://www.cnblogs.com/AProblemSolver/p/18095143

相关文章

  • AtCoder Regular Contest 173 E Rearrange and Adjacent XOR
    洛谷传送门AtCoder传送门不妨考虑最后的结果可以成为哪些\(a_i\)的组合。为了方便分析，我们令\(a_i=2^{i-1}\)。进行一次操作后，所有\(\text{popcount}(a_i)\)都为偶数。所以一个\(x\in[0,2^n-1]\)能被生成出来的必要条件是\(\text{popcount}(x)\)为偶数。然......
  • AtCoder Beginner Contest 346 (ABCDEF)
    AtCoderBeginnerContest346A-AdjacentProduct题意给你一个数组a1,a......
  • 20240325每日一题题解
    20240325每日一题题解Problem给出一个整数\(a\)和一个正整数\(n\)，求乘方\(a^n\)。输入一行，包含两个整数\(a\)和\(n\)。\(-1000000\lea\le1000000\)，\(1\len\le10000\)。输出一个整数，即乘方结果。题目保证最终结果的绝对值不超过\(1000000\)。样例输入23样......
  • 动态尺寸加载libpag文件白边问题解决方案
    加载pag文件时，最理想的情况是canvas的宽高和pag资源文件的宽高一致，或比例一致。否则就会出现四周白边（页面底色），除非是按平铺的样式进行设置（源码暂未找到对应方法）。而对于页面宽高不定的情况下，就无法保证pag文件能适配页面，如果pag文件底色和父级页面底色不一致，就会表现出来......
  • CSP-S 2023 题解
    T1听说有歧义？希卓没看懂。不过真的水。你看能把它拧成什么正确密码。#include<bits/stdc++.h>#defineLLlonglongusingnamespacestd;LLn,sum,a[10][6],p,b[10][6];LLf[100010];intmain(){ scanf("%lld",&n); for(inti=1;i<=n;i++) { for(intj=1;j<=5;j++)......
  • CSP-J 2023 题解
    T1这么水？！赛时AC。思路：小学数学题，我孙子都会做认真点。就是余数和商，小学二年级的知识（毕导：亻尔女子）代码：#include<bits/stdc++.h>#defineLLlonglongusingnamespacestd;LLn,sum;LLt(LLa){ if(a!=1)return1+t(a-((a-1)/3+1)); elsereturn1;}intmain(){......
  • AT_arc175_a [ARC175A] Spoon Taking Problem 题解
    题目翻译link有\(N\)人围坐在一张圆桌旁，按逆时针顺序编号为\(1\)至\(N\)。每个人都有一个惯用手圆桌上有\(N\)把勺子，编号为\(1\)到\(N\)，每对相邻的人之间放一把勺子给你一个\((1,\dots,N)\)的排列组合\((P_1,\dots,P_N)\)。在\(i=1,\dots,N\)的顺序中，人......
  • 题解：AT_abc345_c [ABC345C] One Time Swap
    求过审题面翻译给定一个字符串$s$，求执行以下操作一次可以产生的字符串的个数设$N$为$s$的长度。选择一对整数$(i,j)$，使$1≤i<j≤N$，交换$s$的第$i$个和第$j$个字符可以证明，在这个问题的约束条件下，你总是可以得到它思路暴力做法我们可以......
  • JavaScript:void(0) 用法及常见问题解析
    JavaScript:void(0)用法及常见问题解析javascript:void(0);是一种在JavaScript和网页开发中经常使用的技术，尤其在处理链接的行为时。本文将深入探讨javascript:void(0);的用法，以及在使用过程中可能遇到的常见问题和解决方法。什么是javascript:void(0);？javascript:v......
  • Atcoder ABC144E Gluttony
    [ABC144E]Gluttony题面翻译【题目描述】高桥君参加大胃王比赛。比赛由\(N\)人组成的团队为基本单位参赛，高桥君的队伍的队员从\(1\simN\)编号。第\(i\)名队员的消化代价为\(A_i\)。比赛有\(N\)种不同的食物，每位队员需要负责吃掉其中一种食物，不能有两名队员吃同一种......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99