首页 > 其他分享 >2024CCPC郑州邀请赛

2024CCPC郑州邀请赛

时间：2024-05-15 22:41:17浏览次数：23  
标签：int ll long 郑州 2024CCPC ans using 邀请赛 se

2024CCPC郑州邀请赛题解

[比赛地址](2024 National Invitational of CCPC (Zhengzhou), 2024 CCPC Henan Provincial Collegiate Programming Contest)

A:

解题思路:

设\(n = 12153, m = 5\),其中\(m\)是\(n\)十进制数位个数。

我们构造一个数\(N = 123456789d \times 10^k\)为答案，从高到低前十位满足要求，最后留\(m\)个零放低位。

\(k = \lceil \frac{N}{n}\rceil\)。

如果\(N \% n =0\),那不用解释。

如果\(N \% n != 0\)，我们上取整得到\(k\),那么\(k \times n = N + n\),前面最后留\(m\)个低位零就是为了这里，\(N\)加上\(n\)后不会影响前十位，所以可行。

新小技巧，快速求整型数据十进制数位:

int len = to_string(n).size();

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1ll << 60;
void solve()
{
	ll n, d;
	scanf("%lld %lld", &n, &d);
	int len = to_string(n).size();
	ll N = 1ll * 123456789 * 10 + d;
	for (int i = 1; i <= len; i++)
	{
		N *= 10;
	}
	ll ans = (N + n - 1) / n;
	printf("%lld\n", ans);
}

int main()
{
	int t = 1;
	scanf("%d", &t);
	while (t--)
	{
		solve();
	}
	return 0;
}

B:

解题思路：

考虑对于当前位置\(i\)，会留下多少钱。

如果前面位置能够花费比\(c_i\)更少的钱买探测器，一定比全部存到第\(i\)个点更优。

所以，单调栈优化\(dp\)，每次从前面距离当前位置\(i\)最近的且花费小于\(c_i\)的位置转移到\(i\)。

如果前面没有这种位置，说明存钱到位置\(i\)花费最优。

全过程取最大值。

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
	int n;
	cin >> n;
	vector<ll> a(n + 1);
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	vector<ll> f(n + 1), b(n + 1);
	ll ans = 0;
	stack<int> stk;
	for (int i = 1; i <= n; i++)
	{
		while (stk.size() && a[stk.top()] > a[i])
		{
			stk.pop();
		}
		if (stk.empty())
		{
			f[i] = i / a[i];
			b[i] = i % a[i];
		}
		else
		{
			int idx = stk.top();
			f[i] = f[idx] + (i - idx + b[idx]) / a[i];
			b[i]  = (i - idx + b[idx]) % a[i];
		}
		stk.push(i);
		ans = max(ans, f[i]);
//		cout << i << ' ' << b[i] << ' ' << f[i] << endl;
	}
	printf("%lld\n", ans);
}

int main()
{
	int t = 1;
//	scanf("%d", &t);
	while (t--)
	{
		solve();
	}
	return 0;
}

C:

解题思路:

观察发现，根据题目要求，对于一个数字最开始出现位置到最后出现位置之间的所有数字，变换后都应当相等。否则不可能非递减。

题目案例：

10
1 10 2 6 10 8 9 4 4 5

我们按照上述说法举例分段：

[1], [10, 2, 6, 10], [8], [9], [4, 4], [5]

题目案例变换后:

[1], [2, 2, 2, 2], [2], [2], [4, 4], [5]

通过逻辑发现，如果出现相交，那么直接扩大：

10
1, 10, 9, 8, 6, 10, 7, 6, 4, 5

分段：

[1], [10, 9, 8, 6, 10, 7, 6], [4], [5]

映射函数\(f\):\([1, 2, 3, 4,..., n]\)

题目要求修改最少得映射函数的值，使得原序列映射后非递减。

即，找到原序列中最长上升子序列（\(LIS\))，其余的全部都修改。

我们发现，对于一个元素段，我们最多可以保留一个元素不变，即所有元素都变成那个保留的元素。

所以，我们对每个元素段进行内部降序排序，使得\(LIS\)中的不会有两个元素来自同一个元素段。

