AtCoder Beginner Contest 362

🚀欢迎来到本文🚀
🍉个人简介：陈童学哦，彩笔ACMer一枚。
🏀所属专栏：Codeforces
本文用于记录回顾总结本彩笔的解题思路便于加深理解。

A - Buy a Pen

Problem Statement

Takahashi came to a store to buy a pen. Here, a red pen costs $R$ yen, a green pen costs $G$ yen, and a blue pen costs $B$ yen.

Takahashi dislikes the color $C$ . If $C$ is Red, he cannot buy a red pen; if $C$ is Green, he cannot buy a green pen; and if $C$ is Blue, he cannot buy a blue pen.

Determine the minimum amount of money he needs to buy one pen.

在这里插入图片描述

解题思路

模拟即可。输出另外两只笔的最小值即可。

AC代码

#include<bits/stdc++.h>
#define look(x) cout << #x << " ==  " << x << "\n"
using namespace std;
using i64 = long long;
const int N = 2e3 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
void solve(){
	int a,b,c;
	cin >> a >> b >> c;
	string s;
	cin >> s;
	if(s[0] == 'R'){
		cout << min(b,c);
	}else if(s[0] == 'G'){
		cout << min(a,c);
	}else{
		cout << min(a,b);
	}
}

int main(){	

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
//	cin >> t;

	while(t --){
		solve();
	}
	
	return 0;

B - Right Triangle

Problem Statement

In the $x y$ -plane, there are three points $A(x_A, y_A)$ , $B(x_B, y_B)$ , and $C(x_C, y_C)$ that are not collinear. Determine whether the triangle $A BC$ is a right triangle.

在这里插入图片描述

解题思路

判断是否存在任意两边平方和等于第三条边的平方和即可（直角三角形的判定条件）或判断向量叉积。

AC代码

#include<bits/stdc++.h>
#define look(x) cout << #x << " ==  " << x << "\n"
using namespace std;
using i64 = long long;
const int N = 2e3 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
void solve(){
	int a1,b1,a2,b2,a3,b3;
	cin >> a1 >> b1;
	cin >> a2 >> b2;
	cin >> a3 >> b3;
	string ans;
	if(pow(a1 - a2,2) + pow(b1 - b2,2) + pow(a1 - a3,2) + pow(b1 - b3,2) == pow(a2 - a3,2) + pow(b2 - b3,2)){
		ans = "Yes";
	}else if(pow(a3 - a2,2) + pow(b3 - b2,2) + pow(a1 - a3,2) + pow(b1 - b3,2) == pow(a2 - a1,2) + pow(b2 - b1,2)){
		ans = "Yes"; 
	}else if(pow(a1 - a2,2) + pow(b1 - b2,2) + pow(a2 - a3,2) + pow(b2 - b3,2) == pow(a1 - a3,2) + pow(b1 - b3,2)){
		ans = "Yes";
	}else{
		ans = "No";
	}
	cout << ans << "\n";
}

int main(){	

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
//	cin >> t;

	while(t --){
		solve();
	}
	
	return 0;
}

C - Sum = 0

Problem Statement

You are given $N$ pairs of integers $(L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N)$ .

Determine whether there exists a sequence of $N$ integers $(X_1, X_2, \ldots, X_N)$ that satisfies the following conditions, and print one such sequence if it exists.

$L_i \leq X_i \leq R_i$ for each $\ldots, N$ .
$\displaystyle \sum_{i=1}^N X_i = 0$ .

在这里插入图片描述

解题思路

首先我们先考虑什么情况下不存在这样的一个序列呢？
求所有区间的左边界值的总和 $s u m 1$ ，如果 $s u m 1 > 0$ 的话必然不存在这样的一个序列。
因为在每个区间都取最小值的情况下都只大于0的情况下无论怎么样取每个区间的值都只会大于等于 $s u m 1$ 。
否则 $s u m 1 <= 0$ 的情况下肯定存在一个序列的总和为0。
然后我们就可以依次遍历每个区间让在这个区间的所取得那个数去动态变化保证总和为0。
我们开始可以设置一个 $an s$ 数组依次取值区间得左边界 $l [i]$ ，然后每次加 $an s [i]$ 加上一个 $min (- s u m 1, r [i] - l [i])$ 即可。

AC代码

#include<bits/stdc++.h>
#define look(x) cout << #x << " ==  " << x << "\n"
using namespace std;
using i64 = long long;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
i64 l[N],r[N];
i64 ans[N];
i64 sum1 = 0,sum2 = 0;
void solve(){
	int n;
	cin >> n;
	for(int i = 1;i <= n;i ++){
		cin >> l[i] >> r[i];
		sum1 += l[i];
		sum2 += r[i];
		ans[i] = l[i];  //ans数组记录每个区间所取得数值
	}
	if(sum1 > 0 || sum2 < 0){
		cout << "No\n";
		return;
	}else{
		cout << "Yes\n";
		for(int i = 1;i <= n;i ++){
			//加上使得sum1靠近0得值(不能大于区间的差值也不需要大于sum1的绝对值)
			int t = min(-sum1,r[i] - l[i]);
			sum1 += t;
			ans[i] += t;
			if(sum1 == 0){
				break;
			}
		}
	}
	for(int i = 1;i <= n;i ++){
		cout << ans[i] << " ";
	}
}

int main(){	

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
//	cin >> t;

	while(t --){
		solve();
	}
	
	return 0;
}

D - Shortest Path 3

Problem Statement

You are given a simple connected undirected graph with $N$ vertices and $M$ edges. Each vertex $i\,(1\leq i \leq N)$ has a weight $A_i$ . Each edge $j\,(1\leq j \leq M)$ connects vertices $U_j$ and $V_j$ bidirectionally and has a weight $B_j$ .

The weight of a path in this graph is defined as the sum of the weights of the vertices and edges that appear on the path.

For each $i=2,3,\dots,N$ , solve the following problem:

Find the minimum weight of a path from vertex $1$ to vertex $i$ .

在这里插入图片描述

解题思路

跑个 $D ijk s t r a$ 的堆优化即可，复杂度为 $O (n l o g n)$ 。

AC代码

#include<bits/stdc++.h>
#define look(x) cout << #x << " ==  " << x << "\n"
using namespace std;
using i64 = long long;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
//存图，pair存与之相连的点和两点之间边的权值
vector<pair<int,int>> g[N];
//每个点的权值
int a[N];
//起点1到其他点的最小权值
i64 dis[N];
//判断该点是否跑过
bool st[N];
void solve(){
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
	}
	for(int i = 1;i <= m;i ++){
		int u,v,w;
		cin >> u >> v >> w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	dis[1] = a[1];
	//优先队列，按权值小的优先来排序
	priority_queue<pair<i64,i64>,vector<pair<i64,i64>>,greater<pair<i64,i64>>> q;
	q.push({a[1],1});
	for(int i = 2;i <= n;i ++){
		dis[i] = 1e18;
	}
	//跑Dijkstra
	while(!q.empty()){
		auto [x,y] = q.top();
		q.pop();
		if(st[y]){
			continue;
		}
		st[y] = true;
		for(auto [k1,k2] : g[y]){
			//如果权值更小就更新
			if(dis[k1] > x + k2 + a[k1]){
				dis[k1] = x + k2 + a[k1];
				q.push({dis[k1],k1});
			}
		}
	}
	//输出每个点距离起点的最小权值
	for(int i = 2;i <= n;i ++){
		cout << dis[i] << " ";
	}		
}

int main(){	

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
//	cin >> t;

	while(t --){
		solve();
	}
	
	return 0;
}

E - Count Arithmetic Subsequences

Problem Statement

You are given a sequence $(A_1, A_2, \dots, A_N)$ of length $N$ . For each $\dots, N$ , find the number, modulo $998244353$ , of (not necessarily contiguous) subsequences of $A$ of length $k$ that are arithmetic sequences. Two subsequences are distinguished if they are taken from different positions, even if they are equal as sequences.

What is a subsequence? A subsequence of a sequence $A$ is a sequence obtained by deleting zero or more elements from $A$ and arranging the remaining elements without changing the order.

在这里插入图片描述

解题思路

要求所有长度为 $1 到 N$ 的等差数列各有多少个。
首先我们可以发现N很小，所以其实我们考虑枚举所有的公差，然后考虑dp推出状态转移方程。
首先考虑第一个维度为 $i$ 代表第i个数，第二个维度 $j$ 代表第j个数，但是由于直接枚举出来的公差可能会重复且数值很大，所以我们需要排序去重然后二分求出公差的位置 $x$ 代表这个公差。
所以第二个维度应该为 $x$ ，最后还需要一个维度 $k$ 来表示这个序列的长度。
最后的dp数组就可表示为这样 $d p [i] [k] [x]$ 。

AC代码

#include<bits/stdc++.h>
#define look(x) cout << #x << " ==  " << x << "\n"
using namespace std;
using i64 = long long;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
int a[100];
//dp数组
i64 dp[81][81][81 * 81];
i64 ans[100];
void solve(){
	int n;
	cin >> n;
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
	}
	vector<int> f;
	//枚举所有的公差
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j < i;j ++){
			f.push_back(a[i] - a[j]);
		}
	}
	//排序去重
	sort(f.begin(),f.end());
	f.erase(unique(f.begin(),f.end()),f.end());
	//i代表第i个数现在进行到
	for(int i = 1;i <= n;i ++){
		//j代表在i个数的情况下往前枚举公差
		for(int j = 1;j < i;j ++){
			//k代表序列长度
			for(int k = 1;k <= j;k ++){
				//二分在f中找出a[i]-a[j]公差的位置
				int x = lower_bound(f.begin(),f.end(),a[i] - a[j]) - f.begin() + 1;
				//长度为1就直接加1
				if(k + 1 == 2){
					dp[i][k + 1][x] ++;
				}else{
				//否则就加上没算第i个数是的dp,公差都是x,只不过没算第i个数时长度就是
				//算了第i个数时的k+1减去1也就是k了。
					dp[i][k + 1][x] += dp[j][k][x];
				}
				dp[i][k + 1][x] %= MOD2;
			}
		}
	}
	//将所有公差下长度为k的序列答案累加。
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= f.size();j ++){
			for(int k = 1;k <= n;k ++){
				ans[k] += dp[i][k][j];
				ans[k] %= MOD2;
			}
		}
	}
	//长度为1的序列就是所有完整序列的大小
	cout << n << " ";
	for(int i = 2;i <= n;i ++){
		cout << ans[i] << " ";
	}
	
}
int main(){	

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
//	cin >> t;

	while(t --){
		solve();
	}
	
	return 0;
}

