2022 CSP-J

P8813 乘方（数学，模拟）

题意

给定两个数 \(a,b\)，如果 \(a^b \le 10^9\)，输出 \(a^b\) 的值。否则输出 \(-1\)。

数据规模与约定

对于 \(100\%\) 的数据，\(1 \le a,b \le 10^9\)。

题解

记得开 long long。

如果 \(a=1\)，那么无论 \(b\) 是多少结果都是 \(1\)。

如果 \(a \ne 1\)，那么 \(a\) 至少为 \(2\)。\(2^{30} > 10^9\)。所以最多乘 \(30\) 次。模拟即可。

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
void Solve(void)
{
	int a, b; cin >> a >> b;
	if (a == 1)
	{
		cout << 1 << endl;
	}
	else
	{
		lnt res = 1;
		for (int i = 1; i <= b; ++i)
		{
			res = res * a;
			if (res > 1e9)
			{
				cout << -1 << endl; return;
			}
		}
		cout << res << endl;
	}
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
	freopen("IN.txt", "r+", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int T = 1; //cin >> T;
	while (T--)Solve();
	return 0;
}

P8814 解密（数学，构造，韦达定理，二分）

题意

给定一个正整数 \(k\)，有 \(k\) 次询问，每次给定三个正整数 \(n_i, e_i, d_i\)，求两个正整数 \(p_i, q_i\)，使 \(n_i = p_i \times q_i\)、\(e_i \times d_i = (p_i - 1)(q_i - 1) + 1\)。

以下记 \(m = n - e \times d + 2\)。

数据规模与约定

对于 \(100\%\) 的数据，\(1 \leq k \leq {10}^5\)，对于任意的 \(1 \leq i \leq k\)，\(1 \leq n_i \leq {10}^{18}\)，\(1 \leq e_i \times d_i \leq {10}^{18}\)，\(1 \leq m \leq {10}^9\)。

题解

这题有二分做法，极其天才的构造。可以看洛谷题解的最后一篇。

数学方法也有很多，这里我使用解二次方程的做法。

先把 \(e*d\) 给展开，得 \(e*d=p*q-(p+q)+2\)。

将 \(n=p*q\) 代入，得 \(e*d=n-(p+q)+2\)。

移项得 \(p+q=n-e*d+2\) 即 \(p+q=m\)。

现有 \(\begin{cases}p+q=m \\ p*q=n\end{cases}\)，根据韦达定理，\(x_1 + x_2 = - \frac{b}{a},x_1 * x_2 = \frac{c}{a}\)。

令 \(a=1\)，可以构造出一元二次方程 \(x^2 - m*x+n=0\)。

这个方程的解要先算 \(\Delta = b^2 - 4*a*c\)。随后求根公式求根即可。

最后判断 \(p,q\) 能否验算回 \(n,m\)。

无论是不是完全平方数，都可以用 sqrt。虽然这是一个 double 类型，但精度上在 long long 范围内都能保证。不存在 \(sqrt(4)=2.0001\) 或 \(sqrt(4)=1.99999\)。所以不用担心精度问题（PS：eps的写法早该淘汰了，现在 double 对于精度控制得很好，eps 只是为了更加保险或者避免计算几何中大量的精度误差积累造成蝴蝶效应，且受早年编程界影响导致的）。

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
void Solve(void)
{
	lnt n, e, d; 
	cin >> n >> e >> d;
	lnt m = n - e * d + 2ll;
	lnt delta = m * m - 4ll * n;
	if (delta >= 0)
	{
		lnt squareroot = sqrt(delta);
		lnt p = (m - squareroot) / 2ll;
		lnt q = (m + squareroot) / 2ll;
		if (p + q == m && p * q == n)
		{
			cout << p << " " << q << endl; return;
		}
	}
	cout << "NO" << endl;
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
	freopen("IN.txt", "r+", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int T = 1; cin >> T;
	while (T--)Solve();
	return 0;
}

P8815 逻辑表达式（栈，模拟，表达式求值，中缀表达式，中缀转后缀，表达式树）

题意

给定一个长度为 \(|S|\) 包含 \(\& |\) 与或运算的表达式，求最后的值，并且计算与运算和或运算分别短路了多少次。

数据规模与约定

对于 \(100\%\) 的数据，\(1 \le |S| \le 10^6\)。

题解

先把中缀表达式转换成后缀表达式，方便我们对表达式进行处理。

对后缀表达式建立表达式树。

然后对表达式树进行中序遍历，并且计算短路的次数。

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 1e6 + 10;
/*====================*/
int GetFirst(char c)
{
	if (c == '&')
	{
		return 0;
	}
	else
	{
		if (c == '|')
		{
			return -1;
		}
		else
		{
			return -2;
		}
	}
}
string Change(string str)
{
	string temp;
	stack<char>stk; 
	for (auto c : str)
	{
		if (c == '0' || c == '1')
		{
			temp.push_back(c);
		}
		if (c == '(' || c == ')')
		{
			if (c == '(')
			{
				stk.push('(');
			}
			if (c == ')')
			{
				while (!stk.empty() && stk.top() != '(')
				{
					temp.push_back(stk.top()); stk.pop();
				}
				stk.pop();
			}
		}
		if (c == '&' || c == '|')
		{
			while (!stk.empty() && GetFirst(stk.top()) >= GetFirst(c))
			{
				temp.push_back(stk.top()); stk.pop();
			}
			stk.push(c);
		}
	}
	while (!stk.empty())
	{
		temp.push_back(stk.top());
		stk.pop();
	}
	return temp;
}
/*====================*/
struct Node
{
	int val;
	char tag;
	Node* lch, * rch;
	Node(int _val = 0, char _tag = ' ', Node* _lch = NULL, Node* _rch = NULL)
	{
		val = _val, tag = _tag;
		lch = _lch, rch = _rch;
	}
};
Node* Build(string str)
{
	stack<Node*>stk;
	for (auto c : str)
	{
		if (c == '0' || c == '1')
		{
			stk.push(new Node(c - '0', ' ', NULL, NULL));
		}
		else
		{
			Node* rch = stk.top(); stk.pop();
			Node* lch = stk.top(); stk.pop();
			stk.push(new Node(((c == '&') ? (lch->val & rch->val) : (lch->val | rch->val)), c, lch, rch));
		}
	}
	return stk.top();
}
/*====================*/
int cnt1, cnt2;
void DFS(Node* cur)
{
	if (cur->lch != NULL && cur->rch != NULL)
	{
		DFS(cur->lch);
		if (cur->tag == '&')
		{
			if (cur->lch->val == 0)
			{
				cnt1++;
			}
			else
			{
				DFS(cur->rch);
			}
		}
		if (cur->tag == '|')
		{
			if (cur->lch->val == 1)
			{
				cnt2++;
			}
			else
			{
				DFS(cur->rch);
			}
		}
	}
}
/*====================*/
void Solve(void)
{
	string str; cin >> str;

	Node* root = Build(Change(str));

	DFS(root); cout << root->val << endl << cnt1 << " " << cnt2 << endl;
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
	freopen("IN.txt", "r+", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int T = 1; //cin >> T;
	while (T--)Solve();
	return 0;
}

P8816 上升点列（dp）

题意

在一个二维平面内，给定 \(n\) 个整数点 \((x_i, y_i)\)，此外你还可以自由添加 \(k\) 个整数点。

你在自由添加 \(k\) 个点后，还需要从 \(n + k\) 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 \(1\) 而且横坐标、纵坐标值均单调不减，即 \(x_{i+1} - x_i = 1, y_{i+1} = y_i\) 或 \(y_{i+1} - y_i = 1, x_{i+1} = x_i\)。请给出满足条件的序列的最大长度。

数据规模与约定

对于 \(100\%\) 的数据，\(1 \leq n \leq 500\)，\(0 \leq k \leq 100\)。对于所有给定的整点，其横纵坐标 \(1 \leq x_i, y_i \leq {10}^9\)，且保证所有给定的点互不重合。对于自由添加的整点，其横纵坐标不受限制。

题解

因为题目要求了序列中任意相邻两点间的欧几里得距离恰好为 \(1\) 而且横坐标、纵坐标值均单调不减。所以我们发现，一个点只能向上走或者向右走。

有点类似于过河卒和最长上升子序列，也有点类似于背包。

我们定义状态 \(dp_{i,k}\) 以第 \(i\) 个点为末尾端点，使用了 \(k\) 个自由点的最长序列长度。

那么我们计算一下两个点之间需要多少个自由点，其实是曼哈顿距离减 \(1\)。我们定义两点之间的曼哈顿距离为 \(dis_{i,j}\)。

那么转移方程也就很显然了，\(dp_{i,k}=\max \begin{cases}dp_{j,k-dis_{i,j}}+dis_{i,j}&\forall j,j\ne i，x_j\le x_i,y_j \le y_i,dis_{i,j}\le k \\k+1\end{cases}\)。

但是有一个问题，那就是，\(n\) 个点之间按照上面这个式子，会互相转移。

所以我们再加上一维状态，强行给他加入一个阶段， \(dp_{i,k,s}\)，在前 \(s\) 个点中，以第 \(i\) 个点为末尾端点，使用了 \(k\) 个自由点的最长序列长度。

然后我们发现，\(s\) 所处的阶段维，只和 \(s,s-1\) 有关。所以我们可以滚动掉。

但是，这样太麻烦了。我们使用一个奇技淫巧。将所有点按照 \(x\) 为第一关键字，\(y\) 为第二关键字升序排序。

这样我们就能保证，所有可以使用的 \(j\) 都小于 \(i\)，这样就不存在互相转移的情况了，我们通过这种方式强行给点加入了偏序关系。

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 5e2 + 10;
const int K = 1e2 + 10;
/*====================*/
int n, k;
/*====================*/
struct Point
{
	int x, y;
	Point(int _x = 0, int _y = 0)
	{
		x = _x, y = _y;
	}
	friend bool operator<(const Point& a, const Point& b)
	{
		return a.x != b.x ? a.x < b.x : a.y < b.y;
	}
};
Point point[N];
/*====================*/
int dp[N][K];
/*====================*/
void Solve(void)
{
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
	{
		int x, y; cin >> x >> y;
		point[i] = Point(x, y);
	}
	int ans = 0;
	sort(point + 1, point + 1 + n);
	for (int cur = 1; cur <= n; ++cur)
	{
		for (int use = 0; use <= k; ++use)
		{
			dp[cur][use] = use + 1;
			for (int pre = 1; pre < cur; ++pre)
			{
				if (point[pre].x <= point[cur].x && point[pre].y <= point[cur].y)
				{
					int dis = point[cur].x - point[pre].x + point[cur].y - point[pre].y;
					if (use - (dis - 1) >= 0)
					{
						dp[cur][use] = max(dp[cur][use], dp[pre][use - (dis - 1)] + dis);
					}
				}
			}
			ans = max(ans, dp[cur][use]);
		}
	}
	cout << ans << endl;
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
	freopen("IN.txt", "r+", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int T = 1; //cin >> T;
	while (T--)Solve();
	return 0;
}