如何快速处理出元素段区间？

使用差分，每个元素可看作是一个区间\((l, r)\)，进入就加，出去就减。差分求和后，等于\(0\)的位置就是一个元素段的末尾。

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second

void solve()
{
	int n;
	scanf("%d", &n);
	vector<int> a(n + 1);
	vector<int> l(n + 1, n + 1), r(n + 1, -1);
	vector<bool> vis(n + 1);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		l[a[i]] = min(l[a[i]], i);
		r[a[i]] = i;
		vis[a[i]] = true;
	}
	vector<int> d(n + 1);
	for (int i = 1; i <= n; i++)
	{
		if (l[i] <= r[i])
		{
			d[l[i]]++;
			d[r[i]]--;
		}
	}
	// d[i] = 0µÄλÖ㬾ÍÊÇÒ»¸ö¶ÎµÄĩβ 
	for (int i = 1; i <= n; i++)
	{
		d[i] += d[i - 1];
//		cout << d[i] << " \n"[i == n];
	}
	int lst = 1;
	for (int i = 1; i <= n; i++)
	{
		if (d[i] == 0)
		{
//			cout << lst << ' ' << i << endl;
			sort(a.begin() + lst, a.begin() + i + 1, greater<int>());
			lst = i + 1;
		}
//		cout << i << " " << lst << endl;
	}
//	for (int i = 1; i <= n; i++)
//	{
//		cout << a[i] << " \n"[i == n];
//	}
	vector<int> q(n + 1, 0);
	int len = 0;
	for (int i = 1; i <= n; i++)
	{
		int lp = 0;
		int rp = len + 1;
		while (lp + 1 < rp)
		{
			int mid = lp + rp >> 1;
			if (q[mid] >= a[i])
			{
				rp = mid;
			}
			else
			{
				lp = mid;
			}
		}
		len = max(len, lp + 1);
		q[lp + 1] = a[i];
//		cout << i << ' ' << len << endl;
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		if (vis[i] == true)
		{
			cnt++;
		}
	}
	int ans = cnt - len;
	printf("%d\n", ans);	
}

int main()
{
	int t = 1;
//	scanf("%d", &t);
	while (t--)
	{
		solve();
	}
	return 0;
}

D:

解题思路：

\[\begin{align*} \frac{|x_p - x_q}{|y_p - y_q|} = tan\theta\\ \end{align*} \]

\[\begin{align*} \frac{dist_1(p, q)}{dist_2(p, q)} = cos\theta + sin\theta = \sqrt{2}sin(\theta + \frac{\pi}{4}) \end{align*} \]

可知，当\((p, q)\)两点相连得到的线段与\(x\)轴形成的夹角为\(45°或135°\)时，答案最大。

考虑给定不重合的点集中找到两个点，使得该两点相连后的线段，斜率最接近\(0\)。我们只要按照\(y\)值排序，然后相邻两点相连比较即可。因为\(x\)轴是\(y = 0\),\(y\)值差距越小，越说明二者在一个水平线上。

我们这里将\(45°和135°\)看作水平线​

\(45°\)对应\(x - y = 0\),所以点集按照\(x - y\)进行排序。

同理,\(135°\)按照\(x + y\)进行排序即可。

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
void solve()
{
	ll n;
	scanf("%d", &n);
	vector<pair<ll, ll>> v(n + 1);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld %lld", &v[i].fi, &v[i].se);
	} 
	sort(v.begin() + 1, v.end(), [&](pair<ll, ll> a, pair<ll, ll> b){
		return a.fi + a.se < b.fi + b.se;
	});
	double ans = 0;
	for (int i = 1; i < n; i++)
	{
		ll dx = abs(v[i].fi - v[i + 1].fi);
		ll dy = abs(v[i].se - v[i + 1].se);
		ans = max(ans, 1.0 * (dx + dy) / (sqrt(dx * dx + dy * dy)));
	}
	sort(v.begin() + 1, v.end(), [&](pair<ll, ll> a, pair<ll, ll> b){
		return a.fi - a.se < b.fi - b.se;
	});
	for (int i = 1; i < n; i++)
	{
		ll dx = abs(v[i].fi - v[i + 1].fi);
		ll dy = abs(v[i].se - v[i + 1].se);
		ans = max(ans, 1.0 * (dx + dy) / (sqrt(1.0 * dx * dx + dy * dy)));
	}
	printf("%.12lf\n", ans);
}

