标签：10 le val int stk tag 2020 CSP

2020 CSP-J

P7071 优秀的拆分（语法）

题意

给定一个正整数，输出二进制拆分。如果这个数是奇数输出 -1。

数据规模与约定

对于 \(100\%\) 的数据，\(1 \le n \le 10^7\)。

题解

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
void Solve(void)
{
	int n; cin >> n;
	if (n & 1)
	{
		cout << "-1" << endl;
	}
	else
	{
		for (int i = 30; i >= 0; --i)
		{
			if (n & (1 << i))
			{
				n -= (1 << i);
				cout << (1 << i) << " ";
			}
		}
	}
}
/*====================*/
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;
}

P7072 直播获奖（模拟，桶排）

题意

给定一个长度为 \(n\) 的序列 \(a_i\)，给定一个百分比 \(w\%\)。对于序列的每一个前缀 \(a_1 ... a_i\)，求出第 \(\max(1, \lfloor i \times w \%\rfloor)\) 大的数是多少。

数据规模与约定

对于 \(100\%\) 的数据，\(1 \le n \le 10^5,0 \le a_i \le 6 * 10^2,1 \le w \le 99\)。

题解

动态求动态第 \(k\) 大，因为 \(k\) 不固定，所以不能使用对顶堆。每一次都 sort 一次会超时。考虑使用数据结构，权值线段树或平衡树之类的。考虑到题目给的范围 \(1 \le a_i \le 600\)，我们可以每次进行桶排。复杂度为 \(O(600* n)\)。

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 1e5 + 10;
const int A = 6e2 + 10;
/*====================*/
int n, w;
int arr[N];
int cnt[A];
/*====================*/
void Solve(void)
{
	cin >> n >> w;
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
	}

	for (int i = 1; i <= n; ++i)
	{
		cnt[arr[i]]++;
		int person= max(1, i * w / 100);
		for (int j = 600; j >= 0; --j)
		{
			person -= cnt[j];
			if (person <= 0)
			{
				cout << j << " "; break;
			}
		}
	}
}
/*====================*/
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;
}

P7073 表达式（模拟，栈，树上前缀和，贪心，表达式求值，后缀表达式）

题意

给定一个逻辑表达式的后缀表达形式和其中每一个变量的初值。

\(q\) 次独立询问，每次询问取反某一个变量的值时，原表达式的值为多少。

数据规模与约定

对于 \(100\%\) 的数据，\(1 \le |s| \le 1 \times 10^6\)，\(1 \le q \le 1 \times 10^5\)，\(2 \le n \le 1 \times 10^5\)。

题解

首先对字符串进行处理。这里写一个 string 转 int 即可。

将后缀表达式转化成树的形态，建树。

我们发现：

当运算为 & 时，如果其中一边为 \(0\)，另一边无论取何值都不会对结果产生影响。
当运算为 | 时，如果其中一边为 \(1\)，另一边无论取何值都不会对结果产生影响。
反之，取反操作一定会对结果产生影响。

