第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（沈阳）G F K I

发布于 2022-10-23  868 次阅读

比赛传送门：第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（沈阳）

G - The Witchwood（签到）

选出最大的K个数字求和即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;
int a[maxn];

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int N, K;cin >> N >> K;
	for(int i = 1;i <= N; ++ i)cin >> a[i];
	sort(a + 1,a + 1 + N, [](const int &a,const int &b)
	{
		return a > b;
	});
	int ans = 0;
	for(int i = 1;i <= K; ++ i)ans += a[i];
	cout << ans << '\n';
	return 0;
}

F - Kobolds and Catacombs（排序 + Hash）

给定一个序列，将其划分为若干份，将每一份分别排序后，可以使得整体序列非降序，问怎样划分使得份数最多。

读入a序列，再将b序列作为a序列排序后的序列，从前往后遍历，如果某个区间[l, r]内包含的a中的元素和b中的元素相同，说明这里可以划分为一类，借助Hash来判断两个集合是否相等（没有顺序关系）。

这个Hash十分巧妙，利用三种具有交换律的运算（乘法、加法和异或），只有当参与运算的数字都相同时才会三者都相等，出错概率极低。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 9;
typedef unsigned long long ULL;
int a[maxn], b[maxn];

struct Hash
{
    ULL h1, h2, h3;
    Hash()
    {
        clear();
    }
    void add(int x)
    {
        h1 = h1 * (x * x + 131);
        h2 = h2 + (x * x + 1331);
        h3 = h3 ^ (x * x + 13331);
    }
    void clear()
    {
        h1 = h2 = h3 = 1;
    }
    bool operator == (Hash &b)
    {
        return h1 == b.h1 && h2 == b.h2 && h3 == b.h3;
    }
};


signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int N;cin >> N;
	for(int i = 1;i <= N; ++ i)cin >> a[i], b[i] = a[i];
	sort(b + 1,b + 1 + N);
	
	Hash ha, hb;
	
	int ans = 0;
	for(int i = 1;i <= N; ++ i)
	{
		ha.add(a[i]), hb.add(b[i]);
		if(ha == hb)
		{
			ans ++;
			ha.clear(), hb.clear();
		}
	}
	
	cout << ans << '\n';
	return 0;
}

K - Scholomance Academy（前缀和）

前缀和搞一搞就出来了。将点作为关键帧，描绘出矩形面积。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 9;
int p0[maxn], p1[maxn];//分别表示正负的个数 

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int N;cin >> N;
	vector<pair<int, char> > v;
	v.push_back({0, '#'});
	for(int i = 1;i <= N; ++ i)
	{
		char ch;cin >> ch;
		int x;cin >> x;
		v.push_back({x, ch});
	}
	sort(v.begin(), v.end());
	for(int i = 1;i <= N; ++ i)
	{
		p0[i] = p0[i - 1], p1[i] = p1[i - 1];
		if(v[i].second == '-')p0[i] ++;
		if(v[i].second == '+')p1[i] ++;
	}
	double ans = 0.0, lst = 0.0;
	for(int i = 0;i <= N; ++ i)
	{
		//当cita等于v[i].x时，x <= c的认为负，x > c认为正数
        //如果前后两个关键帧的值相同，直接向后移动，说明当前点不能作为关键帧
		if(i < N && v[i].first == v[i + 1].first)continue;
		int tp = p1[N] - p1[i];
		int fn = p1[i];
		int tn = p0[i];
		int fp = p0[N] - p0[i];
		
		double tpr = 1.0 * tp / (tp + fn), fpr = 1.0 * fp / (tn + fp);
		
		//cout << tpr << ' ' << fpr << '\n';
		
		ans += tpr * (fpr - lst);
		lst = fpr;
	}
	cout << fixed << setprecision(10) << 1.0 - ans << '\n';
	return 0;
}

I - Rise of Shadows（数论）

分享一篇写的很好的题解：2020 ICPC 沈阳站 I - Rise of Shadows 题解 - olderciyuan - 博客园 (cnblogs.com)

选取“分钟”作为原子单位，时针的位置和分针的位置都可以用分钟来表达，设当前时间为t（分钟），则t的取值为[0, HM - 1]，这个不难理解。

当时间为T时，时针相对0刻度的角度为：

\(w_{1} = \frac{2\pi t}{HM}\)

时针转动一周的时间为HM，而当前时间为T，总角度为\(2\pi\)。

同样地，分针的角度为：

\(w_{2} = \frac{2\pi t}{M}\)

不妨设分针永远在时针前面，得到角度差，注意对2pi取模，因为可能出现负数，取模后会变为一个钝角，表示的意义是下一圈的时针减去当前分针的角度：

\(\theta = (w2 - w1) \% (2\pi) = (2\pi / (HM) * t(1 - H))\%(2\pi)\)

再结合题目给的条件：

\(\theta \le 2\pi A / (HM) 或 \theta \ge 2\pi - 2\pi A / (HM)\)

整理一下得到：

\(ans = \sum_{t=0}^{HM - 1}[t(H - 1) \% (HM) \le A 或 t(H-1)\%(HM)\ge HM-A]\)

我们将其分开来考虑，对于左边这个式子，根据完全剩余系的知识，我们知道若a*x mod m是一个完全剩余系，那么x和m互质，且对于a属于[0, m - 1]，a * x在[0, m - 1]是一个满射。

对于上式中如果\(gcd(H-1,HM) = 1\)，那么答案就是A + 1，相当于T在[0, HM - 1]中参数和值一一对应。

如果H-1和HM不互质，就需要构造一下，令\(g = gcd(H-1, HM)\)，将左右两边同时除以g，得到：

\(t(H-1)/g \%(HM/g) \le A/g\)

此时t的取值范围是[0, HM/g - 1]，但是这只是第一个完全剩余系中的结果，一共有多少个呢？一共有g个，所以算出第一个的再乘g就可了，第一个完全剩余系中有多少是<=A/g的呢？显然是A/g + 1个（加上0）。

综上，左边这个式子求和的答案是\(g * (a/g + 1)\)，a/g是向下取整。

右边这个式子，这样考虑，首先如果g = 1，那么就有A个满足条件的t（从HM - A到HM - 1）。

当g>1的时候需要分类讨论，当HM - A能够整除g时，答案是g * (A / g)，当HM - A不能整除g时，答案是g * ((A - g + 1) / g)。这个动手画一画就出来了。

有些大佬分析第二个式子的时候都是g * (A / g)，俺不知道啥原理。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 9;

int gcd(int a,int b)
{
	return b == 0 ? a : gcd(b, a % b);
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int H, M, A;cin >> H >> M >> A;
	if(2 * A == H * M)cout << H * M << '\n';
	else
	{
		int g = gcd(H - 1, H * M);
		if((H * M - A) % g == 0)cout << 2 * g * (A / g) + g << '\n';
        else cout << g * (A / g) + g + g * ((A - g + 1) / g) << '\n';
	}
	return 0;
}