int main()
{
	int t = 1;
	scanf("%d", &t);
	while (t--)
	{
		solve();
	}
	return 0;
}

F:

解题思路：

签到，按题意模拟。

代码：

#include<bits/stdc++.h>

using namespace std;

void solve()
{
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;
		if (s.size() == 5 && s[2] == s[4])
		{
			set<char> se;
			for (int i = 0; i < 4; i++)
			{
				se.insert(s[i]);
			}
			if (se.size() == 4)
			{
				ans++;
			}
		}
	}
	cout << ans << endl;
}

int main()
{
	int t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}

H：

解题思路:

观察发现，最后得到的序列一定是唯一的。

我们可以先将所有数进行排序，得到最终序列。

然后对着最终序列，按照顺序模拟操作：

如果当前没有最小数可以取，那么直接结束，概率为\(0\)。否则，概率为\(\frac{集合中最小数的个数}{集合的大小}\)。就是等概率选一个符合的就行。

暴力模拟即可。

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
const int mod = 998244353;


ll qmi(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
		{
			res = res * a % mod;
		}
		b >>= 1;
		a = a * a % mod;
	}
	return res;
}

void solve()
{
	int n;
	scanf("%d", &n);
	vector<int> a(2 * n + 1);
	vector<int> v;
	for (int i = 1; i <= 2 * n; i++)
	{
		scanf("%d", &a[i]);
		if (a[i] != -1)
		{
			v.push_back(a[i]);
		}
	}
	sort(v.begin(), v.end());
	map<int, int> cnt;
	int cur = 0;
	bool vis = false;
	ll ans = 1;
	int len = 0;
	for (int i = 1; i <= 2 * n; i++)
	{
		if (a[i] == -1)
		{
			int x = v[cur];
			if (cnt[x] > 0)
			{
				ans = ans * (cnt[x] * qmi(len, mod - 2) % mod) % mod;
				cnt[x]--;
				cur++;
				len--;
			}
			else
			{
				vis = true;
				break;
			}
			continue;
		}
		cnt[a[i]]++;
		len++;
	}
	if (vis)
	{
		ans = 0;
	}
	printf("%lld\n", ans);
}

int main()
{
	int t = 1;
//	scanf("%d", &t);
	while (t--)
	{
		solve();
	}
	return 0;
}

J:

解题思路:

出现偶数，使偶数出现在个位。

否则输出\(97531\)。

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
	string s;
	cin >> s;
	int cnt = 0;
	for (int i = 0; i < 5; i++)
	{
		int x = s[i] - '0';
		if (x & 1)
		{
			cnt++;
		}
	}
	if (cnt == 5)
	{
		printf("97531\n");
	}
	else
	{
		int x = s[4] - '0';
		if (x & 1)
		{
			for (int i = 0; i < 4; i++)
			{
				int c = s[i] - '0';
				if (c % 2 == 0)
				{
					swap(s[i], s[4]);
					break;
				}
			}
		}
		cout << s << "\n";	
	}
}

int main()
{
	int t = 1;
	scanf("%d", &t);
	while (t--)
	{
		solve();
	}
	return 0;
}

K：

解题思路:

题目明示换根\(dp\)。

\(f[u]:u的子树中不符合题目要求的边数。\)

美丽节点的判断：对于当前节点来说，如果所有子节点的\(f[v]\)都为\(0\),并且，自身和所有子节点的关系都是符合要求的，那么当前节点一定就是美丽节点。

如何换根：

假设\(u\)是\(v\)的子节点。现在我们要换成\(u\)是\(v\)的子节点。

那么，首先\(f[u]\)会减少\(f[v]\)，同时，我们还要判断\((u,v)\)这条边，因为这条边不包含在\(f[v]\)中。

