IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> C++知识库 -> AtCoder Beginner Contest 252 A~G 题解 -> 正文阅读

[C++知识库]AtCoder Beginner Contest 252 A~G 题解

前言

  • 这是我第一次写7题（A~G）的ABC题解，若有写得不好或者不到位的地方请多多指教，我将万分感激，感谢大家的支持！

ABC252 A~G

A - ASCII code

题目大意

给定正整数 N N N，输出ASCII码是 N N N的字母。
97 ≤ N ≤ 122 97\le N\le 122 97≤N≤122

输入格式

N N N

输出格式

输出ASCII码是 N N N的字母。

分析

注意a对应 97 97 97，b对应 98 98 98，……，z对应 122 122 122。
安上小白专属转换教程：

  • C
    int n = 97;
putchar(n); /* 输出：a */
    putchar函数自动转换为字符，也可以使用printf("%c", n)效果相同
  • C++
    int n = 97;
cout << char(n) << endl; // 输出：a
    直接cout << n会输出97，需要用char转换为字符
  • Python
    n = 97
print(chr(n)) # 输出：a
    同样也不能直接输出，需要用chr转换
  • Java
    int n = 97;
char c = (char) n;
System.out.print(c);
    与C++、Python类似，需要转换
  • JavaScript
    var n = 97;
var c = String.fromCharCode(n);
console.log(c); // 输出：a
    同样使用接口转化，需调用String.fromCharCode

再不懂你试试……

代码

太水，直接走一发py（现场25秒AC）

print(chr(int(input())))

B - Takahashi’s Failure

题目大意

Takahashi的房子里有 N N N个食物。第 i i i个食物的美味度是 A i A_i Ai?。
其中，他不喜欢 K K K个食物： B 1 , B 2 , … , B K B_1,B_2,\dots,B_K B1?,B2?,…,BK?。
已知Takahashi会从 N N N个食物中随机选取一个美味度最大的食物，并把它吃掉。
Takahashi是否有可能迟到不喜欢的食物？

1 ≤ K ≤ N ≤ 100 1\le K\le N\le 100 1≤K≤N≤100
1 ≤ A i ≤ 100 1\le A_i\le 100 1≤Ai?≤100
1 ≤ B i ≤ N 1\le B_i\le N 1≤Bi?≤N

输入格式

N ? K N~K N?K
A 1 ? … ? A N A_1~\dots~A_N A1??…?AN?
B 1 ? … ? B K B_1~\dots~B_K B1??…?BK?

输出格式

如果有可能，输出Yes；否则，输出No。

分析

只要有不喜欢的食物美味度最高就有可能，否则不可能。详见代码。

代码

还是水，注意如果是 0-indexed \text{0-indexed} 0-indexed的话 B i B_i Bi?要减 1 1 1

#include <cstdio>
using namespace std;

int a[105];

int main()
{
	int n, k, mx = 0;
	scanf("%d%d", &n, &k);
	for(int i=0; i<n; i++)
	{
		scanf("%d", a + i);
		if(a[i] > mx) mx = a[i];
	}
	while(k--)
	{
		scanf("%d", &n);
		if(a[--n] == mx)
		{
			puts("Yes");
			return 0;
		}
	}
	puts("No");
	return 0;
}

C - Slot Strategy

题目大意

略，请自行前往AtCoder查看。

2 ≤ N ≤ 100 2\le N\le 100 2≤N≤100

输入格式

N N N
S 1 S_1 S1?
? \vdots ?
S N S_N SN?

输出格式

输出答案。

分析

令 cnt [ i ] [ j ] = ( S k [ j ] = i \text{cnt}[i][j]=(S_k[j]=i cnt[i][j]=(Sk?[j]=i的个数 ) ) )，对最终变成 0 0 0- 9 9 9分别计算代价即可。详见代码。

代码

#include <cstdio>
using namespace std;

int cnt[10][10]; // cnt[i][j] = number of (s[j]=i)

int main()
{
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
	{
		char s[15];
		scanf("%s", s);
		for(int j=0; j<10; j++)
			cnt[s[j] ^ 48][j] ++;
	}
	int ans = 1000;
	for(int i=0; i<10; i++)
	{
		int cur = 0;
		for(int j=0; j<10; j++)
		{
			int c = j + (cnt[i][j] - 1) * 10;
			if(c > cur) cur = c;
		}
		if(cur < ans) ans = cur;
	}
	printf("%d\n", ans);
	return 0;
}