F - Perfect Matching on a Tree

Problem Statement

You are given a tree $T$ with $N$ vertices. The vertices are numbered $1$ to $N$ , and the $i$ -th edge $\leq i \leq N-1)$ connects vertices $u_i$ and $v_i$ bidirectionally.

Using $T$ , define a complete graph $G$ with $N$ vertices as follows:

The weight $w (x, y)$ of the edge between vertices $x$ and $y$ in $G$ is the shortest distance between vertices $x$ and $y$ in $T$ .

Find one maximum weight maximum matching in $G$ . That is, find a set of $\lfloor N/2 \rfloor$ pairs of vertices $M=\{(x_1,y_1),(x_2,y_2),\dots,(x_{\lfloor N/2 \rfloor},y_{\lfloor N/2 \rfloor})\}$ such that each vertex $1,2,\dots, N$ appears in $M$ at most once, and $\displaystyle \sum_{i=1}^{\lfloor N/2 \rfloor} w(x_i,y_i)$ is maximized.

解题思路

$待补$

AC代码

G - Count Substring Query

Problem Statement

You are given a string $S$ consisting of lowercase English letters.

You are also given $Q$ queries to process sequentially. The $i$ -th query is described as follows:

A string $T_i$ consisting of lowercase English letters is given. Print the number of substrings of $S$ that equal $T_i$ . Two substrings are distinguished if they are taken from different positions, even if they are equal as strings.