然后，我们考虑\(f[v]\)会增加变化后的\(f[u]\),同时，我们还要判断\((v, u)\)这条边，因为这条边不包含在\(f[u]\)中。

深搜完记得变回去。

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second

void solve()
{
	int n;
	scanf("%d", &n);
	vector<int> a(n + 1, -1), f(n + 1, 0);
	int ans = 0;
	vector<vector<int>> e(n + 1, vector<int>());
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
	}
	for (int i = 1; i < n; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	auto dfs =[&](auto self, int u, int fa) -> void
	{
		for (auto v : e[u])
		{
			if (v == fa)
			{
				continue;
			}
			self(self, v, u);
			f[u] += f[v];
			if (2 * a[v] < a[u])
			{
				f[u]++;
			}
		}	
	};
	dfs(dfs, 1, 0);
	auto efs =[&] (auto self, int u, int fa) -> void
	{
		bool vis = false;
		for (auto v : e[u])
		{
			if (v == fa)
			{
				continue;
			}	
			f[u] -= f[v] + (2 * a[v] < a[u]);
			f[v] += f[u] + ((2 * a[u] < a[v]));
			self(self, v, u);
			f[v] -= f[u] + ((2 * a[u] < a[v]));
			f[u] += f[v] + (2 * a[v] < a[u]);
		}
		for (auto v : e[u])
		{
			if (f[v] != 0 || 2 * a[v] < a[u])
			{
				vis = true;
			}
		}
		if (!vis)
		{
			ans++;
		}
	};
	efs(efs, 1, 0);
	printf("%d\n", ans);
}

int main()
{
	int t = 1;
	scanf("%d", &t);
	while (t--)
	{
		solve();
	}
	return 0;
}

L：

解题思路:

\(f[i] : 表示处理从第1\sim i个bug的最小花费。\)

观察发现，我们将60个\(bug\)一起处理的话（很粗略的看，实际上限更小)，花费就一定大于所有\(bug\)一个个处理了。

所以，我们最多\(60\)个一起处理，从前面转移即可。

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1ll << 60;
void solve()
{
	int n, m;
	scanf("%d %d", &n, &m);
	vector<int> a(m + 1);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d", &a[i]);
	}
	vector<ll> f(m + 1, inf);
	f[0] = 0;
	ll ans = inf;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= 60; j++)
		{
			if (i - j < 0)
			{
				break;
			}
			f[i] = min(f[i], f[i - j] + a[i] + (ll)pow(j, 4));
		}
	}
	printf("%lld\n", f[m]);
}
 
int main()
{
	int t = 1;
//	scanf("%d", &t);
	while (t--)
	{
		solve();
	}
	return 0;
}

M:

解题思路:

发现对于位置\(i\)可取的数范围为\((a_i - b_i, a_i + b_i)\)，我们目标是使得所有位置的范围存在至少一个相交的元素。

二分。

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
	int n;
	scanf("%d", &n);
	vector<ll> a(n + 1), b(n + 1);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
	}
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &b[i]);
	}
	ll l = -1;
	ll r = 1e9 + 1;
	auto check = [&](ll mid)
	{
		ll tl = 0;
		ll tr = 0;
		for (int i = 1; i <= n; i++)
		{
			if (i == 1)
			{
				tl = a[i] - b[i] * mid;
				tr = a[i] + b[i] * mid;
			}
			else
			{
				tl = max(tl, a[i] - b[i] * mid);
				tr = min(tr, a[i] + b[i] * mid);
			}
			if (tl > tr)
			{
				return false;
			}	
		}	
		return true;
	};
	while (l + 1 < r)
	{
		ll mid = l + r >> 1;
		if (check(mid))
		{
			r = mid;
		}
		else
		{
			l = mid;
		}
	}
	cout << r << '\n';
}

int main()
{
	int t = 1;
	scanf("%d", &t);
	while (t--)
	{
		solve();
	}
	return 0;
}

标签：int,ll,long,郑州,2024CCPC,ans,using,邀请赛,se
From： https://www.cnblogs.com/value0/p/18194858

