首页 > 其他分享 >AtCoder Beginner Contest 321(ABC321)

AtCoder Beginner Contest 321(ABC321)

时间:2023-10-30 20:55:51浏览次数:38  
标签:AtCoder like 10 int long 枚举 321 ABC321

A. 321-like Checker

直接模拟。

Code

B. Cutoff

直接暴力枚举 \([0\sim100]\),每次把第 \(n\) 个数当作当前枚举的 \(i\),然后看看条件是否满足。

Code

C. 321-like Searcher

Description

给你一个 \(K\),求出 \([1 \sim K]\) 区间内有多少个 321-like Number

321-like Number 的定义:

  • 每一位上的数字从左到右严格单调递减。
  • 或者说,若它有 \(d\) 位,对于 \(\forall i\in[1,d-1]\),从左到右第 \(i\) 位上的数大于从左到右第 \(i+1\) 位上的数。

Solution

预处理出所有的 321-like Number,枚举的时候类似枚举集合的做法。

存到 vector 数组里,排序后输出第 \(K\) 大的。

本题需要开 \(\text{long long}\)。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll; // 开long long
ll k;
int main() {
	scanf("%lld", &k);
	k--;
	vector<ll> v; // vector 存放枚举的结果
	for (int i = 2; i < (1 << 10); i++) {
		ll t = 0;
		for (int j = 9; j >= 0; j--) {
			if ((i >> j) & 1) { // 这一位为不为0
				t *= 10, t += j; // 加到结果里
			}
		}
		v.push_back(t);
	}
	sort(v.begin(), v.end()); // 排序
	printf("%lld", v[k]); // 输出结果
	return 0;
}

D. Set Menu

Description

有两个数列 \(A, B\),并给定一个常数 \(P\),现在 \(A_i\) 和 \(B_j\) 的配对总花费为:\(\min(A_i + B_j, P)\)。

现在求:所有可能的配对方式的总和。

\(N, M \le 2 \times 10 ^ 5\)。

Solution

这道题显然不能用暴力,\(O(4 \times 10 ^ {10})\),严重超时。

考虑如何优化。

可以将 \(B\) 从小到大排序,则对于每一个 \(A_i\),满足 \(A_i + B_j \le P\) 的 \(j\) 是一段前缀。

设 \(B_t\) 为最后一个满足 \(A_i + B_j \le P\) 的 \(B_j\),则对应的贡献为 \(tA_i + S_t + (n - t)P\)。其中 \(S_i\) 代表 \(B\) 数组前 \(i\) 个数的前缀和。

对于每一个 \(A_i\),双指针/二分都可求解。

注:在双指针情况下必须先将 \(A\) 数列降序排序。

Code

// LUOGU_RID: 128285445
#include <bits/stdc++.h>

using namespace std;

const int N = 200005;
int a[N], b[N], m, n, p;
long long s[N];
int main() {
	cin >> n >> m >> p;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
	sort(a + 1, a + n + 1, greater<int>());
	sort(b + 1, b + m + 1);
	for (int i = 1; i <= m; i++) s[i] = s[i - 1] + b[i];
	int now = 0;
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		while (now + 1 <= m && a[i] + b[now + 1] <= p) now++;
		ans += s[now] + 1LL * now * a[i] + 1LL * (m - now) * p;
	}
	printf("%lld", ans);
	return 0;
}

其他的题都没做出来,菜鸡一个。

标签:AtCoder,like,10,int,long,枚举,321,ABC321
From: https://www.cnblogs.com/yhx0322/p/17798782.html

相关文章

  • Atcoder Beginner Contest 326 (ABC326)
    不知道为什么拖到现在,我是摆怪。A.2UP3DOWN模拟,略。B.326-likeNumbers模拟,略。C.Peak双指针板子。D.ABCPuzzle基础dfs。但是赛时不知道为什么觉得状态数不会很少,于是写了一个巨大复杂的状压。这里粗略算算有效状态数:仅考虑每行的限制,有\(\binom{3}{5}=10\)种选......
  • AtCoder Beginner Contest 326
    A-2UP3DOWN(abc326A)题目大意100楼层,一次可以上最多两层,或下最多三层。给定两楼层,问能否一次到达。解题思路比较大小,然后判断其差是是不是在\(2\)或\(3\)内即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){......
  • AtCoder Beginner Contest 326 题解
    首先,\(\text{HappyBirthdaytome!}\)A-2UP3DOWN常规ABCA...//If,oneday,Ifinallymanagetomakemydreamsareality...//Iwonder,willyoustillbetherebymyside?#include<bits/stdc++.h>#defineIOSios::sync_with_stdio(false)#defineTI......
  • 【杂题乱写】AtCoder-ARC114
    AtCoder-ARC114_ANotcoprime\(50\)内的质数只有\(15\)个,可能的答案也就只有\(2^{15}\)个,直接枚举。提交记录:Submission-AtCoderAtCoder-ARC114_BSpecialSubsets就是\(i\)与\(f_i\)连边,每个连通块都是基环树,一定能剥叶子变成环,所以答案就是连通块非空子集个数。......
  • AtCoder Beginner Contest(abc) 310
    B-StrictlySuperior难度:⭐题目大意给定n个商品的价格,每个商品还有若干个属性,请问是否存在一个商品是另外一个商品的上位品;上位品的定义分两种,一是价格相同,但是商品A的属性不仅包括了商品B的属性,还比商品B多了至少一个属性;二是如果两商品的属性相同,但是......
  • AtCoder Beginner Contest 325
    感觉错失了上分机会A-Takahashisan(abc325A)题目大意给定姓和名,输出尊称,即姓+san。解题思路按照题意模拟即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(false);cin.tie(......
  • PCB封装命名规则,本文转载https://www.xjx100.cn/news/432127.html?action=onClick
    SO、SOP、SOIC、MSOP、TSSOP、TSOP、VSSOP、SSOP、SOJ封装详解 1. 简要信息如下: 2.SOP和SOIC的规格多是类似的,现在大多数厂商基本都采用的是SOIC的描述:SOIC8有窄体150mil的(外形封装宽度,不含管脚,下同),管脚间距是1.27mm,如下:有宽体的208mil的,管脚间距是1.27mm,如下:......
  • AtCoder Beginner Contest 216 H Random Robots
    洛谷传送门AtCoder传送门下文令\(n\)为原题中的\(K\),\(m\)为原题中的\(N\)。首先概率转方案数,最后除\(2^{nm}\)即可。考虑一个指数级暴力:枚举每个bot的终点\(y_i\)(因为存在不能相交的限制,需要满足\(y_1<y_2<\cdots<y_n\)),相当于为每个bot选一个\((0,x_i)......
  • AtCoder Regular Contest 164 F Subtree Reversi
    洛谷传送门AtCoder传送门非常好题目。发现每个点颜色被反转的次数是固定的,为其深度(根结点深度为\(0\))。于是可以看作是,一放棋子就得到分数。那么先手取偶数层和后手取奇数层都会使先手得分,所以双方的目标都是尽可能多取偶数层的结点。考虑若一开始有偶数层的叶子,那么当前的......
  • AtCoder Beginner Contest(abc) 309
    B-Rotate题目大意给定一个n*n的矩阵,要求把矩阵的最外围按照顺时针转动一个数据,输出转动后的矩阵;解题思路数据不大,暴力即可;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#def......