标签：le string lib int 2021 address CSP block

P7909 分糖果（数学）

题意

给定 \(n,l,r\)，求一个数 \(x\)，当 \(l \le x \le r\) 时，最大的 \(x \bmod n\) 。

数据规模与约定

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

题解

假设 \(l = K_l * n + R_l , r = K_r * n + R_r , x = K_x * n +R_x\)。我们要求 \(R_x\) 尽可能大。

带入到题目给的不等式中，得出 \(K_l * n + R_l \le K_x * n +R_x \le K_r * n + R_r\)。所以 \(x\) 最小值为 \(l = K_l * n + R_l\)。

现在 \(R_x = R_l\)。我们希望 \(R_x\) 尽可能大，而 \(R_x \le n-1\)。所以我们只需要判断 \(l + n - 1 - R_l\) 是否能取到即可。

但有可能 \(r-l\le n - 1 - R_l\)。所以我们要和 \(r\) 取最小值。

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
void Solve(void)
{
	int n, l, r; cin >> n >> l >> r;
	cout << min(l + (n - 1) - (l % n), r) % n << 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;
}

P7910 插入排序（排序，模拟）

题意

给定一个长度为 \(n\) 的数组 \(a\)，数组下标从 \(1\) 开始，并且数组中的所有元素均为非负整数。需要支持在数组 \(a\) 上的 \(Q\) 次操作，操作共两种，参数分别如下：

\(1~x~v\)：这是第一种操作，会将 \(a\) 的第 \(x\) 个元素，也就是 \(a_x\) 的值，修改为 \(v\)。保证 \(1 \le x \le n\)，\(1 \le v \le 10^9\)。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。

\(2~x\)：这是第二种操作，假设对 \(a\) 数组进行排序，需要回答原来 \(a\) 的第 \(x\) 个元素，也就是 \(a_x\)，在排序后的新数组所处的位置。保证 \(1 \le x \le n\)。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。

数据规模与约定

对于 \(100\%\) 的数据，\(1 \le n \le 8000\)，\(1 \le Q \le 2 \times {10}^5\)，\(1 \le x \le n\)，\(1 \le v,a_i \le 10^9\)，保证在所有 \(Q\) 次操作中，至多有 \(5000\) 次操作属于类型一。

题解

这道题的暴力很好想。每次修改操作完后 sort 一遍即可。

考虑优化，我们注意到至多有 \(5000\) 次修改操作。这提示我们修改操作的复杂度可以为 \(O(n)\)。