将无论如何修改都不产生影响的子树标记一下，因为每次询问独立，所以只需要查询该变量叶子节点到根节点的路径上是否是有被标记的节点即可。这里使用树上前缀和加速，每次可以 \(O(1)\) 查询。

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 1e5 + 10;
/*====================*/
int n; string expression;
/*====================*/
struct Node
{
	int val = 0;
	char tag = ' ';
	bool useless = false;
	Node * lch = NULL, * rch = NULL;
};
Node* leaf[N];
/*====================*/
stack<Node*>stk;
/*====================*/
int string_to_int(string str)
{
	int res = 0;
	for (auto c : str)
	{
		res = res * 10 + c - '0';
	}
	return res;
}
/*====================*/
void DFS(Node* pre, Node* cur)
{
	if (cur != NULL)
	{
		if (pre != NULL)
		{
			cur->useless |= pre->useless;
		}
		DFS(cur, cur->lch);
		DFS(cur, cur->rch);
	}
}
/*====================*/
void Solve(void)
{
	do
	{
		getline(cin, expression); cin >> n;
		for (int i = 1; i <= n; ++i)
		{
			leaf[i] = new Node;
			cin >> leaf[i]->val;
		}
	} while (false);

	do
	{
		int last = -1; expression.push_back(' ');
		for (int i = 0; i < expression.size(); ++i)
		{
			if (expression[i] == ' ')
			{
				int l = last + 1, r = i - 1; last = i;
				string str = expression.substr(l, r - l + 1);
				if (str[0] == 'x')
				{
					stk.push(leaf[string_to_int(str.substr(1, str.size() - 1))]);
				}
				else
				{
					Node* root = new Node;
					root->tag = str[0];
					if (str == "!")
					{
						Node* cur = stk.top(); stk.pop();
						root->lch = cur;
						root->val = cur->val ^ 1;
					}
					if (str == "&")
					{
						Node* cur1 = stk.top(); stk.pop();
						Node* cur2 = stk.top(); stk.pop();
						root->lch = cur1; root->rch = cur2;
						root->val = cur1->val & cur2->val;
						if (cur1->val == 0)cur2->useless = true;
						if (cur2->val == 0)cur1->useless = true;
					}
					if (str == "|")
					{
						Node* cur1 = stk.top(); stk.pop();
						Node* cur2 = stk.top(); stk.pop();
						root->lch = cur1; root->rch = cur2;
						root->val = cur1->val | cur2->val;
						if (cur1->val == 1)cur2->useless = true;
						if (cur2->val == 1)cur1->useless = true;
					}
					stk.push(root);
				}
			}
		}
		DFS(NULL, stk.top());
	} while (false);
	
	do
	{
		int q; cin >> q;
		while (q--)
		{
			int x; cin >> x;
			if (leaf[x]->useless)
			{
				cout << (stk.top()->val) << endl;
			}
			else
			{
				cout << (stk.top()->val ^ 1) << endl;
			}
		}
	} while (false);
}
/*====================*/
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;
}

P7074 方格取数（dp）

题意

设有 \(n \times m\) 的方格图，每个方格中都有一个整数（有正有负）。从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。求取到的整数之和的最大值。

数据规模与约定

对于 \(100\%\) 的数据，\(1 \le n,m \le 10^3\)。方格中整数的绝对值不超过 \(10^4\)。

题解

如果只能向上或者只能向下，这题就是过河卒了。但是现在既能向上也能向下，思考一下怎么处理。

我们发现不能重复经过已经走过的方格，且只能向右走。所以当我们来到 \((i,j)\) 时，只能从左边，或者上面或者下面来到当前点。不存在一上一下的情况，因为不能重复经过已经走过的方格。所以我们将 dp 状态加上一维从上面来还是从下面来。明确状态意义后，转移方程很好想。因为边界处理比较麻烦，这里我使用了记忆化搜索的方式实现 dp。

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 1e3 + 10;
const int M = 1e3 + 10;
/*====================*/
const lnt INF = 0X7F7F7F7F;
/*====================*/
int n, m;
lnt val[N][M];
/*====================*/
lnt dp[N][M][2];
bool vis[N][M][2];
lnt DP(int i, int j, int tag)
{
	if (i == 1 && j == 1)return val[i][j];
	if (i<1 || i>n || j<1 || j>m)return -INF;
	if (!vis[i][j][tag])
	{
		vis[i][j][tag] = true;
		dp[i][j][tag] = max(DP(i, j - 1, 0), DP(i, j - 1, 1));
		if (tag == 0)
		{
			dp[i][j][tag] = max(dp[i][j][tag], DP(i - 1, j, tag)) + val[i][j];
		}
		if (tag == 1)
		{
			dp[i][j][tag] = max(dp[i][j][tag], DP(i + 1, j, tag)) + val[i][j];
		}
	}
	return dp[i][j][tag];
}
/*====================*/
void Solve(void)
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			cin >> val[i][j];
		}
	}
	cout << max(DP(n, m, 0), DP(n, m, 1)) << 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;
}

标签：10,le,val,int,stk,tag,2020,CSP
From： https://www.cnblogs.com/ProtectEMmm/p/17966605

2020 CSP-J

2020 CSP-J

P7071 优秀的拆分（语法）

题意

题解

P7072 直播获奖（模拟，桶排）

题意

题解

P7073 表达式（模拟，栈，树上前缀和，贪心，表达式求值，后缀表达式）

题意

题解

P7074 方格取数（dp）

题意

题解

相关文章

赞助商

阅读排行