D - Distinct Trio

题目大意

给定长为 N N N的整数序列 A = ( A 1 , … , A N ) A=(A_1,\dots,A_N) A=(A1?,…,AN?)。
求符合以下条件的整数对 ( i , j , k ) (i,j,k) (i,j,k)的个数：

  • 1 ≤ i < j < k ≤ N 1\le i<j<k\le N 1≤i<j<k≤N
  • A i ≠ A j ≠ A k A_i\ne A_j\ne A_k Ai??=Aj??=Ak?

3 ≤ N ≤ 2 × 1 0 5 3\le N\le 2\times 10^5 3≤N≤2×105
1 ≤ A i ≤ 2 × 1 0 5 1\le A_i\le 2\times 10^5 1≤Ai?≤2×105

输入格式

N N N
A 1 ? … ? A N A_1~\dots~A_N A1??…?AN?

输出格式

输出一行，即符合条件的整数对 ( i , j , k ) (i,j,k) (i,j,k)的个数。

分析

本题主要有两种思路：

  1. 逆向思维，用总数-不符合条件的；
  2. 将题目转化为求 A i < A j < A k A_i<A_j<A_k Ai?<Aj?<Ak?的 ( i , j , k ) (i,j,k) (i,j,k)的个数。

这里介绍第一种方法（第二种方法较为简单，不详细说明）。

首先易得，总共的 1 ≤ i < j < k ≤ N 1\le i<j<k\le N 1≤i<j<k≤N有 C n 3 C_n^3 Cn3?种取法。
然后考虑 A i , A j , A k A_i,A_j,A_k Ai?,Aj?,Ak?中有重复的个数：

  • 对于 A A A中每个数 x x x，我们记录 cnt x = A \text{cnt}_x=A cntx?=A中 x x x出现的次数；
  • 然后，如果 cnt x ≥ 2 \text{cnt}_x\ge 2 cntx?≥2，则将答案减去 C cnt x 2 × ( N ? cnt x ) C_{\text{cnt}_x}^2\times(N-\text{cnt}_x) Ccntx?2?×(N?cntx?)，即 x , x , y x,x,y x,x,y格式出现的次数；
  • 又如果 cnt x ≥ 3 \text{cnt}_x\ge 3 cntx?≥3，将答案减去 C cnt x 3 C_{\text{cnt}_x}^3 Ccntx?3?，即 x , x , x x,x,x x,x,x的次数。

总时间复杂度为 O ( N + max ? A ? min ? A ) \mathcal O(N+\max_A-\min_A) O(N+maxA??minA?)，空间复杂度为 O ( max ? A ? min ? A ) \mathcal O(\max_A-\min_A) O(maxA??minA?)。

代码

#include <cstdio>
#define maxn 200005
using namespace std;

using LL = long long;
int cnt[maxn];

inline LL C2(int n) { return n * (n - 1LL) >> 1LL; }
inline LL C3(int n) { return C2(n) * (n - 2LL) / 3LL; }

int main()
{
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
	{
		int a;
		scanf("%d", &a);
		cnt[a] ++;
	}
	LL ans = C3(n);
	for(int i=1; i<maxn; i++)
		if(cnt[i] > 1)
		{
			ans -= C2(cnt[i]) * (n - cnt[i]);
			if(cnt[i] > 2) ans -= C3(cnt[i]);
		}
	printf("%lld\n", ans);
	return 0;
}

E - Road Reduction

题目大意

给定一张由 N N N个点和 M M M条边组成的简单无向图。
第 i i i条边长度为 C i C_i Ci?，同时连接点 A i A_i Ai?和 B i B_i Bi?。
求任意一颗生成树，使得从点 1 1 1到其他所有点的距离之和最小。