相关文章

  • 一道DP(2024ICPC武汉邀请赛A)-shaking trees
    ShakingTrees题外话这题易哥哥跟我说这题的时候，点明了这题是关于高度\(100\)的\(O(n^3)\)或者\(O(n^4)\)的dp，还有提出切割点的概念使序列化。dp是真的，序列化也是真的。只能说易哥哥我的神。不过其实切割点是根据树形态而变的，之前一直以为是不变的，歪了好久。不知道是我没get到......
  • 2024ICPC武汉邀请赛-G.Pack-数论分块、整除运算相关的不等式
    link：https://codeforces.com/gym/105143Groupcontests：https://codeforces.com/group/DWEH34LQgT/contest/521901题意：有\(n\)件\(A\)物品，\(m\)件\(B\)物品，两种物品价值分别是\(a,b\)，若干件\(A\)和若干件\(B\)可以打包成一个商品，打包尽可能多的商品的情况下让剩余的......
  • ICPC2024 武汉邀请赛 题解
    2024ICPCNationalInvitationalCollegiateProgrammingContest,WuhanSiteB-CountlessMeSolution显然，只能执行\(n\)次操作是没用的条件我们只需要把和\(sum\)分给\(n\)个数，使得\(n\)个数的或和最小即可从高到低考虑每一位，假设此时枚举到第\(i\)位如果这一......
  • 2024“图森未来杯”程序设计邀请赛
    https://voj.mobi/contest/242/problems，密码2024ecnutsolA-调和与折中#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;usingvi=vector<int>;i32main(){ ios::sync_with_stdio(false),cin.tie(nullptr);......
  • 2024 天元公学邀请赛夺金记
    2024.4.14今天是初赛，本来以为初赛就上机，没想到是笔试。考试时有个程序没想出来是什么算法，只能手动模拟，算了很久，后来算出一个580，结果发现最近的一个是579，其他都差得很远，直接选了上去。因为当时快没时间了，赛后才发现少减了一个，xjy和cjz都说是容斥，%%%。2024.4.17初赛稳稳当当......
  • ICPC2023 陕西邀请赛 题解
    G-PermutationQuestion找到一个排列\(p\)，使得\(\prod_{i=1}^nlcm(p_i,p_{(imodn)+1})\)最大Solution考虑到\(x\)和\(x-1\)必然是互质的所以顺序排列即可Code#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin>>n;for(inti......
  • 郑州晨华一张表通用系统
    实现数据共享和信息互通，有效解决基层填报表单繁多、条线分割、多头录入、重复填报等问题。建设背景根据《中共中央国务院关于加强基层治理体系和治理能力现代化建设的意见》，我国积极推进基层社会治理建设。为了解决形式主义问题，2019年，中共中央办公厅印发了《关于解决形式主......
  • 2024第一季天津/苏州/郑州/深圳DAMA-CDGA/CDGP认证报名入口
    2024年度第一季CDGA和CDGP认证考试定于2024年3月17日举行。考试报名现已开启，相关事宜通知如下： —— 考试科目及时间 ——CDGA数据治理工程师：2024年3月17日(周日)14:00-15:40CDGP数据治理专家：2024年3月17日(周日)14:00-16:10——考试地点 —— 考试已确定开放的城市有：北京，上......
  • 郑州 河南职业技术学院Henan Polytechnic Henan Vocational & Technical College
    河南职业技术学院始建于1954年12月，先后历经河南省机器制造技工学校、河南省工人技术学校、河南省工业技术师范学校、河南省技工教育师范学校、河南省第一技工学校、河南省劳动厅第一半工半读技术学校(郑州机床厂)、河南省技工学校、河南职业技术教育学院等历史沿革，1999年3月，经教......
  • 湖南省网络攻防邀请赛 RE 题解
    ez_apkk解题过程：将apk拖入jadx，查看MainActivity，发现是简单RC4加密，密钥是“55667788”，最后再将加密结果+1publicStringEncrypt(StringplainText,Stringkey){int[]S=newint[256];byte[]K=newbyte[256];char[]cArr={'\n','+',18......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99