做法就是题目的名字，插入排序。对于一个已经有序的序列，如果我们修改了其中一项，这一项要么往前调整要么往后调整。而其他元素不需要被调整。所以复杂度为 \(O(n)\)。

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 8e3 + 10;
/*====================*/
int n, q;
int val[N];
int idx[N];
/*====================*/
struct Unit
{
	int x, v;
	Unit(int _x = 0, int _v = 0)
	{
		x = _x, v = _v;
	}
	friend bool operator<(const Unit& a, const Unit& b)
	{
		return a.v != b.v ? a.v < b.v : a.x < b.x;
	}
};
Unit arr[N];
/*====================*/
void GetAns(void)
{
	for (int i = 1; i <= n; ++i)
	{
		idx[arr[i].x] = i;
	}
}
void Change(int x, int v)
{
	for (int i = 1; i <= n; ++i)
	{
		if (arr[i].x == x)
		{
			arr[i].v = v;
			for (int j = i; j - 1 >= 1; --j)
			{
				if (arr[j] < arr[j - 1])
				{
					swap(arr[j], arr[j - 1]);
				}
				else
				{

				}
			}
			break;
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		if (arr[i].x == x)
		{
			arr[i].v = v;
			for (int j = i; j + 1 <= n; ++j)
			{
				if (arr[j] < arr[j + 1])
				{
					
				}
				else
				{
					swap(arr[j], arr[j + 1]);
				}
			}
			break;
		}
	}
	GetAns();
}
/*====================*/
void Solve(void)
{
	cin >> n >> q;
	for (int i = 1; i <= n; ++i)
	{
		cin >> val[i];
	}

	for (int i = 1; i <= n; ++i)
	{
		arr[i] = Unit(i, val[i]);
	}
	sort(arr + 1, arr + 1 + n); GetAns();

	for (int i = 1; i <= q; ++i)
	{
		int op; cin >> op;
		if (op == 1)
		{
			int x, v; cin >> x >> v; Change(x, v);
		}
		if (op == 2)
		{
			int x; cin >> x; cout << idx[x] << 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;
}

P7911 网络连接（模拟）

题意

计算机分为两大类：服务机（Server）和客户机（Client）。服务机负责建立连接，客户机负责加入连接。

需要进行网络连接的计算机共有 \(n\) 台，编号为 \(1 \sim n\)，这些机器将按编号递增的顺序，依次发起一条建立连接或加入连接的操作。

每台机器在尝试建立或加入连接时需要提供一个地址串。服务机提供的地址串表示它尝试建立连接的地址，客户机提供的地址串表示它尝试加入连接的地址。

一个符合规范的地址串应当具有以下特征：

必须形如 a.b.c.d:e 的格式，其中 \(a, b, c, d, e\) 均为非负整数；
\(0 \le a, b, c, d \le 255\)，\(0 \le e \le 65535\)；
\(a, b, c, d, e\) 均不能含有多余的前导 \(0\)。

相应地，不符合规范的地址串可能具有以下特征：

不是形如 a.b.c.d:e 格式的字符串，例如含有多于 \(3\) 个字符 . 或多于 \(1\) 个字符 : 等情况；
整数 \(a, b, c, d, e\) 中某一个或多个超出上述范围；
整数 \(a, b, c, d, e\) 中某一个或多个含有多余的前导 \(0\)。

例如，地址串 192.168.0.255:80 是符合规范的，但 192.168.0.999:80、192.168.00.1:10、192.168.0.1:088、192:168:0:1.233 均是不符合规范的。

如果第 \(i\) 台计算机为服务机，则：

如果其提供符合规范的地址串且成功建立连接，输出字符串 OK。
如果其提供符合规范的地址串，但由于先前有相同地址串的服务机而无法成功建立连接，输出字符串 FAIL。
如果其提供的地址串不是符合规范的地址串，输出字符串 ERR。

如果第 \(i\) 台计算机为客户机，则：

如果其提供符合规范的地址串且成功加入连接，输出一个正整数表示这台客户机连接到的服务机的编号。
如果其提供符合规范的地址串，但无法成功加入连接时，输出字符串 FAIL。
如果其提供的地址串不是符合规范的地址串，输出字符串 ERR。

数据规模与约定

对于 \(100\%\) 的数据， \(1 \le n \le 1000\)。

题解

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
int n;
map<string, int>lib;
/*====================*/
int string_to_int(string str)
{
	int num = 0;
	for (int i = str[0] != '-' ? 0 : 1; i < str.size(); ++i)
	{
		num = num * 10 + str[i] - '0';
	}
	return str[0] != '-' ? num : -num;
}
string int_to_string(int num)
{
	string str;
	bool flag = false;
	if (num < 0)
	{
		num *= -1; flag = true;
	}
	do
	{
		str.push_back(num % 10 + '0'); num /= 10;
	} while (num != 0);
	reverse(str.begin(), str.end());
	if (flag)str = '-' + str;
	return str;
}
/*====================*/
bool Check(string address)
{
	do
	{
		string temp;
		for (auto c : address)
		{
			if (c < '0' || '9' < c)
			{
				temp.push_back(c);
			}
		}
		if (temp != "...:")
		{
			return false;
		}
	} while (false);
	
	vector<string>string_number;
	do
	{
		int last = 0;
		address.push_back('.');
		for (int i = 0; i < address.size(); ++i)
		{
			if (address[i] == ':')
			{
				address[i] = '.';
			}
		}
		for (int i = 0; i < address.size(); ++i)
		{
			if (address[i] == '.' && i > last)
			{
				string_number.push_back(address.substr(last, i - last)); last = i + 1;
			}
		}
	} while (false);

	do
	{
		if (string_number.size() != 5)
		{
			return false;
		}
	} while (false);

	vector<int>int_number;
	do
	{
		for (auto unit : string_number)
		{
			int_number.push_back(string_to_int(unit));
		}
	} while (false);

	do
	{
		for (int i = 0; i < int_number.size(); ++i)
		{
			if (int_to_string(int_number[i]) != string_number[i])
			{
				return false;
			}
		}
	} while (false);

	do
	{
		for (int i = 0; i < int_number.size(); ++i)
		{
			if (i <= 3)
			{
				if (int_number[i] < 0 || int_number[i]>255)
				{
					return false;
				}
			}
			else
			{
				if (int_number[i] < 0 || int_number[i]>65535)
				{
					return false;
				}
			}
		}
	} while (false);

	return true;
}
/*====================*/
void Solve(void)
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		string kind; cin >> kind; 
		string address; cin >> address;
		if (Check(address))
		{
			if (kind == "Server")
			{
				if (lib[address] == 0)
				{
					cout << "OK" << endl;
					lib[address] = i;
				}
				else
				{
					cout << "FAIL" << endl;
				}
			}
			if (kind == "Client")
			{
				if (lib[address] == 0)
				{
					cout << "FAIL" << endl; 
				}
				else
				{
					cout << lib[address] << endl;
				}
			}
		}
		else
		{
			cout << "ERR" << 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;
}

P7912 小熊的果篮（数据结构，STL，模拟，暴力，珂朵莉树，启发式合并，根号均摊，链表，平衡树，线段树，分块）

题意

给定一个长度为 \(n\) 的 \(01\) 串。连续的 \(0\) 或连续的 \(1\) 为一个块。每次输出所有块的第一个元素的下标，然后将其删除。如果一个块内一个元素都没有，则删除块。如果两个相邻块都为 \(0\) 或都为 \(1\) 则合并为一个块。直到所有元素都被删除为止。

数据规模与约定

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

题解

这题怎么实现都可以，有 100 种实现方法。这里我选用 STL 和启发式合并来做。但根据实测，不用启发式合并也能过，并且表现上没有任何差距。

我们用一个 deque 来维护一个块内的下标。用一个 vector 来维护块的下标。

所以输出答案，我们要遍历一遍 vector。并且把每个 deque 的 front 给 pop 掉。

如果把某个 deque 删空了，考虑合并左右。我们每次让 size 小的合并到 size 大的中，进行启发式合并。

分析复杂度，每个元素都会被输出 1 次，每个元素最多合并 log 次，每次输出答案都要遍历一下块的数量，一个块最多被遍历块内元素个数次。\(O(n+nlogn+n)=O(nlogn)\)。实际上远远达不到这个上界，因为一直在删除，很难合并 log 次，更紧的上界我不会证，但反正远小于 \(O(nlogn)\)，我猜测可能接近于 \(O(nloglogn)\)。但即便是 \(O(n \sqrt n )\) 也可以轻松通过此题。

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 2e5 + 10;
/*====================*/
int n;
int arr[N];
/*====================*/
deque<int>lib[N];
vector<int>block;
/*====================*/
void Solve(void)
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
	}

	for (int i = 1; i <= n; ++i)
	{
		if (i == 1 || arr[i] != arr[i - 1])
		{
			block.push_back(block.size());
		}
		lib[block.back()].push_back(i);
	}

	while (!block.empty())
	{
		for (auto idx : block)
		{
			cout << lib[idx].front() << " ";
		}
		cout << endl;
		/*====================*/
		vector<int>_block;
		for (auto idx : block)
		{
			lib[idx].pop_front();
			if (!lib[idx].empty())
			{
				_block.push_back(idx);
			}
		}
		block = _block;
		/*====================*/
		for (int i = 1; i < block.size(); ++i)
		{
			int idx1 = block[i - 1], idx2 = block[i + 0];
			if (arr[lib[idx1].back()] == arr[lib[idx2].front()])
			{
				if (lib[idx1].size() < lib[idx2].size())
				{
					block[i - 1] = block[i + 0] = idx2;
					while (!lib[idx1].empty())
					{
						lib[idx2].push_front(lib[idx1].back());
						lib[idx1].pop_back();
					}
				}
				else
				{
					block[i - 1] = block[i + 0] = idx1;
					while (!lib[idx2].empty())
					{
						lib[idx1].push_back(lib[idx2].front());
						lib[idx2].pop_front();
					}
				}
				block[i - 1] = -1;
			}
		}
		/*====================*/
		_block.clear();
		for (auto idx : block)
		{
			if (idx != -1)
			{
				_block.push_back(idx);
			}
		}
		block = _block;
	}
}
/*====================*/
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;
}

标签：le,string,lib,int,2021,address,CSP,block
From： https://www.cnblogs.com/ProtectEMmm/p/17966568

2021 CSP-J

P7909 分糖果（数学）

题意

题解

P7910 插入排序（排序，模拟）

题意

题解

P7911 网络连接（模拟）

题意

题解

P7912 小熊的果篮（数据结构，STL，模拟，暴力，珂朵莉树，启发式合并，根号均摊，链表，平衡树，线段树，分块）

题意

题解

相关文章

赞助商

阅读排行