2 ≤ N ≤ 2 × 1 0 5 2\le N\le 2\times 10^5 2≤N≤2×105
N ? 1 ≤ M ≤ 2 × 1 0 5 N-1\le M\le 2\times 10^5 N?1≤M≤2×105
1 ≤ A i < B i ≤ N 1\le A_i<B_i\le N 1≤Ai?<Bi?≤N
( A i , B i ) ≠ ( A j , B j ) (A_i,B_i)\ne(A_j,B_j) (Ai?,Bi?)?=(Aj?,Bj?)（ i ≠ j i\ne j i?=j）
1 ≤ C i ≤ 1 0 9 1\le C_i\le 10^9 1≤Ci?≤109

输入格式

N ? M N~M N?M
A 1 ? B 1 ? C 1 A_1~B_1~C_1 A1??B1??C1?
? \vdots ?
A M ? B M ? C M A_M~B_M~C_M AM??BM??CM?

输出格式

按任意顺序输出留下来的 N ? 1 N-1 N?1条边的下标，用空格隔开。

分析

显然，在生成树中，点 1 1 1到任意点的距离肯定不少于在原图中到这个点的距离。
因此，如果两个距离相等，显然就是最优解。
此时可以证明，肯定有这样的解。使用Dijkstra算法求最短路径的同时，记录到每个点之前的最后一条路即可。

代码

Dijkstra的两种经典实现方式， O ( N log ? N + M log ? N ) \mathcal O(N\log N+M\log N) O(NlogN+MlogN)

  • priority_queue优先队列（ 182 ms 182\text{ms} 182ms）
    #include <cstdio>
#include <queue>
#define maxn 200005
#define INF 9223372036854775807LL
using namespace std;

using LL = long long;
using pli = pair<LL, int>;

struct Edge
{
	int v, id; LL d;
	inline Edge(int u, int l, int i): v(u), d(l), id(i) {}
};

vector<Edge> G[maxn];
LL dis[maxn];
int ans[maxn];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		G[--a].emplace_back(--b, c, i);
		G[b].emplace_back(a, c, i);
	}
	priority_queue<pli, vector<pli>, greater<pli>> q;
	for(int i=1; i<n; i++) dis[i] = INF;
	q.emplace(0LL, 0);
	while(!q.empty())
	{
		auto [d, v] = q.top(); q.pop();
		if(dis[v] == d)
			for(const Edge& e: G[v])
			{
				LL nd = d + e.d;
				if(nd < dis[e.v])
					q.emplace(dis[e.v] = nd, e.v),
					ans[e.v] = e.id;
			}
	}
	for(int i=1; i<n; i++) printf("%d ", ans[i]);
	return 0;
}
  • set集合（ 202 ms 202\text{ms} 202ms）
    #include <cstdio>
#include <vector>
#include <set>
#define maxn 200005
#define INF 9223372036854775807LL
using namespace std;

using LL = long long;
using pli = pair<LL, int>;

struct Edge
{
	int v, id; LL d;
	inline Edge(int u, int l, int i): v(u), d(l), id(i) {}
};

vector<Edge> G[maxn];
LL dis[maxn];
int ans[maxn];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		G[--a].emplace_back(--b, c, i);
		G[b].emplace_back(a, c, i);
	}
	set<pli> s; // <distance, vertex>
	for(int i=1; i<n; i++) dis[i] = INF;
	s.emplace(0LL, 0);
	while(!s.empty())
	{
		auto [d, v] = *s.begin(); s.erase(s.begin());
		for(const Edge& e: G[v])
		{
			LL nd = d + e.d;
			if(nd < dis[e.v])
			{
				if(dis[e.v] < INF)
					s.erase(pli(dis[e.v], e.v));
				s.emplace(dis[e.v] = nd, e.v);
				ans[e.v] = e.id;
			}
		}
	}
	for(int i=1; i<n; i++) printf("%d ", ans[i]);
	return 0;
}

注意使用long long。

F - Bread

题目大意

本题翻译已经过简化，部分表示与原题不同，仅供参考，请以原题为准。

有一个的整数序列 S S S，初始只有一个元素 L L L，我们可以执行如下操作无限次：

  • 从 S S S中删去任意元素 k k k（ k > 1 k>1 k>1），同时选取整数 x x x（ 1 ≤ x ≤ k ? 1 1\le x\le k-1 1≤x≤k?1），将 x x x和 k ? x k-x k?x放入 S S S。此操作的代价为 k k k。