在这里插入图片描述

解题思路

要找每个子串出现的次数，AC自动机。

AC代码

#include<bits/stdc++.h>
#define look(x) cout << #x << " ==  " << x << "\n"
using namespace std;
using i64 = long long;
const int N = 1e6 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
int tire[N][26],cnt[N],idx;
int ne[N],q[N],f[N],id[N];
string s;
void insert1(string s){
	int p = 0;
	for(int i = 0;s[i];i ++){
		int u = s[i] - 'a';
		if(!tire[p][u]){
			tire[p][u] = ++ idx;
		}
		p = tire[p][u];
		f[p] ++;
	}
}
void insert2(int x){
	int p = 0;
	for(int i = 0;s[i];i ++){
		int u = s[i] - 'a';
		if(!tire[p][u]){
			tire[p][u] = ++ idx;
		}
		p = tire[p][u];
	}
	id[x] = p;
}
void build(){
	int hh = 0,tt = -1;
	for(int i = 0;i < 26;i ++){
		if(tire[0][i]){
			q[++ tt] = tire[0][i];
		}
	}
	while(hh <= tt){
		int k = q[hh ++];
		for(int i = 0;i < 26;i ++){
			int p = tire[k][i];
			if(!p){
				tire[k][i] = tire[ne[k]][i];
			}else{
				ne[p] = tire[ne[k]][i];
				q[++ tt] = p;
			}
		}
	}
}
void solve(){
	cin >> s;
	insert1(s);
	int n;
	cin >> n;
	for(int i = 1;i <= n;i ++){
		cin >> s;
		insert2(i);
	}
	build();
	for(int i = idx - 1;i >=0;i --){
		f[ne[q[i]]] += f[q[i]];
	}
	for(int i = 1;i <= n;i ++){
		cout << f[id[i]] << "\n";
	}
}


int main(){	

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
//	cin >> t;

	while(t --){
		solve();
	}
	
	return 0;
}