求最小的代价，使得 A A A在 S S S中，即 A A A中每个元素的出现次数 ? ≤ S ~\le S ?≤S中对应元素的出现次数。

2 ≤ N ≤ 2 × 1 0 5 2\le N\le 2\times 10^5 2≤N≤2×105
1 ≤ N ≤ 1 0 9 1\le N\le 10^9 1≤N≤109
A 1 + A 2 + ? + A N ≤ L ≤ 1 0 15 A_1+A_2+\dots+A_N\le L\le 10^{15} A1?+A2?+?+AN?≤L≤1015

输入格式

N ? L N~L N?L
A 1 ? … ? A N A_1~\dots~A_N A1??…?AN?

输出格式

输出最小的代价。

分析

本题考虑逆向思维，仔细思考后发现题目可以如下转化：

  • 令 S = ( A 1 , … , A N , L ? ∑ A ) S=(A_1,\dots,A_N,L-\sum A) S=(A1?,…,AN?,L?∑A)（ L = ∑ A L=\sum A L=∑A时不千万不要加上最后一个元素）
  • 每次操作将 A A A中任意两个元素合并，它们的和即为合并后新的元素，也是本次操作的代价
  • 最后发现全部合并完后 S S S中正好剩下一个 L L L，此时操作结束，所有代价和即为方案的最终代价。

此时，显然每次合并最小的两个数即为最优方案，因此可以使用优先队列实现，总时间复杂度为 O ( N log ? N ) \mathcal O(N\log N) O(NlogN)。

代码

注意使用long long。

#include <cstdio>
#include <queue>
using namespace std;

using LL = long long;

int main()
{
	int n;
	LL l;
	scanf("%d%lld", &n, &l);
	priority_queue<LL, vector<LL>, greater<LL>> q;
	for(int i=0; i<n; i++)
	{
		int x;
		scanf("%d", &x);
		q.push(x);
		l -= x;
	}
	if(l > 0) q.push(l);
	LL ans = 0LL;
	while(q.size() > 1)
	{
		LL x = q.top(); q.pop();
		x += q.top(); q.pop();
		ans += x;
		q.push(x);
	}
	printf("%lld\n", ans);
	return 0;
}

G - Pre-Order

题目大意

有一颗由 N N N个节点 1 , 2 , … , N 1,2,\dots,N 1,2,…,N组成的树，它的根节点为 1 1 1。
它的先序遍历序列是 ( P 1 , P 2 , … , P N ) (P_1,P_2,\dots,P_N) (P1?,P2?,…,PN?)。
每次搜索时，我们都会优先前往编号小的节点。
有多少种不同的树，使其符合上述条件？对 998244353 998244353 998244353取模。

2 ≤ N ≤ 500 2\le N\le 500 2≤N≤500
1 ≤ P i ≤ N 1\le P_i\le N 1≤Pi?≤N
P 1 = 1 P_1=1 P1?=1
P 1 ≠ P 2 ≠ … ≠ P N P_1\ne P_2\ne\dots\ne P_N P1??=P2??=…?=PN?

输入格式

N N N
P 1 ? … ? P N P_1~\dots~P_N P1??…?PN?

输出格式

输出答案，对 998244353 998244353 998244353取模。

分析

我们先将 P P P变为 0-indexed \text{0-indexed} 0-indexed，即原来的 ( P 1 , P 2 , … , P N ) (P_1,P_2,\dots,P_N) (P1?,P2?,…,PN?)分别对应 ( A 0 , A 1 , … , A N ? 1 ) (A_0,A_1,\dots,A_{N-1}) (A0?,A1?,…,AN?1?)。
此时，不妨考虑区间 dp \text{dp} dp的思想，设 d p ( l , r ) = ? ( \mathrm{dp}(l,r)=~( dp(l,r)=?(一棵树已经去掉根节点的先序遍历为 A l , A l + 1 , … , A r ? 1 A_l,A_{l+1},\dots,A_{r-1} Al?,Al+1?,…,Ar?1?的可能数 ) ) )，则 d p ( 1 , N ) \mathrm{dp}(1,N) dp(1,N)即为所求。

下面考虑 d p ( l , r ) \mathrm{dp}(l,r) dp(l,r)的动态转移方程。

  • 先考虑 A l A_l Al?为 A l + 1 , … , A r ? 1 A_{l+1},\dots,A_{r-1} Al+1?,…,Ar?1?的祖宗的情况，如图：
    情况一示意图
    易得，此时 d p ( l , r ) \mathrm{dp}(l,r) dp(l,r)初始化为 d p ( l + 1 , r ) \mathrm{dp}(l+1,r) dp(l+1,r)。
  • 再考虑区分左右子树，对于每个 k k k（ l < k < r l<k<r l<k<r），将 A l , … , A k ? 1 A_l,\dots,A_{k-1} Al?,…,Ak?1?当作左子树（可能数为 d p ( l + 1 , k ) \mathrm{dp}(l+1,k) dp(l+1,k)），再将 A k , … , A r ? 1 A_k,\dots,A_{r-1} Ak?,…,Ar?1?当作右子树（可能数为 d p ( k , r ) \mathrm{dp}(k,r) dp(k,r)），此时如果 A l < A k A_l<A_k Al?<Ak?则符合题意，将 d p ( l , r ) \mathrm{dp}(l,r) dp(l,r)加上 d p ( l + 1 , k ) × d p ( k , r ) \mathrm{dp}(l+1,k)\times \mathrm{dp}(k,r) dp(l+1,k)×dp(k,r)即可。

至此，本题已结束，时间复杂度为 O ( N 3 ) \mathcal O(N^3) O(N3)。

代码

注意事项：

  1. 乘法操作需要转为long long再取模。
  2. 答案为 d p ( 1 , N ) \mathrm{dp}(1,N) dp(1,N)，不是 d p ( 0 , N ) \mathrm{dp}(0,N) dp(0,N)。
  3. 注意区间 dp \text{dp} dp计算顺序，参考代码提供两种写法（先枚举 l l l和先枚举长度）。
  • 写法一（先枚举 l l l， 59 ms 59\text{ms} 59ms）
    #include <cstdio>
#define MOD 998244353
#define maxn 505
using namespace std;

using LL = long long;
int p[maxn], dp[maxn][maxn];

int main()
{
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
		scanf("%d", p + i);
	for(int l=n; l>0; l--)
	{
		dp[l][l] = 1;
		for(int r=l+1; r<=n; r++)
		{
			dp[l][r] = dp[l + 1][r];
			for(int k=l+1; k<r; k++)
				if(p[l] < p[k] && (dp[l][r] += LL(dp[l + 1][k]) * dp[k][r] % MOD) >= MOD)
					dp[l][r] -= MOD;
		}
	}
	printf("%d\n", dp[1][n]);
	return 0;
}
  • 写法二（先枚举长度， 66 ms 66\text{ms} 66ms）
    #include <cstdio>
#define MOD 998244353
#define maxn 505
using namespace std;

using LL = long long;
int p[maxn], dp[maxn][maxn];

int main()
{
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
		scanf("%d", p + i);
	for(int i=1; i<=n; i++)
		dp[i][i] = 1;
	for(int d=1; d<=n; d++)
		for(int l=1, r=d+1; r<=n; l++, r++)
		{
			dp[l][r] = dp[l + 1][r];
			for(int k=l+1; k<r; k++)
				if(p[l] < p[k] && (dp[l][r] += LL(dp[l + 1][k]) * dp[k][r] % MOD) >= MOD)
					dp[l][r] -= MOD;
		}
	printf("%d\n", dp[1][n]);
	return 0;
}
  C++知识库 最新文章
【C++】友元、嵌套类、异常、RTTI、类型转换
通讯录的思路与实现（C语言)
C++PrimerPlus 第七章 函数-C++的编程模块（
Problem C: 算法9-9~9-12：平衡二叉树的基本
MSVC C++ UTF-8编程
C++进阶 多态原理
简单string类c++实现
我的年度总结
【C语言】以深厚地基筑伟岸高楼-基础篇（六
c语言常见错误合集
上一篇文章      下一篇文章      查看所有文章
加:2022-05-27 17:12:03  更:2022-05-27 17:12:48 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年5日历 -2024/5/13 12:20:17-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码